Quantum Security and Fiat-Shamir for Cryptographic Protocols

Abstract

This thesis presents new results on the security of cryptographic protocols in the quantum setting and the Fiat-Shamir heuristic for removing interaction. - 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. We give 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. - Quantum Secure Computation from One-Way Functions. Our second result concerns 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. - The Security of Fiat-Shamir. The final part of this thesis investigates 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. Our final set of results raises the possibility that natural identification protocols can be compiled with simple, non-cryptographic Fiat-Shamir hash functions.