[LM06] Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Authors: Vadim Lyubashevsky, Daniele Micciancio | Venue: FOCS 2006 | Source

Abstract

We investigate the average-case complexity of a generalization of the compact knapsack problem to arbitrary rings. This natural generalization turns out to be intimately related to the complexity of the shortest vector problem in cyclic lattices: if the shortest vector problem in cyclic lattices has a solution, then the generalized compact knapsack problem is computationally hard on average. We use this connection to build one-way functions whose security is based on the worst-case computational complexity of the shortest vector problem in cyclic lattices. These functions are considerably more efficient than previous constructions based on general (non-cyclic) lattices. As a key technical contribution, we also show that the Ring-SIS problem (finding short vectors in the kernel of a random ring element) is as hard as the worst-case shortest vector problem in ideal lattices.

BibTeX

Copy

@Inproceedings{ICALP:LyuMic06,
  author = {Vadim Lyubashevsky and Daniele Micciancio},
  title = {Generalized Compact {Knapsacks} Are Collision Resistant},
  pages = {144--155},
  editor = {Michele Bugliesi and Bart Preneel and Vladimiro Sassone and Ingo Wegener},
  booktitle = {ICALP 2006: 33rd International Colloquium on Automata, Languages and Programming, Part~II},
  volume = {4052},
  series = {Lecture Notes in Computer Science},
  address = {Venice, Italy},
  month = {jul~10--14},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2006},
  doi = {10.1007/11787006_13},
}