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.
|10:30 – 11:30.||Nick Spooner, BU |
Proof-Carrying Data without Succinct Arguments
|11:45 – 12:45.||Dima Kogan, Stanford |
Private Information Retrieval with Sublinear Online Time
|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
Justin Holmgren, NTT Research|
Error Correcting Codes for Uncompressed Messages
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.