[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.

[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)}$.

[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$.