search

microsoft / SEAL

Microsoft SEAL is an easy-to-use and powerful homomorphic encryption library.
https://www.microsoft.com/en-us/research/group/cryptography-research/
MIT License
3.62k stars 709 forks source link

Questions about galois keys #569

Open shuangyichen opened 2 years ago

shuangyichen commented 2 years ago

I am using SEAL to implement Multiparty HE scheme described in this paper. According to the paper, multiparty version galois key generation is similar to the generation of multiparty public key (To sum c0 of all the parties, c1 is a common polynomial). My issue is when I do not specify the steps to generate galois keys, it works for some steps when rotating. e.g., the example of rotation code, when I use the multiparty galois keys to evaluate(not specifying steps), it successfully rotates the steps including 1-1365, 2731-4096 (noise budget after rotation will be about 140 bits), but does not work for step = 1366 to 2730 (noise budget wii be 0). When I specify the steps when generating the keys, e.g. I set steps = [2500], multiparty galois keys can work successfully. Can you give me some suggestions about the possible bugs? Thanks in advance.

WeiDaiWD commented 2 years ago

Did you experiment all 4096 rotations? Did you generate Galois keys for only power-of-two steps or for all 4096 possible steps? This could also be verified by the size of your Galois keys. Are you using 8192 as poly_modulus_degree? I recommend to examine only power-of-two steps, including negative power-of-two steps.

shuangyichen commented 2 years ago

Did you experiment all 4096 rotations? Did you generate Galois keys for only power-of-two steps or for all 4096 possible steps? This could also be verified by the size of your Galois keys. Are you using 8192 as poly_modulus_degree? I recommend to examine only power-of-two steps, including negative power-of-two steps.

I use 8192 as poly_modulus_degree. I did not specify steps. So I think I generated Galois keys for all possible steps.

WeiDaiWD commented 2 years ago

When you create Galois keys, if you do not specify steps or Galois elements, it will generate keys for positive and negative power-of-two steps.

How do you know for sure that all steps between 1366 and 2730 do not work? Have you tested all of them?

shuangyichen commented 2 years ago

When you create Galois keys, if you do not specify steps or Galois elements, it will generate keys for positive and negative power-of-two steps.

How do you know for sure that all steps between 1366 and 2730 do not work? Have you tested all of them?

Yes. I tested all the steps in this range. I also examined power-of-two-steps by specifying power-of-two-steps, it works as normal.

WeiDaiWD commented 2 years ago

For an arbitrary step not represented in Galois keys, SEAL represent the step in non-adjacent form (NAF) to minimize the number of power-of-two rotations. For example, 1365 is represented as 1+4+16+64+256+1024; 1366 is represented as -2-8-32-128-512+2048. Your Galois key created for step 2048 might be wrong. Since step 2048 is exclusively used in steps 1366~2730.