Skip to content

Investigate possibility of integrating pippenger's exponentiation algorithm #1653

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
j2kun opened this issue Apr 3, 2025 · 0 comments
Open
Labels
dialect: polynomial Issues concerning the polynomial dialect newcomer project Project ideas for new contributors research synthesis Reading papers to figure out which ideas can be incorporated

Comments

@j2kun
Copy link
Collaborator

j2kun commented Apr 3, 2025

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.

@j2kun j2kun added dialect: polynomial Issues concerning the polynomial dialect newcomer project Project ideas for new contributors research synthesis Reading papers to figure out which ideas can be incorporated labels Apr 3, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
dialect: polynomial Issues concerning the polynomial dialect newcomer project Project ideas for new contributors research synthesis Reading papers to figure out which ideas can be incorporated
Projects
None yet
Development

No branches or pull requests

1 participant