Literature Review: Homomorphic Encryption
Literature Review: Homomorphic Encryption
Abstract
Homomorphic encryption is a specific type of encryption where mathematical operations on the ciphertext is equivalent to mathematical operations on the corresponding plaintext. Homomorphic encryption (HE) is desirable on account of the fact that it can simply operations on large databases. In this work we examine the fundamental concepts of HE, the practical problems encountered when using HE and a few more commonly known HE schemas and implementations.
1.0 Introduction: Homomorphic Encryption (HE)
Homomorphic Encryption (HE) is a particular type of encryption that maintains certain algebraic structure between the plaintext and ciphertext. One example of HE is where the product of any two ciphertexts is equal to the ciphertext of the sum of the two corresponding plaintexts, when all the encryptions use the same key. This is represented as:
E(m1) * E(m2) = E(m1+m2)
(Tilborg and Jajodia, 2015). Homomorphism therefore simply means that the algebraic operations can be performed on the encrypted text, and when decrypted, the result will be the same as that of performing those operations on the unencrypted text.
Public key cryptosystems such as the RSA, ElGamal, Paillier, etc. are homomorphic. HE is computationally indistinguishable because it is secure against passive attacks. Homormorphism in encryption correspond with mathematical concepts of homomorphism. RSA encryption for example is multiplicatively homomorphic. This is because of the property, for any m1,m2, ϵ Z*n,
(me1 mod n ) * (me2 mod n) = (m1m2)e mod n
The ElGamal encryption is also multiplicatively homomorphic; it can however also be formulated to be additively homomorphic. The Pallier encryption is additively homomorphic –
where r1, r2, ϵ RZ*n
Fontaine and Galand (2007) define homomorphism with the following notation:
For all a and b in P and k in K, if Ek(a) ○ Ek b) = Ek (a ◊ b)
Then the encryption system can be said to be homorphic.
Other types of homomorphisms also exist. For example the Goldwasser-Micali encryption is based on quadratic residues and is XOR-homormorphic.
HE is important in cryptography because it preserves the relationships between elements across the encryption transformation. This means that the natural structure of the elements, and the relationships between them, is preserved in spite of the elements being encrypted.
Fully homomorphic encryption is a strictly more powerful type of HE. It relates to the mathematical concept of ring homomorphism. It involves two operations such as addition and multiplication, and a finite ring. Fully HE is both additively and multiplicatively homomorphic (Smart, 2015). This means that any computing or mathematical function can be evaluated solely on the encrypted values, with knowledge of the public key (Tilborg and Jajodia, 2015).
The usefulness of HE can be seen in the following example. If Alice encrypts some information m and stores the ciphertext c on a remote server, she can perform mathematical functions on the ciphertext as if it were done on the unencrypted text, without having to decrypt the ciphertext. This saves on time and computational power. This is a relevant issue when the ciphertext is a huge database and decrypting would take a long time. With HE, the function can be executed on the ciphertext; even more notably, the fact that makes this characteristic useful is that every mathematical function can be expressed as a series of additions and multiplications over a ring. This means that the mathematical function F can be expressed as a series. A variation of Fully HE is SHE, or somewhat homomorphic encryption, where a limited number of additions and multiplication operations can be evaluated. Beyond the specific threshold of number of operations done on the ciphertext for the encryption system, the ciphertext in SHE (or SWHE, somewhat homomorphic encryption) becomes too noisy and the decryption will fail. Most SHEs can be converted to FHEs with bootstrapping.
Practical Problems
HE was recognised as far back as in the 1970s, in the properties of public key cryptosystems. The potential to use these for advanced privacy protection was also recognised. This is because if the encryption is homomorphic, then fundamental factors (primitives) are enabled, such as oblivious transfer, and consequent on oblivious transfer, secure multiparty computation. HE combined with threshold cryptography makes electronic elections possible (Tilborg and Jajodia, 2015).
One of the main problems with HE systems such as RSA is that RSA has to pad the message with random bits to achieve semantic security, and this padding makes the encryption system lose its homomorphism (Fontaine and Galand, 2007). RSA is deterministic, which means that the encrypted message can be computed whereas in probabilistic encryption systems the outcome is not necessarily computable directly, but can be guessed. A deterministic public key encryption system necessarily leaks information to the adversary. The adversary can intercept the ciphertext c, and know that the message m is from a small set of {m1, m2….mn) of possible messages. He can then find out m by computing the ciphertexts and comparing them with C. The implication of this possibility is that encryption systems have to have a degree of randomness in order to be truly or fully secret. The adversary should not be able to predict the ciphertext of a message. The introduction of randomness makes the encryption system probabilistic rather than deterministic (Delfs and Knebl, 2007). However, Zhou and Young (2010) suggest that it is possible to build a semantically secure public key encryption scheme that is also additively homomorphic. Bogos et al (2016) however contest this claim, publishing details of their attack on a HE that was claimed to be semantically secure, but found to be not semantically secure after the attacks.
Moore et al (2014) explain that current HE schemes are still not efficient enough for real time application, as the execution can take too long. For example they point out that the key generation in Gentry and Halevi’s (2011) scheme can take anywhere between 2.5 seconds to 2.2 hours – this is too long for the encryption program to be practically useful. Waiting for 2.2 hours to encrypt a message will cripple modern communication systems which rely on almost instantaneous communication. Furthermore, FHE schemes also have heavy memory usage. In order to provide security guarantees, very large ciphertext and public keys are required. Finally, the requirement for bootstrapping to reduce and manage noise that is created in the execution of homomorphic operations on ciphertexts. Overall they suggest that improvements in HE can come from improvements in the theory as well as implementation of HE.
HE Schemas
A good classification of HE schemas is presented by dos Santos et al (2015).
Gentry
The Gentry 2009 HE schema is considered to be the earliest HE schema that has been developed. Gentry and Halevi (2011) explain that the construction of the FHE begins with the construction of a SHE scheme that supports evaluating low degree polynomials on the encrypted data. After this the decryption procedure had to be modified so that it can be expressed as a low degree polynomial. Bootstrapping completed the process to make the SHE into an HE. Once the degree of polynomials that can be evaluated by the scheme exceeds twice the degree of the decryption polynomial, the scheme is bootstrappable and can be converted into an FHE. The modification of the decryption procedure is done by adding to the public key an additional hint about the secret key. This is called the sparse subset sum problem (SSSP). The public key is enhanced with a large set of vectors, and a sparse subset of the public keys adds up to the secret key. A ciphertext of the underlying scheme is post-processed using the additional hint. This allows it to be decrypted with a low degree polynomial.
Overall this encryption method is efficient. The most expensive operation during the encryption is evaluating the degree (n-1) polynomial u at the point r.
Helib
The main characteristic of SHEs are that they have noise that grows with each homomorphic encryption, until it is so large that it causes decryption errors. Halevi and Shoup (2014) present Helib, which is a software library that implements the BGV HE. This HE focuses on the use of Smart-Vercauteren ciphertext packing techniues and Gentry-Halevi-Smart optimisations. The system defines the set of operations that can be applied homomorphically and the cost of each operation.
The most efficient FHEs that are currently available are ring learning with errors (RLWEs). There are different types of RLWEs, such as BGVs, Brakerski, etc. RLWE differs from LWE in that a polynomial ring is used instead. Helib is purely written in C++, implements BGV encryption and supports optimisations such as relinearisation, bootstrapping and packing. The key characteristic of BGV is that it is a levelled homomorphic encryption scheme. This means that the ciphertext space is not fixed. Levels are used to reduce noise inside the ciphertext. As multiplication adds greater noise level is generally changed after multiplication. Relinearisation is used to reduce the overhead in ciphertext multiplication. Packing is the use of several messages in one ciphertext. It is used to reduce the numbers of ciphertext, and to club together the computation time required for the encryption. Packing can be done into the coefficients, as well as into the subfields (Halevi and Shoup, 2014). Overall the main drawback of Helib is the overhead that is in the order of seconds (Mazonka et al, 2016).
Cryptoleq
SHE is considered to be sufficient for practical applications, on account of the lower overheads. Although they offer fewer operations, and are less powerful than FHEs in terms of their computational completeness, their efficiency makes up for the shortcomings and makes them a very practical choice. Cryptoleq is a SHE that is based on the concept of an abstract machine that is capable of performing general purpose computation on encrypted programs. The operands of this program are protected using the Paillier SHE (or PHE, partially homomorphic encryption), which supports additive homomorphism. Multiplicative homomorphism is achieved by inventing a heuristically obfuscated software re-encryption module. This module is blended into the program. It also supports probabilistic encryption. This means that Cryptoleq allows both encrypted and unencrypted instruction operands in the same program and memory space (Mazonka et al, 2016)
Because Cryptoleq uses a secure probabilistic PHE, there is generally no leakage of plaintext information. However adversaries may analyse the side channel information of the Cryptoleq execution, such as IP trace patterns, memory events, etc. However the code based obfuscation can provide heuristic guarantees (Mazonka et al, 2016)
DGHV Variant
Dos Santos et al (2015) put forward an implementation of a DGHV variant that reduces the prohibitive size of public keys at the cost of computational power. Their implementation is based on Coron’s () variation of Gentry (2009). It uses Python and is found to be slightly faster compared to Coron’s implementation. This implementation does not contribute any change in the algorithm as put forward by Coron () but it contributes in the form of a better implementation. This shows that execution speed can be improved by implementation strategy and choices. Dos Santos et al (ibid) also suggest that further improvements in execution speed can be done using code parallelism, the Pythom-specific Numba library, the use of FPGAs, etc.
FHE with Noise Reduction by Liu (2015)
Liu (2015) presents a new FHE scheme that he claims is efficient for practical applications. The main advantage of this scheme is that it does not need the noise reduction that is required in other FHE schemes, such as bootstrapping and modulus switching. In essence, it is said that noise reduction is included in the algorithm. This is done by allowing arbitrarily large noises in its ciphertexts. In this method, the dimensions of the ciphertext do not change with homomorphic operations. Furthermore all ciphertext elements are in a finite domain, making the scheme very compact. This method is also semantically secure. Liu (ibid) also implements the proposed algorithm in Java using relevant Java packages such as SunJCE. They find that their scheme is slightly faster than AES for encryption, and much faster than AES for decryption. They also conduct a performance evaluation for homomorphic operations, and find that the time increases with the number of bits; operations with 10,000 bits for example take times of less than 6 seconds. Overall this means that this scheme is useful in data processing applications, and hence can be said to be perhaps the most practical implementation of FHE currently available.
References
Bogos, S., Gaspoz, J., & Vaudenay, S. (2016). Cryptanalysis of a Homomorphic Encryption Scheme. In ArcticCrypt 2016. Retrieved from https://infoscience.epfl.ch/record/220692
Delfs, H., & Knebl, H. (2007). Introduction to Cryptography: Principles and Applications. Springer Science & Business Media.
dos Santos, L. C., Bilar, G. R., & Pereira, F. D. (2015). Implementation of the fully homomorphic encryption scheme over integers with shorter keys. In New Technologies, Mobility and Security (NTMS), 2015 7th International Conference on (pp. 1–5). IEEE. Retrieved from http://ieeexplore.ieee.org/abstract/document/7266495/
Fontaine, C., & Galand, F. (2007). A survey of homomorphic encryption for nonspecialists. EURASIP Journal on Information Security, 2007(1), 1–10.
Gentry, C., & Halevi, S. (2011). Implementing Gentry’s fully-homomorphic encryption scheme. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 129–148). Springer. Retrieved from http://link.springer.com/chapter/10.1007/978-3-642-20465-4_9
Halevi, S., & Shoup, V. (2014). Algorithms in helib. In International Cryptology Conference (pp. 554–571). Springer. Retrieved from http://link.springer.com/chapter/10.1007/978-3-662-44371-2_31
Liu, D. (2015). Practical Fully Homomorphic Encryption without Noise Reduction. IACR Cryptology ePrint Archive, 2015, 468.
Mazonka, O., Tsoutsos, N. G., & Maniatakos, M. (2016). Cryptoleq: A heterogeneous abstract machine for encrypted and unencrypted computation. IEEE Transactions on Information Forensics and Security, 11(9), 2123–2138.
Moore, C., O’Neill, M., O’Sullivan, E., Doroz, Y., & Sunar, B. (2014). Practical homomorphic encryption: A survey. In Circuits and Systems (ISCAS), 2014 IEEE International Symposium on (pp. 2792–2795). IEEE. Retrieved from http://ieeexplore.ieee.org/abstract/document/6865753/
Smart, N. (2015). Cryptography Made Simple. Springer.
Tilborg, H. C. A. van, & Jajodia, S. (2014). Encyclopedia of Cryptography and Security. Springer Science & Business Media.
Zhou, J., & Yung, M. (2010). Applied Cryptography and Network Security: 8th International Conference, ACNS 2010, Beijing, China, June 22-25, 2010, Proceedings. Springer Science & Business Media.
© Copyright Ivory Research Co Ltd. All rights reserved.
You may not copy, modify, publish, transmit, transfer or sell, reproduce, create derivative works from, distribute, perform, display, or in any way exploit any of the content of this report, in whole or in part, save as hereinafter provided. You may download or copy one copy of the report you have purchased only for your own personal use for academic study purposes only, however, you may not submit this document under your own name for academic assessment.
This also applies to any sections we add to the work that you have completed however; it does not apply to sections completed solely by you.
The statements contained herein are statements of opinion of the writer only and not the statements of Ivory Research Ltd, its officers, employees or agents. To the fullest extent permissible by law, Ivory Research Ltd hereby excludes liability for the truth or accuracy of any information provided herein, your statutory rights as a customer are not affected.