Blockchain Papers

Xiang Xie, Rui Xue, Minqian Wang

No abstract is available for this record.

Kai-Min Chung, Rafael Pass, Karn Seth

The simulation paradigm, introduced by Goldwasser, Micali and Racko , is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and su cient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional bene t of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

Chengdong Meng, Zhengyong Zhang, Rong Hu, Yongxiang Yang

DAA (Direct Anonymous Attestation) schemes are generally employed with the hardware of TPM to realize anonymous authentication. Basically, DAA schemes are based on group signatures. We propose a new DAA scheme based on a short group signature without encryption which departs from the traditional sign-encrypt-prove paradigm, only adopts an anonymous signature and non-interactive zero knowledge(NIZK) proofs. Compared to other DAA schemes at present, our scheme is approximately the most efficient and computational cost-saving with shorter signature length and easier signature generation. Our scheme also satisfies anonymity, trace ability and non-frame ability requirements.

Kai-Min Chung, Huijia Lin, Rafael Pass

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol is sound against uniform polynomial-time attackers, and relies on the existence of families of collision-resistant hash functions, and a new (but in our eyes, natural) falsifiable intractability assumption: Roughly speaking, that Micali’s non-interactive CS-proofs are sound for languages in P.

Ketan Mulmuley

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic varieties, the problem that lies at the heart of the foundational classification problem of algebraic geometry. Specifically: (1) It is shown that in characteristic zero black-box derandomization of PIT for diagonal depth three circuits brings the problem of derandomizing Noether's Normalization Lemma, for the ring of invariants of any explicit linear action of a classical algebraic group of constant dimension, from EXPSPACE (where it is currently) to P. Next it is shown that assuming the Generalized Riemann Hypothesis (GRH), instead of the black-box derandomization hypothesis, brings the problem from EXPSPACE to quasi-PH, instead of P. Thus black-box derandomization of diagonal depth three circuits takes us farther than GRH here on the basis of the current knowledge. Variants of the main implication are also shown assuming, instead of the black-box derandomization hypothesis in characteristic zero, Boolean lower bounds for constant-depth threshold circuits or uniform Boolean conjectures, in conjunction with GRH. These results may explain in a unified way why proving lower bounds or derandomization results for constant-depth arithmetic circuits in characteristic zero or constant-depth Boolean threshold circuits, or proving uniform Boolean conjectures without relativizable proofs has turned out to be so hard, and also why GRH has turned out to be so hard from the complexity-theoretic perspective. Thus this investigation reveals that the foundational problems of Geometry (classification and GRH) and Complexity Theory (lower bounds and derandomization) share a common root difficulty that lies at the junction of these two fields. We refer to it as the GCT chasm. (2) It is shown that black-box derandomization of PIT in a strengthened form implies derandomization of Noether's Normalization Lemma in a strict form for any explicit algebraic variety. (3) Conversely, it is shown that derandomization of Noether's Normalization Lemma in a strict form for specific explicit varieties implies this strengthened form of black box derandomization of PIT and its various variants. (4) A unified geometric complexity theory (GCT) approach to derandomization and classification is formulated on the basis of this equivalence.

Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti

We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.

Andrew Drucker

Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $\mathrm{OR}$-compression scheme for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some “target” language $L'$ if and only if $\bigvee_j [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$. Strong compression for SAT seems unlikely. Work of Harnik and Naor [SIAM J. Comput., 39 (2010), pp. 1667--1713] and Bodlaender, Downey, Fellows, and Hermelin [J. Comput. System Sci., 75 (2009), pp. 423--434] showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam [J. Comput. System Sci., 77 (2011), pp. 91--106] showed that if SAT is strongly OR-compressible, then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply nonuniform, statistical zero-knowledge proofs for SAT---an even stronger and more unlikely consequence than $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.

Jinguang Han, Willy Susilo, Yi Mu, Jun Yan

No abstract is available for this record.

Reza Sepahi, Ron Steinfeld, Josef Pieprzyk

No abstract is available for this record.

Jens Groth, Rafail Ostrovsky, Amit Sahai

Noninteractive zero-knowledge (NIZK) proof systems are fundamental primitives used in many cryptographic constructions, including public-key encryption secure against chosen ciphertext attack, digital signatures, and various other cryptographic protocols. We introduce new techniques for constructing NIZK proofs based on groups with a bilinear map. Compared to previous constructions of NIZK proofs, our techniques yield dramatic reduction in the length of the common reference string (proportional to security parameter) and the size of the proofs (proportional to security parameter times the circuit size). Our novel techniques allow us to answer several long-standing open questions in the theory of noninteractive proofs. We construct the first perfect NIZK argument system for all NP. We construct the first universally composable NIZK argument for all NP in the presence of an adaptive adversary. We construct a non-interactive zap for all NP, which is the first that is based on a standard cryptographic security assumption.

Zongyang Zhang, Zhenfu Cao

No abstract is available for this record.

David Galindo, Javier Herranz, Jorge L. Villar

We introduce the concept of identity-based encryption (IBE) with master key-dependent chosenplaintext (mKDM-sID-CPA) security. These are IBE schemes that remain secure even after the adversary sees encryptions, under some initially selected identities, of functions of the master secret key(s). We then propose a generic construction of chosen-ciphertext secure key-dependent encryption (KDM-CCA) schemes in the public key setting starting from mKDM-sID-CPA secure IBE schemes. This is reminiscent to the celebrated work by Canetti, Halevi and Katz (Eurocrypt 2004) on the traditional key-oblivious setting. Previously only one generic construction of KDM-CCA secure public key schemes was known, due to Camenisch, Chandran and Shoup (Eurocrypt 2009), and it required non-interactive zero knowledge proofs (NIZKs). Our transformation shows that NIZKs are not intrinsic to KDM-CCA public key encryption. Additionally, we are able to instantiate our new concept under the Rank assumption on pairing groups and for affine functions of the secret keys. The scheme builds on previous work by Boneh, Halevi, Hamburg and Ostrovsky (Crypto 2008). Our concrete schemes are only able to provide security against a bounded number of encryption queries, which is enough in some practical scenarios. As a corollary we obtain a KDM-CCA secure public key encryption scheme, in the standard model, whose security reduction to a static assumption is independent of the number of challenge queries. As an independent contribution, we give new and better reductions between the Rank problem (previously named as Matrix DDH problem) and the Decisional Linear and the Decisional 3-Party Diffie-Hellman problems.

Dana Dachman-Soled, Abhishek Jain, Yael Tauman Kalai, Adriana López-Alt

The Fiat-Shamir paradigm [CRYPTO’86] is a heuristic for converting 3-round identification schemes into signature schemes, and more generally, for collapsing rounds in public-coin interactive protocols. This heuristic is very popular both in theory and in practice, and many researchers have studied its security (and insecurity). In this work, we continue this study. As our main result, we show that for many well studied interactive proofs (and arguments) the soundness of the Fiat-Shamir heuristic cannot be proven via a black-box reduction to any falsifiable assumption. Previously, the insecurity of this paradigm was exemplified only when applied to interactive arguments (as opposed to proofs). Using similar techniques, we also show a black-box impossibility result for Micali’s CSproofs [FOCS’94]. Namely, we prove that there exist PCPs such that for “sufficiently hard” NP languages, Micali’s CS-proof cannot be proven sound via black-box reduction to any falsifiable assumption. These results are obtained by extending the impossibility of two-message zero knowledge protocols due to Goldreich and Oren [J. Cryptology’94].

Prabhanjan Ananth, Raghav Bhaskar, Vipul Goyal, Vanishree Rao

The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001). An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin’s transformation can be applied to any so called 3-round “Fiat-Shamir proof of knowledge’ ’ and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to

Bo Zhang, Fangguo Zhang

Abstract. Similarity coefficients play an important role in many application aspects. Recently, a privacy-preserving similarity coefficients protocol for binary data was proposed by Wong and Kim (Computers and Mathematics with Application 2012). In this paper, we show that their protocol is not secure, even in the semi-honest model, since the client can retrieve the input of the server without deviating from the protocol. Also we propose a secure similarity coefficients computation in the presence of malicious adversaries, and prove it using the standard simulation-based security definitions for secure two-party computation. We also discuss several extensions of our protocol for settling other problems. Technical tools in our protocol include zero-knowledge proofs and distributed ElGamal encryption.

Alfredo De Santis, Moti Yung

We develop a non-interactive proof-system which we call “Metaproof ” (µ-NIZK proof system); it provides a proof of “the existence of a proof to a statement”. This metamathematical notion indeed seems redundant when we deal with proving N P statements, but in the context of zero-knowledge theory and cryptography it has a large variety of applications. Combined with another tool we develop which we call “on-line simulatable NIZK proofsystem”, it is the key tool used to solve the open problem of the existence of a many prover non-interactive zero-knowledge system (MP-NIZK proof system). This problem was presented by Micali when the important notion of non-interactive zero-knowledge proofs (NIZK) was first suggested and implemented for a sole prover. The solution immensely enlarges the domain of applications of the NIZK model. The work also provides a new connection between bounded (single-theorem) non-interactive zero-knowledge proofs and the unbounded (multi-theorem) one. This may help in reducing the complexity assumption upon which to base NIZK systems. Remark: This is a full version (with more details, more material, and with proofs) of the Crypto 1990 paper on Metaproof. Over the years, the concept has been used and reinvented for specific settings beyond the original ones, by others; (which has made it more useful). Recently, we were asked about this paper and about details, so here they are! For historical reasons, except for this remark, this version is presented as it was in the above mentioned date under the above affiliations, though we did not pursue publication before! 1 1

Melissa Chase, Ivan Visconti

No abstract is available for this record.

Gilles Barthe, Benjamin Grégoire, César Kunz, Yassine Lakhnech · 5 authors

No abstract is available for this record.

Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn

Depending on the application, malleability in cryptography can be viewed as either a flaw or — especially if sufficiently understood and restricted — a feature. In this vein, Chase, Kohlweiss, Lysyanskaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle. Despite these initial steps, a number of natural open problems remain: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth-Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive; and (3) their construction of a compactly verifiable shuffle has proof size O(N 2 + L) (where N is the number of votes and L is the number of mix authorities), whereas in theory such a proof could be of size O(N + L). In this paper, we address these open problems by providing a generic construction of controlledmalleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction has the advantage that we can support a very general class of transformations (as we no longer rely on the transformations that Groth-Sahai proofs can support), and that we can use it to obtain a proof of size O(N + L) for the compactly verifiable shuffle.

Yi Deng, Juan A. Garay, San Ling, Huaxiong Wang · 5 authors

Abstract. In 2001, a breakthrough result by Barak [FOCS 2001] showed how to achieve public-coin zero-knowledge (ZK) arguments in constant rounds, a feature known to be impossible using black-box simulation. In this approach, the simulator makes use of the code of the malicious verifier in computing the prover messages (albeit without understanding it), and does not rewind the malicious verifier—and it is hence called a straight-line simulator. Since then, however, we have witnessed little progress on the basic question whether Barak’s technique can be extended to ZK proof systems. In this paper we make progress on this front, by providing strong evidence that such an extension is far from likely. Specifically, we show that for a natural class of constant-round public-coin ZK proofs (which we call “canonical, ” as all known non-black-box ZK protocols fall in this category), a straight-line simulator based on the known non-black-box technique for such a proof system can actually be used to solve a seemingly unrelated problem, namely, to figure out some non-trivial property of a verifier’s program, and without executing the target code, a problem commonly viewed as notoriously hard. A key tool in our reduction is an improved structure-preserving version of the well-known Babai-Moran Speedup (derandomization) Theorem, which essentially says that, for a constant-round public-coin interactive proof system in which the verifier sends m messages and each of the prover messages is of length p, if the cheating probability for an unbounded prover is ϵ, then there exist (p/O(log 1

Jan Camenisch, Maria Dubovitskaya, Kristiyan Haralambiev

No abstract is available for this record.

Masayuki Abe, Kristiyan Haralambiev, Miyako Ohkubo

No abstract is available for this record.

Joshua Baron, Rafail Ostrovsky, Ivan Visconti

No abstract is available for this record.

Kai-Min Chung, Rafael Pass, Wei-Lung Dustin Tseng

No abstract is available for this record.