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.

Wednesday, August 05, 2015

MO - Puzzles (I)

❚ I stumbled upon a really nice MO puzzle. No, that's is not a puzzle for my dog, who is also named MO, but a puzzle taken from the well known Mathematical Olympiad, which takes places once every year.

Puzzle 1: Find all triples of integers $(a,b,c) \in \mathbb{N}^3_{> 0}$ such that $$\text{I)}\;ab-c = 2^{e_1}, \;\; \text{II)}\;ac-b = 2^{e_2}, \;\; \text{III)}\; bc-a = 2^{e_3}$$ with $(e_1,e_2,e_3) \in \mathbb{N}^3$

If you have some free hours, try it for yourself. I don't think that the proof below the fold is very nice or beautiful, and also for my taste distinguished too many cases, but it is overall not that hard to follow.

Proof 

Wednesday, July 01, 2015

D'Agapeyeff Cipher (Part 2)

❚ I don't know why, but in the last days I used my spare time to think about the good old D'Agapeyeff Cipher.

      75628 28591 62916 48164 91748 58464 74748 28483 81638 18174
      74826 26475 83828 49175 74658 37575 75936 36565 81638 17585
      75756 46282 92857 46382 75748 38165 81848 56485 64858 56382
      72628 36281 81728 16463 75828 16483 63828 58163 63630 47481
      91918 46385 84656 48565 62946 26285 91859 17491 72756 46575
      71658 36264 74818 28462 82649 18193 65626 48484 91838 57491
      81657 27483 83858 28364 62726 26562 83759 27263 82827 27283
      82858 47582 81837 28462 82837 58164 75748 58162 92000


Remark: In the first post, i wrote that the puzzle only appeared in the 1939 version of the book but meanwhile i got new information. The puzzle is still contained in the reprinted version from 1949. The first version that comes without the puzzle is the version that was published in 1952.

Note that the puzzle was not altered in any way in the 1949 reprint. This can be seen as a clue, that D'Agapeyeff still believes that the puzzle itself was correct (e.g., not printed in a erroneous way).

Monday, January 26, 2015

Efficient integer factoring knowing the inverse of p mod q

Several weeks ago, i heard a nice talk from one of my colleagues about the Coppersmith method and it application to factoring integers. It is a very powerful method and can, e.g., be applied if partial information of $p$ or $q$ is known, the factors $p$ and $q$ of $N=pq$ have a small differences or to obtain a deterministic algorithm that returns a factor if a multiple of $\varphi(N)$ is known.

The trigger for the talk was a discussion about the risk if the inverse of one factor modulo the other factor of an RSA modulus is leaked. That means knowing the following integer $I$: $$I \equiv p^{-1} \pmod{q},\;p,q \in \mathbb{P},\;N=pq$$ Since the Coppersmith method is very powerful it is actually not surprising that it could be used to accomplish this task, at least partially.

❰Coppersmith's Theorem❱ Let $0 < \beta < 1$ and $c,N \geq 1$ and $f \in \mathbb{Z}[x]$ be a monic polynomial of degree $\delta$. The set of all integer $a \in \mathbb{Z}$ with $$\gcd(f(a),N) \geq N^\beta \; \text{and} \; |a| \leq cN^{\beta^2/\delta}$$ can be computed in time $\text{poly}(c,\delta,\log N)$.

Suppose you are given $N=pq$ and $I \equiv p^{-1}\mod{q}$ and $2^{n-1} < p < q < 2^n$, that is a balanced RSA-Modulus, which counts as a secure choice in cryptography. Then you have $$I \equiv p^{-1}\mod{q} \Leftrightarrow Ip = 1 + qk, k \in \mathbb{Z}$$ which is equivalent to $Ip^2 = p + Nk$, hence we get the monic polynomial $$f(x) = x^2 - xI^{-1} \equiv 0 \pmod{N}$$ of degree $\delta = 2$ that has $p$ as a root modulo $N$. If we assume that $p < q$, it is $p \leq N^{1/2}$ and $\gcd(f(p),N) = N$, hence $\beta = 1$. So indeed we have a case where our root is $|p| < N^{\beta^2/\delta} = N^{1/2}$ and we can find it in polynomial time.

But what if we have the inverse of $q^{-1} \pmod{p}$? In that case it is $$|q| > N^{1/2} = N^{1/2+\epsilon} = N^{\epsilon}N^{1/2} = cN^{1/2}$$
If $\epsilon = c'\log n/n$, for a constant $c'$, one gets $$N^{\epsilon} = N^{c'\log n/n} \approx 2^{n\cdot c'\log n/n} = 2^{c'\log n} = n^{c'}$$ But already a non-constant but slightly increasing $c' = n$ would lead to a quasi-polynomial complexity.
To give an example, take $n = 2048$ and $c' = 1$, which leads to $\epsilon = 11/2048 \approx 0.0050537$. So the algorithm will only be successful if the larger factor is not much larger than $\sqrt{N}$.

Are there alternative Methods ?