On the computational hardness needed for quantum cryptography
, Boston University
Date: Friday, September 30, 2022
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Event Type: Seminar
Room Description: 32-G822
Host: Vinod Vaikuntanathan , CSAIL MIT
Contact: Felicia Raton, firstname.lastname@example.org
Speaker URL: None
TALK: On the computational hardness needed for quantum cryptography
In the classical model of computation, it is well established that one-way functions (OWF) are essential for almost every computational cryptographic application. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether a minimal primitive exists remains open.
We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of distributions. Building on the work of Yan (2022) which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary and sufficient for a large class of quantum-cryptographic applications. Specifically, while it was known how to construct commitments schemes, oblivious transfer, and general secure multiparty computation from any EFI, we show how to construct EFI pairs from minimalistic versions of each one of these primitives. We also construct from EFI quantum computational zero knowledge (QCZK) proofs for all of QIP, and construct EFI pairs from essentially any non-trivial QCZK.
This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.
Algorithms & Theory
Created by Mark J. Pearrow at Thursday, September 22, 2022 at 2:36 PM.