The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence
Miklós Ajtai, Cynthia Dwork · 2007
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 Õ(n²)-unique shortest vector problem for lattices, and requires a public key of size at most O(n⁴) bits. The new cryptosystem generalizes a conceptually simple modification of the “Ajtai-Dwork” cryptosystem. We provide a unified treatment of the two cryptosystems.