Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

2.1 Homomorphic Encryption Definition

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures, such as groups.

A group is a set, G, together with an operation ∘ (called the group law of G) that combines any two elements a and b to form another element, denoted a ∘ b. To qualify as a group, the set and operation, (G, ∘), must satisfy four requirements known as the group axioms:

  • Closure: For all a, b in G, the result of the operation, a ∘ b, is also in G.

  • Associativity: For all a, b, and c in G, (a ∘ b) ∘ c = a ∘ (b ∘ c).

  • Identity element: There exists an element e in G, such that for every element a in G, the equality e ∘ a = a ∘ e = a holds. Such an element is unique, and thus one speaks of the identity element.

  • Inverse element: For each a in G, there exists an element b in G such that a ∘ b = b ∘ a = e, where e is the identity element.

The identity element of a group G is often written as 1.

The result of an operation may depend on the order of the operands. In other words, the result of combining element a with element b need not yield the same result as combining element b with element a; the equation a ∘ b = b ∘ a may not always be true. This equation always holds in the group of integers under addition, because a + b = b + a for any two integers (commutativity of addition). Groups for which the commutativity equation a ∘ b = b ∘ a always holds are called abelian groups.

Given two groups (G, ⋄) and (H, ∘), a group homomorphism from (G, ⋄) to (H, ∘) is a function f: G → H such that for all g and g′ in G it holds that

$$\displaystyle\begin{array}{rcl} f(g \diamond g') = f(g) \circ f(g')\ & &{}\end{array}$$
(2.1)

Group homomorphism can be illustrated as in Fig. 2.1.

Fig. 2.1
figure 1

Group Homomorphism

Full size image

Let (P, C, K, E, D) be an encryption scheme, where P, C are the plaintext and ciphertext spaces, K is the key space, and E, D are the encryption and decryption algorithms. Assume that the plaintexts forms a group (P, ⋄) and the ciphertexts forms a group (C, ∘), then the encryption algorithm E is a map from the group P to the group C, i.e., E k : P → C, where k ∈ K is either a secret key (in a secret key cryptosystem) or a public key (in a public-key cryptosystem).

For all a and b in P and k in K, if

$$\displaystyle\begin{array}{rcl} E_{k}(a) \circ E_{k}(b)& =& E_{k}(a \diamond b){}\end{array}$$
(2.2)

the encryption scheme is homomorphic.

In an unpadded RSA [18], assume that the public key pk = (n, e), the plaintexts form a group (P, ⋅ ), and the ciphertexts form a group (C, ⋅ ), where ⋅ is the modular multiplication. For any two plaintexts m 1, m 2 in P, it holds that

$$\displaystyle\begin{array}{rcl} E(m_{1},pk) \cdot E(m_{2},pk)& =& m_{1}^{e} \cdot m_{ 2}^{e}(mod\ n) {}\\ & =& (m_{1} \cdot m_{2})^{e}(mod\ n) {}\\ & =& E(m_{1} \cdot m_{2},pk)\ {}\\ \end{array}$$

Therefore, the unpadded RSA has the homomorphic property. Unfortunately, the unpadded RSA is insecure.

2.2 Goldwasser–Micali Encryption Scheme

The Goldwasser–Micali (GM) encryption scheme [7] is a public-key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as ciphertexts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely used definition of semantic security.

GM consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.

The scheme relies on deciding whether a given value x is a square mod N, given the factorization (p, q) of N. This can be accomplished using the following procedure:

Compute

$$\displaystyle\begin{array}{rcl} x_{p}& =& x(mod\ p){}\end{array}$$
(2.3)
$$\displaystyle\begin{array}{rcl} x_{q}& =& x(mod\ q){}\end{array}$$
(2.4)

If

$$\displaystyle\begin{array}{rcl} x_{p}^{(p-1)/2}& =& 1(mod\ p){}\end{array}$$
(2.5)
$$\displaystyle\begin{array}{rcl} x_{q}^{(q-1)/2}& =& 1(mod\ q){}\end{array}$$
(2.6)

then x is a quadratic residue mod N.

Key Generation: The modulus used in GM encryption is generated in the same manner as in the RSA cryptosystem.

Alice generates two distinct large prime numbers p and q, such that p = q = 3(mod 4), randomly and independently of each other. Alice computes N = pq. She then finds some non-residue a such that

$$\displaystyle{a_{p}^{(p-1)/2} = -1(mod\ p),a_{ q}^{(q-1)/2} = -1(mod\ q)}$$

The public key consists of (a, N). The secret key is the factorization (p, q).

Encryption: Suppose Bob wishes to send a message m to Alice. Bob first encodes m as a string of bits (m 1, ⋯ , m n ).

For every bit m i , Bob generates a random value b i from the group of units modulo N, or gcd(b i , N) = 1. He outputs the value

$$\displaystyle\begin{array}{rcl} c_{i}& =& b_{i}^{2} \cdot a^{m_{i} }(mod\ N){}\end{array}$$
(2.7)

Bob sends the ciphertext (c 1, c 2, ⋯ , c n ) to Alice.

Decryption: Alice receives (c 1, c 2, ⋯ , c n ). She can recover m using the following procedure:

For each i, using the prime factorization (p, q), Alice determines whether the value c i is a quadratic residue; if so, m i  = 0, otherwise m i  = 1. Alice outputs the message m = (m 1, ⋯ , m n ).

GM Example: We choose small parameters in this example. In key generation, we let

$$\displaystyle{p = 7,q = 11}$$

where p = q = 3(mod 4). So

$$\displaystyle{N = pq = 77}$$

Take

$$\displaystyle{a = 6}$$

where

$$\displaystyle{6^{(7-1)/2} = -1(mod\ 7),6^{(11-1)/2} = -1(mod\ 11)}$$

The public key is (6, 77) and the private key is (7,11).

To encrypt 3-bit message m 1 m 2 m 3 = 101. Choose

$$\displaystyle{b_{1} = 2,b_{2} = 3,b_{3} = 5}$$

and compute

$$\displaystyle\begin{array}{rcl} & c_{1} = 2^{2} \cdot 6^{1} = 24(mod\ 77)& {}\\ & c_{2} = 3^{2} \cdot 6^{0} = 9(mod\ 77) & {}\\ & c_{3} = 5^{2} \cdot 6^{1} = 73(mod\ 77)& {}\\ \end{array}$$

The ciphertext is (24,9,73).

To decrypt the ciphertext, compute

$$\displaystyle\begin{array}{rcl} & 24^{(7-1)/2} = -1(mod\ 7) & {}\\ & 9^{(7-1)/2} = 1(mod\ 7),9^{(11-1)/2} = 1(mod\ 11)& {}\\ & 73^{(7-1)/2} = -1(mod\ 7) & {}\\ \end{array}$$

This shows that 24 and 73 are non-quadratic residue and 9 is quadratic residue, and thus outputs the plaintext 101.

Homomorphic Property: The GM encryption scheme has a homomorphic property, in the sense that if c 0, c 1 are the encryptions of bits m 0, m 1, then c 0 c 1(mod N) will be an encryption of m 0 ⊕ m 1, where ⊕ denotes addition modulo 2 (i.e., exclusive-OR).

Assume that

$$\displaystyle{c_{0} = b_{0}^{2} \cdot a^{m_{0} }(mod\ N),c_{1} = b_{1}^{2} \cdot a^{m_{1} }(mod\ N)}$$

we have

$$\displaystyle\begin{array}{rcl} c_{0} \cdot c_{1}& =& (b_{0}^{2} \cdot a^{m_{0} }) \cdot (b_{1}^{2} \cdot a^{m_{1} })(mod\ N) {}\\ & =& (b_{0}b_{1})^{2} \cdot a^{m_{0}+m_{1} }(mod\ N) {}\\ \end{array}$$

When m 0 + m 1 is either 0 or 1, we have m 0 + m 1 = m 0 ⊕ m 1. When m 0 = m 1 = 1, m 0 + m 1 = 2 and c 0 c 1(mod N) is a quadratic residue and thus it is an encryption of 0. In this case, we have m 0 ⊕ m 1 = 1 ⊕ 1 = 0 as well.

Security: The GM encryption scheme is a probabilistic encryption [8]. Probabilistic encryption refers to the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term “probabilistic encryption” is typically used in reference to public-key encryption algorithms; however, various secret key encryption algorithms achieve a similar property (e.g., block ciphers when used in a chaining mode such as CBC). To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

Probabilistic encryption is particularly important when using public-key encryption. Suppose that the adversary observes a ciphertext and suspects that the plaintext is either “YES” or “NO.” When a deterministic encryption algorithm is used, the adversary can simply try encrypting each of his or her guesses under the recipient’s public key and compare each result to the target ciphertext. To combat this attack, public-key encryption schemes must incorporate an element of randomness, ensuring that each plaintext maps into one of a large number of possible ciphertexts.

An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm, such as padding RSA. Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding. However, early schemes which applied this naive approach were broken due to limitations in some deterministic encryption schemes. Techniques such as OAEP integrate random padding in a manner that is secure using any trapdoor permutation.

The GM encryption scheme is semantically secure [8]. Semantic security is commonly defined by the following game:

  • Initialize: The challenger runs the key generation algorithm, gives the public key pk to a probabilistic polynomial time-bounded (PPT) adversary, but keeps the private key sk to itself.

  • Phase 1: The adversary adaptively asks a number of different encryption queries C i  = E(m i , pk) for m i , where i = 1, 2, ⋯ , n.

  • Challenge: Once the adversary decides that Phase 1 is over, it outputs a pair of equal length plaintexts (M 0, M 1) on which it wishes to be challenged. The challenger picks a random bit b ∈ { 0, 1} and sends C = E(M b , pk) as the challenge to the adversary.

  • Phase 2: The adversary issues more encryption queries adaptively as in Phase 1.

  • Guess: Finally, the adversary outputs a guess b′ ∈ { 0, 1} and wins the game if b′ = b.

The public-key encryption cryptosystem is semantically secure under chosen-plaintext attack if the adversary cannot determine which of the two messages was chosen by the challenger, with probability significantly greater than 1/2 (the success rate of random guessing).

The GM encryption scheme is semantically secure based on the assumed intractability of the quadratic residuosity problem modulo a composite N = pq where p, q are large primes. This assumption states that given (a, N) it is difficult to determine whether a is a quadratic residue modulo N (i.e., a = b 2(mod N) for some b). The quadratic residue problem is easily solved given the factorization of N. The GM encryption scheme leverages this asymmetry by encrypting individual plaintext bits as either random quadratic residues or non-residues modulo N. Recipients use the factorization of N as a secret key and decrypt the message by testing the quadratic residuosity of the received ciphertext values.

Because the GM encryption scheme produces a value of size approximately | N | to encrypt every single bit of a plaintext, GM encryption results in substantial ciphertext expansion. To prevent factorization attacks, it is recommended that | N | be several hundred bits or more. Thus, the scheme serves mainly as a proof of concept, and more efficient provably secure schemes such as ElGamal encryption scheme have been developed since.

2.3 ElGamal Encryption Scheme

The ElGamal encryption scheme [4] is a public-key encryption algorithm based on the Diffie–Hellman key exchange. It was invented by Taher Elgamal in 1985. The ElGamal encryption scheme is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The ElGamal encryption scheme can be defined over any cyclic group G. Its security depends upon the difficulty of a certain problem in G related to computing discrete logarithms.

The ElGamal encryption scheme consists of three components: the key generation, the encryption algorithm, and the decryption algorithm.

Key Generation: The key generator works as follows:

Alice generates an efficient description of a cyclic group G, of order q, with generator g.

Alice chooses a random x ∈ { 1, …, q − 1}.

Alice computes

$$\displaystyle\begin{array}{rcl} y& =& g^{x}{}\end{array}$$
(2.8)

Alice publishes y along with the description of G, q, g, as her public key. Alice retains x, as her private key which must be kept secret.

Encryption: The encryption algorithm works as follows:

To encrypt a message m, to Alice under her public key (G, q, g, y), Bob chooses a random r ∈ { 1, …, q − 1}, then computes

$$\displaystyle\begin{array}{rcl} c_{1}& =& g^{r}\ {}\end{array}$$
(2.9)

Bob computes the shared secret

$$\displaystyle\begin{array}{rcl} s& =& y^{r}\ {}\end{array}$$
(2.10)

Bob converts his secret message m, into an element m′ ∈ G.

Bob computes

$$\displaystyle\begin{array}{rcl} c_{2}& =& m' \cdot s\ {}\end{array}$$
(2.11)

Bob sends the ciphertext (c 1, c 2) = (g r, m′ ⋅ y r) to Alice.

Note that one can easily find y r, if one knows m′. Therefore, a new r, is generated for every message to improve security. For this reason, r, is also called an ephemeral key.

Decryption: The decryption algorithm works as follows:

To decrypt a ciphertext (c 1, c 2), with her private key x, Alice computes the shared secret

$$\displaystyle\begin{array}{rcl} t& =& c_{1}^{x}\ {}\end{array}$$
(2.12)

and then computes

$$\displaystyle\begin{array}{rcl} m'& =& c_{2} \cdot t^{-1}\ {}\end{array}$$
(2.13)

which she then converts back into the plaintext message m, where t −1 is the inverse of t in the group G (e.g., modular multiplicative inverse if G is a subgroup of a multiplicative group of integers modulo n).

The decryption algorithm produces the intended message, since

$$\displaystyle\begin{array}{rcl} c_{2} \cdot t^{-1}& =& (m' \cdot s) \cdot c_{ 1}^{-x} {}\\ & =& m' \cdot y^{r} \cdot g^{-xr} {}\\ & =& m' \cdot g^{xr} \cdot g^{-xr} {}\\ & =& m'\ {}\\ \end{array}$$

The ElGamal encryption scheme is probabilistic, meaning that a single plaintext can be encrypted to many possible ciphertexts, with the consequence that a general ElGamal encryption produces a 2:1 expansion in size from plaintext to ciphertext.

Encryption under ElGamal requires two exponentiations; however, these exponentiations are independent of the message and can be computed ahead of time if need be. Decryption only requires one exponentiation.

The division by t can be avoided by using an alternative method for decryption. To decrypt a ciphertext (c 1, c 2), with Alice’s private key x, Alice computes t′ = c 1 q−x = g (q−x)r. t′ is the inverse of t. This is a consequence of Lagrange’s theorem, because

$$\displaystyle{t \cdot t' = g^{xr} \cdot g^{(q-x)r} = (g^{q})^{r} = 1^{r} = 1}$$

where 1 is the identity element of G.

Alice then computes m′ = c 2 ⋅ t′, by which she then converts back into the plaintext message m. The decryption algorithm produces the intended message, since

$$\displaystyle{c_{2} \cdot t' = m'\cdot s\cdot t' = m'\cdot y^{r}\cdot t' = m'\cdot g^{xr}\cdot t' = m'\cdot (g^{r})^{x}\cdot t' = m'\cdot c_{ 1}^{x}\cdot t' = m'\cdot t\cdot t' = m'}$$

ElGamal Example: An example of the ElGamal encryption with small parameters is given as follows:

At first, Alice generates a prime modulo p and a group generator g which is between 1 and p − 1:

$$\displaystyle\begin{array}{rcl} p = 2879& & {}\\ g = 2585& & {}\\ \end{array}$$

Alice selects a random number (x) which will be her private key:

$$\displaystyle{x = 47}$$

She then calculates

$$\displaystyle{y = g^{x} = 2585^{47} = 2826(mod\ 2879)}$$

Alice’s public key is now (p, g, y) and sends them to Bob. The private key x is known to Alice only.

Bob then creates a message

$$\displaystyle{m = 77}$$

and then selects a random value

$$\displaystyle{r = 65}$$

and calculates the ciphertext (c 1, c 2) where

$$\displaystyle\begin{array}{rcl} & c_{1} = g^{r} = 2585^{65} = 319(mod\ 2879) & {}\\ & c_{2} = m \cdot y^{r} = 77 \cdot 2826^{65} = 472(mod\ 2879)& {}\\ \end{array}$$

Alice can decrypt the ciphertext:

$$\displaystyle{c_{2}/c_{1}^{x} = 472/319^{47} = 77(mod\ 2879).}$$

Homomorphic Property: ElGamal encryption scheme has a homomorphic property. Given two encryptions

$$\displaystyle{(c_{11},c_{12}) = (g^{r_{1} },m_{1}y^{r_{1} }),(c_{21},c_{22}) = (g^{r_{2} },m_{2}y^{r_{2} })}$$

where r 1, r 2 are randomly chosen from {1, 2, ⋯ , q − 1} and m 1, m 2 ∈ G, one can compute

$$\displaystyle\begin{array}{rcl} (c_{11},c_{12})(c_{21},c_{22})& =& (c_{11}c_{21},c_{12}c_{22}) {}\\ & =& (g^{r_{1} }g^{r_{2} },(m_{1}y^{r_{1} })(m_{2}y^{r_{2} })) {}\\ & =& (g^{r_{1}+r_{2} },(m_{1}m_{2})y^{r_{1}+r_{2} })\ {}\\ \end{array}$$

The resulted ciphertext is an encryption of m 1 m 2.

ElGamal Security: The security of the ElGamal scheme depends on the properties of the underlying group G as well as any padding scheme used on the messages.

If the computational Diffie–Hellman assumption (CDH) holds in the underlying cyclic group G, then the ElGamal encryption function is one way. The CDH is the assumption that a certain computational problem within a cyclic group G is hard. Consider a cyclic group G of order q, the CDH assumption states that, given (g, g a, g b) for a randomly chosen generator g and random a, b ∈ { 0, ⋯ , q − 1}, it is computationally intractable to compute the value g ab.

If the decisional Diffie–Hellman assumption (DDH) holds in G, then ElGamal achieves semantic security. Semantic security is not implied by the CDH alone. The DDH is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. Consider a (multiplicative) cyclic group G of order q, and with generator g. The DDH assumption states that, given g a and g b for uniformly and independently chosen \(a,b \in \mathbb{Z}_{q}\), the value g ab “looks like” a random element in G. This intuitive notion is formally stated by saying that the following two probability distributions are computationally indistinguishable:

  • (g a, g b, g ab), where a and b are randomly and independently chosen from \(\mathbb{Z}_{q}\);

  • (g a, g b, g c), where a, b, c are randomly and independently chosen from \(\mathbb{Z}_{q}\).

ElGamal encryption is unconditionally malleable and therefore is not secure under chosen-ciphertext attack. For example, given an encryption (c 1, c 2) of some (possibly unknown) message m, one can easily construct a valid encryption (c 1, 2c 2) of the message 2m.

To achieve chosen-ciphertext security, the scheme must be further modified, or an appropriate padding scheme must be used. Depending on the modification, the DDH assumption may or may not be necessary.

Other schemes related to ElGamal which achieve security against chosen-ciphertext attacks have also been proposed. The Cramer–Shoup cryptosystem [3] is secure under chosen-ciphertext attack assuming DDH holds for G. Its proof does not use the random oracle model. Another proposed scheme is DHAES [1], whose proof requires an assumption that is weaker than the DDH assumption.

The ElGamal encryption scheme is usually used in a hybrid cryptosystem, i.e., the message itself is encrypted using a symmetric cryptosystem and ElGamal is then used to encrypt the key used for the symmetric cryptosystem. This is because asymmetric cryptosystems like ElGamal are usually slower than symmetric ones for the same level of security, so it is faster to encrypt the symmetric key (which most of the time is quite small if compared to the size of the message) with ElGamal and the message (which can be arbitrarily large) with a symmetric cryptosystem.

2.4 Paillier Encryption Scheme

The Paillier encryption scheme [11], named after and invented by Pascal Paillier in 1999, is a probabilistic public-key algorithm. The problem of computing nth residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

The Paillier encryption scheme is composed of key generation, encryption, and decryption algorithms as follows:

Key Generation: Choose two large prime numbers p and q randomly and independently of each other, such that

$$\displaystyle{\gcd (pq,(p - 1)(q - 1)) = 1}$$

This property is assured if both primes are of equal length.

Compute

$$\displaystyle{n = pq,\lambda = lcm(p - 1,q - 1)}$$

where lcm stands for the least common multiple.

Select random integer g where \(g \in \mathbb{Z}_{n^{2}}^{{\ast}}\).

Ensure n divides the order of g by checking the existence of the following modular multiplicative inverse:

$$\displaystyle\begin{array}{rcl} \mu & =& (L(g^{\lambda }(mod\ n^{2})))^{-1}(mod\ n)\ {}\end{array}$$
(2.14)

where function L is defined as

$$\displaystyle\begin{array}{rcl} L(u)& =& \frac{u - 1} {n} \ {}\end{array}$$
(2.15)

Note that the notation a∕b does not denote the modular multiplication of a times the modular multiplicative inverse of b, but rather the quotient of a divided by b.

Finally, the public (encryption) key is (n, g) and the private (decryption) key is (λ, μ).

If using p, q of equivalent length, a simpler variant of the above key generation steps would be to set

$$\displaystyle{g = n + 1,\lambda =\varphi (n),\mu =\varphi (n)^{-1}(mod\ n)}$$

where φ(n) = (p − 1)(q − 1).

Encryption: Let m be a message to be encrypted where \(m \in \mathbb{Z}_{n}\).

Select random r where \(r \in \mathbb{Z}_{n}^{{\ast}}\)

Compute ciphertext as

$$\displaystyle\begin{array}{rcl} c& =& g^{m} \cdot r^{n}(mod\ n^{2})\ {}\end{array}$$
(2.16)

Decryption: Let c be the ciphertext to decrypt, where \(c \in \mathbb{Z}_{n^{2}}^{{\ast}}\)

Compute the plaintext message as:

$$\displaystyle\begin{array}{rcl} m& =& L(c^{\lambda }(mod\ n^{2})) \cdot \mu (mod\ n)\ {}\end{array}$$
(2.17)

As the original paper points out, decryption is “essentially one exponentiation modulo n 2.”

The Paillier encryption scheme exploits the fact that certain discrete logarithms can be computed easily. For example, by binomial theorem,

$$\displaystyle{(1 + n)^{x} =\sum _{ k=0}^{x}{x\choose k}n^{k} = 1 + nx +{ x\choose 2}n^{2} + \text{higher powers of }n}$$

This indicates that

$$\displaystyle{(1 + n)^{x} = 1 + nx\pmod n^{2}}$$

Therefore, if

$$\displaystyle{y = (1 + n)^{x}\mod n^{2}}$$

then

$$\displaystyle{x = \frac{y - 1} {n} \pmod n}$$

Thus

$$\displaystyle{L((1 + n)^{x}(mod\ n^{2})) = x\pmod n}$$

for any \(x \in \mathbb{Z}_{n}\).

Therefore, when g = n + 1, we have

$$\displaystyle\begin{array}{rcl} L(c^{\lambda }(mod\ n^{2}))\cdot \mu & =& L((g^{m}r^{n})^{\lambda }(mod\ n^{2})) \cdot \lambda ^{-1} {}\\ & =& L((g^{m\lambda }(mod\ n^{2})) \cdot \lambda ^{-1} {}\\ & =& \lambda \cdot m \cdot \lambda ^{-1} = m(mod\ n)\ {}\\ \end{array}$$

Paillier Example: An example of the Paillier encryption scheme with small parameters is shown as follows.

For ease of calculations, the example will choose small primes, to create a small n. Let

$$\displaystyle{p = 7,q = 11}$$

then

$$\displaystyle{n = pq = 7 \cdot 11 = 77}$$

Next, an integer g must be selected from \(\mathbb{Z}_{n^{2}}^{{\ast}}\), such that the order of g is a multiple of n in \(\mathbb{Z}_{n^{2}}\). If we randomly choose the integer

$$\displaystyle{g = 5652}$$

then all necessary properties, including the yet to be specified condition, are met, as the order of g is 2310 = 30 ⋅ 77 in \(\mathbb{Z}_{n^{2}}\). Thus, the public key for the example will be

$$\displaystyle{(n,g) = (77,5652)}$$

To encrypt a message

$$\displaystyle{m = 42}$$

where \(m \in \mathbb{Z}_{n}\), choose a random

$$\displaystyle{r = 23}$$

where r is a nonzero integer and \(r \in \mathbb{Z}_{n}\).

Compute

$$\displaystyle\begin{array}{rcl} c& =& g^{m}r^{n}(mod\ n^{2}) {}\\ & =& 5652^{42} \cdot 23^{77}(mod\ 5929) {}\\ & =& 4624(mod\ 5929) {}\\ \end{array}$$

To decrypt the ciphertext c, compute

$$\displaystyle{\lambda = lcm(6,10) = 30}$$

Define L(u) = (u − 1)∕n, compute

$$\displaystyle\begin{array}{rcl} k& =& L(g^{\lambda }(mod\ n^{2})) {}\\ & =& L(5652^{30}(mod\ 5929)) {}\\ & =& L(3928) {}\\ & =& (3928 - 1)/77 {}\\ & =& 3927/77 {}\\ & =& 51\ {}\\ \end{array}$$

Compute the inverse of k,

$$\displaystyle\begin{array}{rcl} \mu & =& k^{-1}(mod\ n) {}\\ & =& 51^{-1} = 74(mod\ 77)\ {}\\ \end{array}$$

Compute

$$\displaystyle\begin{array}{rcl} m& =& L(c^{\lambda }modn^{2}) \cdot \mu (mod\ n) {}\\ & =& L(4624^{30}(mod\ 5929)) \cdot 74(mod\ 77) {}\\ & =& L(4852) \cdot 74(mod\ 77) {}\\ & =& 42\ {}\\ \end{array}$$

Homomorphic Properties: A notable feature of the Paillier scheme is its homomorphic properties. Given two ciphertexts \(E(m_{1},pk) = g^{m_{1}}r_{1}^{n}(mod\ n^{2})\) and \(E(m_{2},pk) = g^{m_{2}}r_{2}^{n}(mod\ n^{2})\), where r 1 and r 2 are randomly chosen from \(\mathbb{Z}_{n}^{{\ast}}\), we have

  • Homomorphic Addition of Plaintexts

    The product of two ciphertexts will decrypt to the sum of their corresponding plaintexts, i.e.,

    $$\displaystyle{D(E(m_{1},pk) \cdot E(m_{2},pk)\ (mod\ n^{2})) = m_{ 1} + m_{2}(mod\ n)}$$

    because

    $$\displaystyle\begin{array}{rcl} E(m_{1},pk) \cdot E(m_{2},pk)& =& (g^{m_{1} }r_{1}^{n})(g^{m_{2} }r_{2}^{n})\ (mod\ n^{2}) {}\\ & =& g^{m_{1}+m_{2} }(r_{1}r_{2})^{n}(mod\ n^{2}) {}\\ & =& E(m_{1} + m_{2},pk)\ {}\\ \end{array}$$

    The product of a ciphertext with a plaintext raising g will decrypt to the sum of the corresponding plaintexts, i.e.,

    $$\displaystyle{D(E(m_{1},pk) \cdot g^{m_{2} }(mod\ n^{2})) = m_{ 1} + m_{2}(mod\ n)}$$

    because

    $$\displaystyle\begin{array}{rcl} E(m_{1},pk) \cdot g^{m_{2} }& =& (g^{m_{1} }r_{1}^{n})g^{m_{2} }\ (mod\ n^{2}) {}\\ & =& g^{m_{1}+m_{2} }r_{1}^{n}(mod\ n^{2}) {}\\ & =& E(m_{1} + m_{2},pk)\ {}\\ \end{array}$$

  • Homomorphic Multiplication of Plaintexts

    An encrypted plaintext raised to the power of another plaintext will decrypt to the product of the two plaintexts, i.e.,

    $$\displaystyle{D(E(m_{1},pk)^{m_{2} }(mod\ n^{2})) = m_{ 1}m_{2}(mod\ n)}$$

    because

    $$\displaystyle\begin{array}{rcl} E(m_{1},pk)^{m_{2} }& =& (g^{m_{1} }r_{1}^{n})^{m_{2} }\ (mod\ n^{2}) {}\\ & =& g^{m_{1}m_{2} }(r_{1}^{m_{2} })^{n}(mod\ n^{2}) {}\\ & =& E(m_{1}m_{2},pk)\ {}\\ \end{array}$$

    More generally, an encrypted plaintext raised to a constant k will decrypt to the product of the plaintext and the constant, i.e.,

    $$\displaystyle{D(E(m_{1},pk)^{k}(mod\ n^{2})) = km_{ 1}(mod\ n)}$$

However, given the Paillier encryptions of two messages, there is no known way to compute an encryption of the product of these messages without knowing the private key.

Paillier Security: The Paillier encryption scheme provides semantic security against chosen-plaintext attacks (IND-CPA). The ability to successfully distinguish the challenge ciphertext essentially amounts to the ability to decide composite residuosity. The semantic security of the Paillier encryption scheme was proved under the decisional composite residuosity (DCR) assumption—the DCR problem is intractable.

The DCR problem states as follows: Given a composite N and an integer z, it is hard to decide whether z is a N-residue modulo N 2 or not, i.e., whether there exists y such that

$$\displaystyle{z = y^{n}(mod\ n^{2})}$$

Because of the homomorphic properties, the Paillier encryption scheme, however, is malleable and therefore does not protect against adaptive chosen-ciphertext attacks (IND-CCA2). Usually in cryptography the notion of malleability is not seen as an “advantage,” but under certain applications such as secure electronic voting and threshold cryptosystems, this property may indeed be necessary.

Paillier and Pointcheval [12] however went on to propose an improved cryptosystem that incorporates the combined hashing of message m with random r. Similar in intent to the Cramer–Shoup cryptosystem, the hashing prevents an attacker, given only c, from being able to change m in a meaningful way. Through this adaptation the improved scheme can be shown to be IND-CCA2 secure in the random oracle model.

2.5 Boneh–Goh–Nissim Encryption Scheme

Boneh–Goh–Nissim encryption scheme [2], BGN scheme by brevity, resembles the Paillier [11] and the Okamoto–Uchiyama [10] encryption schemes. The BGN scheme was the first to allow both additions and multiplications with a constant-size ciphertext. The multiplication is possible due to the fact that pairings can be defined for elliptic curves.

Let G 1, G 2 be additive groups and G T a multiplicative group, all of prime order p. Let P ∈ G 1, Q ∈ G 2 be generators of G 1 and G 2, respectively.

A pairing is a map

$$\displaystyle{e: G_{1} \times G_{2} \rightarrow G_{T}}$$

for which the following holds:

  1. 1.

    Bilinearity: \(\forall a,b \in \mathbb{Z}_{p}^{{\ast}}\):

    $$\displaystyle{e(P^{a},Q^{b}) = e(P,Q)^{ab}}$$
  2. 2.

    Non-degeneracy: \(e(P,Q)\not =1\).

  3. 3.

    For practical purposes, e has to be computable in an efficient manner.

In cases when G 1 = G 2 = G, the pairing is called symmetric. If, furthermore, G is cyclic, the map e will be commutative; that is, for any P, Q ∈ G, we have

$$\displaystyle{e(P,Q) = e(Q,P)}$$

This is because for a generator g ∈ G, there exist integers p, q such that P = g p and Q = g q. Therefore

$$\displaystyle{e(P,Q) = e(g^{p},g^{q}) = e(g,g)^{pq} = e(g^{q},g^{p}) = e(Q,P)}$$

On the basis of pairing, BGN scheme can be described by three algorithms—key generation, encryption, and decryption algorithms—as follows:

Key Generation: Given a security parameter \(\lambda \in \mathbb{Z}^{+}\), generate a tuple (q 1, q 2, G, G 1, e), where q 1 and q 2 are two distinct large primes, G is a cyclic group of order q 1 q 2, and e is a pairing map e: G × G → G 1. Let N = q 1 q 2. Pick up two random generators g, u from G and set \(h = u^{q_{2}}\). Then h is a random generator of the subgroup of G of order q 1. The public key is PK = { N, G, G 1, e, g, h}. The private key SK = q 1.

Encryption: Assume the message space consists of integers in the set {0, 1, ⋯ , T} with T < q 2. We encrypt bits in which case T = 1. To encrypt a message m using the public key PK, pick a random r from {1, 2, ⋯ , N} and compute

$$\displaystyle\begin{array}{rcl} C = g^{m}h^{r} \in G\ & &{}\end{array}$$
(2.18)

Output C as the ciphertext.

Decryption: To decrypt a ciphertext C using the private key SK = q 1, observe that

$$\displaystyle\begin{array}{rcl} C^{q_{1} } = (g^{m}h^{r})^{q_{1} } = (g^{q_{1} })^{m}\ & &{}\end{array}$$
(2.19)

To recover the message m, it suffices to compute the discrete logarithm of \(C^{q_{1}}\) to the base \(g^{q_{1}}\). Since 0 ≤ m ≤ T, this takes expected time \(O(\sqrt{T})\) using Pollard’s lambda method [9].

Homomorphic Properties: The BGN scheme is clearly additively homomorphic. Let PK = { N, G, G 1, e, g, h} be a public key. Given two ciphertexts \(C_{1} = g^{m_{1}}h^{r_{1}} \in G,C_{2} = g^{m_{2}}h^{r_{2}} \in G\) of messages m 1, m 2 ∈ { 0, 1, ⋯ , T} respectively, anyone can create a uniformly distributed encryption of m 1 + m 2(mod N) by computing the product

$$\displaystyle\begin{array}{rcl} C& =& C_{1}C_{2}h^{r}\ {}\end{array}$$
(2.20)

for a random r in {1, 2, ⋯ , N − 1}, because

$$\displaystyle{C_{1}C_{2}h^{r} = (g^{m_{1} }h^{r_{1} })(g^{m_{2} }h^{r_{2} })h^{r} = g^{m_{1}+m_{2} }h^{r_{1}+r_{2}+r}}$$

is an encryption of m 1 + m 2.

More importantly, anyone can multiply two encrypted messages once using the bilinear map. Let

$$\displaystyle{g_{1} = e(g,g)}$$

and

$$\displaystyle{h_{1} = e(g,h)}$$

then g 1 is of order N and h 1 is of order q 1. There is some (unknown) \(\alpha \in \mathbb{Z}\) such that

$$\displaystyle{h = g^{\alpha q_{2} }}$$

Suppose that we are given two ciphertexts \(C_{1} = g^{m_{1}}h^{r_{1}} \in G\) and \(C_{2} = g^{m_{2}}h^{r_{2}} \in G\). To build an encryption of the product m 1 m 2(mod N), (1) pick a random \(r \in \mathbb{Z}_{N}\), and (2) let

$$\displaystyle\begin{array}{rcl} C& =& e(C_{1},C_{2})h_{1}^{r} \in G_{ 1}\ {}\end{array}$$
(2.21)

We have

$$\displaystyle\begin{array}{rcl} C& =& e(C_{1},C_{2})h_{1}^{r} {}\\ & =& e(g^{m_{1} }h^{r_{1} },g^{m_{2} }h^{r_{2} })h_{1}^{r} {}\\ & =& e(g^{m_{1}+\alpha q_{2}r_{1} },g^{m_{2}+\alpha q_{2}r_{2} })h_{1}^{r} {}\\ & =& e(g,g)^{(m_{1}+\alpha q_{2}r_{1})(m_{2}+\alpha q_{2}r_{2})}h_{ 1}^{r} {}\\ & =& e(g,g)^{m_{1}m_{2}+\alpha q_{2}(m_{1}r_{2}+m_{2}r_{1}+\alpha q_{2}r_{1}r_{2})}h_{ 1}^{r} {}\\ & =& e(g,g)^{m_{1}m_{2} }h_{1}^{r+m_{1}r_{2}+m_{2}r_{1}+\alpha q_{2}r_{1}r_{2} }\ {}\\ \end{array}$$

where \(r + m_{1}r_{2} + m_{2}r_{1} +\alpha q_{2}r_{1}r_{2}\) is distributed uniformly in \(\mathbb{Z}_{N}\). Thus C is a uniformly distributed encryption of m 1 m 2(mod N), but in G 1 rather than G. We note that the BGN scheme is still additively homomorphic in G 1.

BGN Example: We will demonstrate the operation of the BGN scheme with a small example. First we choose two distinct prime numbers

$$\displaystyle{q_{1} = 7,q_{2} = 11}$$

and compute the product

$$\displaystyle{N = q_{1}q_{2} = 77}$$

Next we construct an elliptic curve group with order N that has an associated bilinear map e. The equation for the elliptic curve is

$$\displaystyle{y^{2} = x^{3} + x}$$

and is defined over the field \(F_{q}\) for some prime \(q = 3\bmod 4\). In this example, we set

$$\displaystyle{q = 307}$$

Therefore, the curve is supersingular with #(E(q)) = q + 1 = 308 rational points, which contains a subgroup G with the order N = 77 (=308/4).

Within the group G, we choose two random generators

$$\displaystyle{g = [182,240],u = [28,262]}$$

where these two generators have order N, and compute

$$\displaystyle{h = u^{q_{2} } = [28,262]^{11} = [99,120]}$$

where h has order q 1 = 7.

We compute the ciphertext of a message

$$\displaystyle{m = 2}$$

Take r = 5 and compute

$$\displaystyle{C = g^{m}h^{r} = [182,240]^{2} \oplus [99,120]^{5} = [256,265]}$$

To decrypt we first compute

$$\displaystyle{\hat{g} = g^{q_{1} } = [182,240]^{7} = [146,60]}$$

and

$$\displaystyle{C^{q_{1} } = [256,265]^{7} = [299,44]}$$

Now we find the discrete logarithm by iterating through all the powers of \(\hat{g} = g^{q_{1}}\) as follows:

$$\displaystyle\begin{array}{rcl} & \hat{g}^{1} = [146,60] & {}\\ & \hat{g}^{2} = [299,44] & {}\\ & \hat{g}^{3} = [272,206] & {}\\ & \hat{g}^{4} = [191,151] & {}\\ & \hat{g}^{5} = [79,171] & {}\\ & \hat{g}^{6} = [79,136] & {}\\ & \hat{g}^{7} = [191,156] & {}\\ & \hat{g}^{8} = [272,101] & {}\\ & \hat{g}^{9} = [299,263] & {}\\ & \hat{g}^{10} = [146,247]& {}\\ & \hat{g}^{11} = \infty & {}\\ \end{array}$$

Observe that \(\hat{g}^{2} = C^{q_{1}}\). Therefore, decryption of the ciphertext equals 2, which is the same as the original message.

BGN Security: The BGN encryption scheme has been proved to be semantically secure on basis of the subgroup decision problem in [2]. The subgroup decision (SD) problem is stated as follows.

Given a group G of composite order n = pq, where p, q are distinct (unknown) primes, and generators g p  ∈ G p and g ∈ G, distinguish between whether an element x is a random element of the subgroup G p or a random element of the full group G.

Gjosteen [6] has undertaken an extensive survey of such problems, which he calls subgroup membership problems. For example, the quadratic residuosity problem is a subgroup membership problem: if we let N = pq be a product of two distinct primes and define the group G to be the group of elements of \(\mathbb{Z}_{N}^{{\ast}}\) with Jacobi symbol 1, the problem is to determine whether a given element in G lies in the subgroup of squares in G.

Boneh, Goh, and Nissim [2] defined their SD problem for pairs of groups (G, G 1) of composite order N = pq for which there exists a nondegenerate bilinear map, or pairing, e: G × G → G 1. The problem is to determine whether a given element x ∈ G is in the subgroup of order p. Note that if g generates G, then e(g, x) is a challenge element for the same problem in G 1; thus if the SD problem is infeasible in G, then it is in G 1 as well.

Freeman [5] developed an abstract framework that encompasses the key properties of bilinear groups of composite order that are required to construct secure pairing-based cryptosystems and showed how to use prime-order elliptic curve groups to construct bilinear groups with the same properties. In particular, he defined a generalized version of the subgroup decision problem and give explicit constructions of bilinear groups in which the generalized subgroup decision assumption follows from the decision Diffie–Hellman assumption, the decision linear assumption, and/or related assumptions in prime-order groups.