Quantum Computation and Information Seminar 

15/03/2013, 16:15 — 17:15 — Room P3.10, Mathematics Building
Tomoyuki Yamakami, University of Fukui

Quantum Hardcores and Quantum Public-Key Cryptosystems

We will cover two important notions in quantum cryptography and give their concrete examples: quantum hardcores and quantum public-key cryptosystems. 1) Hardcore functions have played an essential role in building a secure cryptosystem. They are closely associated with the list-decodability of certain codes. We establish a close relationship between quantum hardcore functions and quantum list-decoding. From three classical codes, we construct three new quantum hardcore functions for quantum one-way functions. 2) A private-key cryptosystem requires a large number of keys whereas a public-key cryptosystem needs only a single encoding key for all senders. To develop a large scale quantum network in a near future, it is thus desirable to build an efficient public-key quantum cryptosystem. We present the first quantum public-key cryptosystem that withstands any eavesdropper’s chosen plaintext quantum attack if a certain graph-theoretic problem cannot be solved efficiently by quantum computers.