## CryptoDB

### Yi Deng

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Promise $\Sigma$-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups
Abstract

Threshold Signatures allow $n$ parties to share the ability of issuing digital signatures so that any coalition of size at least $t+1$ can sign, whereas groups of $t$ or less players cannot. The currently known class-group-based threshold ECDSA constructions are either inefficient (requiring parallel-repetition of the underlying zero knowledge proof with small challenge space) or requiring rather non-standard assumptions. In this paper, under \emph{standard assumptions} we present efficient threshold ECDSA protocols from encryption schemes based on class groups \emph{without parallel repeating the underlying zero knowledge proof}, yielding a significant efficiency improvement in the key generation over previous constructions (even those based on non-standard assumptions).
Along the way we introduce a new notion of \emph{promise} $\Sigma$-protocol that satisfies only a weaker soundness called \emph{promise extractability}. An accepting \emph{promise} $\Sigma$-proof for statements related to class-group-based encryptions does not establish the truth of the statement but provides security guarantees (promise extractability) that are sufficient for our applications. We also show how to simulate homomorphic operations on a (possibly invalid) class-group-based encryption whose correctness has been proven via our \emph{promise} $\Sigma$-protocol. We believe that these techniques are of independent interest and applicable to other scenarios where efficient zero knowledge proofs for statements related to class-group is required.

2020

ASIACRYPT

Individual Simulations
📺
Abstract

We develop an individual simulation technique that explicitly makes use of particular properties/structures of a given adversary's functionality. Using this simulation technique, we obtain the following results.
1. We construct the first protocols that break previous black-box barriers under the standard hardness of factoring, both of which are polynomial time simulatable against all a-priori bounded polynomial size distinguishers:
a)Two-round selective opening secure commitment scheme.
b)Three-round concurrent zero knowledge and concurrent witness hiding
argument for NP in the bare public-key model.
2. We present a simpler two-round weak zero knowledge and witness hiding argument for NP in the plain model under the sub-exponential hardness of factoring. Our technique also yields a significantly simpler proof that existing distinguisher-dependent simulatable zero knowledge protocols are also polynomial time simulatable against all distinguishers of a-priori bounded polynomial size.
The core conceptual idea underlying our individual simulation technique is an observation of the existence of nearly optimal extractors for all hard distributions: For any NP-instance(s) sampling algorithm, there exists a polynomial-size witness extractor (depending on the sampler's functionality) that almost outperforms any circuit of a-priori bounded polynomial size in terms of the success probability.

2018

PKC

On the Security of Classic Protocols for Unique Witness Relations
Abstract

We revisit the problem of whether the known classic constant-round public-coin argument/proof systems are witness hiding for languages/distributions with unique witnesses. Though strong black-box impossibility results are known, we provide some less unexpected positive results on the witness hiding security of these classic protocols:We give sufficient conditions on a hard distribution over unique witness NP relation for which all witness indistinguishable protocols (including all public-coin ones, such as ZAPs, Blum protocol and GMW protocol) are indeed witness hiding. We also show a wide range of cryptographic problems with unique witnesses satisfy these conditions, and thus admit constant-round public-coin witness hiding proof system.For the classic Schnorr protocol (for which the distribution of statements being proven seems not to satisfy the above sufficient conditions), we develop an embedding technique and extend the result of Bellare and Palacio to base the witness hiding property of the Schnorr protocol in the standalone setting on a relaxed version of one-more like discrete logarithm (DL) assumption, which essentially assumes there does not exist instance compression scheme for the DL problem, and show that breaking this assumption would lead to some surprising consequences, such as zero knowledge protocols for the AND-DL language with extremely efficient communication and highly non-trivial hash combiner for hash functions based on the DL problem. Similar results hold for the Guillou-Quisquater protocol.

2008

EPRINT

On Resettably-Sound Resttable Zero Knowledege Arguments
Abstract

We study the simultaneous resettability problem, namely whether resettably-sound resettable ZK arguments for non-trivial languages exist (posed by Barak et al. [BGGL FOCS'01]), in both the plain model and the bare public-key (BPK for short) model. Under
general hardness assumptions, we show:
1. in the BPK model, there exist constant-round (full-fledged) resettably-sound resettable ZK arguments for NP.
This resolves a main problem in this model that remained open since the Micali and Reyzin's identification of notions of soundness [MR Crypto 2001] in the BPK model.
2.in the plain model, there exist constant-round (unbounded) resettably-sound class-bounded resettable ZK (as defined by Deng and Lin in [DL Eurocrypt 2007]) arguments for NP.
This improves the previous result of Deng and Lin [Eurocrypt 2007] in that the DL construction for class-bounded resettable ZK argument achieves only a weak notion of resettable-soundness.
The crux of these results is a construction of constant-round instance-dependent (full-fledged) resettably-sound resettable WI argument of knowledge (IDWIAOK for short) for any NP statement of the form x_0\in L_0 or x_1\in L_1, a notion also introduced by Deng and Lin [Eurocrypt 2007], whose construction, however, obtains only weak resettable-soundness when x_0\notin L_0.
Our approach to the simultaneous resettability problem in the BPK model is to make a novel use of IDWIAOK, which gives rise to an elegant structure we call \Sigma-puzzles. Given the fact that all previously known resettable ZK arguments in the BPK model can be achieved in the
plain model when ignoring round complexity, we believe this approach will shed light on the simultaneous resettability problem in the plain model.

2007

EUROCRYPT

2006

EPRINT

Resettable Zero Knowledge in the Bare Public-Key Model under Standard Assumption
Abstract

In this paper we resolve an open problem regarding resettable zero
knowledge in the bare public-key (BPK for short) model: Does there
exist constant round resettable zero knowledge argument with
concurrent soundness for $\mathcal{NP}$ in BPK model without
assuming \emph{sub-exponential hardness}? We give a positive answer
to this question by presenting such a protocol for any language in
$\mathcal{NP}$ in the bare public-key model assuming only
collision-resistant hash functions against \emph{polynomial-time}
adversaries.

2006

EPRINT

Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model
Abstract

We consider a type of zero-knowledge protocols that are of interest
for their practical applications within networks like the Internet:
efficient zero-knowledge arguments of knowledge that remain secure
against concurrent man-in-the-middle attacks. As negative results in
the area of concurrent non-malleable zero-knowledge imply that
protocols in the standard setting (i.e., under no setup assumptions)
can only be given for trivial languages, researchers have studied
such protocols in models with setup assumptions, such as the common
reference string (CRS) model. This model assumes that a reference
string is honestly created at the beginning of all interactions and
later available to all parties (an assumption that is satisfied, for
instance, in the presence of a trusted party).
A growing area of research in Cryptography is that of reducing the
setup assumptions under which certain cryptographic protocols can be
realized. In an effort to reduce the setup assumptions required for
efficient zero-knowledge arguments of knowledge that remain secure
against concurrent man-in-the-middle attacks, we consider a model,
which we call the Authenticated Public-Key (APK) model. The APK
model seems to significantly reduce the setup assumptions made by the CRS model
(as no trusted party or honest execution of a centralized algorithm
are required), and can be seen as a slightly stronger variation of
the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a
weaker variation of the registered public-key model used in \cite{BCNP}.
We then define and study man-in-the-middle attacks in the APK model.
Our main result is a constant-round concurrent non-malleable
zero-knowledge argument of knowledge for any polynomial-time
relation (associated to a language in $\mathcal{NP}$), under the
(minimal) assumption of the existence of a one-way function family.
We also show time-efficient instantiations of our protocol, in which
the transformation from a 3-round honest-verifier zero-knowledge
argument of knowledge to a 4-round concurrently non-malleable
zero-knowledge argument of knowledge for the same relation incurs
only $\mathcal{O}(1)$ (precisely, a {\em small} constant) additional
modular exponentiations, based on known number-theoretic
assumptions. Furthermore, the APK model is motivated by the
consideration of some man-in-the-middle attacks in models with setup
assumptions that had not been considered previously and might be of
independent interest.
We also note a negative result with respect to further reducing the
setup assumptions of our protocol to those in the (unauthenticated)
BPK model, by showing that concurrently non-malleable zero-knowledge
arguments of knowledge in the BPK model are only possible for
trivial languages.

#### Program Committees

- PKC 2019

#### Coauthors

- Yu Chen (2)
- Sherman S. M. Chow (1)
- Giovanni Di Crescenzo (1)
- Dengguo Feng (1)
- Vipul Goyal (1)
- Dongdai Lin (5)
- Shunli Ma (1)
- Baodong Qin (1)
- Amit Sahai (1)
- Xuyang Song (2)
- Hailong Wang (1)
- Xiang Xie (1)
- Jingyue Yu (1)
- Moti Yung (1)
- Xinxuan Zhang (1)
- Jiang Zhang (1)