Friday, Feb 12 (Virtual)

When: Friday, Feb 12, 2021.

Where: Virtual: A zoom link will be sent to the e-mail list. If you do not receive it, e-mail the organizers to ask for one.

Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.

Program:

10:30 – 11:30.	Nick Spooner, BU Proof-Carrying Data without Succinct Arguments video
11:45 – 12:45.	Dima Kogan, Stanford Private Information Retrieval with Sublinear Online Time video
12:45 – 1:30.	Lunch
1:30 – 3:15.	Alex Bredariol Grilo (CNRS/Sorbonne) and James Bartusek (UC Berkeley) (double feature with 15 min break in the middle) Secure Computation is in MiniQCrypt video
3:30-4:30.	Justin Holmgren, NTT Research Error Correcting Codes for Uncompressed Messages video

Abstracts:

Speaker: Nick Spooner, BU
Title: Proof-Carrying Data without Succinct Arguments

Abstract: Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Prior approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this talk I will describe how to obtain PCD without relying on SNARKs. In particular, we construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. We then exploit this new framework to achieve a more efficient PCD construction, by giving an accumulation scheme for a non-interactive argument of knowledge for R1CS with constant verification time. Our results are supported by a modular and efficient implementation.

Speaker: Dima Kogan (Stanford)
Title: Private Information Retrieval with Sublinear Online Time

Speaker: Alex Bredariol Grilo (CNRS/Sorbonne) and James Bartusek (UC Berkeley)
Title: Secure Computation is in MiniQCrypt

Abstract: MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. This talk will show that simulation-secure oblivious transfer is in MiniQCrypt, and thus that secure multi-party computation of any quantum functionality is in MiniQCrypt. The main technical contribution is a construction of extractable and equivocal bit commitment from quantum-secure one-way functions, which is used to instantiate the Bennet-Brassard-Crépeau-Skubiszewska (CRYPTO 91) framework to yield simulation-secure OT.

Speaker: Justin Holmgren (NTT Research)
Title: Error Correcting Codes for Uncompressed Messages

Abstract: Most types of messages we transmit (e.g., video, audio, images, text)
are not fully compressed, since efficient compression algorithms
can fail to reach the information-theoretic limit. In this
work, we study the transmission of partially compressed messages
over a noisy channel, noting that these messages may have additional
structure that is unused by standard error correcting codes.

We introduce a model in which “well-formed” messages comprise a
small fraction of all strings, and are recognizable. In this model,
we construct a (probabilistic) encoding procedure that achieves
better tradeoffs between data rates and error-resilience (compared to
just applying a standard error correcting code).

Surprisingly, our techniques also yield better tradeoffs in the standard setting
where all binary strings are valid messages.