Quantum computers, still in the development stage, will introduce unprecedented computational power and present new threats and opportunities for cryptography.
In the first part of this talk, we discuss the security of cryptographic functions against the large-scale quantum computer, especially with in the prescence of preprocessing. We show that the cryptographic problems regarding hash functions are secure in the presence of precomputed (quantum) data, resolving an open problem suggested by Nayebi, Aaronson, Belovs, and Trevisan. As a corollary, we prove the complexity-theoretic statement BQP/qpoly≠NP∩coNP relative to an oracle, resolving an open problem posed by Aaronson. We also give a new quantum preprocessing algorithm for those problems.
The second part of this talk presents new constructions of the quantum bit-commitment scheme and efficient conversion of hiding and binding commitment. Interestingly, our conversion is based on a recent theorem of Aaronson, Atia, and Susskind, whose original motivation was quantum gravity.

발표시간 10:00 ~