4TH EDITION THEORY AND PRACTICE OF CRYPTOGRAPHY AND NETWORK SECURITY PROTOCOLS AND TECHNOLOGIES BY JAYDIP SEN

Document Content and Description Below

4TH EDITION THEORY AND PRACTICE OF CRYPTOGRAPHY AND NETWORK SECURITY PROTOCOLS AND TECHNOLOGIES BY JAYDIP SEN India Chapter 1 Homomorphic Encryption — Theory and Application J... aydip Sen 1. Introduction The demand for privacy of digital data and of algorithms for handling more complex structures have increased exponentially over the last decade. This goes in parallel with the growth in communication networks and their devices and their increasing capabilities. At the same time, these devices and networks are subject to a great variety of attacks involving manipulation and destruction of data and theft of sensitive information. For storing and accessing data securely, current technology provides several methods of guaranteeing privacy such as data encryption and usage of tamper-resistant hardwares. However, the critical problem arises when there is a requirement for computing (publicly) with private data or to modify functions or algorithms in such a way that they are still executable while their privacy is ensured. This is where homomorphic cryptosystems can be used since these systems enable computations with encrypted data. In 1978 Rivest et al. (Rivest et al, 1978a) first investigated the design of a homomorphic encryption scheme. Unfortunately, their privacy homomorphism was broken a couple of years later by Brickell and Yacobi (Brickell & Yacobi, 1987). The question rose again in 1991 when Feigenbaum and Merritt (Feigenbaum & Merritt, 1991) raised an important question: is there an encryption function (E) such that both E(x + y) and E(x.y) are easy to compute from E(x) and E(y)? Essentially, the question is intended to investigate whether there is any algebraically homomorphic encryption scheme that can be designed. Unfortunately, there has been a very little progress in determining whether such encryption schemes exist that are efficient and secure until 2009 when Craig Gentry, in his seminal paper, theoretically demonstrated the possibility of construction such an encryption system (Gentry, 2009). In this chapter, we will discuss various aspects of homomorphic encryption schemes – their definitions, requirements, applications, formal constructions, and the limitations of the current homomorphic encryption schemes. We will also briefly discuss some of the emerging trends in research in this field of computer science. The chapter is organized as follows. In Section 2, we provide some basic and fundamental information on cryptography and various types of encryption schemes. Section 3 presents a formal discussion on homomorphic encryption schemes and discusses their various features. In Section 4, we discuss some of the most well-known and classical homomorphic encryption schemes in the literature. Section 5 provides a brief presentation on various properties and applications of homomorphic cryptosystems. Section 6 presents a discussion on fully homo‐ morphic encryption schemes which are the most powerful encryption schemes for providing a framework for computing over encrypted data. Finally, Section 7 concludes the chapter while outlining a number of research directions and emerging trends in this exciting field of computation which has a tremendous potential of finding applications in the real-world deployments. 2. Fundamentals of cryptography In this Section, we will recall some important concepts on encryption schemes. For more detailed information, the reader may refer to (Menezes et al., 1997; Van Tilborg, 2011). Encryption schemes are designed to preserve confidentiality. The security of encryption schemes must not rely on the obfuscation of their codes, but it should only be based on the secrecy of the key used in the encryption process. Encryption schemes are broadly of two types: symmetric and asymmetric encryption schemes. In the following, we present a very brief discussion on each of these schemes. Symmetric encryption schemes: In these schemes, the sender and the receiver agree on the key they will use before establishing any secure communication session. Therefore, it is not possible for two persons who never met before to use such schemes directly. This also implies that in order to communicate with different persons, we must have a different key for each people. Requirement of large number of keys in these schemes make their key generation and management relatively more complex operations. However, symmetric schemes present the advantage of being very fast and they are used in applications where speed of execution is a paramount requirement. Among the existing symmetric encryption systems, AES (Daemen & Rijmen, 2000; Daemen & Rijmen, 2002), One-Time Pad (Vernam, 1926) and Snow (Ekdahl & Johansson, 2002) are very popular. Asymmetric encryption schemes: In these schemes, every participant has a pair of keys- private and public. While the private key of a person is known to only her, the public key of each participant is known to everyone in the group. Such schemes are more secure than their symmetric counterparts and they don’t need any prior agreement between the communicating parties on a common key before establishing a session of communication. RSA (Rivest et al., 1978b) and ElGamal (ElGamal, 1985) are two most popular asymmetric encryption systems. Security of encryption schemes: Security of encryption schemes was first formalized by Shannon (Shannon, 1949). In his seminal paper, Shannon first introduced the notion of perfect secrecy/unconditional secrecy, which characterizes encryption schemes for which the knowl‐ edge of a ciphertext does not give any information about the corresponding plaintext and the encryption key. Shannon also proved that One-Time Pad (Vernam, 1926) encryption scheme is perfectly secure under certain conditions. However, no other encryption scheme has been proved to be unconditionally secure. For asymmetric schemes, we can rely on their mathe‐ matical structures to estimate their security strength in a formal way. These schemes are based on some well-identified mathematical problems which are hard to solve in general, but easy to solve for the one who knows the trapdoor – i.e., the owner of the keys. However, the estimation of the security level of these schemes may not always be correct due to several reasons. First, there may be other ways to break the system than solving the mathematical problems on which these schemes are based (Ajtai & Dwork, 1997; Nguyen & Stern, 1999). Second, most of the security proofs are performed in an idealized model called random oracle model, in which involved primitives, for example, hash functions, are considered truly random. This model has allowed the study of the security level of numerous asymmetric ciphers. However, we are now able to perform proofs in a more realistic model called standard model (Canetti et al., 1998; Paillier, 2007). This model eliminates some of the unrealistic assumptions in the random oracle model and makes the security analysis of cryptographic schemes more practical. Usually, to evaluate the attack capacity of an adversary, we distinguish among several contexts (Diffie & Hellman, 1976): cipher-text only attacks (where the adversary has access only to some ciphertexts), known-plaintext attacks (where the adversary has access to some pairs of plaintext messages and their corresponding ciphertexts), chosen-plaintext attacks (the adversary has access to a decryption oracle that behaves like a black-box and takes a ciphertext as its input and outputs the corresponding plaintexts). The first context is the most frequent in real-world since it can happen when some adversary eavesdrops on a communication channel. The other cases may seem difficult to achieve, and may arise when the adversary is in a more powerful position; he may, for example, have stolen some plaintexts or an encryption engine. The chosen one exists in adaptive versions, where the opponents can wait for a computation result before choosing the next input (Fontaine & Galand, 2007). Probabilistic encryption: Almost all the well-known cryptosystems are deterministic. This means that for a fixed encryption key, a given plaintext will always be encrypted into the same ciphertext under these systems. However, this may lead to some security problems. RSA scheme is a good example for explaining this point. Let us consider the following points with reference to the RSA cryptosystem: • A particular plaintext may be encrypted in a too much structured way. With RSA, messages 0 and 1 are always encrypted as 0 and 1, respectively. • It may be easy to compute some partial information about the plaintext: with RSA, the ciphertext c leaks one bit of information about the plaintext m, namely, the so called Jacobi symbol (Fontaine & Galand, 2007). • When using a deterministic encryption scheme, it is easy to detect when the same message is sent twice while being processed with the same key. In view of the problems stated above, we prefer encryption schemes to be probabilistic. In case of symmetric schemes, we introduce a random vector in the encryption process (e.g., in the pseudo-random generator for stream ciphers, or in the operating mode for block ciphers) – generally called initial vector (IV). This vector may be public and it may be transmitted in a clear-text form. However, the IV must be changed every time we encrypt a message. In case of asymmetric ciphers, the security analysis is more mathematical and formal, and we want the randomized schemes to remain analyzable in the same way as the deterministic schemes. Researchers have proposed some models to randomize the existing deterministic schemes, as the optimal asymmetric encryption padding (OAEP) for RSA (or any scheme that is based on a trapdoor one-way permutation) (Bellare & Rogaway, 1995). In the literature, researchers have also proposed some other randomized schemes (ElGamal, 1985; Goldwasser & Micali, 1982; Blum & Goldwasser, 1985). A simple consequence of this requirement of the encryption schemes to be preferably proba‐ bilistic appears in the phenomenon called expansion. Since, for a plaintext, we require the existence of several possible ciphertexts, the number of ciphertexts is greater than the number of possible plaintexts. This means that the ciphertexts cannot be as short as the plaintexts; they have to be strictly longer. The ratio of the length of the ciphertext and the corresponding plaintext (in bits) is called expansion. The value of this parameter is of paramount importance in determining security and efficiency tradeoff of a probabilistic encryption scheme. In Paillier’s scheme, an efficient probabilistic encryption mechanism has been proposed with the value of expansion less than 2 (Paillier, 1997). We will see the significance of expansion in other homomorphic encryption systems in the subsequent sections of this chapter. 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. [Show More]

Last updated: 2 months ago

Preview 1 out of 147 pages