## 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

2008

EPRINT

Non-black-box Techniques Are Not Necessary for Constant Round Non-malleable Protocols
Abstract

Recently, non-black-box techniques have enjoyed great success in cryptography. In particular, they have led to the construction of \emph{constant round} protocols for two basic cryptographic tasks (in the plain model): non-malleable zero-knowledge (NMZK) arguments
for NP, and non-malleable commitments. Earlier protocols, whose security proofs relied only on black-box techniques, required non-constant (e.g., $O(\log n)$) number of rounds. Given the inefficiency (and complexity) of existing non-black-box techniques, it is natural to ask whether they are \emph{necessary} for achieving constant-round non-malleable cryptographic protocols.
In this paper, we answer this question in the \emph{negative}. Assuming the validity of a recently introduced assumption, namely
the \emph{Gap Discrete Logarithm} (Gap-DL) assumption [MMY06], we construct a constant round \emph{simulation-extractable} argument system for NP, which implies NMZK. The Gap-DL assumption also leads to a very simple and natural construction of \emph{non-interactive non-malleable commitments}. In addition, plugging our simulation-extractable argument in the construction of Katz, Ostrovsky, and
Smith [KOS03] yields the first $O(1)$-round secure multiparty computation with a dishonest majority using only black-box techniques.
Although the Gap-DL assumption is relatively new and non-standard, in
addition to answering some long standing open questions, it brings a
new approach to non-malleability which is simpler and very natural. We also demonstrate that \odla~holds unconditionally against \emph{generic} adversaries.

2007

EPRINT

Private Locally Decodable Codes
Abstract

We consider the problem of constructing efficient locally decodable
codes in the presence of a computationally bounded adversary.
Assuming the existence of one-way functions, we construct {\em
efficient} locally decodable codes with positive information rate
and \emph{low} (almost optimal) query complexity which can correctly
decode any given bit of the message from constant channel error rate
$\rho$. This compares favorably to our state of knowledge
locally-decodable codes without cryptographic assumptions. For all
our constructions, the probability for any polynomial-time
adversary, that the decoding algorithm incorrectly decodes any bit
of the message is negligible in the security parameter.

2007

EPRINT

Precise Concurrent Zero Knowledge
Abstract

\emph{Precise zero knowledge} introduced by Micali and Pass
(STOC'06) guarantees that the view of any verifier $V$ can be
simulated in time closely related to the \emph{actual} (as opposed
to worst-case) time spent by $V$ in the generated view. We provide
the first constructions of precise concurrent zero-knowledge
protocols. Our constructions have essentially optimal precision;
consequently this improves also upon the previously tightest
non-precise concurrent zero-knowledge protocols by Kilian and
Petrank (STOC'01) and Prabhakaran, Rosen and Sahai (FOCS'02) whose
simulators have a quadratic worst-case overhead.
Additionally, we achieve a statistically-precise concurrent
zero-knowledge property---which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions;
as such we obtain the first (even non-precise)
concurrent zero-knowledge protocols which handle verifiers
participating in a super-polynomial number of concurrent executions.

2006

EPRINT

Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data
Abstract

As more sensitive data is shared and stored by third-party sites on
the Internet, there will be a need to encrypt data stored at these
sites. One drawback of encrypting data, is that it can be
selectively shared only at a coarse-grained level (i.e., giving
another party your private key). We develop a new cryptosystem for
fine-grained sharing of encrypted data that we call Key-Policy
Attribute-Based Encryption (KP-ABE). In our cryptosystem, ciphertexts
are labeled with sets of attributes and private keys are associated
with access structures that control which ciphertexts a user is able
to decrypt. We demonstrate the applicability of our construction to
sharing of audit-log information and broadcast encryption. Our
construction supports delegation of private keys which subsumes
Hierarchical Identity-Based Encryption (HIBE).

#### Program Committees

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

#### Coauthors

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