Tag: conference

17th IMA Conference on Cryptography and Coding

IMA-CC is a crypto and coding theory conference biennially held in the UK. It was previously held in Cirencester. So you might have heard of it as the “Cirncester” conference. However, it has been moved to Oxford, so calling it Cirencester now is a bit confusing. Anyway, it is happening again this year. IMA is a small but fine conference with the added perk of being right before Christmas. This is great because around that time of the year Oxford is a fairly Christmas-y place to be.

16 – 18 December 2019, St Anne’s College, University of Oxford

Continue reading “17th IMA Conference on Cryptography and Coding” →

16th IMA International Conference on Cryptography and Coding

IMA-CCC is a crypto and coding theory conference biennially held in the UK. It was previously held in Cirencester. So you might have heard of it as the “Cirncester” conference. However, it has been moved to Oxford, so calling it Cirencester now is a bit confusing. Anyway, it is happening again this year. IMA is a small but fine conference with the added perk of being right before Christmas. This is great because around that time of the year Oxford is a fairly Christmas-y place to be.

12 – 14 December 2017, St Catherine’s College, University of Oxford

Continue reading “16th IMA International Conference on Cryptography and Coding” →

15th IMA International Conference on Cryptography and Coding

IMA-CCC (Facebook) is a crypto and coding conference biennially held in the UK. It was previously held in Cirencester. So you might have heard of it as the “Cirncester” conference. However, it has been moved to Oxford, so calling it Cirencester now is a bit confusing. Anyway, it is happening again this year. IMA is a small but fine conference with the added perk of being right before Christmas. This is great because around that time of the year Oxford is a fairly Christmas-y place to be.

Continue reading “15th IMA International Conference on Cryptography and Coding” →

Lattice Stuff

We — with Jean-Charles Faugère, Robert Fitzpatrick and Ludovic Perret – managed to finish our work on the cryptanalysis of all proposed parameters of the public-key encryption scheme proposed at PKC 2012 by Huang, Liu and Yang. The key observation is that the scheme can be viewed as an easy LWE instance:

In this paper, we investigate the security of a public-key encryption scheme introduced by Huang, Liu and Yang (HLY) at PKC’12. This new scheme can be provably reduced to the hardness of solving a set of quadratic equations whose coefficients of highest degree are chosen according to a discrete Gaussian distributions. The other terms being chosen uniformly at random. Such a problem is a variant of the classical problem of solving a system of non-linear equations (PoSSo), which is known to be hard for random systems. The main hypothesis of Huang, Liu and Yang is that their variant is not easier than solving PoSSo for random instances. In this paper, we disprove this hypothesis. To this end, we exploit the fact that the new problem proposed by Huang, Liu and Yang reduces to an easy instance of the Learning With Errors (LWE) problem. The main contribution of this paper is to show that security and efficiency are essentially incompatible for the HLY proposal. That is, one cannot find parameters which yield a secure and a practical scheme. For instance, we estimate that a public-key of at least 1.03 GB is required to achieve 80-bit security against known attacks. As a proof of concept, we present practical attacks against all the parameters proposed Huang, Liu and Yang. We have been able to recover the private-key in roughly one day for the first challenge proposed by HLY and in roughly three days for the second challenge.

Furthermore, I gave a talk yesterday on solving LWE with binary secret using a variant of the BKW algorithm at SIAM AG’13.

LPN and SVP

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: 

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

sage:  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
sage: B = A.kernel().matrix()
sage: L = B.change_ring(ZZ).LLL()

# because a short vector there, means few additions which means a higher bias in the sum
sage: Av = A.augment(v)
sage: 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.

An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers

a paper that I wrote with Gregor Leander is finally done, out and accepted for presentation at SAC.

We present a framework that unifies several standard differential techniques. This unified view allows us to consider many, potentially all, output differences for a given input difference and to combine the information derived from them in an optimal way. We then propose a new attack that implicitly mounts several standard, truncated, impossible, improbable and possible future variants of differential attacks in parallel and hence allows to significantly improve upon known differential attacks using the same input difference. To demonstrate the viability of our techniques, we apply them to KATAN-32. In particular, our attack allows us to break 115 rounds of KATAN-32, which is 37 rounds more than previous work. For this, our attack exploits the non-uniformity of the difference distribution after 91 rounds which is 20 rounds more than the previously best known differential characteristic. Since our results still cover less than 1/2 of the cipher, they further strengthen our confidence in KATAN-32’s resistance against differential attacks.

 

Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations

As you may know, today is the last day of the wokshop on Efficient Linear Algebra for Gröbner Basis Computations that Christian Eder, Burcin Eröcal, Alexander Dreyer and I organised.

I have to say that I am quite pleased with how the workshop played out. We planned the whole thing to be hands on: people were strongly encouraged to work on projects, i.e., to write code preferably together, in addition to attending talks. Those who attended a Sage Days workshop in the past, will know what workshop format I am referring to. Continue reading “Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations” →

Efficient Linear Algebra for Gröbner Basis Computations – June 4-8, 2012 – Kaiserslautern, Germany

Linear algebra plays an important role in modern efficient implementations of Gröbner basis algorithms. Consequently, a number of groups aim at developing linear algebra packages for these computations: we mention the HPAC project, LELA by the Singular team, the FGB package by Jean-Charles Faugère, the M4RI libraries, specialised linear algebra routines in PolyBoRi as well as non-public projects. In this workshop we want to bring researchers interested in this problem and developers of these packages together to discuss and develop solutions. The format of this workshop will be a mixture of talks, coding sprints and design discussions.

Topics will include but are not limited to:

  • presentation of existing software packages and solutions for linear algebra suitable for Gröbner basis computations
  • presentation of scientific results on linear algebra for Gröbner basis computations
  • modular approaches to Gröbner basis computations which allow to swap linear algebra packages
  • approaches to parallelization of linear algebra routines on multicore machines, multiple machines and GPUs.
  • suitable benchmark and test matrices, ideals and their format.

Invited Speakers

  • Brice Boyer (Grenoble, France)
  • Michael Brickenstein (Oberwolfach, Germany)
  • Daniel Cabarcas (Darmstadt, Germany)
  • Jean-Charles Faugère (Paris, France)
  • Bradford Hovinen (Munich, Germany)
  • Sylvain Lachartre (Paris, France)
  • Emmanuel Thomé (Nancy, France)

The workshop will feature mathematical talks, presentations on software and coding sprints.

Registration

There is no registration fee for the workshop. Please email the organizers beforehand if you intend to participate.

It is strongly recommended that participants bring their own laptop for use during the coding sprints.

More information regarding this event is available at http://wiki.lmona.de/events/elagb