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.