Abstract. Modern cryptography is based on various building blocks such as one way functions with or without trapdoors, pseudo-random functions, one way permutations with or without trapdoors, etc. In a quantum world some of the main candidates for these building blocks are broken. For instance, the most popular public-key cryptosystem - RSA - is based on the difficulty of factoring large numbers and is broken (in principle) by a quantum computer. We investigate some of the remaining candidates, and discuss the resulting "modern cryptography in a quantum environment".

About half a decade ago Ajtai and Dwork (and later on, also Goldreich, Goldwasser and Halevi) proposed a public key cryptosystem that has a proven security under a plausible complexity assumption. The plausible assumption is that the so called unique shortest vector problem (u-SVP) is hard on the worst case. This problem is potentially still hard also in a quantum environment. Recently, Regev introduced a new (and much simpler) public key cryptosystem, based on the same u-SVP hardness assumption, but with improved parameters. Furthermore, Regev's cryptosystem is more practical due to its much higher efficiency.

In this short paper we present a chosen ciphertext attack (CCA) against Ajtai-Dwork's cryptosystem. The attacks against the other two cryptosystems are similar and are described in the journal version of our paper. Our attacks show that these cryptosystems are totally insecure against chosen ciphertext attacks, because the private keys can be recovered in polynomial time. We then discuss the possibility of making public key encryption (PKE) secure against chosen ciphertext attacks, without adding stronger assumptions than the assumption that u-SVP is hard; In particular, without adding the assumption of the existence of secure non-interactive zero knowledge proofs or the assumption of the existence of trap-door one way permutations, as there are no candidates yet for these generic protocols if the adversary holds a quantum computer.

We conclude that the current understanding of modern cryptography in a quantum environment can only suggest CCA-secure interactive-PKE, which is obviously weaker than CCA-secure PKE. Finally, we discuss the relation of our attack to the reaction attack of Hall, Goldberg and Schneier, which we only recently became aware of.

Full-text: PDF