Omar Fawzi, McGill University
The goal of two-party cryptography is to enable Alice and Bob to solve tasks in cooperation even if they do not trust each other. Examples of such tasks include bit commitment, coin flipping and oblivious transfer. Unfortunately, it has been shown that even using quantum communication, none of these tasks can be implemented when the adversary is completely general.
Instead of making computational assumptions based on complexity-theoretic conjectures, the bounded quantum-storage model introduced in 2005 takes advantage of the difficulty of building reliable quantum memories to establish secure two-party computation. More precisely, it was shown that if the cheating party’s storage device is such that it can store at most half of the qubits communicated during the protocol, then security can be achieved. Here, we push the range where security is possible to its limit: security is possible as soon as the adversary’s ability to store quantum information is less than the number of qubits communicated during the protocol.