Is there an example implementation of slot-shuffling homomorphically in the library? Or is it possible that there was a POC done for the same in threshold holomorphic encryption?
I understand that it can be done using the RLWE to LWE conversion described by Chen et al..
Please point out if I have missed something in the library.
Hi @radhika,
When you are referring to slot shuffling, are you talking about an arbitrary permutation of an encrypted vector or specific rotations? If it is just one rotation, you can use EvalRotate. For arbitrary permutations, there are more complicated options.
I mean arbitrary permutations. By specific rotations, if you mean rotation defined by f_r, for instance, instead of changing the index from i to i+r, the final index is f_r(i), and f is a predefined function (e.g., where f is xor).
I am not sure if the second case is possible to achieve in FHE but I mentioned it because the possibilities of arbitrary permutation are k! while by f_r are |Z_k| so there is a gap. (If k is the number of slots in the ciphertext.)
The most efficient way for performing such homomorphic arbitrary permutations that I am aware of is based on a linear transformation of an encrypted vector, where the linear map is composed of 0’s and 1’s. Two relevant papers are Faster Homomorphic Linear Transformations in HElib and Secure Outsourced Matrix Computation and Application to Neural Networks. The matrix arithmetic library we are adding for OpenFHE is based on some of these algorithms.
In OpenFHE, there is a function EvaLT that can be used for such linear transforms. Ar a high level, you can use rotations, multiplications by masks with 1’s and 0’s, and additions to obtain any permutation.
To further clarify what @ypolyakov said, refer to this wikipedia article for examples.
The function is EvalLinearTransform and is currently only available in the CKKS scheme (i.e. approx. floating point data).
If you do write your own, if the permutation matrix is not needing to be secret, then use (plaintext * encrypted) function calls for the mask multiplications as they are faster than (encrypted * encrypted).
Thank you, that helps a lot!
Thanks for the pointer however I think the API’s for EvalLT is not very clear. I have realized that FHECKKSRNS::EvalLinearTransform is not exposed to the user.
Another point is that it is very much tied to the Bootstrapping, would it be possible to refactor the general LinearTransform into its own user-callable function? Sorry if I am missing anything.
Yes, we are planning to do it in the future as part of adding the matrix arithmetic library.