Rotation by encrypted value

FHE Questions
1

Hi all,

I was wondering if there is any way to perform rotations by an encrypted value (blind rotation?) in any of the schemes using batching (mainly CKKS)? Of course, normal rotations are a standard feature, but has anyone looked into this for rotating by a secret value?

Any insight would be appreciated.

Thanks!
Karl

2

It might be worth looking at SHIP: A Shallow and Highly Parallelizable CKKS Bootstrapping Algorithm and PaCo: Bootstrapping for CKKS via Partial CoeffToSlot. These papers try to work with a different definition of rotation, which is inspired by DM/CGGI blind rotation. The normal CKKS rotations are not directly compatible with the concept of rotating by a secret index.

3

I’ll add a concrete solution, not necessarily the best, but it is straight forward, which is to provide a base-d decomposition of the automorphism value in RGSW (one hot encoded) and evaluating log_{d}(n/2)+1 (+1 for complex conjugation) sequential CMUX of the type CMUX(CT, rot(CT, d^i)…, RGSW(x_i)…), each requiring d-1 automorphism (1 for complex conjugation) and RGSW products. Total key size would be d*log_{d}(n/2)+1 RGSW and automorphism keys.

1 Like