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 →

Encouraging female reverse engineers

by

Thomas Dullien is running a nice competition to address the gender gap in IT security or more precisely reverse engineering:

As a field, reverse engineering has undergone a rapid change in recent years:
a rise in importance and visibility has led to a rapidly growing community of
reverse engineers. More people are doing reverse engineering, better tools are
developed, and it has mutated from a “dark art” to an almost-mainstream
endeavor.

However, as the community grows, the most visible parts  remain unchanged.
While there are female reverse engineers in the field, they are still under-
represented in absolute numbers and visibility of their work in conference
attendance and presentations.

What can we, as a growing field, do to change this? Progress can be made on the
macro level by many small and decentralized contributions on the micro level.
So, when I heard about the Syscan speaker’s honorarium this year, I decided to
put it to good use.

I asked a few friends if they’d be willing to form a panel of judges for a
women-only reverse engineering challenge, with the first (and only) prize being
a ticket to fly to and attend Syscan Singapore 2013. Luckily for me, they
agreed :-)