Rishab Goyal

FOCS Conference 2022 Conference Paper

Rate-1 Non-Interactive Arguments for Batch-NP and Applications

• Lalita Devadas
• Rishab Goyal
• Yael Tauman Kalai
• Vinod Vaikuntanathan

We present a rate-1 construction of a publicly verifiable non-interactive argument system for batch-NP (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of k NP statements each with an m-bit witness, has size $m+poly(\lambda, log k)$. In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size m. poly $(\lambda, \log k)$ (Choudhuri, Jain, and Jin, STOC 2021, following Kalai, Paneth, and Yang 2019). We show how to use our rate-l BARG scheme to obtain the following results, all under the LWE assumption: •A multi-hop BARG scheme for NP. •A multi-hop aggregate signature scheme (in the standard model). •An incrementally verifiable computation (IVC) scheme for arbitrary T-time deterministic computations with proof size poly $(\lambda, log T)$. Prior to this work, multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model; IVC schemes with proofs of size poly $(\lambda, T^{\epsilon})$ were known under a bilinear map assumption, and with proofs of size poly $(\lambda, log T)$ under non-standard knowledge assumptions or in the random oracle model.

STOC Conference 2018 Conference Paper

Collusion resistant traitor tracing from learning with errors

• Rishab Goyal
• Venkata Koppula
• Brent Waters

FOCS Conference 2017 Conference Paper

Lockable Obfuscation

• Rishab Goyal
• Venkata Koppula
• Brent Waters

In this paper we introduce the notion of lockable obfuscation. In a lockable obfuscation scheme there exists an obfuscation algorithm Obf that takes as input a security parameter, a program P, a message msg and lock value lck and outputs an obfuscated program oP. One can evaluate the obfuscated program oP on any input x where the output of evaluation is the message msg if P(x) = lck and otherwise receives a rejecting symbol. We proceed to provide a construction of lockable obfuscation and prove it secure under the Learning with Errors (LWE) assumption. Notably, our proof only requires LWE with polynomial hardness and does not require complexity leveraging. We follow this by describing multiple applications of lockable obfuscation. First, we show how to transform any attribute-based encryption (ABE) scheme into one in which the attributes used to encrypt the message are hidden from any user that is not authorized to decrypt the message. (Such a system is also know as predicate encryption with one-sided security.) The only previous construction due to Gorbunov, Vaikuntanathan and Wee is based off of a specific ABE scheme of Boneh. By enabling the transformation of any ABE scheme we can inherent different forms and features of the underlying scheme such as: multi-authority, adaptive security from polynomial hardness, regular language policies, etc. We also show applications of lockable obfuscation to separation and uninstantiability results. We first show how to create new separation results in circular encryption that were previously based on indistinguishability obfuscation. This results in new separation results from learning with error including a public key bit encryption scheme that it IND-CPA secure and not circular secure. The tool of lockable obfuscation allows these constructions to be almost immediately realized by translation from previous indistinguishability obfuscation based constructions. In a similar vein we provide random oracle uninstantiability results of the Fujisaki-Okamoto transformation (and related transformations) from the lockable obfuscation combined with fully homomorphic encryption. Again, we take advantage that previous work used indistinguishability obfuscation that obfuscated programs in a form that could easily be translated to lockable obfuscation.