Blockchain Papers

Aggelos Kiayias, Hong-Sheng Zhou

No abstract is available for this record.

Yehuda Lindell, Hila Zarosim

Abstract. In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it con-trols a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this paper, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems: – Adaptive zero-knowledge proofs: We ask whether it is possible to con-struct adaptive zero-knowledge proofs (with unconditional sound-ness). Beaver (STOC 1996) showed that known zero-knowledge proofs are not adaptively secure, and in addition showed how to construct zero-knowledge arguments (with computational soundness). – Adaptively secure oblivious transfer: All known protocols for adap-tively secure oblivious transfer rely on seemingly stronger hardness assumptions than for the case of static adversaries. We ask whether this is inherent, and in particular, whether it is possible to construct adaptively secure oblivious transfer from enhanced trapdoor permu-tations alone. We provide surprising answers to the above questions, showing that achieving adaptive security is sometimes harder than achieving static se-curity, and sometimes not. First, we show that assuming the existence of one-way functions only, there exist adaptive zero-knowledge proofs for all languages in NP. In order to prove this, we overcome the problem that all adaptive zero-knowledge protocols known until now used equivocal commitments (which would enable an all-powerful prover to cheat). Sec-ond, we prove a black-box separation between adaptively secure oblivious transfer and enhanced trapdoor permutations. As a corollary, we derive a black-box separation between adaptively and statically securely obliv-ious transfer. This is the first black-box separation to relate to adaptive security and thus the first evidence that it is indeed harder to achieve security in the presence of adaptive adversaries than in the presence of static adversaries. 1

Ueli Maurer

No abstract is available for this record.

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

A zero-knowledge proof allows a prover to convince a verifier of an assertion without revealing any further information beyond the fact that the assertion is true. Secure multiparty computation allows n mutually suspicious players to jointly compute a function of their local inputs without revealing to any t corrupted players additional information beyond the output of the function. We present a new general connection between these two fundamental notions. Specifically, we present a general construction of a zero-knowledge proof for an NP relation $R(x,w)$, which makes only a black-box use of any secure protocol for a related multiparty functionality f. The latter protocol is required only to be secure against a small number of “honest but curious” players. We also present a variant of the basic construction that can leverage security against a large number of malicious players to obtain better efficiency. As an application, one can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming that one-way functions exist, we get the following types of zero-knowledge proof protocols: (1) Approaching the witness length. If C has constant depth over $\wedge,\vee,\oplus,\neg$ gates of unbounded fan-in, we get a zero-knowledge proof protocol with communication complexity $m\cdot{poly}(k)\cdot{polylog}(s)$, where k is a security parameter. (2) “Constant-rate” zero-knowledge. For an arbitrary circuit C of size s and a bounded fan-in, we get a zero-knowledge protocol with communication complexity $O(s)+{poly}(k,\log s)$. Thus, for large circuits, the ratio between the communication complexity and the circuit size approaches a constant. This improves over the $O(ks)$ complexity of the best previous protocols.

Benny Applebaum, Boaz Barak, David Xiao

We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.

Payman Mohassel, Enav Weinreb

No abstract is available for this record.

Yevgeniy Dodis, Victor Shoup, Shabsi Walfish

No abstract is available for this record.

Chris Peikert, Vinod Vaikuntanathan

No abstract is available for this record.

Ning Ding, Dawu Gu

No abstract is available for this record.

Yael Tauman Kalai, Ran Raz

No abstract is available for this record.

Joachim von zur Gathen, Oded Goldreich, Madhu Sudan

The workshop Complexity Theory was organized by Joachim von zur Gathen (Universität Bonn), Oded Goldreich (Weizmann Institute), and Madhu Sudan (MIT). The workshop was held on June 24th–30th 2007, and attended by approximately 50 participants spanning a wide range of interests within the field of Computational Complexity. The plenary program, attended by all participants, featured eight long lectures as well as short (10-minute) reports by almost all participants. In addition, extensive interaction took place in smaller groups. The Oberwolfach Meeting on Complexity Theory is marked by a long tradition and a continuous transformation. Originally starting with a focus on algebraic and Boolean complexity, the meeting has continuously evolved to cover a wide variety of areas, most of which were not even in existence at the time of the first meeting (in 1972). While inviting many of the most prominent researchers in the field, the organizers try to identify and invite a fair number of promising young researchers. Computational complexity (a.k.a. complexity theory) is a central field of computer science with a remarkable list of celebrated achievements as well as a vibrant research activity. The field is concerned with the study of the intrinsic complexity of computational tasks, and this study tends to aim at generality : it focuses on natural computational resources, and considers the effect of limiting these resources on the class of problems that can be solved. Computational complexity is related to and has substantial interaction with other areas of mathematics such as number theory, algebra, combinatorics, coding theory, and optimization. The workshop focused on several sub-areas of complexity theory and its nature may be best illustrated by a brief survey of some of the meeting's highlights. Connections to the Theory of Error-Correcting Codes. The interplay between coding theory and complexity theory first emerged in the context of “hardness amplification” (almost two decades ago) and other connections are less than a decade old (e.g., the connection to probabilistic checking of proofs and extraction of pure randomness). Several applications of the known connections were presented in the current meeting, and in addition a new connection to algebraic complexity was presented. While previous applications of the aforementioned connections went in the direction of coding theory to complexity theory, a recent result reported by Venkat Guruswami goes in the opposite direction. This work, by Guruswami and his graduate student (Rudra), resolves a decades-old central problem in coding theory by presenting an explicit error-correcting code of constant-size alphabet that approaches the capacity bound (under worst-case errors, using list decoding). Extracting randomness. Extracting almost-perfect randomness from weak sources of (imperfect) randomness is crucial for the actual use of randomized procedures. Typical analyses of randomized procedures assume that the procedures have access to a perfect random source. However, in reality one only has access to sources of weak randomness (e.g., having constant entropy rate). Indeed, the problem has attracted a lot of attention in the last couple of decades. In the meeting, Chris Umans has presented recent work with Guruswami and Vadhan, which utilizes recent algebraic and coding theoretic techniques to the construction of (single-source) randomness extractors. This construction meets (and actually improves) the best known parameters for the problem (which are almost optimal), but does so by a relatively simple construction rather than by a complex combination of numerous constructs (as done in prior work). Furthermore, the new work introduces improved constructions for an intermediate primitive (called randomness condenser), which is of independent interest. While single-source randomness extractors must utilize an auxiliary random seed (which may be very short), some applications do not allow for such a seed. In this case, extraction from several (e.g., two) independent sources of weak randomness is called for. An important step in the study of this direction was made by Anup Rao, and presented by him in the meeting. Algebraic complexity and modular polynomial composition. An important task in algebraic computation is modular polynomial composition; that is, given three univariate polynomials f,g and h , one is required to obtain the coefficients of the polynomial f \circ g \bmod h . This task has many applications, most notably as an ingredient in algorithms for polynomial factorization. The previously best algorithm was presented 30 years ago and uses O(n^{1.7}) arithmetic operations, where n denotes the maximum degree of the polynomials. In the meeting, Chris Umans presented significant progress on this celebrated open problem in the form of an almost linear-time algorithm that works for fields of small characteristic. This major progress on a purely algebraic problem is essentially based on methods that were introduced into coding theory by Guruswami and Rudra, and then applied to complexity theory in the context of randomness extractors (see foregoing paragraphs). All three results, which are major achievements in their respective areas, were presented at the meeting. Cryptography and Zero-Knowledge. Zero-knowledge proofs are fascinating concepts and extremely useful constructs. Their fascinating nature is due to their seemingly contradictory definition that mandates that they be convincing and yet yield nothing beyond the validity of the assertion being proved. Their applicability in the domain of cryptography is vast; they are typically used to force malicious parties to behave according to a predetermined protocol. In addition to their direct applicability in cryptography, zero-knowledge proofs serve as a good bench-mark for the study of various problems regarding cryptographic protocols. Zero-knowledge proofs come in many flavors, and it is of great theoretical and practical importance to investigate the relationship among them. A central problem in this area, which has been open since 1986, refers to the gap between the known results regarding two dual notions: the notion of general zero-knowledge proofs (in which the secrecy condition holds with respect to feasible adversaries) and the notion of statistical zero-knowledge arguments (in which the soundness condition holds with respect to feasible adversaries). This gap was bridged in a recent work of Salil Vadhan, jointly with his graduate students (Nguyen and Ong), and was presented by Vadhan in this meeting. A problem related to both cryptography and coding theory is the problem of constructing private information retrieval schemes and/or locally decodable codes. In the context of error-correcting codes, such schemes should allow the recovery of any bit in the original message based on a constant number (e.g., three) probes to the corrupted codeword. For more than a decade it was believed that the length of such codewords must be (weakly) exponential in the length of the message. In the meeting, Sergey Yekhanin (PhD student) presented his recent result that refutes this belief. Delegating your work to an untrusted entities. Needless to say, it is nice to delegate your work to others, but what if you don't trust the others? The very definition of a proof system refers to such a possibility – the hard task of finding a proof is delegated to the outside while you make sure that the proof is valid by performing the easier task of verification. However, facilitating verification may mean making the task of finding adequate proofs even harder. In the context of program checking this phenomenon is explicitly disallowed: wishing to solve some problem you may use an untrusted program that supposedly solves this problem (but not a program that solve more complex problems). Needless to say, the aim is allowing the delegator, called a checker, to use significantly few

Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a "muggle". The verifier should be super-efficient and run in nearly-linear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result's correctness in nearly-linear time (instead of running the entire computation itself). Previously, related questions were considered in the Holographic Proof setting by Babai, Fortnow, Levin and Szegedy, in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. Our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth d and input length n. The verifier runs in time (n+d) • polylog(n) and space O(log(n)), the communication complexity is d • polylog(n), and the prover runs in time poly(n). In particular, for languages computable by log-space uniform NC (circuits of polylog(n) depth), the prover is efficient, the verifier runs in time n • polylog(n) and space O(log(n)), and the communication complexity is polylog(n). Using this theorem we make progress on several questions: We show how to construct short (polylog size) computationally sound non-interactive certificates of correctness for any log-space uniform NC computation, in the public-key model. The certificates can be verified in quasi-linear time and are for a designated verifier: each certificate is tailored to the verifier's public key. This result uses a recent transformation of Kalai and Raz from public-coin interactive proofs to one-round arguments. The soundness of the certificates is based on the existence of a PIR scheme with polylog communication. Interactive proofs with public-coin, log-space, poly-time verifiers for all of P. This settles an open question regarding the expressive power of proof systems with such verifiers. Zero-knowledge interactive proofs with communication complexity that is quasi-linear in the witness, length for any NP language verifiable in NC, based on the existence of one-way functions. Probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than the instance length) for any NP language verifiable in NC, under computational assumptions.

Avi Wigderson

No abstract is available for this record.

Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam

Few techniques for obtaining concurrent zero-knowledge exist; all require a complex and subtle analysis. We provide an arguably simpler and more general analysis of the oblivious simulation technique of Kilian and Petrank (STOC’01) while achieving the same bounds as Prabhakaran, Rosen and Sahai (FOCS’02). Using this analysis, and relying on tools recently developed by Ong and Vadhan (Eurocrypt’07, TCC’08) we are able to establish the following unconditional results: • every language inNP which has a ZK proof (resp. ZK argument, statistical ZK argument) also has a black-box concurrent ZK proof (resp. ZK argument, statistical ZK argument). • every languge which has a statistical ZK proof also has an ω(log n)-round black-box con-current statistical ZK proof.

Vipul Goyal, Payman Mohassel, Adam Smith

No abstract is available for this record.

Jens Groth, Yuval Ishai

No abstract is available for this record.

Dario Catalano, Mario Di Raimondo, Dario Fiore, Mariagrazia Messina

Zero knowledge sets (ZKS), introduced by Micali, Rabin, and Kilian in 2003, allow a prover to commit to a secret set$S$in a way such that it can later prove, non interactively, statements of the form$x\in S$(or$x\notin S$), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on$S$, not even its size. Later, Chaseabstracted away the Micali, Rabin, and Kilian's construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. Using this primitive, it was shown how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic). This paper introduces the notion of trapdoor$q$-mercurial commitments (${\ssr qTMC}$s), a notion of mercurial commitment that allows the sender to commit to an ordered sequence of exactly$q$messages, rather than to a single one. Following the previous work, it is shown how to construct ZKS from${\ssr qTMC}$s and collision resistant hash functions. Then, it is presented an efficient realization of${\ssr qTMC}$s that is secure under the so called Strong Diffie Hellman (SDH) assumption, a number theoretic conjecture recently introduced by Boneh and Boyen. Using such scheme as basic building block, it is obtained a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of nonmembership. Experimental tests confirm practical time performances.

Rui Xue, Ninghui Li, Jiangtao Li

No abstract is available for this record.

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

No abstract is available for this record.

Oleg Verbitsky

We show that the Double Coset Membership problem for permutation groups possesses perfect zero-knowledge proofs.

Oleg Verbitsky

We design a perfect zero-knowledge proof system for recognition if two permutation groups are conjugate.

Xuan Yang, Zhaoping Yu, Bin Kang

A fair exchange protocol allows two parties to exchange items in a fair way so that either each party gets the other's item or neither party does. In this paper, we propose a key-exposure-free chameleon hashing scheme based on the discrete logarithm assumption, and prove that it enjoys all advantages of previous schemes: collision resistant, semantic security, message hiding and key exposure freeness. Using this new scheme as kernel, an efficient and secure chameleon-based optimistic fair exchange protocol is proposed. Unlike the vast majority of previously proposed protocols, above approach has no use for verifiably encrypted signature and does not use any zero knowledge proofs, which avoids most of the costly computations. The security of the newly devised protocol is also examined. It is showed that the proposed scheme is secure and efficient.

Zuzana Beerliová-Trubíniová, Martin Hirt, Jesper Buus Nielsen

Abstract. Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to t of the n parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to t < n/2 faulty parties, whereas in the more realistic asynchronous setting (with no a priory information on maximal message delay) only security against t < n/3 is possible. Note that even asynchronous Byzantine agreement requires t < n/3. In this paper, we are interested in the minimal synchronicity assumption for achieving security against t < n/2. It turns out that the bottleneck of asynchronous MPC is the distribution of the inputs: Once the inputs are correctly distributed, any deterministic function can be computed over a fully asynchronous network with t < n/2. Furthermore, we show that the inputs can be verifiably distributed with t < n/2, if a single round of synchronous broadcast is available. Composing the above, we obtain the first MPC protocol that achieves security against t < n/2 without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an almost asynchronous network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of n−t parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of almost non-interactive verifiable secret-sharing and almost non-interactive zero-knowledge proof of knowledge, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.

Dennis Hofheinz

The selective decommitment problem can be described as follows: assume an adversary receives a number of commitments and then may request openings of, say, half of them. Do the unopened commitments remain secure? Although this question arose more than twenty years ago, no satisfactory answer could be presented so far. We answer the question in several ways: 1. If simulation-based security is desired (i.e., if we demand that the adversary's output can be simulated by a machine that does not see the unopened commitments), then security is not achievable for non-interactive or perfectly binding commitment schemes via black-box reductions to standard cryptographic assumptions. However, we show how to achieve security in this sense with interaction and a non-black-box reduction to one-way permutations. 2. If only indistinguishability of the unopened commitments from random commitments is desired, then security is not achievable for (interactive or non-interactive) perfectly binding commitment schemes, via black-box reductions to standard cryptographic assumptions. However, any statistically hiding scheme does achieve security in this sense. Our results give an almost complete picture when and how security under selective openings can be achieved. Applications of our results include: • Essentially, an encryption scheme must be non-committing in order to achieve provable security against an adaptive adversary. • When implemented with our secure commitment scheme, the interactive proof for graph 3-coloring due to Goldreich et al. becomes zero-knowledge under parallel composition. On the technical side, we develop a technique to show very general impossibility results for black-box proofs.