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

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.

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

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.

Coldboot Code Available

After receiving two inquiries about the coldboot attack paper which were best answered by looking at the code or by comparing with our code, I figured it was about time I put it online. So here it is:

https://bitbucket.org/malb/algebraic_attacks/src/1af75effcc7d/coldboot

For this code to run you’ll need to apply this patch to Sage:

http://trac.sagemath.org/sage_trac/ticket/10879

which adds an interface to SCIP. Unfortunately, this patch crashes on OSX and I didn’t figure out yet why. Anybody willing to help, please step forward

Also, I assume the code on bitbucket needs some patching to work with the most recent version of Sage. Patches very welcome!

Ring-LWE and the GB(N) Problem

Over at the Bristol Cryptography Blog Martijn Stam writes about our “Polly Cracker, Revisted” paper:

We did not discuss the paper  in great detail, but Jake did mention one interesting avenue for continued research. Given that this new approach allows one to cast both LWE and approximate GCD in the same framework, can one also capture ring-LWE. If so, this might enable a better comparison of the various fully homomorphic encryption (FHE) schemes out there. The hope expressed by Jake was that this might allow a reduction to standard LWE (for the current batch of ring-LWE schemes), which would boost our confidence in those schemes.

This motivated me to express the Ring-LWE problem in a language of Gröbner bases, here’s what I could come up with so far.

Challenge matrices

Now, that we have a decent PNG reader/writer in M4RI, it’s much easier to get some challenge matrices out of the library. Below, I list and link a few such matrices as they appear during Gröbner basis computations.

file	matrix dimensions	density	PLE	M4RI	GB
HFE 25 matrix 5 (5.1M)	12307 x 13508	0.07600	1.03	0.59	0.81
HFE 30 matrix 5 (16M)	19907 x 29323	0.06731	4.79	2.70	4.76
HFE 35 matrix 5 (37M)	29969 x 55800	0.05949	19.33	9.28	19.51
Mutant matrix (39M)	26075 x 26407	0.18497	5.71	3.98	2.10
random n=24, m=26 matrix 3 (30M)	37587 x 38483	0.03832	20.69	21.08	19.36
random n=24_ m=26 matrix 4 (24M)	37576 x 32288	0.04073	18.65	28.44	17.05
SR(2,2,2,4) compressed, matrix 2 (328K)	5640 x 14297	0.00333	0.40	0.29	0.18
SR(2,2,2,4) compressed, matrix 4 (2.4M)	13665 x 17394	0.01376	2.18	3.04	2.04
SR(2,2,2,4) compressed, matrix 5 (2.8M)	11606 x 16282	0.03532	1.94	4.46	1.59
SR(2,2,2,4) matrix 6 (1.4M)	13067 x 17511	0.00892	1.90	2.09	1.38
SR(2,2,2,4) matrix 7 (1.7M)	12058 x 16662	0.01536	1.53	1.93	1.66
SR(2,2,2,4) matrix 9 (36M)	115834 x 118589	0.00376	528.21	578.54	522.98

The first three rows are from GB computations for the hidden field equations cryptosystem (those matrices were provided by Michael Brickenstein). The “mutant” row is a matrix as it appears during a run of the MXL2 algorithm on a random system (I believe). It was contributed by Wael Said. The rows “random n=25,m=26″ are matrices as they appear during a GB computation with PolyBoRi for a random system of equations in 24 variables and 26 equations. The remaining rows are matrices from PolyBoRi computations on small scale AES instances. Those rows which have “compressed” in their description correspond to systems where “linear variables” were eliminate before running the Gröbner basis algorithm.

The last three columns give running times (quite rough ones!) for computing an echelon form (not reduced) using (a) the M4RI algorithm, (b) PLE decomposition and (c) a first implementation of the TRSM for trivial pivots trick. As you can see, currently it’s not straight-forward to pick which strategy to use to eliminate matrices appearing during Gröbner basis computations: the best algorithm to pick varies between different problems and the differences can be dramatic.

This looks interesting: Code Audit Feed

You’re a developer. And you’ve spent the last 2 years working with Java sockets in an uninteresting trading app. But you also happen to support anonymity – but have no idea how to get involved. Or you’re a security researcher who’s spent the last two months understanding the padding oracle backwards and forwards. Wouldn’t it be nice to see a personalized RSS feed of cryptography, anonymity, and privacy projects containing the keywords “java.net.Socket” or “CBC Mode”? Then you could skim commits, and if something interesting came up, you may be able to lend your expertise. That’s exactly what the Code Audit Feed is for.

The goal is to aggregate relevant open source projects, watch their commits, and deliver personalized information via RSS, email, and a web interface to encourage people to get involved with projects and audit and improve the code. Development and Design are in the early stages, with a github repo located here. If interested, you can find the developer(s) onthe crypto.is IRC channel.

Website: https://crypto.is/projects/audit/ (via: https://blog.crypto.is/TCP-Newsletter-One/)

“Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis”

Recently, Nicolas Courtois sent me a revised version of my PRESENT bitslice implementation which improves the representation of the S-Box and hence the performance considerably. A paper describing the techniques used to arrive at this new S-box representation is now available on eprint:

Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis

Nicolas T. Courtois, Daniel Hulme and Theodosis Mourouzis

Abstract: One of the hardest problems in computer science is the problem of gate-eficient implementation. Such optimizations are particularly important in industrial hardware implementations of standard cryptographic algorithms. In this paper we focus on optimizing some small circuits such as S-boxes in cryptographic algorithms. We consider the notion of Multiplicative Complexity, a new important notion of complexity introduced in 2008 by Boyar and Peralta and applied to find interesting optimizations for the S-box of the AES cipher. We applied this methodology to produce a compact implementation of several ciphers. In this short paper we report our results on PRESENT and GOST, two block ciphers known for their exceptionally low hardware cost. This kind of representation seems to be very promising in implementations aiming at preventing side channel attacks on cryptographic chips such as DPA. More importantly, we postulate that this kind of minimality is also an important and interesting tool in cryptanalysis.

Chen & Nguyen’s algorithm and Arora & Ge’s algorithm

In Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers Yuanmi Chen and Phong Q. Nguyen (preprint here) propose a new algorithm for solving the approximate GCD problem. It drops the complexity from to in the general case and from to in the partial case (one multiple of is given noise-free) which is a pretty big deal.

The algorithm is based on two key ideas (explained using the partial approximate GCD problem):

AsiaCrypt 2011 accepted papers

The list of accepted papers for AsiaCrypt 2011 is out … which I find exciting  because for the first time I have a paper at one of the three big IACR conferences. yay!

Yet another Polly Cracker talk

… but this time

• it has less formal definitions.
• I also added a section talking about trading noise for degree and
• a brief discussion on related work.

Speaking of related work: Efficient Fully Homomorphic Encryption from (Standard) LWE by Zvika Brakerski and Vinod Vaikuntanathan is a good read. In summary, it has two main contributions:

1. a somewhat homomorphic scheme based on LWE which turns out to be the same (as far as I can tell) as ours and
2. a new dimension reduction trick which allows to turn it into a fully homomorphic scheme.

What is kind of curious about this work is its explicit non-algebraic perspective. While we talk about LWE from a multivariate polynomial ideal perspective the authors of 2011/344 explicitly state that their scheme is not.  I am not sure we’d have seen the dimension reduction trick with our perspective, though.