In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This ...
❚ In the previous post, i gave a short introduction about homomorphic encryption and presented the DGHV scheme [5] as an example. The scheme was published in 2010 and got several important updates from Coron et al. in the following papers:
[1], 2011 : The first improvement enhances the original system by reducing the size of the public key from $\mathcal{\tilde{O}}(\lambda^{10})$ to $\mathcal{\tilde{O}}(\lambda^{7})$. The idea is, to publish fewer elements that can be combined on-the-fly to reach a larger public key if necessary. To achieve this, they need the already discussed optimization to set $x_0 = pq_0$, hence they settle the system on the stronger partial approximate common divisor problem.
[2], 2012 : In this paper, they further reduce the size of the public key down to $\mathcal{\tilde{O}}(\lambda^5)$. Instead of storing the large numbers $r_i+pq_i$, they only store a public seed $\text{se}$ and a set of small $\delta_i$ values that are of size $~p$. To recover the original public key, the seed $\text{se}$ is fed into the PRNG and it is $x_i = \text{PRNG}_i(\text{se}) - \delta_i$. The published $\delta_i$ are chosen that way that $$x_i = \text{PRNG}_i(\text{se}) - \delta_i \equiv r_i\pmod{q}, r_i\;\text{small}$$ The $\delta_i$ are now of the same bitsize as $p$ which is much smaller than the $x_i$ values, that were stored previously. Additionally, the apply the concept of modulus switching to the DGHV scheme. Modulus switching is a technique to reduce the noise level of a ciphertext. It does not allow infinitely many homomorphic operations, but reduces the noise grow rate from exponentially to linear (i.e. a leveled scheme), which is huge.
[3], 2013 : In this paper, the authors enhance the performance of the DGHV scheme, by converting it to a batch scheme, i.e., a scheme which allows to simultaneously process a vector of plaintexts bits. Just view this technique as some kind of parallel execution. In a simplified form, their idea is not to use a single prime $p$ as their secret key, but to use several such primes $p_0,p_1,...,p_{l-1}$. Hence their public key consists not of integers $x_i = r_i+q_ip$ but $x_i = r_i+q_i\prod^{l-1}_{j=0} p_j$. Each $p_j$ is responsible for another plaintext bit, and the ciphertext is then $$c= \text{CRT}_{p_0,...,p_{l-1}}(2r_0+m_0,...,2r_{l-1}+m_{r-1}) + q\prod^{l-1}_{j=0} p_j$$ (CRT = Chinese Remainder Theorem). Each bit can be recovered individually by computing $c$ mod $p_j$.
[4], 2014 : In this paper, the authors apply the scale-invariant property to the DGHV scheme. This technique allows get linear noise grow rate but without modulus switching. The key trick is, given a ciphertext $c$, that the message is not anymore encoded in the least significant bit of $c\;\text{mod}\;p$ but in the most significant bit of $c\;\text{mod}\;p$. A ciphertext $c$ has the form $$\text{TYPE-1:}\;\;c = r + (m+2r')\frac{p-1}{2}+qp^2$$ After multiplication of two ciphertexts $c_1$ and $c_2$ one gets a ciphertext of the form $$\text{TYPE-2:}\;\;2c_1c_2 = r'' + m_1m_2\frac{p^2-1}{2}+q'p^2$$. Then they show how publicly convert a TYPE-2 ciphertext back to TYPE-1.
One drawback of the DGHV scheme and its variants is that the public key size is still too big. But if the number of elements in the public key of the DGHV scheme gets too small, one could build all possible subsets sums. Probably only one will be close to a given ciphertext value. Based on the fact that the added noise is even, one could deduce the parity of the message, hence break the protocol.
Below i propose an idea, which allows only 4 elements in the public key. I do not state that the scheme is secure, it might be obviously insecure, but it is perhaps another tool for FHE that has been overlooked so far.
If you have a RSA modulus $N=pq$, then there exists exactly two fixpoints $\zeta_1$ and $\zeta_2$ greater than one, such that $$\zeta^e_i \equiv \zeta_i \pmod{N}, \;\text{for all}\;e>0,1\leq i \leq 2$$. These are the integers $$\zeta_1 = p(p^{-1}\pmod{q}) = pI_p$$ and $$\zeta_2 = q(q^{-1}\pmod{p}) = qI_q$$. These are not the usual fixpoints regarding a RSA encryption, which are all the points $M$, given the fixed public exponent $e$, such that $M^e \equiv M\pmod{N}$. Here, we only pick the subset of the strong fixpoints, which are fixpoints regarding every integer $e >0$.
Assume the integer $T \equiv \zeta_1A + qB \pmod{N}$ for a random integer $A,B \in \mathbb{Z}^*_N$, then $T$ does not give away any information about the factorization of $N$. The reason is, that any element of $\mathbb{Z}^*_N$ could be written in the form $pA'+qB'$. Observe, that if you have two integers $T_1=\zeta_1A_1+qB_1$ and $T_2=\zeta_1A_2+qB_2$, then
\begin{align*}
T_1T_2 & = \zeta_1^2A_1A_2 + \zeta_1A_1qB_2 + \zeta_1A_2qB_1 + q^2B_1B_2 \\
T_1T_2 & \equiv \zeta_1A_1A_2 + q^2B_1B_2 \pmod{N}\\
T_1T_2 & \equiv \zeta_1A' + qB' \pmod{N}\\
\end{align*} due to $\zeta_1^2 \equiv \zeta_1$ and $\zeta_1q \equiv 0$. So integers of that form could be multiplied or added and still keep their form, because both summands are ideals in $\mathbb{Z}^*_N$.
If the ciphertext of a message $m$ is $$C \equiv \zeta_1m + qB\pmod{N},\;B\in\mathbb{Z}^*_N$$, homomorphic operations could be executed simply by multiplication or addition of ciphertexts. Since $\zeta_1 \equiv 1\pmod{q}$, decryption is simply $$C \pmod{q} = m$$
The addition of some noise is the first step to semantic security. Hence we change the ciphertext to $$C \equiv \zeta_1(m+2k) + qB\pmod{N},\;B\in\mathbb{Z}^*_N$$, for some suitable sized integer $k$. Decryption then changes to $$(C \pmod{q})\pmod{2} = m$$, which reduces the plaintext space to $\{0,1\}$.
The problem is, how to encrypt $m$ without to leak the factorization of $N$? Publishing $\zeta_i$ or $p,q$ is obviously not a good idea.
One solution could be to publish some "helper" elements, which could be used to encrypt the message. These helper elements could be for example an encryption of $0$ or $1$.
$\text{Keygen}(\lambda):$ $p \leftarrow \mathbb{P}(\lambda-\text{bit})$, $q \leftarrow \mathbb{P}(\lambda-\text{bit})$. Then compute $\zeta_1 = p(p^{-1}\pmod{q}$ and $\zeta_2 = q(q^{-1}\pmod{p}$ as well as the random integers $k_i,r_i \leftarrow [-2^\rho,2^\rho]$, $1\leq i \leq 3$. Then the public key is
$$\text{PK} = (N=pq, 2\zeta_1k_1+qr_1, 2\zeta_1k_2+qr_2,\zeta_1(1+2k_3)+qr_3 ) = (N,E_1,E_2,E_3)$$, which contains $N$, two encryptions of $0$ and one encryption of $1$.
Encryption is then a linear combination of the following terms:
$\text{Enc}(m\in\{0,1\},\text{PK}): mE_3+h_1E_1+h_2E_2\pmod{N}$, with $h_i \leftarrow [-2^\rho,2^\rho]$, which is equal to
\begin{align*}
& \zeta_1(m+2(mk_3+k_1h_1+k_2h_2))+q(mr_3+h_1r_1+h_2r_2)\pmod{N}\\
& \equiv \zeta_1(m+2K)+qR\pmod{N}\\
& = c
\end{align*}
$\text{Dec}(c,\text{SK}) = (c\pmod{q})\pmod{2}$
The noise increases exponentially, but perhaps the same (or similar) optimizations as for the DGHV scheme could be applied here.
[1] Coron, Jean-Sébastien; Mandal, Avradip; Naccache, David; Tibouchi, Mehdi. Fully Homomorphic Encryption over the Integers with Shorter Public Keys. CRYPTO 2011 (Springer).
[2] Coron, Jean-Sébastien; Naccache, David; Tibouchi, Mehdi. Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. EUROCRYPT 2012 (Springer).
[3] Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi. Batch Fully Homomorphic Encryption over the Integers. EUROCRYPT 2013 (Springer).
[4] Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi. Scale-Invariant Fully Homomorphic Encryption over the Integers. PKC 2014 (Springer).
[5] Marten, van Dijk; Gentry, Craig; Halevi, Shai; Vinod, Vaikuntanathan. Fully Homomorphic Encryption over the Integers. EUROCRYPT 2010 (Springer).
[1], 2011 : The first improvement enhances the original system by reducing the size of the public key from $\mathcal{\tilde{O}}(\lambda^{10})$ to $\mathcal{\tilde{O}}(\lambda^{7})$. The idea is, to publish fewer elements that can be combined on-the-fly to reach a larger public key if necessary. To achieve this, they need the already discussed optimization to set $x_0 = pq_0$, hence they settle the system on the stronger partial approximate common divisor problem.
[2], 2012 : In this paper, they further reduce the size of the public key down to $\mathcal{\tilde{O}}(\lambda^5)$. Instead of storing the large numbers $r_i+pq_i$, they only store a public seed $\text{se}$ and a set of small $\delta_i$ values that are of size $~p$. To recover the original public key, the seed $\text{se}$ is fed into the PRNG and it is $x_i = \text{PRNG}_i(\text{se}) - \delta_i$. The published $\delta_i$ are chosen that way that $$x_i = \text{PRNG}_i(\text{se}) - \delta_i \equiv r_i\pmod{q}, r_i\;\text{small}$$ The $\delta_i$ are now of the same bitsize as $p$ which is much smaller than the $x_i$ values, that were stored previously. Additionally, the apply the concept of modulus switching to the DGHV scheme. Modulus switching is a technique to reduce the noise level of a ciphertext. It does not allow infinitely many homomorphic operations, but reduces the noise grow rate from exponentially to linear (i.e. a leveled scheme), which is huge.
[3], 2013 : In this paper, the authors enhance the performance of the DGHV scheme, by converting it to a batch scheme, i.e., a scheme which allows to simultaneously process a vector of plaintexts bits. Just view this technique as some kind of parallel execution. In a simplified form, their idea is not to use a single prime $p$ as their secret key, but to use several such primes $p_0,p_1,...,p_{l-1}$. Hence their public key consists not of integers $x_i = r_i+q_ip$ but $x_i = r_i+q_i\prod^{l-1}_{j=0} p_j$. Each $p_j$ is responsible for another plaintext bit, and the ciphertext is then $$c= \text{CRT}_{p_0,...,p_{l-1}}(2r_0+m_0,...,2r_{l-1}+m_{r-1}) + q\prod^{l-1}_{j=0} p_j$$ (CRT = Chinese Remainder Theorem). Each bit can be recovered individually by computing $c$ mod $p_j$.
[4], 2014 : In this paper, the authors apply the scale-invariant property to the DGHV scheme. This technique allows get linear noise grow rate but without modulus switching. The key trick is, given a ciphertext $c$, that the message is not anymore encoded in the least significant bit of $c\;\text{mod}\;p$ but in the most significant bit of $c\;\text{mod}\;p$. A ciphertext $c$ has the form $$\text{TYPE-1:}\;\;c = r + (m+2r')\frac{p-1}{2}+qp^2$$ After multiplication of two ciphertexts $c_1$ and $c_2$ one gets a ciphertext of the form $$\text{TYPE-2:}\;\;2c_1c_2 = r'' + m_1m_2\frac{p^2-1}{2}+q'p^2$$. Then they show how publicly convert a TYPE-2 ciphertext back to TYPE-1.
Below the fold, i show how to use fixpoints of a RSA modul for homomorphic encryption.
# Fixpoint-based homomorphic encryption #
One drawback of the DGHV scheme and its variants is that the public key size is still too big. But if the number of elements in the public key of the DGHV scheme gets too small, one could build all possible subsets sums. Probably only one will be close to a given ciphertext value. Based on the fact that the added noise is even, one could deduce the parity of the message, hence break the protocol.
Below i propose an idea, which allows only 4 elements in the public key. I do not state that the scheme is secure, it might be obviously insecure, but it is perhaps another tool for FHE that has been overlooked so far.
If you have a RSA modulus $N=pq$, then there exists exactly two fixpoints $\zeta_1$ and $\zeta_2$ greater than one, such that $$\zeta^e_i \equiv \zeta_i \pmod{N}, \;\text{for all}\;e>0,1\leq i \leq 2$$. These are the integers $$\zeta_1 = p(p^{-1}\pmod{q}) = pI_p$$ and $$\zeta_2 = q(q^{-1}\pmod{p}) = qI_q$$. These are not the usual fixpoints regarding a RSA encryption, which are all the points $M$, given the fixed public exponent $e$, such that $M^e \equiv M\pmod{N}$. Here, we only pick the subset of the strong fixpoints, which are fixpoints regarding every integer $e >0$.
Assume the integer $T \equiv \zeta_1A + qB \pmod{N}$ for a random integer $A,B \in \mathbb{Z}^*_N$, then $T$ does not give away any information about the factorization of $N$. The reason is, that any element of $\mathbb{Z}^*_N$ could be written in the form $pA'+qB'$. Observe, that if you have two integers $T_1=\zeta_1A_1+qB_1$ and $T_2=\zeta_1A_2+qB_2$, then
\begin{align*}
T_1T_2 & = \zeta_1^2A_1A_2 + \zeta_1A_1qB_2 + \zeta_1A_2qB_1 + q^2B_1B_2 \\
T_1T_2 & \equiv \zeta_1A_1A_2 + q^2B_1B_2 \pmod{N}\\
T_1T_2 & \equiv \zeta_1A' + qB' \pmod{N}\\
\end{align*} due to $\zeta_1^2 \equiv \zeta_1$ and $\zeta_1q \equiv 0$. So integers of that form could be multiplied or added and still keep their form, because both summands are ideals in $\mathbb{Z}^*_N$.
If the ciphertext of a message $m$ is $$C \equiv \zeta_1m + qB\pmod{N},\;B\in\mathbb{Z}^*_N$$, homomorphic operations could be executed simply by multiplication or addition of ciphertexts. Since $\zeta_1 \equiv 1\pmod{q}$, decryption is simply $$C \pmod{q} = m$$
The addition of some noise is the first step to semantic security. Hence we change the ciphertext to $$C \equiv \zeta_1(m+2k) + qB\pmod{N},\;B\in\mathbb{Z}^*_N$$, for some suitable sized integer $k$. Decryption then changes to $$(C \pmod{q})\pmod{2} = m$$, which reduces the plaintext space to $\{0,1\}$.
The problem is, how to encrypt $m$ without to leak the factorization of $N$? Publishing $\zeta_i$ or $p,q$ is obviously not a good idea.
One solution could be to publish some "helper" elements, which could be used to encrypt the message. These helper elements could be for example an encryption of $0$ or $1$.
$\text{Keygen}(\lambda):$ $p \leftarrow \mathbb{P}(\lambda-\text{bit})$, $q \leftarrow \mathbb{P}(\lambda-\text{bit})$. Then compute $\zeta_1 = p(p^{-1}\pmod{q}$ and $\zeta_2 = q(q^{-1}\pmod{p}$ as well as the random integers $k_i,r_i \leftarrow [-2^\rho,2^\rho]$, $1\leq i \leq 3$. Then the public key is
$$\text{PK} = (N=pq, 2\zeta_1k_1+qr_1, 2\zeta_1k_2+qr_2,\zeta_1(1+2k_3)+qr_3 ) = (N,E_1,E_2,E_3)$$, which contains $N$, two encryptions of $0$ and one encryption of $1$.
Encryption is then a linear combination of the following terms:
$\text{Enc}(m\in\{0,1\},\text{PK}): mE_3+h_1E_1+h_2E_2\pmod{N}$, with $h_i \leftarrow [-2^\rho,2^\rho]$, which is equal to
\begin{align*}
& \zeta_1(m+2(mk_3+k_1h_1+k_2h_2))+q(mr_3+h_1r_1+h_2r_2)\pmod{N}\\
& \equiv \zeta_1(m+2K)+qR\pmod{N}\\
& = c
\end{align*}
$\text{Dec}(c,\text{SK}) = (c\pmod{q})\pmod{2}$
The noise increases exponentially, but perhaps the same (or similar) optimizations as for the DGHV scheme could be applied here.
[1] Coron, Jean-Sébastien; Mandal, Avradip; Naccache, David; Tibouchi, Mehdi. Fully Homomorphic Encryption over the Integers with Shorter Public Keys. CRYPTO 2011 (Springer).
[2] Coron, Jean-Sébastien; Naccache, David; Tibouchi, Mehdi. Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. EUROCRYPT 2012 (Springer).
[3] Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi. Batch Fully Homomorphic Encryption over the Integers. EUROCRYPT 2013 (Springer).
[4] Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi. Scale-Invariant Fully Homomorphic Encryption over the Integers. PKC 2014 (Springer).
[5] Marten, van Dijk; Gentry, Craig; Halevi, Shai; Vinod, Vaikuntanathan. Fully Homomorphic Encryption over the Integers. EUROCRYPT 2010 (Springer).
Comments
Post a Comment