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.58k stars 709 forks source link

Regarding the new features of v3.3.0 #39

Closed xiangxiecrypto closed 5 years ago

xiangxiecrypto commented 5 years ago

Hi there, The released new version (3.3.0) has some nice properties, but there are little explanations.

  1. What is the mathematical background of preserving the noise budget after relinearization and rotation operations?
  2. What is the exact definition of "special prime"? why using this special prime?
  3. The new version also brings larger noise budgets of fresh ciphertext, what is the basic idea behind that?

Looking forward to detailed explanations or references.

best

WeiDaiWD commented 5 years ago

Thanks for asking. We tried to make Microsoft SEAL easier to use and understand by developers with a broader background, which is why we have intentionally separated mathematical explanations from the repository. We do plan to have a document (in progress) that covers theoretic explanations for advanced users like you.

We call this new improvement that reduces noise in relinearization, rotation, and encryption, the "special modulus" technique. It is explained in our recent paper. I can give you some short answers for now.

The special prime is not very different from other primes except:

  1. It is introduced for noise reduction only. It is used when representing relinearization keys, rotation keys, public keys, and operations involving those keys. It is not used to represent ciphertext or plaintext. Once you set up the correct EncryptionParameters, you do not need to care about this special prime any more.
  2. It has to be larger than all other primes to fully reduce the noise growth. If it is not the largest, there will be noise growth in relinearization and rotation.

We perform relinearization or rotation by taking a ciphertext in Rq, computing it with relinearization keys or rotation keys in Rpq, performing modulus switching from Rpq to Rq. Without modulus switching, the noise growth is the same with SEAL 3.2.0 with decomposition_bit_count set to maximum. Modulus switching divides a ciphertext by the special prime, resulting in a smaller noise (similar to the noise before relinearization or rotation).

Similarly in encryption, we first generate an encryption of zero in Rpq, perform modulus switching to Rq, add plaintext to the encryption. This results in a fresh ciphertext with more noise budget.

lsu1 commented 5 years ago

Hi WeiDaiWD:

I am wondering if there is any documentation for version 3.3. The latest one I could find online is for version 2.3.1.

A newbie for SEAL here so want to start with the library documentation first. Thank you!

Regards,

WeiDaiWD commented 5 years ago

To get started with SEAL, we recommend developers to run all examples while reading the comments in example source codes. Those comments are phrased to include as little math as possible and are focused on explaining the API and functionality of SEAL, BFV, CKKS, encoders, etc.

We are working on a documentation that focuses on the mathematical construction behind SEAL and adopted homomorphic encryption schemes.

Pro7ech commented 5 years ago

Hi,

If I understand correctly, the idea is to compute the switching-key with a RNS "gadget" decomposition, and multiply it by this special prime and store the keys in Rpq, and the apply a modulus switching to divide by p, dividing therefore the added noise by p, which (roughly) bounded by some small multiple of thebiggest prime of Rq (thank's to the RNS "gadget" decomposition). This would be some sort a hybrid noise management between the type 1 and type 2 relinearization proposed in https://eprint.iacr.org/2012/144.pdf.

Since the switching-keys are stored in Rpq (and sampled in Rpq), and not Rq, do the parameters take into account the total size Rpq for security? For big parameters this should'nt have much of an impact, but for small parameters (like a modulus Rq of a total size of less than 200 bits), this a relative size increase of about 30-50% in the modulus of the switching-keys.

WeiDaiWD commented 5 years ago

Your understanding of key switching in SEAL is correct. We do base security on the size of pq. EncryptionParameters should be set up with the special prime. For the same security level (and a ring degree), we actually lose one prime rather than adding a special one. When there is only one prime in EncryptionParameters::coeff_modulus_, key switching is disabled, which can happen when degree is only 1024 or 2048.