Ajtai and Dwork proposed a public-key encryption scheme in 1996 which they proved secure under the assumption that the unique shortest vector problem is hard in the worst case. This cryptosystem and its extension by Regev are the only one known for which security can be proved under a worst case assumption, and as such present a particularly interesting case to study.

In this paper, we show statistical zero-knowledge protocols for statements of the form "plaintext m corresponds to ciphertext c" and "ciphertext c and c' decrypt to the same value" for the Ajtai-Dwork cryptosystem. We then show a interactive zero-knowledge proof of plaintext knowledge (PPK) for the Ajtai-Dwork cryptosystem, based directly on the security of the cryptosystem rather than resorting to general interactive zero-knowledge constructions. The witness for these proofs is the randomness used in the encryption.

References

[1] Shafi Goldwasser and Dmitriy Kharchenko. Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem. In Joe Kilian (Ed.): Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings. Lecture Notes in Computer Science 3378 Springer 2005.