google / google/heir

Investigate possibility of integrating pippenger's exponentiation algorithm

Open
#1,653 1 comment 0 reactions 0 assignees View on GitHub
dialect: polynomial newcomer project research synthesis
Dominant language
MLIR
Stars
906
Forks
171
Avg merge
4d 12h
Merged PRs (30d)
32

Description

I was talking with a colleague about Pippenger's exponentiation algorithm (in the context of elliptic curves) and it occurred to me that we could use that for a potential optimization of polynomial evaluation in HEIR.

See section 7 of https://cr.yp.to/papers/pippenger.pdf for an overview, but there are two parts of it: computing many exponents of a single base `x` and computing multinomials across multiple bases. The first one seems directly applicable to polynomial.eval lowerings, especially when you have to evaluate multiple polynomials on the same input and want to jointly optimize across them all.

The second one (multiple bases) seems like it could be useful if there comes a time when we want to evaluate multi-variable polynomials on multiple input ciphertexts in service of some other computation.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.