Cryptography: Public Key Encryption
UCL Course COMP0143 Cryptocurrencies: Prerequisite Cryptography Part II
Background
Public Key Encryption is initially designed to solve the Key Distribution problem in Private Key Encryption,
where senders and receivers during the Private Key Encryption process have already shared a private key \(k\).
The key generation algorithm in Public Key Encryption splits the key into two parts:
-
Public Key \(pk\): Anyone can encrypt information using the public key \(pk\).
-
Private Key: \(sk\): Only who owns private key \(sk\) can decrypt the information.
Relationships between Public Key and Private Key
-
Private key \(sk\) is chosen uniformly at random in some space.
-
Public key \(pk\) is derived from private key \(sk\) via some function \(f\) such that \(pk := f(sk)\)
-
Public key \(pk\) must be computationally infeasible to compute private key \(sk\)
\(\implies\) the function \(f\) is a one-way function
Definition
A Public Key Encryption (PKE) scheme defined over \((\mathcal{K}, \mathcal{M}, \mathcal{C})\) is a tuple of efficient algorithms \((\text{Gen}, \text{Enc}, \text{Dec})\):
-
\(\text{Gen}(\lambda)\): Generate a public-private key pair \((pk, sk)\).
-
\(\text{Enc}(pk, m)\): Encrypt the plaintext \(m\) using \(pk\) and output the ciphertext \(c\).
-
\(\text{Dec}(sk, c)\): Decrypt the ciphertext \(c\) using \(sk\) and output the plaintext \(m\).
Correctness
\[\forall \, \lambda \in \mathbb{N}, \forall \, (pk, sk) \xleftarrow{\$} \text{Gen}(\lambda), \forall \, m \in \mathcal{M}: \text{Dec}(sk, \text{Enc}(pk, m)) = m\]IND-CPA
IND-CPA is short for Indistinguishable against Chosen-Plaintext Attacks.
\[Pr[\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CPA}}(\lambda) = 1] \leq \frac{1}{2} + negl(\lambda)\]where \(\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CPA}}(\lambda)\):
-
Roles: Challenger and Adversary. Adversary has implicit access to Encryption Oracle since the PKE scheme is public.
-
\((pk, sk) \xleftarrow{$} \text{Gen}(\lambda)\): Challenger generates \((pk, sk)\) and keeps \(sk\), then sends \(pk\) to Adversary.
-
\((m_0, m_1) \leftarrow \mathcal{A}(\lambda, pk)\): Adversary submits two distinct chosen plaintexts \((m_0, m_1)\)to Challenger.
-
\(b \xleftarrow{$} {0,1}\): Challenger selects a bit uniformly at random.
-
\(c \leftarrow Enc(pk, m_b)\): Challenger sends the challenge ciphertext \(c\) back to Adversary.
-
\(b^\prime \leftarrow \mathcal{A}(c)\): Adversary outputs his guess for the value \(b^\prime\).
-
\(\text{return} \ b == b^\prime\): If the guessed value is the selected one, return \(1\); otherwise, return \(0\).
Note: IND-CPA is the weakest requirement for Public Key Encryption.
IND-CCA
IND-CCA \(\Rightarrow\) IND-CPA but IND-CCA \(\not\Leftarrow\) IND-CPA
IND-CCA1
IND-CCA1 is short for Indistinguishable against Non-Adaptive Chosen-Ciphertext Attacks.
\[Pr[\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CCA1}}(\lambda) = 1] \leq \frac{1}{2} + negl(\lambda)\]where \(\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CCA1}}(\lambda)\):
-
Roles: Challenger and Adversary. Adversary has access to both Encryption and Decryption Oracles.
-
\((pk, sk) \xleftarrow{$} \text{Gen}(\lambda)\): Challenger generates \((pk, sk)\) and keeps \(sk\), then sends \(pk\) to Adversary.
-
\((m_0, m_1) \leftarrow \mathcal{A}^{\text{Dec}_{sk} \ (\cdot)} \ (\lambda, pk)\): Adversary submits two distinct chosen plaintexts \((m_0, m_1)\)to Challenger.
-
\(b \xleftarrow{$} {0,1}\): Challenger selects a bit uniformly at random.
-
\(c \leftarrow Enc(pk, m_b)\): Challenger sends the challenge ciphertext \(c\) back to Adversary.
-
\(b^\prime \leftarrow \mathcal{A}(c)\): Adversary outputs his guess for the value \(b^\prime\).
-
\(\text{return} \ c \notin \mathcal{Q} \land b == b^\prime\): If the guessed value is the selected one, return \(1\); otherwise, return \(0\).
Note:
-
\(\text{Dec}_{sk} \ (\cdot)\) is the Decryption Oracle,
\(\mathcal{Q}\) is all ciphertexts \(c_j\) queried by Adversary to ask for decryption,
Challenger decrypts \(c_j\) and sends \(m_j = \text{Dec}(sk, c_j)\) back to Adversary. -
Adversary only has access to the Decryption Oracle \(\text{Dec}_{sk} \ (\cdot)\) before he receives \(c\).
IND-CCA2
IND-CCA2 is short for Indistinguishable against Adaptive Chosen-Ciphertext Attacks
\[Pr[\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CCA2}}(\lambda) = 1] \leq \frac{1}{2} + negl(\lambda)\]where \(\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CCA2}}(\lambda)\):
-
Roles: Challenger and Adversary. Adversary has access to both Encryption and Decryption Oracles.
-
\((pk, sk) \xleftarrow{$} \text{Gen}(\lambda)\): Challenger generates \((pk, sk)\) and keeps \(sk\), then sends \(pk\) to Adversary.
-
\((m_0, m_1) \leftarrow \mathcal{A}^{\text{Dec}_{sk} \ (\cdot)} \ (\lambda, pk)\): Adversary submits two distinct chosen plaintexts \((m_0, m_1)\)to Challenger.
-
\(b \xleftarrow{$} {0,1}\): Challenger selects a bit uniformly at random.
-
\(c \leftarrow Enc(pk, m_b)\): Challenger sends the challenge ciphertext \(c\) back to Adversary.
-
\(b^\prime \leftarrow \mathcal{A}^{\text{Dec}_{sk} \ (\cdot)} \ (c)\): Adversary outputs his guess for the value \(b^\prime\).
-
\(\text{return} \ c \notin \mathcal{Q} \land b == b^\prime\): If the guessed value is the selected one, return \(1\); otherwise, return \(0\).
Note:
-
\(\text{Dec}_{sk} \ (\cdot)\) is the Decryption Oracle,
\(\mathcal{Q}\) is all ciphertexts \(c_j\) queried by Adversary to ask for decryption,
Challenger decrypts \(c_j\) and sends \(m_j = \text{Dec}(sk, c_j)\) back to Adversary. -
Adversary has access to the Decryption Oracle \(\text{Dec}_{sk} \ (\cdot)\) before and after he receives \(c\), such that
Adversary can adapt his decryption queries based on the challenge \(c\) he is trying to break (more powerful and realistic).
RSA Cryptosystem
Integer Factorization Problem
Given an integer \(n = pq\) that is the product of two unknown primes \(p\) and \(q\),
the Integer Factorization Problem (IFP) is defined as the problem of finding the factorization of \(n\) (finding \(p\) and \(q\)).
Note: A number \(n \in \mathbb{N}\) is called prime if it is only divisible by \(1\) and \(n\).
Time Complexity
Brute Force: \(O(2^{2\lambda} \cdot t)\), where
-
\(\lambda\) is the length of \(p\) and \(q\) in bits, and
-
\(t\) is the time for division (testing the value \(\frac{n}{x}\) where \(x\) is the searched value).
Slight Improvement: \(O(2^{\lambda} \cdot t)\), since \(p\) and \(q\) have the same length \(\lambda\),
the searched value should be limited \(x \in [2, \dots, \sqrt n]\); otherwise, the \(pq > n\).
There is currently NO known algorithm (except for Quantum Algorithm)
that can factor \(n\) in polynomial time if \(p\) and \(q\) are different large primes (computationally hard).
Extended Problem
-
It is hard to compute \(\phi(n) = (p-1)(q-1)\) if \(p\) and \(q\) are unknown, where \(\phi(n)\) is defined by Euler’s Totient Function:
\[\phi(n) = \prod_{i=1}^m p_i^{e_i-1}(p_i - 1)\] \[\phi(n) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)\] -
\(\phi(n)\) is the order of \(\mathbb{Z}_n^{*}\) since it counts the number of integers less than \(n\) that are co-prime to \(n\) (also elements in \(\mathbb{Z}_n^{*}\)).
-
Euler’s Theorem: If \(n \in \mathbb{N}\), \(a \in [0, \dots, n - 1]\), and \(gcd(a, a) = 1\), then
\[a^{\phi(n)} \equiv 1 \, (\text{mod} \, n)\]This theorem can be used to get the inverse of \(a\):
\[a^{-1} \equiv a^{\phi(n) - 1} \, (\text{mod} \, n)\]
Text-book RSA Encryption
Key Generation
-
Pick two large random primes \(p\) and \(q\) of length \(\lambda\).
-
Compute \(n = pq\) and \(\phi(n) = (p-1)(q-1)\).
-
Pick a random integer \(e \in [1, \dots, \phi(n)-1]\) which is co-prime to \(\phi(n)\) \(\implies gcd(e, \phi(n)) = 1\).
-
Compute the \(d\) which is the inverse of \(e\) such that \(ed \equiv 1 \, (\text{mod} \, \phi(n))\).
-
The private key \(sk = (d, n)\) and public key \(pk = (e, n)\).
Encryption
\[c \equiv m^e \, (\text{mod} \, n)\]Decryption
\[m \equiv c^d \, (\text{mod} \, n)\]Correctness
According to Euler’s Theorem,
\[a^{\phi(n)} \equiv 1 \, (\text{mod} \, n)\]Therefore,
\[m \equiv c^d \equiv {(m^e)}^d \equiv m^{ed} \equiv m^{1+k\phi(n)} \equiv m \Big({(m^{\phi(n)})}^k \Big) \equiv m(1^k) \equiv m \, (\text{mod} \, n)\]Hardness
\[Pr[\text{Game}_{\mathcal{A}, \text{Gen}}^{\text{RSA}}(\lambda) = 1] \leq negl(\lambda)\]where \(\text{Game}_{\mathcal{A}, \text{Gen}}^{\text{RSA}}(\lambda)\):
-
Roles: Challenger and Adversary.
-
\(\Big((e, n), (d, n) \Big) \xleftarrow{$} \text{Gen}\): Challenger generates \(\Big((e, n), (d, n)\Big)\) and keeps \((d, n)\), then sends \((e, n)\) to Adversary.
-
\(c \xleftarrow{$} \mathbb{Z}_n^{*}\): Challenger sends a random ciphertext \(c\) to Adversary.
-
\(m \leftarrow \mathcal{A}(d, n, c)\): Adversary outputs his plaintext and sends back to Challenger.
-
\(\text{return} \ m^e \equiv c \, (\text{mod} \, n)\): If the output from Adversary meets the requirement, return \(1\); otherwise, return \(0\).
RSA Problem \(\leq\) Integer Factorization Problem
Let \(\mathcal{B}\) be a PPT adversary which breaks the hardness of Integer Factorization Problem.
According to the assumption of \(\mathcal{B}\)’s capability, \(\mathcal{B}\) can get \(p\) and \(q\),
which means that \(\mathcal{B}\) can construct a PPT adversary \(\mathcal{A}\) who can get \((p-1)\) and \((q-1)\) from \(\mathcal{B}\),
which means that \(\mathcal{A}\) can output \(\phi(n)\),
which means that \(\mathcal{A}\) can output \(d\) since \(ed \equiv 1 \, (\text{mod} \, \phi(n))\),
which means that \(\mathcal{A}\) can output \(m\) that meets \( m^e \equiv c \, (\text{mod} \, n)\) to break RSA.
Therefore, \(\mathcal{A}\) is a PPT adversary which breaks the hardness of RSA Problem.
Not Have IND-CPA Security
Text-book RSA does not have IND-CPA security since it is deterministic
where Deterministic means that the same input will always get the same output.
Since Adversary \(\mathcal{A}\) in \(\text{Game}_{\mathcal{A}, \text{PKE}}^{\text{IND-CPA}}(\lambda)\) gets \(pk\) and has access to Encryption Oracle,
Adversary can always know \(c_0\) to \(m_0\) and \(c_1\) to \(m_1\), and then always output the correct \(b’ = b\).
Message Encoding for RSA Cryptosystem
Previously, the message for encryption should meet the requirement: \(m \in \mathbb{Z}_n^{*}\).
However, messages are typically given as binary strings having arbitrary length \(M \in \{0, 1\}^{*}\).
Let \(l := |n|\) be the length of \(n\) in bits, and binary string \(M\) should meet \(|M| < |n| = l\)
Therefore, binary string \(M\) with length \(l-1\) must be an element of \(\mathbb{Z}_n\) (\(M < n\)).
-
If \(M \in \mathbb{Z}_n^{*}\), the proof of correctness can be done directly as above.
-
If \(M \in \mathbb{Z}_n \setminus \mathbb{Z}_n^{*}\), which means \(gcd(m, n) \neq 1\)
since \(n = pq\) and \(M < n\), there will exist 3 cases to consider:
-
\(M = 0\)
\[M \equiv 0 \equiv c^d \equiv {(0^e)}^d \equiv 0^{ed} \equiv 0 \equiv M \, (\text{mod} \, n)\] -
\(gcd(M, n) = p\)
(1) According to GCD’s Definition,
\[M = kp \implies gcd(M, p) = p \implies M \equiv 0 \, (\text{mod} \, p)\](2) Since \(p\) and \(q\) are two large random primes,
\[gcd(M, q) = 1 \implies M \in \mathbb{Z}_q^*\]According to Euler’s Theorem,
\[M^{q-1} \equiv 1 \, (\text{mod} \, q)\](3) According to Chinese Remainder Theorem,
\[M \, (\text{mod} \, n) \mapsto \Big(M \, (\text{mod} \, p), \ M \, (\text{mod} \, q) \Big)\](4) Consider \(\text{mod} \, p\) and \(\text{mod} \, q\) separately
\[M \equiv 0 \equiv c^d \equiv {(0^e)}^d \equiv 0^{ed} \equiv 0 \equiv M \, (\text{mod} \, p)\] \[M \equiv c^d \equiv {(M^e)}^d \equiv M^{ed} \equiv M^{1+k(p-1)(q-1)} \equiv M^{1+k^\prime(q-1)} \equiv M \Big({(M^{q-1})}^{k^\prime} \Big) \equiv M(1^{k^\prime}) \equiv M \, (\text{mod} \, q)\]Therefore,
\[M \equiv c^d \equiv M \, (\text{mod} \, n)\] -
\(gcd(M, n) = q\) is similar.
-
Padded RSA Encryption
To solve the deterministic problem in Text-book RSA Encryption,
Let \(\forall \ \lambda: l(\lambda) \leq 2\lambda - 2\), and \(\mathcal{M} = \{0,1\}^{l(\lambda)}\)
-
\(\text{Gen}(\lambda)\): return \(sk = (d, n)\) and \(pk = (e, n)\) where \(|n| = 2\lambda\)
-
\(Enc_{{e,n}}(m): c \leftarrow (r \, \parallel \, m)^e \ mod \ n\) where \(r \xleftarrow{$} \{0,1\}^{|n| - l(\lambda) - 1}\)
-
\(Dec_{{d,n}}(c): m \leftarrow \lfloor c^d \ mod \ n \rfloor _{l(\lambda)}\)
which means returning the \(l(\lambda)\) lower bits of \(m^\prime = c^d \ mod \ n\)
Have IND-CPA Security
\(l(\lambda)\) cannot be too large since the length of \(r\) will relatively too small
such that a brute force attack over \(r\) may be possible.
For example, \(l(\lambda) \geq 2\lambda - O(log\lambda)\), the required trials for a CPA attack is \(2^{O(log\lambda)}\),
therefore, for \(l(\lambda) = O(log\lambda)\), padded RSA encryption is IND-CPA secure.
Have IND-CCA2 Security ???
-
RSA Encryption with PKCS #1 v1.5 is susceptible to Bleichenbacher’s Padding Oracle Attack (Not have IND-CCA2 Security).
-
RSA Encryption with OAEP has IND-CCA2 security if the based Hash Functions are Random Oracles.
ElGamal Cryptosystem
Discrete Logarithm Problem
Given a cyclic group \(\mathbb{G} = \langle g \rangle \) of order \(q\) with generator \(g\), and some element \(h \in \mathbb{G}\),
the Discrete Logarithm Problem (DLP) is defined as the problem of finding \(x \in \mathbb{Z}_q\) such that \(h = g^x\).
Note:
-
A group \(\mathbb{G}\) is called cyclic if it is generated by a single element \(g \in \mathbb{G}\).
-
The order \(q\) is the number of elements in \(\mathbb{G}\): \(q = |\mathbb{G}|\).
-
The element \(g\) is the generator of \(\mathbb{G}\) such that \(\mathbb{G} = \{\, g^0, g^1, \dots, g^{q-1} \,\}\)
-
Any element \(h \in \mathbb{G}\) can be represented as \(h = g^x\) for some \(x \in \mathbb{Z}_q\).
Time Complexity
Brute Force: \(O(2^\lambda)\) where is the length of \(q\) in bits.
There is currently NO known algorithm (except for Quantum Algorithm)
that can compute \(x\) in polynomial time if the order \(q\) is a large prime (computationally hard).
ElGamal Encryption
Key Generation
-
Construct a cyclic group \(\mathbb{G} = \langle g \rangle \) of prime order \(q\).
-
Pick a random integer \(x \in \mathbb{Z}_q\).
-
Compute \(h = g^x\).
-
The private key \(sk = x\) and public key \(pk = h\).
Encryption
-
Encode the message \(M\) into an element \(m \in \mathbb{Z}_q\).
-
Pick a random integer \(r \in \mathbb{Z}_q\).
-
Compute the ciphertext \(c\) using public key \(h\):
\[c = (\, c_1, c_2 \,) = (\, g^r, h^r \cdot m \,)\]
Decryption
Compute the plaintext \(m\) using private key \(x\)
\[m = c_2 \cdot c_1^{-x}\]Correctness
\[m = c_2 \cdot c_1^{-x} = (h^r \cdot m) \cdot (g^r)^{-x} = (g^{xr} \cdot m) \cdot g^{-xr} = (g^{xr} \cdot g^{-xr}) \cdot m = m\]Hardness
Hardness of Computational Diffie-Hellman Problem
\[Pr[\text{Game}_{\mathcal{A}, \text{Gen}}^{\text{CDH}}(\lambda) = 1] \leq negl(\lambda)\]where \(\text{Game}_{\mathcal{A}, \text{Gen}}^{\text{CDH}}(\lambda)\):
-
Roles: Challenger and Adversary.
-
\( (\mathbb{G}, g, q) \xleftarrow{$} \text{Gen}\): Challenger constructs a cyclic group \(\mathbb{G} = \langle g \rangle \) of prime order \(q\) (parameters of \(\mathbb{G}\) are public).
-
\((x_1, x_2) \xleftarrow{$} \mathbb{Z}_q\): Challenger picks two random integers \((x_1, x_2)\) and sends \((g^{x_1}, g^{x_2})\) to Adversary.
-
\(h \leftarrow \mathcal{A}(\mathbb{G}, g, q, g^{x_1}, g^{x_2})\): Adversary outputs his result and sends back to Challenger.
-
\(\text{return} \ h = g^{x_1 x_2}\): If the output from Adversary meets the requirement, return \(1\); otherwise, return \(0\).
Computational Diffie-Hellman Problem \(\leq\) Discrete Logarithm Problem
Let \(\mathcal{B}\) be a PPT adversary which breaks the hardness of Discrete Logarithm Problem.
According to the assumption of \(\mathcal{B}\)’s capability, \(\mathcal{B}\) can get \(x_1\) and/or \(x_2\),
which means \(\mathcal{B}\) can construct a PPT adversary \(\mathcal{A}\) who can compute \(h = g^{x_1 x_2} = {(g^{x_1})}^{x_2} = {(g^{x_2})}^{x_1}\),
Therefore, \(\mathcal{A}\) is a PPT adversary which breaks the hardness of Computational Diffie-Hellman Problem.
Hardness of Decisional Diffie-Hellman Problem
\[| Pr[\mathcal{D}(\mathbb{G}, g, q, g^{x_1}, g^{x_2}, g^{x_1 x_2}) = 1] - Pr[\mathcal{D}(\mathbb{G}, g, q, g^{x_1}, g^{x_2}, g^y) = 1] | \leq negl(\lambda)\]where
-
Roles: Challenger and Adversary.
-
\( (\mathbb{G}, g, q) \xleftarrow{$} \text{Gen}\): Challenger constructs a cyclic group \(\mathbb{G} = \langle g \rangle \) of prime order \(q\) (parameters of \(\mathbb{G}\) are public).
-
\((x_1, x_2) \xleftarrow{$} \mathbb{Z}_q\): Challenger picks two random integers \((x_1, x_2)\) and sends \((g^{x_1}, g^{x_2})\) to Adversary.
-
\(y \xleftarrow{$} \mathbb{Z}_q\): Challenger picks an extra random integer \(y\) and randomly sends \(g^{x_1 x_2}\) or \(g^y\) to Adversary.
-
Adversary needs to distinguish which value that Challenger sends: \(g^{x_1 x_2}\) or \(g^y\) ?
Decisional Diffie-Hellman Problem \(\leq\) Computational Diffie-Hellman Problem
Let \(\mathcal{B}\) be a PPT adversary which breaks the hardness of Computational Diffie-Hellman Problem.
According to the assumption of \(\mathcal{B}\)’s capability, \(\mathcal{B}\) can compute \(g^{x_1 x_2}\),
which means \(\mathcal{B}\) can construct a PPT adversary \(\mathcal{A}\) who can distinguish between \(g^{x_1 x_2}\) and \(g^y\),
Therefore, \(\mathcal{A}\) is a PPT adversary which breaks the hardness of Decisional Diffie-Hellman Problem.
Have IND-CPA Security
By Contradiction and Reduction
Assume ElGamal Encryption does not have IND-CPA Security
when the Decisional Diffie-Hellman Problem is computationally hard.
Let \(\mathcal{A}\) be a PPT adversary which breaks the IND-CPA Security of ElGamal Encryption.
Let \(\mathcal{B}\) be a PPT adversary against Decisional Diffie-Hellman Problem that simulates ElGamal Encryption for \(\mathcal{A}\).
-
\(\mathcal{A}\) receives public key \(h = g^{x_1}\) from \(\mathcal{B}\).
-
\(\mathcal{A}\) submits two distinct chosen plaintexts \((m_0, m_1)\) to \(\mathcal{B}\).
-
\(\mathcal{A}\) receives \( c_b = (g^{x_2}, h^{x_2} \cdot m_b) \) from \(\mathcal{B}\) (here takes \(x_2\) as randomness \(r \in \mathbb{Z}_q\)).
-
According to the assumption of \(\mathcal{A}\)’s capability,
\(\mathcal{A}\) can return the correct \(b^\prime = b\),
which means \(\mathcal{B}\) can know whether \(b^\prime\) is correct or not (distinguish between \(c_b\) and \(c_{b^\prime}\)),
which means \(\mathcal{B}\) can distinguish between \(c_2 = h^{x_2} \cdot m_b\) and \(c^\prime_2 = g^y \cdot m_b\), and \(c^\prime_2\) is uniformly distributed in \(\mathbb{G}\).
which means \(\mathcal{B}\) can distinguish between \(h^{x_2} = g^{x_1 x_2}\) and \(g^y\) to break DDH Problem,
such that ElGamal Encryption has IND-CPA Security when DDH Problem is computationally hard.
Another Proof
-
\(Pr[\mathcal{D}(\mathbb{G}, g, q, g^{x_1}, g^{x_2}, g^{x_1 x_2}) = 1] = Pr[\text{Game}_{\mathcal{A}, \text{ElGamal}}^{\text{IND-CPA}}(\lambda) = 1]\) by construction.
-
\(Pr[\mathcal{D}(\mathbb{G}, g, q, g^{x_1}, g^{x_2}, g^y) = 1] = Pr[b^\prime = b] = \frac{1}{2}\) since \(c_2\) is uniformly distributed in \(\mathbb{G}\).
-
By the definition of DDH Problem:
\[Adv_{\mathcal{B}, \text{Gen}}^{\text{DDH}}(\lambda) = | Pr[\text{Game}_{\mathcal{A}, \text{ElGamal}}^{\text{IND-CPA}}(\lambda) = 1] - \frac{1}{2} | = Adv_{\mathcal{A}, \text{ElGamal}}^{\text{IND-CPA}}(\lambda)\] -
\(Adv_{\mathcal{A}, \text{ElGamal}}^{\text{IND-CPA}}(\lambda) = Adv_{\mathcal{B}, \text{Gen}}^{\text{DDH}}(\lambda) \leq negl(\lambda)\)
such that ElGamal Encryption has IND-CPA Security when DDH Problem is computationally hard.
Not Have IND-CCA2 Security
-
\(\mathcal{A}\) picks a random element \(r^\prime \xleftarrow{$} \mathbb{G}\) such that \(r^\prime = g^a\).
-
\(\mathcal{A}\) computes \(c_2^\prime = c_2 \cdot r^\prime = (h^r \cdot m) \cdot r^\prime = = h^r \cdot (m \cdot r^\prime)\) after he receives \(c = (c_1, c_2)\).
-
\(\mathcal{A}\) queries \(c_2^\prime\) to Decryption Oracle and gets \(m^\prime = m \cdot r^\prime\).
-
\(\mathcal{A}\) gets \(m_b = m = m^\prime \cdot {r^\prime}^{-1}\) where \({r^\prime}^{-1} = g^{q - a}\)
Message Encoding for ElGamal Encryption
Previously, the message for encryption should meet the requirement: \(m \in \mathbb{G}\).
However, messages are typically given as binary strings having arbitrary length \(M \in \{0, 1\}^{*}\).
Let \(p = 2q + 1\) where \(p\) and \(q\) are primes with \(l := |q|\) the length of \(q\) in bits.
-
Here \(p\) is Safe Prime and \(q\) is Sophie Germain Prime (Wiki - Safe and Sophie Germian Primes)
-
Property: \(\mathbb{Z}_p^{*}\) must have a cyclic subgroup of prime order \(q\)
Let \(g := h^2 \ mod \ p \ \) where \( \ h \xleftarrow{$} \mathbb{Z}_p^{*} \setminus \{\, 1, p - 1\,\}\)
such that \(g\) is one generator of a subgroup of prime order \(q\) inside \(\mathbb{Z}_p^{*}\).
-
The order of \(\mathbb{Z}_p^{*}\): \(|\mathbb{Z}_p^{*}| = \phi(p) = p - 1 = 2q\) (via Euler’s Totient Function).
-
\(\mathbb{Z}_p^{*}\) must have two non-trivial subgroups of order \(2\) and of prime order \(q\) (via Lagrange’s Theorem).
-
The subgroup of order \(2\) has two elements: \(\{\, 1, p - 1 \, \}\).
-
The square operation in \(g := h^2 \ mod \ p \ \) where \( \ h \xleftarrow{$} \mathbb{Z}_p^{*} \setminus \{\, 1, p - 1\,\}\)
will always let \(g\) be an element in a non-trivial subgroup of prime order \(q\) and not the identity element \(e\).
Moreover, since this subgroup has prime order \(q\), this subgroup will be a cycle group,
and all its non-identity elements are generators of the subgroup of prime order \(q\),
therefore, \(g\) and \(h\) can be randomly selected from their scope.
-
The subgroup of order \(q\) with a generator \(g\) is the \(\mathbb{G}\) we need.
Let \(M \in \{0,1\}^{l-1}\) be a binary string of the message with length \(l - 1\).
Consider \(M\) as an integer \(M \in \{0, 1, \dots, q-1\}\).
Encoding
-
Compute \(y = M + 1 \in \{1, 2, \dots, q\}\).
-
Compute \(z = y^2 \ mod \ p\) which enures that \(z \in \mathbb{G}\).
-
Find that \(y \in \mathbb{Z}_p^{*} = \{1, 2, \dots, p-1\} \) due to \(p - 1 = 2q\).
-
Find that \(z\) is a quadratic residue modulo \(p\).
-
Since squaring is a two-to-one mapping in \(\mathbb{Z}_p^{*}\),
the order of subgroup formed by quadratic residues modulo \(p\)
is half the order of \(\mathbb{Z}_p^{*}\), which is \(\frac{1}{2} \cdot \phi(p) = \frac{1}{2} \cdot 2q = q\).
-
According to Lagrange’s Theorem,
the subgroup of \(\mathbb{Z}_p^{*}\) of a specific order \(q\) is unique,
therefore, the subgroup formed by quadratic residues is exactly \(\mathbb{G}\).
-
To conclude, \(z \in \mathbb{G}\) is guaranteed.
-
Decoding
-
Compute \(y = z^{\frac{1}{2}} \ mod \ p\)
-
compute \(M = y - 1\)
Hash-based ElGamal Encryption
Definition
-
\(\text{Gen}(\lambda)\)
Private key \(sk = x \xleftarrow{$} \mathbb{Z}_q\)
Public Key \(pk = h = g^x\)
return \((pk, sk) = (h, x) = (g^x, x)\)
-
\(Enc_{h}(m): c = (c_1, c_2) = (g^r, H(h^r) \oplus m)\)
where
-
Randomness \(r \xleftarrow{$} \mathbb{Z}_q\)
-
Plaintext \(m \in \mathbb{G}\)
-
Collision Resistant Hash Function \(H: \mathbb{G} \rightarrow {0,1}^{\lambda}\)
-
-
\(Dec_{x}(c): m = c_2 \oplus H(c_1^x)\)
Correctness
\[c_2 \oplus H(c_1^x) = (H(h^r) \oplus m) \oplus H(g^{rx}) = (H(g^{xr}) \oplus m) \oplus H(g^{rx}) = m \oplus (H(g^{xr}) \oplus H(g^{rx})) = m\]Efficiency
Decryption is slightly more efficient since computing \({(c_1^x)}^{-1}\) is not required.
Have IND-CPA Security
Hash-based ElGamal Encryption has IND-CPA security if
-
the CRHF \(H\) is in the Random Oracle Model (ROM), and
-
under the assumption Computational Diffie-Hellman Problem is computationally hard.