Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Lattice-based cryptography:
TR07-133 | 20th November 2007
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

Trapdoors for Hard Lattices and New Cryptographic Constructions

We show how to construct a variety of ``trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient ``hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, ... more >>>

TR08-100 | 14th November 2008
Chris Peikert

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

We construct public-key cryptosystems that are secure assuming the
\emph{worst-case} hardness of approximating the length of a shortest
nonzero vector in an $n$-dimensional lattice to within a small
$\poly(n)$ factor. Prior cryptosystems with worst-case connections
were based either on the shortest vector problem for a \emph{special
class} of lattices ... more >>>

TR10-066 | 14th April 2010
Sanjeev Arora, Rong Ge

Learning Parities with Structured Noise

Revisions: 1

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we
have access to an oracle that, each time we press a button,
returns a random vector $ a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as
$a\cdot u +\eta$, where ... more >>>

ISSN 1433-8092 | Imprint