15/03/2013, 16:15 — 17:15 — Sala P3.10, Pavilhão de Matemática
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.
