Fermi Ma will present his Pre-FPO talk "Secure Computation in a Quantum World" on Friday, May 28, 2021 at 1PM via Zoom.

Zoom Link: https://princeton.zoom.us/j/99360445283

Fermi’s committee is as follows:

Examiners: Mark Zhandry (advisor), Sanjeev Arora, and Gillat Kol

Readers: Ran Raz and Zeev Dvir

All are welcome to attend.

Title: Secure Computation in a Quantum World

Abstract: This talk will cover new results on two central cryptographic tools — succinct arguments and multi-party computation — and novel aspects that arise given the emergence of  quantum computers.

(1) Quantum-Secure Succinct Arguments. A succinct argument enables an untrusted (but computationally bounded) prover to convince a verifier of any NP statement with total communication independent of the witness length. The security of all known succinct argument systems has only been established against classical attackers, as security relies on the ubiquitous “rewinding technique” from classical cryptography, which is not applicable to quantum adversaries. The lack of a general-purpose quantum rewinding technique has been a long-standing source of frustration in developing quantum-secure cryptosystems. In the first part of this talk, I will present the first general-purpose technique for rewinding a quantum attacker. This technique allows us to transfer classical rewinding-based proofs to the quantum setting, and proves that succinct arguments secure against quantum attackers exist under standard cryptographic assumptions.

(2) Multi-Party Quantum Computation from One-Way Functions. Another central primitive in classical cryptography is multi-party computation, which enables a group of mutually distrusting parties to compute a shared function over their inputs while revealing no other information. In the second part of this talk, I will describe new results showing that when all parties are quantum, secure multi-party computation can be based solely on the existence of the minimal cryptographic primitive: one-way functions. This is in stark contrast to the classical setting where no such implication is known.