google / heir

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

Implement a baseline packing/layout conversion algorithm #914

Open j2kun opened 3 months ago

j2kun commented 3 months ago

As we start to add support for different RLWE packings to HEIR, we will need to implement packing layout conversion operations and lowerings.

Once we have an attribute for layout (cf. https://github.com/google/heir/issues/913), and have decided on what types to store the attribute, we will need:

Other issues will handle optimization passes at the switch_packing op level to reduce the cost of switching packings (this is what Fhelipe does in #800), and more advanced lowerings that create deeper shift networks (larger multiplicative depth) to allow for a smaller number of rotation groups.

AlexanderViand-Intel commented 3 months ago

While this is the issue for the baseline approach, I wanted to throw in that Vos et al., Efficient Circuits for Permuting and Mapping Packed Values Across Leveled Homomorphic Ciphertext, ESORICS'22 claims to outperform the (non-naive) HElib approach significantly (of course, never trust a benchmark you haven't cherrypicked yourself... 😉)