Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR07-097 | 8th October 2007 00:00

#### The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

TR07-097
Authors: Miklos Ajtai, Cynthia Dwork
Publication: 11th October 2007 07:18
Keywords:

Abstract:

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 simple modification of the
Ajtai-Dwork'' cryptosystem. We provide a unified treatment of the
two cryptosystems.

ISSN 1433-8092 | Imprint