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:

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

**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/.

## No comments:

## Post a Comment