Spring 2020

One-Way Functions Imply Secure Computation in a Quantum World

Tuesday, Jul. 13, 2021 9:45 am10:30 am

Add to Calendar


Andrea Coladangelo (UC Berkeley)



The topic of this talk fits within the intriguing line of research that aims to use quantum information to build cryptographic primitives from weaker assumptions than is possible classically. I will talk about a recent result showing that, assuming quantum communication, quantum-hard one-way functions imply oblivious transfer, a central primitive in cryptography. In particular, the latter primitive is known to suffice for secure computation of arbitrary functionalities. In addition, our construction only makes black-box use of the one-way function. This result is in stark contrast with what is possible in the classical world, where it is known that one-way functions cannot imply oblivious transfer, when used in a black-box way.

This work is the result of a collaboration with James Bartusek, Dakshita Khurana and Fermi Ma, which started at "the Quantum Wave in Computing" semester.