Homomorphic Encrypion
Post Quantum Cryptography, Encrypted Computng, Homomorphic Encryption, Noise Management
Beschreibung
Homomorphic Encryption (HE) is a type of encryption that allows calculations to be performed on the ciphertexts [1]. If any kind of operation is allowed, it is called Fully Homomorphic Encryption (FHE). This concept offers many opportunities regarding data protection for cloud services. This technology allows users to keep their data secret, while still being able to outsource calculations on this data to a server. For example, in the field of machine learning, the training can be carried out on private data.
The first fully homomorphic encryption scheme was introduced by Gentry in 2009 [2]. Since then, many other schemes and optimizations have been proposed. For a first overview, [3] is recommended. Two of the most prominent and widely implemented schemes today are BGV [4], named after Brakerski, Gentry and Vaikuntanathan, and BFV [5, 6], named after Brakerski, Fan and Vercauteren. Both are based on the (Ring) Learning With Errors problem and support exact arithmetic on encrypted integers. However, they differ in how the message is encoded in the ciphertext and in how the noise that grows during homomorphic operations is managed. BGV relies on modulus switching to keep the noise under control, while BFV follows a scale-invariant approach.
Comparing the BGV and BFV Homomorphic Encryption Schemes:
The goal of the seminar would be to give a short introduction to Homomorphic Encryption, including the variants and definitions, and then to study the BGV and BFV schemes in detail. Both original papers should be read and the schemes presented. Building on this, the similarities and differences between the two schemes should be worked out and compared, for example regarding message encoding, noise growth and noise management, key generation and relinearization, security assumptions, and efficiency.
[1] Rivest, Ronald L., Len Adleman, and Michael L. Dertouzos. "On data banks and privacy homomorphisms." Foundations of secure computation 4.11 (1978): 169-180.
[2] Gentry, Craig. "Fully homomorphic encryption using ideal lattices." Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009.
[3] Vaikuntanathan, Vinod. "Computing blindfolded: New developments in fully homomorphic encryption." 2011 IEEE 52nd annual symposium on foundations of computer science. IEEE, 2011.
[4] Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. "(Leveled) fully homomorphic encryption without bootstrapping." Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS). 2012.
[5] Brakerski, Zvika. "Fully homomorphic encryption without modulus switching from classical GapSVP." Advances in Cryptology–CRYPTO 2012: 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings. Springer Berlin Heidelberg, 2012.
[6] Fan, Junfeng, and Frederik Vercauteren. "Somewhat practical fully homomorphic encryption." Cryptology ePrint Archive, Paper 2012/144, 2012.