arnab roy

Research Manager, Fujitsu Labs of America

Arnab Roy Presents a More Efficient Approach to NIZK: Quasi Adaptivity

Zero-Knowledge protocol is a valuable cryptographic tool in that it enables the proof of ownership of a digital object without revealing the digital contents of that object, or “the secret.” But implementations of zero-knowledge encryption can be computationally inefficient. It was this problem that two researchers – Charanjit S. Jutla of IBM T. J. Watson Research Center  and Arnab Roy, Research Manager, Fujitsu Laboratories – set out to address.


Roy gave a talk about their work at Upgrade 2020, the recent NTT Research Summit. (Watch Arnab Roy’s full presentation below.)


The motivation for Zero-Knowledge goes back to the heart of why we need cryptography, Roy said: identity, ownership, community and control. While much of cryptography exists to support controlled communication among individuals, he said today we also consider devices as extensions of individuals and corporations as communities of individuals.


“Here is how Zero-Knowledge fits in this picture,” Roy said. “What defines the boundary of an individual is the ability to hold a secret, which may be itself attached to the ownership of some asset. We want the ability to use the secret to prove ownership of this asset.”


But passing the secret from one party to another essentially announces ownership of the secret, he said. “Zero-Knowledge gives us tools to prove ownership without revealing the secret.”


This notion of proving ownership of a digital object without revealing the contents of the object was formalized and constructed by Goldwasser, Micali and Rackoff in the late 1980s. For the purposes of his talk, and the paper on which it was based, Roy focused on Non-Interactive Zero-Knowledge, or NIZK, which was first developed by Blum, Feldman and Micali (1988). While general Zero-Knowledge protocols can involve multiple rounds of back-and-forth communications, NIZK allows only a single message to be transmitted.


Jutla and Roy’s work defines a novel notion of “quasi-adaptive” NIZK proofs for probability distributions on parameterized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the language parameters. However, the simulation is required to be a single, uniform algorithm that works for a whole class of parameterized languages.


In his Upgrade 2020 talk, Roy focused on Linear Subspace Languages, a class of languages that is the basis of hardness assumptions like DDH and DLIN, which have proved useful in crypto constructions. This work improves on a breakthrough NIZK construction that Groth and Sahai presented at Eurocrypt 2008, he said, the first efficient construction for linear subspaces based on DDH and DLIN in bilinear groups.


“The quest remained to build even shorter NIZKs, he said. “Maybe there’s a way to increase efficiency at the cost of having a tailored CRS for each given language.”


The solution Jutla and Roy came up with involved language constants embedded into the CRS in such a way that the object functions as its own commitment. “So, we end up not needing any separate commitment in the proof itself. Our particular construction also needed fewer elements in the equation proof as well,” he said, making it more efficient. “On the flip side the CRS blows up to quadratic instead of constant.” Subsequent work by Jutla and Roy developed constant-sized NIZK proofs with linear size CRS.


For the full transcript of Arnab Roy’s presentation, click here.


Watch Arnab Roy’s full presentation below.

A Brief History of Quasi-Adaptive NIZKs


Arnab Roy,
Research Manager, Fujitsu Labs of America