Slides of Talk on Sage & Algebraic Techniques

June 11, 2013 by martinralbrecht

The slides of my Icebreak talk on Sage and algebraic techniques for (lazy) cryptographers are now available (LaTeX sources here).

LPN and SVP

January 16, 2013 by martinralbrecht

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.

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

August 5, 2012 by martinralbrecht

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

June 8, 2012 by martinralbrecht

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 →

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

May 10, 2012 by martinralbrecht

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

Call for Papers: 3nd International Conference on Symbolic Computation and Cryptography

March 22, 2012 by martinralbrecht

CIEM – Castro Urdiales, Spain, 11-13 July 2012, http://scc2012.unican.es/

CALL FOR PAPERS

IMPORTANT DATES

Deadline for submission: April 28, 2012
Notification of acceptance or rejection: May 18, 2012
Deadline for final version: May 30, 2012
Deadline for registration: June 12, 2012
Deadline for special issue JSC: September 30, 2012

SCC 2012 is the third edition of a new series of conferences where research and development in symbolic computation and cryptography may be presented and discussed. It is organized in response to the growing interest in applying and developing methods, techniques, and software tools of symbolic computation for cryptography. The use of Lattice Reduction algorithms in cryptology and the application of Groebner bases in the context of algebraic attacks are typical examples of explored applications. The SCC 2012 conference is co-located with third Workshop on Mathematical Cryptology (WMC 2012, http://wmc2012.unican.es/) , an event also organized by research group Algorithmic Mathematics And Cryptography (AMAC), which will be held on 9-11 July 2012.

Continue reading →

Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.

March 1, 2012 by martinralbrecht

Slightly redacted announcement for the 2012 Summer School on Tools below.

Following the success of the ECRYPT Workshop on Tools for Cryptanalysis 2010,the ECRYPT II Symmetric Techniques Virtual Lab (SymLab) is pleased to announce the 2012 Summer School on Tools. Covering selected topics in both symmetric and asymmetric cryptography, this summer school will provide a thorough overview of some of the most important cryptographic tools that emerged in recent years. While the summer school is aimed primarily at postgraduate students, attendance is open to all. Continue reading →

Sage/FLINT Days aka Sage Days 35

December 22, 2011 by martinralbrecht

I am writing this while waiting for my taxi to leave Sage Days 35. Although, I didn’t get much actual coding done, it was great fun and very useful. I met a lot of old friend, new faces and managed to put faces to e-mail addresses.

In terms of coding projects, first, I tried to speed up linear algebra mod p where p is a 32 or 64 bit prime. But it turns out that any trick I could think of could not improve on Frederik’s code. So that didn’t lead anywhere but I allowed me to read some code of FLINT2 (very readable) and admire how carefully it is written.

My other two projects both involved evaluate–pointwise-multiply–interpolate algorithms for fast matrix-matrix products over finite extension fields or for matrices with polynomial coefficients (over prime fields). After my talk on M4RI(E) David Harvey worked out how to improve multiplication over $\mathbb{F}_{2^6}$ from 17 multiplications over $\mathbb{F}_2$ to 15, which then lead to a general approach for $\mathbb{F}_{2^m}$ with composite $m$ . Much of it remains to be implemented (efficiently), but the $\mathbb{F}_{2^6}$ example indeed shows a 10% speed-up as expected. The code is not clean yet, uses way too much memory and doesn’t deal with the more advanced finite field stuff appropriately. It should end up in M4RIE eventually though.

I also contributed a bit to #12177 which is about a “prime slice” implementation of matrices over $\mathbb{F}_{p^k}$ . The idea is essentially to represent these matrices as polynomials with matrix coefficients and to use fast polynomial multiplication algorithms for these polynomials. It turns out, this works very well even for small finite fields. Burcin Eröcal did all the coding, I only helped with some discussions. We need to polish the code a lot to be usable, so if you like matrices over $\mathbb{F}_{p^k}$ head over to #12177 and help out.