Upgrade 2021: CIS LAB Speakers

September 21, 2021 // Upgrade 2021: CIS LAB Speakers

Towards Accountability in CRS Generation

Vipul Goyal, Senior Scientist, NTT Research Cryptography & Information Security


Various useful cryptographic primitives are known to be unachievable unless the parties involved share a Common Reference String (CRS). It is customary to use a CRS generated by a trusted authority A, but in our cynical modern age, when elected leaders and major corporations have so often been found to have betrayed the public trust, can any authority be trusted without some form of accountability?

Previous approaches have concentrated on technical means of mitigating the threat of an untrustworthy A. At UPGRADE 2021, Dr. Vipul Goyal, a Senior Scientist with NTT Research, presented joint work with colleagues P. Ananth (UCSB), G. Asharov (Bar-Ilan University) and H. Dahari (Weizmann Institute) to address the problem of adding accountability to a CRS-generating authority, so that A might expect misbehavior to result in a negative outcome.

Goyal models a corrupt A which uses a backdoor to its CRS-generation process to enable it to recover private information from an encrypted transcript (presumed to be available to an eavesdropper), and subsequently makes that information available to the eavesdropper in return for payment. The response is to use a pair of entities, both probabilistic polynomial-time algorithms, called the Extractor and the Judge.

The Extractor poses as an eavesdropper offering payment for private information obtained by A via the backdoor. It is assumed that A will abort the exchange if it suspects the identity of the Extractor (many of the technical complications in the proofs of the results arise from the need to disguise the Extractor). The Judge subsequently ensures that any private information obtained could not have been obtained honestly except with negligible probability – to avoid defaming an honest A. A successful ‘sting’ of this form provides a cryptographic proof of the untrustworthiness of A.

Results obtained include a proof that there exist cryptographic primitives for which no such accountability approach can be successful, but also proofs that for other well-known primitives and under certain standard assumptions, this approach can work with a probability g which is polynomially related to the probability f of success of A’s backdoor. These positive results apply specifically to two-party computation and to non-interactive zero-knowledge proof.

Goyal concluded by mentioning a selection of open problems concerned with the concept of accountability in cryptography.

Click below for the full transcript.


Vipul Goyal

Senior Scientist, NTT Research Cryptography & Information Security

Vipul Goyal is a senior scientist at NTT Research and an Associate Professor in the Computer Science Department at CMU. Previously, he was a researcher in the Cryptography and Complexity group at Microsoft Research, India. He received his PhD in Computer Science from University of California, Los Angeles in Dec 2009. He received his B.Tech. in Computer Science from Indian Institute of Technology (BHU), Varanasi. He is broadly interested in all areas of cryptography (and in theoretical computer science in general). Currently his research topics include secure multi-party computation, non-malleable cryptography, and foundations of blockchains.  Dr. Goyal is a winner of several honors including a 2016 ACM CCS test of time award, a Microsoft Research graduate fellowship, and, a Google outstanding graduate student award. He was named to the Forbes magazine “30 under 30” list of people changing science and healthcare in 2013.