Bar-Ilan Winter School on Cryptography - New trapdoors for Lattices. Simpler, Tighter, Faster, Smaller

This week some members of the group have been in Tel Aviv for the 2nd Bar-Ilan Winter School on Cryptography - Lattice-based Cryptography and Applications. The school was really well organized and useful: the programme was diversified (basics and hard problems on lattices, cryptographic constructions based on lattices, recent advances in fully homomorphic encryption), yet coherent and interesting for everyone.

In the session "Trapdoors and Application'', Chris Peikert presented some aspects of the joint work with Daniele Micciancio ([MP2012]) which will be published at Eurocrypt 2012.

The main idea of this work is a new method of generating random lattices  Λ┴(A) (defined by an uniformly random matrix A  in Z_q^{n x m}) together with an associated secret "strong''  trapdoor  ([GPV08])  S in Z_q^{m x m}, i.e.  short basis for Λ┴(A).  Such strong trapdoors are then used to give specialized inversion algorithms for the functions

                 f_A (x) = Ax  mod q    and   g_A (s; e) = s^t A + e^t      mod q

where  q=poly(n)  and   x, e are short integer vectors.

Recall that many cryptographic applications need to sample preimages for the SIS function f_A and/or invert the LWE function g_A  (Hash-and-sign digital signatures [GPV08], Standard Model signatures [CHKP10, R10, Boy10 ], SM CCA-secure encryption [PVW08,  Pei09], SM (H)IBE [GPV08, CHKP10, ABB10a , ABB10b]), and that general methods to solve these tasks are already known ([Bab85] for inverting  g_A  and [Klein01Klein00, GPV08, Pei10] for preimage sampling of  f_A) but they are complex and they trade quality for efficiency.

The general idea of the new method of trapdoor generation is the following. They design a fixed well-structured  public lattice defined by a ``gadget'' matrix  G for which the associated functions f_G and g_G admit fast, parallel and high-quality inversion algorithms.
Then they randomize G in two steps:

1. define a semi-random matrix  B = [ A |  G] for uniform A in  Z^{n x m'},  m' sufficiently large; 
2. apply to this matrix  B a  "nice'' unimodular transformation T and let  A =  B T.
    

 At this point the unimodular transformation  will be a trapdoor for A, and preimage sampling for   f_A and inversion of  g_A reduces efficiently to the corresponding tasks for  f_G and g_G.

It is worth to note that for G=0 we get Ajtai's original method ([Ajt96]) for constructing a random A together with a ``weak'' trapdoor of one or more short vectors (but not a full basis), while the comparison with the GGH approach ([GGH97]) is not appropriate as in GGH the private and public
lattices are the same.

The new trapdoor is an easily generated unimodular transformation instead of a short basis of a lattice as in  Ajt99 and AP09, but is at least as powerful since we can efficiently construct a basis for Λ┴(A) from a basis of Λ┴(G) and T. This new method does not require computations of Hermite normal forms or matrix inverses but only one matrix multiplication and the  inversion operations drastically decrease in comparison with the prior and general algorithms for these tasks.

The slides and the video of  the lecture will be available in the school website http://crypto.biu.ac.il/winterschool2012/.