A New Hope

There is new hope, new hope for a feasible algorithm that survives Quantum Computer attacks and will give us secure cryptographic key agreements in the future. It is based on Ring-LWE, where LWE is the abbreviation for Learning With Errors and Ring simply means, that you are working over some ring structure. Roughly you can put LWE in the corner of lattice based cryptography, which is one of the contestants for post-quantum cryptography. The other contestants are multivariate equations and coding based cryptography (i.e. McEliece and Niederreiter). In the meantime, one major application of LWE is also fully homomorphic encryption [4].

The underlying scheme for the $\text{NewHope}$ algorithm was proposed by Jintai Ding, Xiang Xie and Xiaodong Lin [1] in 2012, then got improved by Peikert in 2014 [2]. Joppe W. Bos, Craig Costello, Michael Naehrig and Douglas Stebila [3] presented an implementation in 2015. The next major improvement by Erdem Alkim, Léo Ducas, Thomas Pöppelmann and Peter Schwabe [4] finally led to the $\text{NewHope}$ algorithm.


Let me first describe Ring-LWE in a short, rather informal manner. Assume you have a system of equations, with unknowns $s_0,s_1,\ldots,s_{n-1}$.
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & = b_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & = b_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & = b_{m-1} \\
\end{align*} where usually $m > n$. Given this system of equations, pick $n$ equations and solve for $s_i$, which could be done using the folklore Gaussian elimination algorithm. For LWE, this system of equation is slightly changed. Instead of given a system of equations as above, you have:
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & \approx b_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & \approx b_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & \approx b_{m-1} \\
\end{align*} You only know the approximate value of each equation. To be a little bit more precise, we can write:
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & = b_0 + e_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & = b_1 + e_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & = b_{m-1} + e_{m-1} \\
\end{align*} where the $e_i$ are the small error terms that are sampled from a certain distribution. Solving this system of equations (of course with unknown $e_i$) is roughly speaking the Learning with Error problem. If you work over a ring, e.g. $\mathbb{Z}_q[x]/(f(x))$ you get Ring-LWE (some details are missing here, but this should illustrate the concept). The believe in its hardness stems from the fact Regev [6] proved that the LWE problem is as hard as to solve several worst-case lattice problems, which again are known to resist quantum computer attacks.

The question is: How can this be turned into key exchange protocol?

Using the ABC-Conjecture in Cryptography

The ABC-Conjecture is a very famous conjecture in Number Theory which is perhaps not a conjecture anymore if it the proof of Shinichi Mochizuki will turn out to be correct. I can not say anything useful about proving this conjecture, but i thought about its application for a while. Let me state the stronger version of the conjecture due to Baker [1];

ABC-Conjecture (strong, explicit version)

Given co-prime integers $a,b,c$ with $a + b = c$ then $$ c < (\text{rad}(abc))^{1.75}$$

The operator $\text{rad}$ (=radical) means the product of the distinct prime numbers dividing $n$. The version was derived from the (following) explicit ABC-Conjecture, also due to Baker:

ABC-Conjecture (explicit version)

Given co-prime integers $a,b,c$ with $a + b = c$ and let $\omega(n)$ be the number of distinct prime factors of $n$ then $$c < \frac{6}{5}\text{rad}(abc)\frac{(\log(\text{rad}(abc)))^{\omega(abc)}}{\omega(abc)!}$$

Assume you have co-prime integers $a,b,c$, wlog $a < b < c$, with $\text{rad}(a) < a^{1/6}$,  $\text{rad}(b) < b^{1/6}$ and $\text{rad}(c) < c^{1/6}$, then it is
\begin{align*}
 c &\leq \text{rad}(abc)^{1.75} = (\text{rad}(a)\text{rad}(b)\text{rad}(c))^{1.75}\\
 &< (a^{1/6}b^{1/6}c^{1/6})^{1.75} < (c^{1/2})^{1.75} = c^{15/16}\\
& < c
\end{align*} which is a contradiction and hence such integers can not exists. That's also the reason, why the even more famous Fermat Last Theorem follows from the ABC-Conjecture, which shows how deep the ABC-Conjecture is.

Observe the following simple Heuristic:

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.

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 ?

Learning a Sine-Wave (Part 2) - A partial solution

For convenience, i restate the problem definition here:

Problem-Definition. Assume you have an integer interval $I = [0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \text{sign}(\sin(2x\pi/p))$. Find the secret parameter $p$.

Formulated in words, the set $Z$ contains randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that integer (i.e. the sign value) and your goal is to find that particular sine wave.

Heuristically, $\log p$ points should be sufficient, and in the first part on this topic, i described an easy instance of this problem that indeed finds $p$ using only $\mathcal{O}(\log p)$ points. Then i showed what causes the algorithm to fail if the problem instance gets a little bit more complicated. The algorithm then fails because the solution space falls apart (this could be very well shown visually if the solution spaces are drawn on a unity disk) and keeping track all the scattered solution spaces is too inefficient.

Estimating discrete logarithms via sum of group elements

The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox.

I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$

Pairings-based Cryptography (Part 1)

This post contains some basic facts about Pairing-based Cryptography. I write this post mainly for the reason to have a easy to find reference for myself and to recall some definitions. For readers that are more interested in pairings in context of cryptography, a good further reading source is the dissertation of Lynn [1], wherefrom i also adopted the usage of the multiplicative notation as a shortcut to represent $$\underbrace{a\circ a\circ ... \circ a}_{n\;times} = a^n$$ if $\circ$ is the group operation of $\mathbb{G}$ and $a \in \mathbb{G}$.

Definition [Pairing] Let $r$ be a prime number and $\mathbb{G}_1$ and $\mathbb{G}_T$ be cyclic groups of order $r$. Let $\mathbb{G}_2$ [not necessary cyclic] in which every element has order $r$. Then a pairing is the map \begin{equation} e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T \end{equation} and which has the properties ($\mathsf{e}$ is the neutral element in the group): (Non-Degeneracy) $e(g_1,g_2) = \mathsf{e}_{\mathbb{G}_T}$ for all $g_2\in\mathbb{G}_2$ if and only if $g_1 = \mathsf{e}_{\mathbb{G}_1}$ (Non-Degeneracy) $e(g_1,g_2) = \mathsf{e}_{\mathbb{G}_T}$ for all $g_1\in\mathbb{G}_1$ if and only if $g_2 = \mathsf{e}_{\mathbb{G}_2}$ (Bilinearity) $e(g_1^a,g_2^b) = e(g_1,g_2)^{ab}$ for all $g_1\in\mathbb{G}_1$ and $g_2\in\mathbb{G}_2$ for all $a,b\in\mathbb{Z}$.

An explicit formula for the discrete logarithm

I guess, but i am not sure, many people don't know that there is an explicit formula for the discrete logarithm in finite fields $\mathbb{F}^*_p$. I remember that i was quite surprised when i learned the formula many years ago.

Theorem [Explicit DL Formula] Let $p$ be a prime number $>2$ and $g$ be a primitive root in $\mathbb{F}^*_p$. Then the discrete logarithm of the element $a \in \mathbb{F}^*_p$ is equal to \begin{equation} \mathsf{dlog}_{p,g}(a) = \sum^{p-2}_{k=1} \frac{a^k}{1-g^k}\pmod{p}\end{equation}

The proof is actually not that complicated and can be found in Niederreiter [1]. I will give here a new proof for you:

The l-Hensel Lifting Assumption

In one of my previous posts, i talked about the possibilities to insert backdoors in prime numbers (beside the property that $p-1$ is smooth). One of the potential ideas for a backdoor was to generate primes that allow an easy lift from $\mathbb{Z}/p$ to $\mathbb{Z}/{p^2}\mathbb{Z}$. But under the consideration of the $l$-Hensel Discrete Logarithm Assumption, this should be actually hard in the general case.

Because if you could successfully lift the element $e\equiv g^x\pmod{p}$ to $E\equiv g^x\pmod{p^2}$, then you could, as long as $x < \mathsf{ord}_p(g) = r$, compute
\begin{align*}
\left(g^x\right)^{r} \equiv (g^{r})^x \equiv (1+p\lambda)^x \pmod{p^2}
\end{align*}
Next, the Binomial Theorem gives
\begin{align*}
(1+p\lambda)^x \equiv \sum^x_{i=0}\binom{x}{i}p^i\lambda^i \equiv 1 + xp\lambda\pmod{p^2}
\end{align*}
and hence
\begin{align*}
\frac{E^{r} - 1}{p\lambda} \equiv x \pmod{p}
\end{align*}

[Paper Review] Non-uniform cracks in the concrete: the power of free precomputation

Again, another paper discussion. It is the paper from D.J. Bernstein and T. Lange that will be presented on the Asiacrypt this year. It is a very special paper with the titel "Non-uniform cracks in the concrete: the power of free precomputation". It subtle criticizes the way security proofs are made in the area of provable cryptography. They describe that the current proofs do not cover the free will of an attacker correctly. E.g., they argue, that the proofs do not consider the possibility of precomputation or the option for an attacker to trade success probability for an easier to find algorithm.

# Background #

Koeblitz and Menenzes did something similar before and they were criticized due to scratching at the base elements of provable cryptography. From my point of view, i can understand both sides and i don't like blaming the other side for having a different opinion.

All the achievements in provable cryptography gave us nice and beautiful tools to work with. These tools seem to work very well and having them in the toolbox are by far better than having nothing at hand. However, trying to enhance a current situation in order to give people even better tools at hand, can not be bad at all. And whenever there is an argument that could falsify some theorems systematically (not just because of bad / wrong proofs), one has to somehow incorporate those arguments. Are they correct, are they relevant? Could previous definitions slightly changed to cover those new arguments to increase the security strength to a higher level?

The attacks presented in the paper are not efficient enough to pose a security risk in practise, but show that the theoretical lower bounds from given standard assumptions/theorems can be beaten significantly.

What if $\sigma_0(n)$ could be computed efficiently?

What would be the consequences if the sum of divisors function with $k=0$ could be computed efficiently, that is polynomial in $\log (n)$ if $n$ is the input to $\sigma_0(n)$? Note that if $n=p_1^{e_1}p_2^{e_2}...p_m^{e_m}$ then $$\sigma_0(n) = \sum_{d|n} d^0 =  \sum_{d|n} 1 = (e_1+1)(e_n+1)...(e_m+1)$$ For square-free numbers $n$, this is always a power of $2$, hence $\log_2(\sigma_0(n))$ gives the number of prime factors in this case. Furthermore, the famous AKS-algorithm gives a deterministic polynomial time algorithm, that decides if $\sigma_0(n) = 2$ or not, i.e. $n$ is prime or composite.

For the general case, Terence Tao gave an heuristic argument that generally this should be as hard as factoring a number:

"There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors  problem is believed to have comparable difficulty to factoring itself."

[Paper Review] A new index calculus algorithm with complexity $L(1/4 + o(1))$ in small characteristic.

Scientific breakthroughs are rare events. And I can not directly judge if this is indeed a breakthrough or not, but there are people out there, which do so.

It is the paper from Antoine Joux. It introduces a new techniques for the index calculus algorithm and improves the running time to $L(1/4+o(1))$. And it is also the follow up paper by Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé. The later improves (heuristically) the running time even to quasi-polynomial complexity, i.e., $n^{\mathcal{O}(\log n)}$.

Backdooring Discrete Logarithms in $\mathbb{Z}^*_p$

In one of my previous post, i talked about the (potential) backdoor in the pseudo random number generator described in SP800-90 Dual Ec PRNG. The backdoor could be exploited by the usage of some perhaps existing secret relation among two given constants.

The concept of elliptic curves cryptography and its whole theory is much more complicated than the cryptography based on the finite fields $\mathbb{F}_p$ for a large prime number $p$. Implementing a backdoor in that case seems to be harder. Some people indeed say, that we should switch back to the good old fields $\mathbb{Z}^*_p$ to increase the confident in our systems.

Learning a Sine-Wave

A few month ago, i locked up myself into a mental hole, by trying to solve or at least partially solve the following problem:

Problem-Definition. Assume you have a sufficient long integer interval $I=[0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \mathsf{sign}(\sin(2x\pi/p))$. Formulated in words, the set $Z$ contains the randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that point (i.e., the sign value). Find the secret parameter $p$.

# Heuristic argument #

It can be heuristically proved, that even as few as $m =\log p$ points should be enough to find a unique value for $p$. Imagine a random sine wave that is plotted along the interval $I$. Since the points $x_i$ are randomly chosen from $I$, the chance that a point $x_i$ is traversed by the sine wave equal to its assigned sign value is $1/2$. Hence, the chances that a random curves traverses all $m$ points correct is $(1/2)^m$.

But it seems one can not do better than $\mathcal{O}(p)$, that is exponential in $m$.

[Paper Review] Efficient Cryptosystems From $2^k$-th Power Residue Symbols

Today i want to present a paper from the 2013 Eurocrypt conference. The paper is written by Marc Joye and Benoît Libert with the name Efficient Cryptosystems From $2^k$-th Power Residue Symbols [1]. It describes a cryptosystem that is a generalization of the Goldwasser-Micali cryptosystems [2] from quadratic residues to $2^k$-th power residues.

The scheme provides

• indistinguishable encryption under the $k$-QR assumption 
• a small ciphertext expansion rate 
• a fast decryption algorithm
• additive homomorphic operations
• a (more) efficient Lossy Trapdoor Function

Just as the Goldwasser-Micali cryptosystem the Joye-Libert cryptosystems works in the ring $\mathbb{Z}_N$ for a RSA-modulus $N$. The factorization of $N = pq$ is chosen to be $p \equiv q  \equiv 1\pmod{2^k}$. Then they make use of the $n$-th power residue symbol:

Definition. [$n$-th power residue symbol]. Let $p$ be an odd prime and let $n \geq 2$ such that $n | (p-1)$. Then the symbol $$ \binom{a}{p}_n = a^{(p-1)/n}\pmod{p}$$ is called the $n$-th power residue symbol modulo $p$. $\blacktriangleleft$.

Double Columnar Transposition (Part 1)

Even in the 21st century, there still exists cipher methods that can be executed by pencil and paper and that are concurrently strong enough to resists the computational power of modern PCs quite well. One of those cipher systems is the Double Columnar Transposition Cipher (DCTC), or for the german speaking readers Der Doppelwürfel.

[Double Columnar Transposition Cipher]. The DCTC works as follows: Assume a plaintext $\mathcal{P} = n_1 n_2 ... n_k$. Pick two key words from an (e.g.) english dictionary or even better two short sentences: $\mathcal{K}_1$ and $\mathcal{K}_2$ of length $s_1$ and $s_2$ respectively. To encrypt a message, write the plaintext in a block (or matrix) layout with $s_1$ columns. Now sort the columns regarding the first keyword $\mathcal{K}_1$. E.g. using the plaintext THIS IS IMPORTANT and the first keyword DOUBLE:

$$ \begin{bmatrix}
\textbf{D} & \textbf{O} & \textbf{U} & \textbf{B} & \textbf{L} & \textbf{E} \\
- & - & - & - & - & - \\
\text{T} & \text{H} & \text{I} & \text{S} & \text{I} & \text{S} \\
\text{I} & \text{M} & \text{P} & \text{O} & \text{R} & \text{T}\\
\text{A} & \text{N} & \text{T} & & & \\
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
 \begin{bmatrix}
\textbf{B} & \textbf{D} & \textbf{E} & \textbf{L} & \textbf{O} & \textbf{U} \\
- & - & - & - & - & - \\
\text{S} & \text{T} & \text{S} & \text{I} & \text{H} & \text{I} \\
\text{O} & \text{I} & \text{T} & \text{R} & \text{M} & \text{P}\\
 & \text{A} & & & \text{N} & \text{T}\\
\end{bmatrix}  \stackrel{\text{read column by column}}{\rightarrow}$$
(The keyword above the text is only displayed for clarity reasons.) After sorting, read the text column by column from the block, thereby skipping the empty places in the last row. In this order write the text again in block-size form, this time with $s_2$ columns. Again, sort the block according to the second keyword $\mathcal{K}_2$, here CUBE:
 $$ \begin{bmatrix}
\textbf{C} & \textbf{U} & \textbf{B} & \textbf{E} \\
- & - & - & - \\
\text{S} & \text{O} & \text{T} & \text{I} \\
\text{A} & \text{S} & \text{T} & \text{I} \\
\text{R} & \text{H} & \text{M} & \text{N} \\
\text{I} & \text{P} & \text{T} &
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
\begin{bmatrix}
\textbf{B} & \textbf{C} & \textbf{E} & \textbf{U} \\
- & - & - & - \\
\text{T} & \text{S} & \text{I} & \text{O} \\
\text{T} & \text{A} & \text{I} & \text{S} \\
\text{M} & \text{R} & \text{N} & \text{H} \\
\text{T} & \text{I} & & \text{P}
\end{bmatrix}\stackrel{\text{read column by column}}{\rightarrow}$$
Read the text once again column by column from the block, which is the resulting ciphertex:

 TTMTS ARIII NOSHP