M.Sc Student | Oleg Izmerly |
---|---|

Subject | Modern Cryptography in a Quantum World |

Department | Department of Computer Science |

Supervisor | Professor Mor Tal |

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.