Use in cryptography Lattice problem

average case hardness of problems forms basis proofs-of-security cryptographic schemes. however, experimental evidence suggests np-hard problems lack property: worst case hard. many lattice problems have been conjectured or proven average-case hard, making them attractive class of problems base cryptographic schemes on. moreover, worst-case hardness of lattice problems have been used create secure cryptographic schemes. use of worst-case hardness in such schemes makes them among few schemes secure against quantum computers.

the above lattice problems easy solve if algorithm provided basis. lattice reduction algorithms aim, given basis lattice, output new basis consisting of relatively short, orthogonal vectors. lenstra–lenstra–lovász lattice basis reduction algorithm (lll) efficient algorithm problem output reduced lattice basis in polynomial time. algorithm , further refinements used break several cryptographic schemes, establishing status important tool in cryptanalysis. success of lll on experimental data led belief lattice reduction might easy problem in practice. however, belief challenged when in late 1990s, several new results on hardness of lattice problems obtained, starting result of ajtai.

in seminal papers, ajtai showed svp problem np-hard , discovered connections between worst-case complexity , average-case complexity of lattice problems. building on these results, ajtai , dwork created public-key cryptosystem security proven using worst case hardness of version of svp, making first result have used worst-case hardness create secure systems.