International Association for Cryptologic Research

International Association
for Cryptologic Research


Yi Deng


Knowledge Encryption and Its Applications to Simulatable Protocols With Low Round-Complexity 📺
Yi Deng Xinxuan Zhang
We introduce a new notion of public key encryption, knowledge encryption, for which its ciphertexts can be reduced to the public-key, i.e., any algorithm that can break the ciphertext indistinguishability can be used to extract the (partial) secret key. We show that knowledge encryption can be built solely on any two-round oblivious transfer with game-based security, which are known based on various standard (polynomial-hardness) assumptions, such as the DDH, the Quadratic($N^{th}$) Residuosity or the LWE assumption. We use knowledge encryption to construct the first three-round (weakly) simulatable oblivious transfer. This protocol satisfies (fully) simulatable security for the receiver, and weakly simulatable security ($(T,\epsilon)$-simulatability) for the sender in the following sense: for any polynomial $T$ and any inverse polynomial $\epsilon$, there exists an efficient simulator such that the distinguishing gap of any distinguisher of size less than $T$ is at most $\epsilon$. Equipped with these tools, we construct a variety of fundamental cryptographic protocols with low round-complexity, assuming only the existence of two-round oblivious transfer with game-based security. These protocols include three-round delayed-input weak zero knowledge argument, three-round weakly secure two-party computation, three-round concurrent weak zero knowledge in the BPK model, and a two-round commitment with weak security under selective opening attack. These results improve upon the assumptions required by the previous constructions. Furthermore, all our protocols enjoy the above $(T,\epsilon)$-simulatability (stronger than the distinguisher-dependent simulatability), and are quasi-polynomial time simulatable under the same (polynomial hardness) assumption.
Non-Malleable Functions and their Applications
We formally study “non-malleable functions” (NMFs), a general cryptographic primitive which simplifies and relaxes “non-malleable one-way/hash functions” (NMOWHFs) introduced by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009) and refined by Baecher et al. (in: CT-RSA 2011, pp 268–283, 2011). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs. We formalize a game-based definition for NMFs. Roughly, a function f is non-malleable if given an image $$y^* \leftarrow f(x^*)$$ y ∗ ← f ( x ∗ ) for a randomly chosen $$x^*$$ x ∗ , it is hard to output a value y together with a transformation $$\phi $$ ϕ from some prefixed transformation class such that y is an image of $$\phi (x^*)$$ ϕ ( x ∗ ) under f . Our non-malleable notion is strong in the sense that only trivial copy solution $$(\mathsf {id}, y^*)$$ ( id , y ∗ ) is forbidden, where $$\mathsf {id}$$ id is the identity transformation. We also consider the adaptive notion, which stipulates that non-malleability holds even when an inversion oracle is available. We investigate the relations between non-malleability and one-wayness in depth. In the non-adaptive setting, we show that non-malleability generally implies one-wayness for poly-to-one functions but not vice versa. In the adaptive setting, we show that for most algebra-induced transformation classes, adaptive non-malleability (ANM) is equivalent to adaptive one-wayness (AOW) for injective functions. These results establish theoretical connections between non-malleability and one-wayness for functions and extend to trapdoor functions as well, resolving the open problems left by Kiltz et al. (in: Advances in cryptology—EUROCRYPT 2010, pp 673–692, 2010). We also study the relations between standard OW/NM and hinting OW/NM, where the latter notions are typically more useful in practice. Toward efficient realizations of NMFs, we give a deterministic construction from adaptive trapdoor functions as well as a randomized construction from all-but-one lossy functions and one-time signature. This partially solves an open problem posed by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009). Finally, we explore applications of NMFs in security against related-key attacks (RKA). We first show that, somewhat surprisingly, the implication AOW $$\Rightarrow $$ ⇒ ANM sheds light on addressing non-trivial copy attacks in RKA security. We then show that NMFs give rise to a generic construction of RKA-secure authenticated key derivation functions, which have proven to be very useful in achieving RKA security for numerous cryptographic primitives. Particularly, our construction simplifies and unifies the result due to Qin et al. (in: Public-key cryptography—PKC 2015, volume 9020 of LNCS. Springer, Berlin, pp 557–578, 2015).
Promise $\Sigma$-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups 📺
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.
Individual Simulations 📺
Yi Deng
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.
On the Security of Classic Protocols for Unique Witness Relations
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.

Program Committees

PKC 2021
PKC 2019