## CryptoDB

### Omkant Pandey

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Towards a Unified Approach to Black-Box Constructions of Zero-Knowledge Proofs
📺
Abstract

General-purpose zero-knowledge proofs for all $\NP$ languages greatly simplify secure protocol design. However, they inherently require the code of the underlying relation. If the relation contains black-box calls to a cryptographic function, the code of that function must be known to use the ZK proof, even if both the relation and the proof require only black-box access to the function. Rosulek (Crypto'12) shows that non-trivial proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access.
We propose an alternative approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given one-way function $f$, we seek to construct a {\em new} one-way function $F$ given only black-box access to $f$, {\em and} an associated ZK protocol for proving non-trivial statements, such as range membership, over its output. We say that $F$, along with its proof system, is a {\em proof-based} one-way function. We similarly define proof-based versions of other primitives, specifically pseudo-random generators and collision-resistant hash functions.
We show how to construct proof-based versions of each of the primitives mentioned above from their ordinary counterparts under mild but necessary restrictions over the input. More specifically,
\begin{itemize}
\item We first show that if the prover entirely chooses the input, then proof-based pseudo-random generators cannot be constructed from ordinary ones in a black-box manner, thus establishing that some restrictions over the input are necessary.
\item We next present black-box constructions handling inputs of the form $(x,r)$ where $r$ is chosen uniformly by the verifier. This is similar to the restrictions in the widely used Goldreich-Levin theorem. The associated ZK proofs support range membership over the output as well as arbitrary predicates over prefixes of the input.
\end{itemize}
Our results open up the possibility that general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future without violating their black-box nature by instantiating them using proof-based primitives instead of ordinary ones.

2021

CRYPTO

Compact Ring Signatures from Learning With Errors
📺
Abstract

Ring signatures allow a user to sign a message on behalf of a ``ring'' of signers, while hiding the true identity of the signer. As the degree of anonymity guaranteed by a ring signature is directly proportional to the size of the ring, an important goal in cryptography is to study constructions that minimize the size of the signature as a function of the number of ring members.
In this work, we present the first compact ring signature scheme (i.e., where the size of the signature grows logarithmically with the size of the ring) from the (plain) learning with errors (LWE) problem. The construction is in the standard model and it does not rely on a trusted setup or on the random oracle heuristic. In contrast with the prior work of Backes
\etal~[EUROCRYPT'2019], our scheme does not rely on bilinear pairings, which allows us to show that the scheme is post-quantum secure assuming the quantum hardness of LWE.
At the heart of our scheme is a new construction of compact and statistically witness-indistinguishable ZAP arguments for NP $\cap$ coNP, that we show to be sound based on the plain LWE assumption. Prior to our work, statistical ZAPs (for all of NP) were known to exist only assuming \emph{sub-exponential} LWE. We believe that this scheme might find further applications in the future.

2015

TCC

2015

TCC

#### Program Committees

- PKC 2020
- Eurocrypt 2017
- PKC 2016
- TCC 2016

#### Coauthors

- Divesh Aggarwal (1)
- Shashank Agrawal (3)
- Prabhanjan Ananth (1)
- Rahul Chatterjee (1)
- Sanjam Garg (8)
- Vipul Goyal (3)
- Divya Gupta (4)
- Mohammad Hajiabadi (1)
- Yuval Ishai (1)
- Dakshita Khurana (1)
- Susumu Kiyoshima (2)
- Abishek Kumarasubramanian (1)
- Xiaohui Liang (2)
- Huijia Lin (1)
- Hemanta K. Maji (3)
- Giulio Malavolta (1)
- Peihan Miao (1)
- Ilya Mironov (4)
- Pratyay Mukherjee (1)
- Rafail Ostrovsky (2)
- Rafael Pass (3)
- Antigoni Polychroniadou (1)
- Manoj Prabhakaran (4)
- Omer Reingold (3)
- Yannis Rouselakis (1)
- Amit Sahai (5)
- Gil Segev (2)
- Sina Shiehian (1)
- Akshayaram Srinivasan (2)
- Wei-Lung Dustin Tseng (1)
- Salil P. Vadhan (1)
- Vinod Vaikuntanathan (1)
- Muthuramakrishnan Venkitasubramaniam (1)
- Ivan Visconti (1)
- Akshay Wadia (1)
- Mark Zhandry (1)