سخنرانی دکتر محمد محمودی,
University of Virginia, USA
زمان: 3 دی, ساعت 15 الی 16
محل: vc.sharif.edu/ch/s-akbari
عنوان:
On the (Im)possibility of Key Agreement from Quantum-Accessed Random Oracles
چکیده:
Suppose two communicating parties A and B access a "random oracle", which is simply a function f:{0,1}^* -> {0,1} chosen at random, and agree on a "shared key" k. It is known [IR89,BM09] that in this case an eavesdropper Eve who only sees their exchanged messages can find k with constant probability by asking ~n^2 queries. This result has fundamental implications on the limitations of basing public-key encryption on private-key encryption. We study a variant of this question when A and B can call f in quantum superposition and show that under a natural conjecture regarding low degree polynomials, again an eavesdropper can find the key using n^O(1) queries. The implication is that, if the conjecture is true, one cannot use classical communication and quantum computation to base public-key encryption on private-key encryption in a black-box way.

The talk will assume no familiarity with quantum computation.

Based on joint work with: Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, and Yao-Ting Lin