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.