How to Implement Double Hoisting

Library Questions
1

Hi,

I would like to ask how to implement Double Hoisting in OpenFHE. This paper discusses how rotations are composed of Decompose, MultSum, ModDown, and Permute in that order (Algorithm 4). The paper later discusses how they are able to introduce Double Hoisting by reducing the number of ModDown operations (Algorithm 6). What confuses me is that in Algorithm 6, rotations are now ordered as Decompose, MultSum, Permute, and then ModDown (enabling them to hoist out the ModDown operation).

I am wondering how to do this double hoisting in OpenFHE. In OpenFHE, I can see rotations are indeed ordered as ModDown first then Permute, but my initial tests showed that if I simply changed the order to Permute first then ModDown, it results in decryption failures.

2

Double hoisting is already implemented in OpenFHE. The simplest instance is provided at openfhe-development/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp at v1.4.0 · openfheorg/openfhe-development · GitHub This instance corresponds to Algorithm 6 (with some optimizations). The number of ModDown calls is reduced just like in Algorithm 6. Note that to support double hoisting, the automorphism key generation is done differently (see EvalAutomorphismKeyGen ModInverse index and LeveledSHEBase<Element>::EvalAutomorphism code order for more details)

2 Likes