M.Sc Thesis

M.Sc StudentIzmerly Oleg
SubjectModern Cryptography in a Quantum World
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Tal Mor


Public key encryption is a cryptographic system that uses two keys - a public key known to everyone and a private or secret key known only to the recipient of the message. In order to send a secure message, one uses a public key to encrypt the message. This message can be decrypted using a secret key. An important element of the public key system is that the public and private keys are related in such a way that only the public key can be used to encrypt messages and only the corresponding private key can be used to decrypt them. Moreover, it is virtually impossible to deduce the private key from the public one.

In a quantum world the main candidates for public key encryption (those based on factoring problems and DLOG) are broken. We investigate some of the remaining candidates.

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 hard also in a quantum environment. Recently, Regev introduced a new public key cryptosystem, based on the same assumption. In this paper we present chosen ciphertext attacks against all three cryptosystems. Our attacks show that these cryptosystems are totally insecure against chosen ciphertext attacks, because the private keys can be recovered in polynomial time. We discuss various suggested ways of protection against such attacks, and we discuss the relation to the reaction attack of Hall, Goldberg and Schneier.