Fermi Ma will present his FPO "Quantum Security and Fiat-Shamir for Cryptographic Protocols" on Tuesday, August 24, 2021 at 4pm via Zoom. Zoom link: https://princeton.zoom.us/j/97642906902 The members of his committee are as follows: Mark Zhandry (Adviser); Readers: Zeev Dvir, Ran Raz; Examiners: Sanjeev Arora, Gillat Kol, and Mark Zhandry. A copy of his thesis is available upon request. Please email gradinfo@cs.princeton.edu mailto:gradinfo@cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract: This talk will cover new results on the security of cryptographic protocols in the quantum setting and the Fiat-Shamir heuristic for removing interaction. (1) Quantum Rewinding. Many cryptosystems are proven secure by rewinding an interactive adversary to extract its responses across multiple invocations. Unfortunately, this technique only suffices for classical security, since recording the outputs of a quantum adversary may irreversibly damage its state. Obtaining a suitable quantum analogue of rewinding has been a long-standing open problem in post-quantum cryptography. In this talk, I will describe a general-purpose quantum rewinding procedure capable of extracting an unlimited number of responses from any quantum adversary; prior techniques were limited to a constant number. Our primary application is to prove that Kilian's succinct argument system for NP is post-quantum secure. (2) Quantum Secure Computation from One-Way Functions. Next, I will cover results on multi-party computation, a central primitive in cryptography that enables mutually distrusting parties to compute a shared function over their inputs while revealing no other information. We show 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 such an implication is not known, and is considered unlikely. (3) The Security of Fiat-Shamir. The final part of this talk will cover the soundness of the Fiat-Shamir heuristic, a powerful technique that uses a cryptographic hash function to remove interaction from certain cryptographic protocols. We consider two popular applications of Fiat-Shamir: building non-interactive succinct arguments from Kilian's protocol and obtaining digital signatures from a wide range of identification protocols. We demonstrate significant barriers to soundly instantiating Fiat-Shamir for Kilian's succinct arguments using any concrete Fiat-Shamir hash function. We also raise the interesting possibility that natural identification protocols can be compiled with simple, non-cryptographic Fiat-Shamir hash functions.