Switching Key Generation

FHE Questions
1

Hi,

I’ve been reading through several FHE accelerator papers, and one common trend is that they produce half of their key-switching keys on-chip. For example:

From CraterLake:
As half of each key-switch hint (KSH) is pseudo-random, it can be generated on the fly from a small seed, halving KSH storage and bandwidth.

However it also seems that each key-switching key is roughly of the form:
{-a*s'+s*P+e, a} for some key-switch s \rightarrow s'.

Since a, the pseudo-random half, is in both polynomials of the key, it feels like the above optimization won’t work? As in, you can’t independently sample a on-the-fly. In a client/server model, is the client required to send both polynomials of each switching key to the server? Or am I missing something and this on-the-fly generation is fine?

2

The first half of the KS key is computed on the client side. As for the second half, a, it can be generated from a small seed (something like 32- or 64-bit integer). Given the client and the server share the same pseudo-random number generator, the server can use the seed to generate a, resulting in having the whole key.
This trick is used to reduce the IO complexity at the accelerator. The intuition is that generating a is cheaper than loading it from memory to the chip.

1 Like
3

Ah, I see! I wasn’t aware that the client and server could share the same pseudo-random number generator. This makes much more sense now. Thank you!