A Quantum Public-Key Cryptosystem - with a Brief Introduction to Quantum Computation

7^th February 2013, 16:00 Ashton Lecture Theatre
Dr. Tomoyuki Yamakami
Department of Information Science
University of Fukui
Japan

Abstract

Quantum computation is a new paradigm based on quantum physics and it was proven that quantum computers can easily break a popular cryptosystem RSA and several other cryptosystems. In an era of quantum computers, a new and powerful notion of quantum cryptography is much needed. In 1984, the first quantum cryptosystem--quantum key distribution scheme--emerged and it has been physically implemented using optical fibers. This is a scheme in which we securely send a secret key to a target receiver through a quantum channel.

However, quantum public-key cryptosystems are much more difficult to build. Here, we present the first concrete example of a quantum public-key cryptosystem in which we transfer a classical bit by encoding it into O(log n) quantum bits and transmitting them through an insecure quantum channel. Our cryptosystem was proven to be secure under a plausible assumption that the graph automorphism problem is rather difficult to solve on any quantum computer. This is based on a recently published work at Journal of Cryptology (vol.25, pp.528-555, 2012) with A. Kawachi, T. Koshiba, and H. Nishimura.

In this talk, we will review a foundation of quantum computation for the sake of non-specialists.