CRYPTOGRAPHY AND NETWORK SECURITY PROTOCOLS AND TECHNOLOGIES BY JAYDIP SEN

CRYPTOGRAPHY AND NETWORK SECURITY PROTOCOLS AND TECHNOLOGIES BY JAYDIP SEN 3. Homomorphic encryption schemes During the last few years, homomorphic encryption schemes have been studied extensively since they have beco ...

CRYPTOGRAPHY AND NETWORK SECURITY PROTOCOLS AND TECHNOLOGIES BY JAYDIP SEN 3. Homomorphic encryption schemes During the last few years, homomorphic encryption schemes have been studied extensively since they have become more and more important in many different cryptographic protocols such as, e.g., voting protocols. In this Section, we introduce homomorphic cryptosystems in three steps: what, how and why that reflects the main aspects of this interesting encryption technique. We start by defining homomorphic cryptosystems and algebraically homomorphic cryptosystems. Then we develop a method to construct algebraically homomorphic schemes given special homomorphic schemes. Finally, we describe applications of homomorphic schemes. Definition: Let the message space (M, o) be a finite (semi-)group, and let σ be the security parameter. A homomorphic public-key encryption scheme (or homomorphic cryptosystem) on M is a quadruple (K, E, D, A) of probabilistic, expected polynomial time algorithms, satisfying the following functionalities: • Key Generation: On input 1σ the algorithm K outputs an encryption/decryption key pair (ke, kd ) = k ∈, where denotes the key space. • Encryption: On inputs 1σ, ke, and an element m ∈ M the encryption algorithm E outputs a ciphertext c ∈ C , where C denotes the ciphertext space. • Decryption: The decryption algorithm D is deterministic. On inputs 1σ, k, and an element c ∈ C it outputs an element in the message space M so that for all m ∈ M it holds: if c = E (11σ, ke, m) then Prob D(1σ, k , c) ≠ m is negligible, i.e., it holds that Prob D(1σ, k , c) ≠ m ≤ 2-σ. • Homomorphic Property: A is an algorithm that on inputs 1σ, ke , and elements c1, c2 ∈ C outputs an element c3 ∈ C so that for all m1, m2 ∈ M it holds: if m3 = m1 o m2 and c1 = E (1σ, ke, m1), and c2 = E (1σ, ke, m2), then Prob D(A(1σ, ke, c1, c2)) ≠ m3 is negligible. Informally speaking, a homomorphic cryptosystem is a cryptosystem with the additional property that there exists an efficient algorithm to compute an encryption of the sum or the product, of two messages given the public key and the encryptions of the messages but not the messages themselves. If M is an additive (semi-)group, then the scheme is called additively homomorphic and the algorithms A is called Add Otherwise, the scheme is called multiplicatively homomorphic and the algorithm A is called Mult. With respect to the aforementioned definitions, the following points are worth noticing: • For a homomorphic encryption scheme to be efficient, it is crucial to make sure that the size of the ciphertexts remains polynomially bounded in the security parameter σ during repeated computations. • The security aspects, definitions, and models of homomorphic cryptosystems are the same as those for other cryptosystems. If the encryption algorithm E gets as additional input a uniform random number r of a set , the encryption scheme is called probabilistic, otherwise, it is called deterministic. Hence, if a cryptosystem is probabilistic, there belong several different ciphertexts to one message depending on the random number r ∈ . But note that as before the decryption algorithm remains deterministic, i.e., there is just one message belonging to a given ciphertext. Further‐ more, in a probabilistic, homomorphic cryptosystem the algorithm A should be probabilistic too to hide the input ciphertext. For instance, this can be realized by applying a blinding algorithm on a (deterministic) computation of the encryption of the product and of the sum respectively. Notations: In the following, we will omit the security parameter σ and the public key in the description of the algorithms. We will write Eke(m) or E(m) for E (1σ, ke, m) and Dk (c) or D(c) for D(1σ, k , c) when there is no possibility of any ambiguity. If the scheme is probabilistic, we will also write Eke(m) or E(m) as well as Eke(m, r) or E(m, r) for E (1σ, ke, m, r). Further‐ more, we will write A(E (m), E (m ')) = E (m o m') to denote that the algorithm A (either Add or Mult) is applied on two encryptions of the messages m, m' ∈(M , o) and outputs an encryp‐ tion of m o m', i.e., it holds that except with negligible probability: D(A(1σ, ke, Eke(m), Eke(m ')))= m o m ' Example: In the following, we give an example of a deterministic multiplicatively homomor‐ phic scheme and an example of a probabilistic, additively homomorphic scheme. The RSA Scheme: The classical RSA scheme (Rivest et al., 1987b) is an example of a deter‐ ministic multiplicatively homomorphic cryptosystem on M =(ℤ / N ℤ, .), where N is the product of two large primes. As ciphertext space, we have C =(ℤ / N ℤ, .) and as key space we have ={(ke, kd ) =((N , e), d )| N = pq, ed ≡ 1 mod φ(N )}. The encryption of a message m ∈ M is defined as E (m) = me mod N for decryption of a ciphertext E (m) = c ∈ C we compute e e D (c) = c d mod N = m mod N . Obviously, the encryption of the product of two messages can e, d be efficiently computed by multiplying the corresponding ciphertexts, i.e., Ek (m1.m2) =(m1.m2)emod N =(me mod n)(me mod N ) = Ek (m1). Ek (m2) e 1 2 e e where m1, m2 ∈ M . Therefore, the algorithm for Mult can be easiliy realized as follows: Mult(Ek (m1), Ek (m2)) = Ek (m1). Ek (m2) Usually in the RSA scheme as well as in most of the cryptosystems which are based on the difficulty of factoring the security parameter σ is the bit length of N. For instance, σ = 1024 is a common security parameter. The Goldwasser-Micali Scheme: The Goldwasser-Micali scheme (Goldwasser & Micali, 1984) is an example of a probabilistic, additively homomorphic cryptosystem on M =(ℤ / 2ℤ, + ) with the ciphtertext space C = Z =(ℤ / N ℤ)* where N = pq is the product of two large primes. We have. K ={(k , k ) =((N , a), ( p, q)) | N = pq, a ∈(ℤ / N ℤ)* : ( a )= ( a )= - 1} Since this scheme is probabilistic, the encryption algorithm gets as additional input a random value r ∈. We define Ek (m, r) = amr 2 mod N and D(k k ) = 0 if c is a square and = 1 otherwise. The following relation therefore holds good: Ek (m1, r1). Ek (m2, r2) = Ek (m1 + m2, r1r2) The algorithms Add can, therefore, be efficiently implemented as follows: Add (Ek (m1, r1), Ek (m2, r2), r3) = Ek (m1, r1). Ek (m2, r2). r 2 mod N = Eke(m1 + m2, r1r2r3) e e e e 3 In the above equation, r 2 mod N is equivalent to E (0, r ). Also, m , m ∈ M and r , r ,r ∈ Z . 3 ke 3 1 2 1 2 3 Note that this algorithm should be probabilistic, since it obtains a random number r3 as an additional input. A public-key homomorphic encryption scheme on a (semi-)ring (M, +,.) can be defined in a similar manner. Such schemes consist of two algorithms: Add and Mult for the homomorphic property instead of one algorithm for A, i.e., it is additively and multiplicatively homomorphic at the same time. Such schemes are called algebraically homomorphic. Definition: An additively homomorphic encryption scheme on a (semi-)ring (M, +,.) is called scalar homomorphic if there exists a probabilistic, expected polynomial time algorithm Mixed_Mult that on inputs 1σ, ke, s ∈ M and an element c ∈ C outputs an element c ' ∈ C so that for all m ∈ M it holds that: if m' = s.m and c = E (1σ, ke, m) then the probability Prob D(Mixed _ Mult(1σ, ke, s, s)) ≠ m' is negligible. Thus in a scalar homomorphic scheme, it is possible to compute an encryption E (1σ, ke, s.m) = E (1σ, ke, m') of a product of two messages s, m ∈ M given the public key ke and an encryption c = E (1σ, ke, m) of one message m and the other message s as a plaintext. It is clear that any scheme that is algebraically homomorphic is scalar homomorphic as well. We will denote by Mixed _ Mult(m, E (m ')) = E (mm') if the following equation holds good except possibly with a negligible probability of not holding. D(Mixed _ Mult(1σ, ke, m, Ek (m '))= m . m ' Definition: A blinding algorithm is a probabilistic, polynomial-time algorithm which on inputs 1σ, ke, and c ∈ Eke(m, r) where r ∈ is randomly chosen outputs another encryption c ' ∈ Eke(m, r ') of m where r ' ∈ is chosen uniformly at random. For instance, in a probabilistic, homomorphic cryptosystem on (M, o) the blinding algorithm can be realized by applying the algorithm A on the ciphertext c and an encryption of the identity element in M. If M is isomorphic to ℤ / nℤ if M is finite or to ℤ otherwise, then the algorithm Mixed_Mult can easily be implemented using a double and Add algorithm. This is combined with a blinding algorithm is the scheme is probabilistic (Cramer et al., 2000). Hence, every additively homo‐ morphic cryptosystem on ℤ / nℤ or ℤ is also scalar homomorphic and the algorithm Mixed_Mult can be efficiently implemented (Sander & Tschudin, 1998). Algebraically Homomorphic Cryptosystems: The existence of an efficient and secure algebraically homomorphic cryptosystem has been a long standing open question. In this Section, we first present some related work considering this problem. Thereafter, we describe the relationship between algebraically homomorphic schemes and homomorphic schemes on special non-abelian groups. More precisely, we prove that a homomorphic encryption scheme on the non-ableain group (S7,.), the symmetric group on seven elements, allows to construct an algebraically homomorphic encryption scheme on (F2, +,.). An algebraically homomorphic encryption scheme on (F2, +,.) can also be obtained from a homomorphic encryption scheme on the special linear group (SL(3, 2),.) over F2. Furthermore, using coding theory, an algebra‐ ically homomorphic encryption on an arbitrary finite ring or field could be obtained given a homomorphic encryption scheme on one of these non-abelian groups. These observations could be a first step to solve the problem whether efficient and secure algebraically homo‐ morphic schemes exist. The research community in cryptography has spent substantial effort on this problem. In 1996, Boneh and Lipton proved that under a reasonable assumption every deterministic, algebraically homomorphic cryptosystem can be broken in sub-exponential time (Boneh & Lipton, 1996). This may be perceived as a negative result concerning the existence of an algebraically homomorphic encryption scheme, although most of the existing cryptosystems, e.g., RSA scheme or the ElGamal scheme can be also be broken in sub- exponential time. Furthermore, if we seek for algebraically homomorphic public-key schemes on small fields or rings such as M = F2, obviously such a scheme has to be probabilistic in order to be secure. Some researchers also tried to find candidates for algebraically homomorphic schemes. In 1993, Fellows and Koblitz presented an algebraic public-key cryptosystem called Polly Cracker (Fellows & Koblitz, 1993). It is algebraically homomorphic and provably secure. Unfortunately, the scheme has a number of difficulties and is not efficient concerning the ciphertext length. Firstly, Polly Cracker is a polynomial-based system. Therefore, computing an encryption of the product E (m1.m2) of two messages m1 and m2 by multiplying the corresponding ciphertext polynomials E (m1) and E (m2), leads to an exponential blowup in the number of monomials. Hence, during repeated computations, there is an exponential blow up in the ciphertext length. Secondly, all existing instantiations of Polly Cracker suffer from further drawbacks (Koblitz, 1998). They are either insecure since they succumb to certain attacks, they are too inefficient to be practical, or they lose the algebraically homomorphic property. Hence, it is far from clear how such kind of schemes could be turned into efficient and secure algebraically homomorphic encryption schemes. A detailed analysis and description of these schemes can be found in (Ly, 2002). In 2002, J. Domingo-Ferrer developed a probabilistic, algebraically homomorphic secret-key cryptosystem (Domingo-Ferrer, 2002). However, this scheme was not efficient since there was an exponential blowup in the ciphertext length during repeated multiplications that were required to be performed. Moreover, it was also broken by Wagner and Bao (Bao, 2003; Wagner, 2003). Thus considering homomorphic encryption schemes on groups instead of rings seems more promising to design a possible algebraically homomorphic encryption scheme. It brings us closer to structures that have been successfully used in cryptography. The following theorem shows that indeed the search for algebraically homomorphic schemes can be reduced to the search for homomorphic schemes on special non-abelian groups (Rappe, 2004). Theorem I: The following two statements are equivalent: (1) There exists an algebraically homomorphic encryption scheme on (F2, +,.). (2) There exists a homomorphic encryption scheme on the symmetric group (S7,.). Proof: 1 → 2: This direction of proof follows immediately and it holds for an arbitrary finite group since operations of finite groups can always be implemented by Boolean circuits. Let S7 be represented as a subset of {0, 1}l, where e.g. l = 21 can be chosen, and let C be a circuit with addition and multiplication gates that takes as inputs the binary representations of elements m1, m2 ∈ S7 and outputs the binary representations of m1m2. If we have an algebraically homomorphic encryption scheme (K, E, D, Add, Mult) on (F2, +,.) then we can define a homo‐ morphic encryption scheme (K˜, E˜, D˜, M˜ult) on S7 by defining E˜(m) =(E (s0), ….E (sl -1)) where (s0, sl -1) denotes the binary representation of m. M˜ult is constructed by substituting the addition gates in C by Add and the multiplication gates by Mult. K˜ and D˜ are defined in the obvious way. 2 → 1: The proof has two steps. First, we use a construction of Ben-Or and Cleve (Ben-Or & Cleve, 1992) to show that the field (F2, +,.) can be encoded in the special linear group (SL(3,2),.) over F2. Then, we apply a theorem from projective geometry to show that (SL(3,2),.) is a subgroup of S7. This proves the claim. Homomorphic encryption schemes on groups have been extensively studied. For instance, we have homomorphic schemes on groups (ℤ / M ℤ, +), for M being a smooth number (Gold‐ wasser & Micali, 1984; Benaloh, 1994; Naccache & Stern, 1998) for M = p.q being an RSA modulus (Paillier, 1999; Galbraith, 2002), and for groups ((ℤ / N ℤ) *, .) where N is an RSA modulus. All known efficient and secure schemes are homomorphic on abelian groups. However, S7 and SL(3, 2) are non-abelian. Sander, Young and Yung (Sander et al., 1999) investigated the possibility of existence of a homomorphic encryption scheme on non-abelain groups. Although non-abelian groups had been used to construct encryption schemes (Ko et al., 2000; Paeng et al., 2001; Wagner & Magyarik, 1985; Grigoriev & Ponomarenko, 2006), the resulting schemes are not homomorphic in the sense that we need for computing efficiently on encrypted data. Grigoriev and Ponomarenko propose a novel definition of homomorphic cryptosystems on which they base a method to construct homomorphic cryptosystems over arbitrary finite groups including non-abelian groups (Grigoriev & Ponomarenko, 2006). Their construction method is based on the fact that every finite group is an epimorphic image of a free product of finite cyclic groups. It uses existing homomorphic encryption schemes on finite cyclic groups as building blocks to obtain homomorphic encryption schemes on arbitrary finite groups. Since the ciphertext space obtained from the encryption scheme is a free product of groups, an exponential blowup of the ciphertext lengths during repeated computations is produced as a result. The reason is that the length of the product of two elements x and y of a free product is, in general, the sum of the length of x and the length of y. Hence, the technique proposed by Grigoriev and Ponomarenko suffers from the same drawback as the earlier schemes and does not provide an efficient cryptosystem. We note that using this construction it is possible to construct a homomorphic encryption scheme on the symmetric group S7 and on the special linear group SL(3, 2). If we combine this with Theorem 1, we can construct an algebraically homomorphic cryptosystem on the finite field (F2, +,.). Unfortunately, the exponential blowup owing to the construction method in the homomorphic encryption scheme on S7 and on SL(3, 2) respectively, would lead to an exponential blowup in F2 and hence leaves the question open