On the computational hardness needed for quantum cryptography

Speaker: Luowen Qian , Boston University

Date: Friday, September 30, 2022

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location:

Event Type: Seminar

Room Description: 32-G822

Host: Vinod Vaikuntanathan , CSAIL MIT

Contact: Felicia Raton, fraton@mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Cryptography and Information (CIS) Seminar 2022.

Created by Mark J. Pearrow at Thursday, September 22, 2022 at 2:36 PM.