search

google / heir

A compiler for homomorphic encryption
https://heir.dev/
Apache License 2.0
237 stars 34 forks source link

poly: use poly.ntt as a rewrite for polynomial.mul #680

Closed asraa closed 2 months ago

asraa commented 2 months ago

Right now --bgv-to-polynomial uses polynomial.mul, and we should create a rewrite pattern that converts polynomial.mul to a polynomial.ntt and tensor elementwise multiplication (with moduli?)

OR should this just be the default lowering from bgv.mul to polynomial.ntt, multiplication, and polynomial.intt?

AlexanderViand-Intel commented 2 months ago

I think it'd be nice to have this be a separate pass, both because it's conceptually neater and because it'd allow pipelines for targets that don't have efficient NTT implementations to substitute their own "fast poly.mul" lowering pass. In practice, though, it's not entirely clear to me at the moment how parameter selection/etc would work with a design where such decision are left until such a late point in the compilation.

j2kun commented 2 months ago

Finn implemented this in https://github.com/google/heir/pull/657, and I think he's on vacation so hasn't been able to reply to the minor review comments. Agreed about @AlexanderViand-Intel's comment about parameter selection, though.

j2kun commented 2 months ago

Marking as a dupe of https://github.com/google/heir/issues/541

asraa commented 2 months ago

Oh thank you! I wanted to experiment with it and I'll clone the PR. Thanks!