Showing posts with label Homomorphic Encryption. Show all posts
Showing posts with label Homomorphic Encryption. Show all posts

Wednesday, January 13, 2016

Homomorphic encryption using Ring Fixpoints

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.

Below the fold, i show how to use fixpoints of a RSA modul for homomorphic encryption.

Tuesday, December 22, 2015

Homomorphic encryption and the key recovery problem

1 :: What is homomorphic encryption

Homomorphic encryption was for many years the holy grail in cryptography after it was introduced by Rivest, Adleman and Dertouzos [5] in the year 1978, shortly after the first two authors together with A. Shamir published the famous RSA scheme. The idea is simple and its usefulness is obvious: Find an encryption system, that allows to add and multiply ciphertexts, such that the executed operations on the ciphertexts transfer to the plaintexts.

Simplified-Example. Input $m_1 = 4$, $m_2 = 9$ and $m_3 =5$. Then encrypt these three values using a public key PK
\begin{align*}
 \text{Enc}(m_1,PK) & = \text{Enc}(4,PK) = 11 = c_1\\
 \text{Enc}(m_2,PK) & = \text{Enc}(9,PK) = 21 = c_2\\
 \text{Enc}(m_3,PK) & = \text{Enc}(5,PK) = 13 = c_3 \\
\end{align*} Then you compute $$ (c_1 + c_2)*c_3 = (11+21)*13 = 416 = C $$
Next, you decrypt the result $C$ using the secret key SK, which leads magically to $$\text{Dec}(C,SK) = \text{Dec}(416,SK) = 65 = (4+9)*5 = (m_1+m_2)*m_3$$
All operations you do on the ciphertexts are executed in the same manner on the plaintexts, despite they are not directly accessible.

For many years, cryptographers tried to find functions $\text{Enc}$ and $\text{Dec}$ that have this property. In 2009, the theoretically search came to an end when Craig Gentry published [1] the construction of the first working fully homomorphically encryption scheme. The bad news was, that the scheme was not efficient at all. The good news is, that history shows, that after a first new scheme is published, the research community is mostly able to increase the efficiency to a practical degree. And indeed, the efficiency of the new schemes increased but the search for a system that can handle realworld problems is still ongoing.