In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
❚ 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