Rubik's for cryptographers
A cryptographic hash function with natural parallelism? Factoring is hard over the integers. What about finite matrix groups? An old conjecture Traveling in large (Cayley) graphs? Generalizing the Rubik's cube for cryptography? Perspectives Related papers and talks
A cryptographic hash function with natural parallelism?
Hash functions are one of the most important cryptographic primitives. They are used in almost every cryptographic protocol including digital signatures or message authentication schemes. Informally speaking, a hash function takes arbitrarily large messages as inputs and it "hashes" them into small, fixed-size hash values. The main security properties required from a hash function are collision resistance (hard to find two messages with the same hash value), preimage resistance (given a hash value, hard to find a preimage) and second preimage resistance (given a message, hard to find a second message hashing to the same value). More precise definitions can be found here. Efficiency really matters in practice when we need to hash big data. Parallelism is a common way to increase the speed of an algorithm. In 1991, Gilles Zémor introduced a construction of cryptographic hash functions based on matrix multiplication over a finite field [Z91]. The scheme was later broken and modified by Tillich and Zémor at the conference CRYPTO'94 [TZ94]. Despite some partial cryptanalytic results, it remained unbroken for more than 15 years until it was finally broken in 2009. In the meanwhile, the principles of the construction had been rediscovered in 2007 by Charles, Goren and Lauter who introduced new parameters [CGL07]. The basic principles of the construction are very simple. Let G be a non-Abelian finite group and let {S_1,...,S_k} be generators for this group. A message m is first decomposed into k-digits (bits for k=2).Factoring is hard over the integers. What about finite matrix groups?
Another nice aspect of this construction is that the security properties of the hash function can be linked to mathematical problems that can be studied independently. Of course, the problems must be "hard" in the cryptographic sense, or at least there should be good reasons to believe so. The factorization problem in finite groups is the following. Let G be a non-Abelian finite group and let {S_1,...,S_k} be generators for this group. Given h in G, find a representation of h as a product of the generators. We don't know whether this problem is hard or not. Like for other ''hard'' cryptographic problems (integer factoring, discrete logarithms...), the only way to know it is to study the problem and try to solve it. That has taken a substantial part of my research time so far. It turns out that all parameters proposed for cryptography have been broken. The constructions in [Z91], [TZ94], [CGL07], [PLQ07] were respectively broken in [TZ94], [GIMS09] and [PQ10], [TZ08] and [PLQ08], and [PLQ08]. However, the parameters used in these functions were all but generic. [Z91] and [TZ94] use ''small'' parameters to make the function more efficient, while [CGL07] and [PLQ07] use very special parameters for optimal expansion. Some other parameters were also ''broken'' independently by the Mathematics community, see [PQ11]. Again, those parameters looked anything but generic. For generic parameters, the hardness is still unknown. (Even RSA is broken if the parameters are badly chosen.) Some of my recent work provides a partial answer for the group SL(2,2^n): for any generator set, we can find short factorizations of any element in subexponential time [P11,FPPR11]. The problem is still widely open, though, and I will keep working on it. The factorization problem in finite groups is related to an old group-theoretical conjecture, Babai's conjecture [BS91]. Roughly speaking, the conjecture states that for finite simple non-Abelian groups, "short" factorizations always exist. Solving the factorisation problem in finite groups can be seen as providing a constructive proof of Babai's conjecture. The conjecture has recently gained a lot of interest in the Mathematics community after a breakthrough by Helfgott [H05]. In the survey paper [PQ11], we review the literature on this problem and its connection to the above factorisation problem.Traveling in large (Cayley) graphs?
Cayley graphs are graphs constructed from groups. Let G be a non-Abelian finite group and let {S_1,...,S_k} be generators for this group. The corresponding Cayley graph has one vertex per group element and each vertex g is connected to the k vertices gS_1,...,gS_k. Solving the factoring problem is equivalent to providing a path-finding algorithm in this graph. An expander graph is a graph with good connectivity properties: it has few edges at each vertex, still you can quickly connect any vertex to any other vertex in the graph. Expander graphs have a lot (really a lot) of applications in computer science: see the excellent survey [HLW06]. Cayley graphs tend to be good expanders. Path-finding algorithms in these graphs certainly have a lot of applications there, too. Ramanujan graph are graphs with optimal connectivity property in some sense. Some of these graphs were proposed for building hash functions [CGL07], [PLQ07]. However, the strong symmetries and structure that seem to be implied by the Ramanujan property also made those functions more vulnerable to attacks [TZ08,PLQ08]. BTW, here is a nice graph of the Tillich-Zémor hash function for small parameters [PQTZ09]:
Let G be the subgroup of all permutations of a 3*3*3 cube, consisting of permuting the corners, permuting the central edge elements or changing their orientations.
The identity of this group is the trivial permutation that lets every block unchanged.
Let S be the elementary permutations of the six faces in both directions.
Solving the Rubik's cube can then be seen as a special instance of the above factorization problem.
Of course, the Rubik's cube itself is not sufficiently hard for cryptography, as you can see for example here.
However, some of the extensions we are considering, in particular for matrix groups, could be hard enough.
In the paper [PQ11], we describe how some of the principles widely used to solve the Rubik's cube also extend to other groups of cryptographic interest.
My personal guess is that all those problems can be solved in polynomial time. I'm working on it.
It is only a guess. We are still very far of proving it.
For many years, nothing was known about Babai's conjecture.
A lot of progress has been made since Helfgott's paper [H05], but most of these proofs are non constructive.
The papers [P11,FPPR11] are a step forward in the direction of a full solution, but a lot of work remains to be done.
Here are some papers and talks that are related to this beautiful topic. Your questions/comments are welcome!
Talk on "Towards factoring in $SL(2,\mathbb{F}_{2^n})$"
BCRYPT workshop, Gent (Nov. 2010)
Talk on "Hash functions and Cayley graphs: the end of the story ?"
Slides at the LIP6, Université de Paris VI, Paris (Nov. 2010)
Slides at the Center for Cryptology and Information Security (CCIS) at Florida Atlantic University (Nov. 2010)
Slides at the Workshop on Computer Security and Cryptography, IRM, Montréal (Apr. 2010)
Slides at Microsoft Research, Seattle (Mar. 2010)
Slides at the Institut mathématique de Bordeaux (Dec. 2009)
Slides at the ECRYPT II workshop "Cryptographic hash functions: theory and practice" (Nov. 2009)
Talk on "Cryptographic hash functions from expander graphs"
Slides at the ECRYPT workshop on 'Hash Functions in Cryptography: from Theory to Practice', Lorentz Center, Leiden, the Netherland (2-06/06/08).
Slides at the Large Graphs Group seminar, UCL (Feb. 2009).
Cryptographic Hash Functions and Expander Graphs: The End of the Story ?
Christophe Petit and Jean-Jacques Quisquater
Preprint (2013)
New subexponential algorithms for factoring in SL(2,2^n)
Jean-Charles Faugčre, Ludovic Perret, Christophe Petit, Guénaël Renault
Preprint (2011)
Paper.
Rubik's for cryptographers
Christophe Petit and Jean-Jacques Quisquater
Notices of the American Mathematical Society (June/July 2013)
Paper. Extended version.
Rubik's for cryptographers
Christophe Petit and Jean-Jacques Quisquater
To appear in Mathematical Advance in Translation
NB: Chinese translation of the previous paper, with permission of the AMS
Towards factoring in SL(2,2^n)
Christophe Petit
To appear in Design, Codes and Cryptography
Preprint. http://www.springerlink.com/content/545822356k747017/ Springer link.
Preimage algorithms for the Tillich-Zémor hash function
Christophe Petit, and Jean-Jacques Quisquater
SAC 2010 - Selected areas in Cryptography
Paper. Slides.
Cryptographic hash functions from expander graphs
Christophe Petit
PhD thesis, UCL (2009)
Text.
Slides of the private defense.
Slides of the public defense.
ZesT : an all-purpose hash function based on Zémor-Tillich
Christophe Petit, Giacomo de Meulenaer, Jean-Jacques Quisquater, Jean-Pierre Tillich, Nicolas Veyrat-Charvillon and Gilles Zémor
Preprint (2009)
Paper.
Hardware Implementations of a Variant of the Zémor-Tillich Hash Function
Giacomo de Meulenaer, Christophe Petit and Jean-Jacques Quisquater
Preprint (2009)
Paper.
Hard and easy Components of Collision Search in the Zémor-Tillich Hash Function : New Instances and Reduced Variants with equivalent Security
Christophe Petit, Jean-Jacques Quisquater, Jean-Pierre Tillich and Gilles Zémor
CT-RSA 2009 - Topics in Cryptology, The Cryptographers' Track at the RSA Conference 2009
Paper. Slides at CT-RSA.
Full Cryptanalysis of LPS and Morgenstern Hash Functions
Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater
SCN 2008 - Sixth Conference on Security and Cryptography for Networks
Paper. Slides at SCN08.
Efficiency and Pseudo-Randomness of a Variant of Zémor-Tillich Hash Function
Christophe Petit, Nicolas Veyrat-Charvillon, and Jean-Jacques Quisquater
WIC'2008 - Symposium on Information Theory and
Communication in the BénéluxISECS'2008 - The 15th IEEE International Conference on Electronics, Circuits and
Systems (invited paper)
Paper. Slides at WIC08.
Cayley Hashes: A Class of Efficient Graph-based Hash Functions
Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater
Preprint (2007)
Paper.