We describe a public-key cryptosystem with worst-case/average case
equivalence. The cryptosystem has an amortized plaintext to
ciphertext expansion of $O(n)$, relies on the hardness of the
$\tilde O(n^2)$-unique shortest vector problem for lattices, and
requires a public key of size at most $O(n^4)$ bits. The new
cryptosystem generalizes a conceptually ... more >>>

A zap is a two-round, witness-indistinguishable protocol in which
the first round, consisting of a message from the verifier to the
prover, can be fixed ``once-and-for-all" and applied to any instance,
and where the verifier does not use any private coins.
We present a zap for every language in NP, ... more >>>

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose length ... more >>>