Secure multi-party computation in MiniQCrypt

Alex B. Grilo - CNRS/Sorbonne Université

April 9, 2021, 2:30 p.m. - April 9, 2021, 3:30 p.m.

Zoom (see link below)

Hosted by: Claude Crepeau


One of the main goals of theoretical cryptography is to implement cryptographic primitives from the weakest possible assumption to achieve more robust security. Unfortunately, this is not always possible. For example, the celebrated result of Impagliazzo-Rudich'91 implies that secure multi-party computation cannot be implemented from one-way functions (i.e., functions that are easy to compute but hard to invert). On the other hand, Crépeau-Killian'88 and Bennet-Brassard-Crépeau-Skubiszewska'91 proposed a template of a protocol that would enable secure multi-party computation from one-way functions in the quantum setting. However, the security of such a protocol depends on the existence of bit-commitment schemes with simulation security, which was not previously known to exist from one-way functions. In this talk, I will present a recent quantum protocol that implements such a strong bit-commitment scheme, resulting in the fact that secure multi-party computation is in MiniQCrypt (the world where one-way functions exist and quantum resources are available).

This is based on a joint work with Huijia Lin, Fang Song, Vinod Vaikuntanathan, and on a concurrent and independent work by James Bartusek, Andrea Coladangelo, Dakshita Khurana, Fermi Ma. 


Alex B. Grilo is a CNRS researcher at LIP6 (CNRS/Sorbonne Université). Previously, he was a post-doc at CWI and QuSoft, a research fellow at the Simons Institute (UC Berkeley) and a PhD student at IRIF (CNRS/Université Paris Diderot) under the supervision of Iordanis Kerenidis. Alex is interested in (quantum) complexity theory and (quantum) cryptography, mostly in the interplay of both. Some problems of particular interest are the Quantum PCP conjecture, verifiable delegation of quantum computation by classical clients, and the interplay between quantum computation and classical complexity theory.

Zoom link: (zoom login required)

Reception after the talk in ohyay: