Disclaimer: These notes are taken for the CS577 Data Privacy course offered by Dr. Erman Ayday in the 2021/2022 Fall Semester at Bilkent University.
Secure multiparty computation (SMC) aims to create methods for parties to jointly compute a function over their inputs while preserving their privacy. While communicating with an untrusted party, we would encrypt our message before sending it and then decrypt the response. Of course, the decrypted response should be equal to the desired response which would be received if the original data was sent without encryption. By doing so, we would prevent the untrusted party to obtain the actual information while performing necessary calculations to obtain the proper response. Homomorphic encryption was proposed to ensure coherence between desired response to the message and the received response after the decryption. Since its first establishment in 1978, several studies proposed improvements to flaws of the first proposal for dedicated application contexts.
The basic definition of homomorphic encryption is based on the commutativity between encryption and some data processing operations. There are mainly two encryption schemes: symmetric and asymmetric. In symmetric encryption, the message is encrypted and decrypted with the same key. They have the advantage of fast computation. On the other hand, asymmetric encryption requires multiple keys. The encryption key is public so that when Alice wished to send a message to Bob she can easily encrypt it and send it. However, the decryption key is secret and only known by the target, in this case, Bob. hence, Bob can decrypt the received message with his secret key. Asymmetric encryption schemes are more complicated and slower than symmetric ones by their nature. Because of that, generally, the actual message is encrypted with symmetric encryption and the public key to decrypt it is sent with an additional asymmetric cipher. Except for the one-time pad protocol proposed by Shannon, no other encryption scheme has been proved unconditionally secure yet.
The choice of the right encryption scheme depends on the system requirements and constraints in time, memory, or security. However, a good practice is to select a probabilistic encryption scheme instead of a deterministic one. Because with deterministic schemes, some plain texts can be encrypted in a too structured way or it may be easy to compute partial information. Also, with deterministic encryption, the same plain text is presented with the same ciphertext which implies that the number of times a message is sent can be tracked. The consequence of using probabilistic encryption schemes is the expansion which means that the ciphertext domain should be larger than the actual plain text-domain for a plain text to have multiple ciphertext representations.
An encryption algorithm is malleable if it is possible to transform a ciphertext into another ciphertext that decrypts to a related plaintext. That is, given an encryption of a plaintext m, it is possible to generate another ciphertext that decrypts to f(m), for a known function f, without necessarily knowing or learning m. Malleability is often an undesirable property in a general-purpose cryptosystem since it allows an attacker to modify the contents of a message.
With the introduction of semantic security and probabilistic encryption, different security notations have been established. The summary of relations between semantic security levels is presented in the figure below [2]. IND-CCA2 implies nonmalleability. However, due to the principle of commutativity of the encryption function over data operations, homomorphic encryption cannot satisfy nonmalleability and it has only IND-CPA security level.
State-of-the-Art Homomorphic Encryption Schemes
RSA and ElGamal are both asymmetric encryption schemes that are also multiplicatively homomorphic. RSA as a deterministic scheme cannot even satisfy requirements for IND-CPA. However, ElGamal and its additively homomorphic variant achieve IND-CPA which makes it a good candidate for realistic homomorphic encryption schemes.
Goldwasser-Micali(GM) describes a simple scheme for probabilistic systems which refers to a family of homomorphic encryption. The trick that GM makes use of over RSA, is to let the well-chosen subset of integers, modulo n, be partitioned into two secret parts: M0 and M1. The key point is to choose the subset and partition it.
Benaloh generalizes GM in such a way that multiple bits can be encrypted at the same time. Although the encryption is similar to GM, the decryption process is more complex, leading to O(√k l(k)) for k, a prime number with constraints represented in l(k) bits. Then, for practical cases, k needs to be small which limits the improvements that Benaloh proposes.
Naccache-Stern (NS) achieves smaller expansions for greater k values with slightly different constraints. Even though the expansion length is the same, the decryption cost is decreased to O(l(n)^5log(l(n))) where l(n) is the output size in bits.
Okamoto-Uchiyama changed the base group of GM in order to improve previous works and achieve an expansion equal to 3. EPOC is designed with this scheme, even though earlier versions show security flaws due to bad implementation.
One of the most well-known homomorphic schemes is Paillier. Using the Chinese Remainder Problem, the decryption is managed more efficiently with respect to its precedents. Two different variations of Paillier are proposed by Cramer and Shoup and Bresson et al.
A generalization of Paillier is proposed by Damgard and Jurik (DJ). Although it achieves a smaller expansion, the decryption is more costly. For k blocks of l(n) bits, DJ is k times more costly than Paillier.
Galbraith makes use of elliptic curves and achieves an expansion equal to 3. The main improvement of Galbraith over DJ is the decrease of the cost while preserving the strength of the scheme.
Castagnos also achieved an expansion equal to 3 by considering quadratic field quotients.
Finally, ElGamal-Paillier amalgam combines variants of the Paillier scheme with the additively homomorphic variant of ElGamal. The amalgam combines the analysis of Damgard and Jurik with the works of Cramer and Shoup to minimize the drawbacks of both schemes while making use of their advantages.
A comparison of some homomorphic encryption schemes by [3] is given in the table below. The schemes presented with *are also discussed in [1].
Garbled Circuits
Garbling is a process by means of which the Boolean gate truth table is obfuscated. As the constructor, Alice takes 4 random keys, K{x0}, K{x1}, K{y0}, K{y1}. Then, she uses every pair of keys corresponding to a possible scenario, i.e., a row in the truth table, to encrypt the regarding output. The garbled gate consists of the four resulting ciphertexts, in a random order, as presented in the figure.
Once the evaluator Bob receives the garbled gate, he needs to decrypt exactly one ciphertext: the one corresponding to the real values. In order to do this, he needs to receive the values Kx and Ky. Since Alice knows her input, she can send K{xa}, but she cannot send both K{y0} and K{y1} to Bob, because that will allow Bob to decrypt two ciphertexts in the garbled gate. So, Alice and Bob use oblivious transfer, which allows Bob to learn only K_yb without revealing it to Alice.
In order for this to work, Bob needs to know when decryption succeeds, and when it does not. Otherwise, there is no way for him to know which ciphertext yields the correct answer. Note that Yao's Garbled Circuit is secure against a semi-honest adversary. Hence, it is more challenging to make this protocol secure against a malicious adversary that deviates from the protocol.
[1] C. Fontaine and F. Galand, “A survey of homomorphic encryption for nonspecialists,” EURASIP Journal on Information Security, vol. 2007, pp. 1–10, 2007
[2] A. Bagherzandi, K. Azimian, J. Mohajeri, and M. Salmasizadeh, “Relations between semantic security and indistinguishability against cpa, non-adaptive cca and adaptive cca in comparison based framework,”arXiv preprint cs/0508110, 2005.
[3] Y. Hu, “Improving the efficiency of homomorphic encryption schemes,” Ph.D. dissertation, Worcester Polytechnic Institute, 2013.
Comments