search

google / heir

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

poly: add an extra modulus for lowering mul with non-machine-word sized coefficients #201

Closed j2kun closed 5 months ago

j2kun commented 10 months ago

See TODO linking to this issue in PolyToStandard.cpp

github-actions[bot] commented 7 months ago

This issue has 1 outstanding TODOs:

This comment was autogenerated by todo-backlinks

inbelic commented 5 months ago

Hey @j2kun, I would be interested in contributing to the project. Would this still be an applicable issue? Having skimmed through the most recent meeting, is there a more helpful issue to work on with respect to the bgv -> poly -> pipeline? Thanks

j2kun commented 5 months ago

Hi @inbelic, thanks for taking an interest!

This issue is definitely still open. @AlexanderViand-Intel is doing some work on the polynomial side of the house right now, but otherwise I'd say that part of the codebase is rather under-developed. I will try to file some additional issues that could constitute low-hanging fruit here, and tag them with the polynomial dialect label.

I think the main thrust that is relevant to FHE would be supporting special lowerings for particularly-structured polynomial rings, like (Z/qZ)[x] / (x^N + 1), as well as incorporating NTT/FFT operations and passes to identify when to switch to and from the NTT/FFT domain.

AlexanderViand-Intel commented 5 months ago

Hi @inbelic! Yes, there's lots to do around polynomial. I did some infrastructure work last week to make the existing bgv->poly lowerings work with the existing poly->standard lowering and now the next point on my agenda is to extend the bgv->poly lowerings (which currently only have add and mul) to support noise management, i.e., mod switching and key switching (specifically, relinearization).

However, with the current poly -> standard lowerings (which support a wide set of polynomial rings generically) the code generated would likely be prohibitively slow to run 🐌. So, as Jeremy said, a more HE-optimized lowering (like what was done in HEaaN.MLIR) is indeed the next big thing for poly.

inbelic commented 5 months ago

Awesome! I already see some of the new issues you created. I will begin digging into them this week and start with this one.

inbelic commented 5 months ago

I pushed my current work towards an implementation in the above pull request. Unfortunately, I have come across a lowering issue that I haven't been able to resolve and would appreciate some help or pointers. Thanks!

Edit: Comment linked here: https://github.com/google/heir/pull/545#issuecomment-2016015585