Homomorphic Encryption

History

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)\)?

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).

Fundamentals

Symmetric encryption schemes:

  • The sender and the receiver agree on the key they will use before establishing any secure communication session.

    • It is not possible for two persons who never met before to use such schemes directly.

    • In order to communicate with different persons, we must have a different key for each people.

  • Existing symmetric encryption systems

    • AES (Daemen & Rijmen, 2000; Daemen & Rijmen, 2002)

    • One-Time Pad (Vernam, 1926)

    • Snow (Ekdahl & Johansson, 2002)

Asymmetric encryption schemes:

  • every participant has a pair of keys - private and public.

    • More secure than their symmetric counterparts

    • Don’t need any prior agreement between the communicating parties on a common key before establishing a session of communication.

  • Popular Asymmetric Encryption Schemes:

    • RSA (Rivest et al., 1978b)

    • ElGamal (ElGamal, 1985)

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 knowledge 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.

For asymmetric schemes, we can rely on their mathematical 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 (NP), the estimation of the security level of these schemes may not always be correct due to several reasons:

  1. 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).

  2. 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.

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.

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

    • It can happen when some adversary eavesdrops on a communication channel.

  • 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 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. - For a fixed encryption key, a given plaintext will always be encrypted into the same ciphertext under these systems. this may lead to some security problems.

E.g.

  • RSA scheme

      1. 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.

      1. 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).

      1. 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.

We prefer encryption schemes to be probabilistic.

symmetric schemes case

we introduce a random vector in the encryption process, initial vector (IV).

  • IV

    • May be public and it may be transmitted in a clear-text form.

    • IV must be changed every time we encrypt a message.

asymmetric ciphers case

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, Such as:

  • Randomized schemes

    • The optimal asymmetric encryption padding (OAEP) for RSA (or any scheme that is based on a trapdoor one-way permutation) (Bellare & Rogaway, 1995).

    • ElGamal, 1985; Goldwasser & Micali, 1982; Blum & Goldwasser, 1985

Expansion

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.

E.g.

In Paillier’s scheme, an efficient probabilistic encryption mechanism has been proposed with the value of expansion less than 2 (Paillier, 1997).

Homomorphic encryption schemes

Definition: Let the message space \((\mathbf{M}, o)\) be a \(finite (semi-)group\), and let \(\sigma\) be the security parameter.

A homomorphic public-key encryption scheme(or homomorphic cryptosystem) on \(\mathbf{M}\) is a quadruple \((K, E, D, A)\) of probabilistic.

expected polynomial time algorithms, satisfying the following functionalities:

  • Key Generation:

    • On input \(1^\sigma\), the algorithm \(K\) outputs an encryption/decryption key pair \((k_{e}, k_d)=k \in \mathbb{K}\), where \(\mathbb{K}\) denotes the key space.

  • Encryption:

    • On inputs \(1^{\sigma} , k_{e}\), and an element \(m \in \mathbf{M}\), the encryption algorithm \(E\) outputs a ciphertext \(c \in C\) , where \(C\) denotes the ciphertext space.

  • Decryption:

The decryption algorithm \(D\) is deterministic. On input \(1^{\sigma‘}k\), and an element \(c \in C\), it outputs an element in the message space \(\mathbf{M}\) so that:

\[Pr[m \leftarrow \mathbf{M} ;c = E(1^\sigma, k_e, m): D(1^{\sigma}, k, c \neq m] \le 2^{-\sigma}\ is \ negligiable\]

  • Homomorphic Property:

\(A\) is an algorithm that on input \(1^{\sigma}, k_e\), and elements \(c_1, c_2 \in C\), outputs an element \(C_3 \in C\).

So that for all \(m_1, m_2 \in \mathbf{M}\), it holds:

\[Pr[m_1, m_2 \leftarrow \mathbf{M}; m_3 = m_1 \circ m_2: D(A(1^\sigma, k_1, E(1^\sigma, k_e, m_1), E(1^\sigma, k_e, m_1)))\neq m_3]\ is \ negligiable\]

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 \(\mathbf{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.

If the encryption algorithm \(E\) gets as additional input a uniform random number \(r\) of a set \(Z\), the encryption shceme is called probablistic, otherwise, it is called deterministic.

If a cryptosystem is probabilistic, there belong several different ciphertexts to one message depending on the random number \(r \in Z\).