Category Archives: cryptography

BKW: Update

by

We have updated our pre-print titled “On the Complexity of the BKW Algorithm on LWE” on ePrint.

There are two main changes and the reasons why I am mentioning this update here.

  1. We included a more thorough comparison with other approaches, in particular, with lattice reduction (reducing LWE to SIS). To our surprise, BKW is quite competitive even in relatively modest dimensions. For Regev’s and Lindner-Peikert’s parameter sets (as interpreted here) we get that BKW is at least as fast as BKZ starting in dimension n \approx 250, which I find very low (see Table 4 on page 19).
  2. We also provide an alternative approximating for the running time of BKZ. The standard estimate due to Lindner-Peikert is \log_2 T_{sec} = \log_2 1.8/\delta_0 - 110 where \delta_0 is the targeted root hermit factor. Interpolating estimates from the BKZ 2.0 simulator and reflecting on the doubly exponential running time of BKZ in the blocksize \beta we found: \log_2 T_{sec} = \log_2 0.009/\delta^2_0 - 27. However, since this might be controversial, we include estimates for both models.

A Generator for LWE and Ring-LWE Instances

by

We’re ready to announce our LWE/Ring-LWE generators for Sage:

We introduce software for the generation of instances of the LWE and Ring-LWE problems, allowing both the generation of generic instances and also particular instances closely-related to those arising from cryptomania proposals in the literature. Our goal is to allow researchers to attack different instances in order to assess the practical hardness of LWE and Ring-LWE. This will in turn give insight to the practical security of cryptographic systems based on both problems.

IACR Announcement, interactive demo.

A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy

by

At CT-RSA 2013 a paper titled “A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy” by Michal Hojsík and Veronika Půlpánová was presented. Here is the abstract:

We propose a new fully homomorphic cryptosystem called Symmetric Polly Cracker (SymPC) and we prove its security in the information theoretical settings. Namely, we prove that SymPC approaches perfect secrecy in bounded CPA model as its security parameter grows (which we call approximate perfect secrecy). In our construction, we use a Gröbner basis to generate a polynomial factor ring of ciphertexts and use the underlying field as the plaintext space. The Gröbner basis equips the ciphertext factor ring with a multiplicative structure that is easily algorithmized, thus providing an environment for a fully homomorphic cryptosystem.

The proposal seems to have succeeded where we could not: a fully homomorphic encryption scheme that also is information theoretic secure. Indeed, the authors reference our work and point out that they are taking a different approach (from ours) which allows them to succeed in realising these two goals. Continue reading →

LPN and SVP

by

I am currently attending ESC 2013 in Mondorf, Luxembourg. Over dinner someone mentioned that there is no known reduction from LPN to lattice reduction, i.e., it is not known that you can solve LPN with LLL and friends.  This seems rather strange to me, because the standard lattice attack on LWE seems to be carrying over as is:

n = 100 # number of variables
m = 400 # number of samples
A = random_matrix(GF(2), m, n)
s = random_vector(GF(2), n) # our secret
p = 0.25 # our error rate

v = A*s + vector(GF(2),[1 if random() < p else 0 for _ in range(m)])

# we are searching for a short vector in the dual lattice
B = A.kernel().matrix()
L = B.change_ring(ZZ).LLL()

# because a short vector there, means few additions which means a higher bias in the sum
Av = A.augment(v)
sum(map(lambda x: abs(x) % 2,L[0])), (L[0]*Av)[-1]

Of course, this means running lattice reduction many times, but still: what am I missing?

PS: Obligatory, Sage cell here.

Matrix Multiplication over GF(p^e)

by

After my talk at Sage Days 35 in Warwick (that was in winter 2011) David Harvey had an idea on how to speed up matrix multiplication over \mathbb{F}_{p^n}. We spend some time on this in Warwick and developed this idea further (adding fun stuff like Mixed Integer Programming in the process) but did not get around to do much on this project in the mean time (I have explained the idea at the end of my talk in Mykonos, though).

Just now, in a conversation with Richard Parker I was reminded of this dormant project, i.e., the question of how many multiplications i \mathbb{F}_p it takes to do a multiplication in \mathbb{F}_{p^n}. In particular, I recalled to have written some code for Sage which gives some upper bound to this answer which is better than Karatsuba.

Well, here’s an interactive demo … gosh, I love the Sage cell server.

DTU Crypto Group is hiring

by

the group I am in is hiring an assistant/associate professor.

DTU Compute at the Technical University of Denmark calls for applications for a position as associate or assistant professor. The department is looking for a dynamic faculty member to participate in research and teaching in computer science and mathematics. The position is available from 1 May 2013.

DTU Compute conducts research and provides teaching in the fields of mathematics, modeling and computer science. The expanding mass of information and the increasingly complex use of advanced technology in society demand development of advanced computer based mathematical models and calculations. The unique skills of the department are in high demand in IT innovation and production.

Through the position the University seeks to strengthen the research within cryptology. The cryptology group at DTU has experts in design and analysis of ciphers and hash functions and in side-channel analysis. Experience with implementing cryptography in software and/or hardware is regarded as a plus. Interest and skills in pedagogical work and dissemination of mathematical sciences will play an important role.

On the Complexity of the BKW Algorithm on LWE

by

We (with Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick and Ludovic Perret) have finally managed to put our work on BKW on ePrint.

Abstract:

In this paper we present a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and, as a result,  provide new upper bounds for the concrete hardness of these LWE-based schemes.

The source code of our (not very efficient!) implementation of BKW is available on bitbucket.