Blockchain Papers

Moti Yung, Yunlei Zhao

No abstract is available for this record.

Tsuyoshi Yamamoto, Eiichiro Fujisaki, Masayuki Abe

No abstract is available for this record.

Luis von Ahn, Nicholas Hopper, John Langford

We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs xA and xB respectively, to compute a function f(xA,xB) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(xA,xB) only when it equals a certain value of interest (such as "Yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xA,xB) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the "honest but curious" model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.

Dario Catalano, Ivan Visconti

No abstract is available for this record.

Aggelos Kiayias, Antonina Mitrofanova

No abstract is available for this record.

Giovanni Di Crescenzo

No abstract is available for this record.

Jonathan Katz, Yehuda Lindell

No abstract is available for this record.

Joël Alwen, Giuseppe Persiano, Ivan Visconti

No abstract is available for this record.

Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin

No abstract is available for this record.

Rafael Pass, Abhi Shelat

No abstract is available for this record.

Xavier Boyen, Brent Waters

No abstract is available for this record.

Matt Lepinski, Silvio Micali, Abhi Shelat

No abstract is available for this record.

Moses Liskov

Abstract. Micali, Rabin, and Kilian [9] recently introduced zero-knowledge sets and databases, in which a prover sets up a database by publishing a commitment, and then gives proofs about particular values. While an elegant and useful primitive, zero-knowledge databases do not offer any good way to perform updates. We explore the issue of updating zero-knowledge databases. We define and discuss transparent updates, which (1) allow holders of proofs that are still valid to update their proofs, but (2) otherwise maintain secrecy about the update. We give rigorous definitions for transparently updatable zero-knowledge databases, and give a practical construction based on the Chase et al [2] construction, assuming that verifiable random functions exist and that mercurial commitments exist, in the random oracle model. We also investigate the idea of updatable commitments, an attempt to make simple commitments transparently updatable. We define this new primitive and give a simple secure construction.

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

Abstract. We provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices. For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have ~O(log n) rounds, which is known to be essentially optimal for black-box simulation.

Hongda Li, Bao Li

No abstract is available for this record.

Jens Groth, Rafail Ostrovsky, Amit Sahai

No abstract is available for this record.

Salil Vadhan

We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist. We establish several new characterizations of CZK, and use these characterizations to prove results such as: 1) Honest-verifier CZK equals general CZK. 2) Public-coin CZK equals private-coin CZK. 3) CZK is closed under union (and more generally, "monotone formula closure"). 4) CZK with imperfect completeness equals CZK with perfect completeness. 5) Any problem in CZK /spl cap/ NP can be proven in computational zero knowledge by a BPP/sup NP/ prover. 6) CZK with black-box simulators equals CZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.

Yuanbo Guo, Jianfeng Ma

An original approach to establish a computationally secure and robust conference key between multiple users is presented, which is built on known secret sharing schemes and requires the authenticated and encrypted point-to-point channels between servers and users. By running of the protocol, every honest user of a given conference can get a common key, even if a minority of the servers malfunction or misbehave. This scheme does not rely on any unproven cryptographic assumptions or on the availability of any tamper-proof hardware. By using zero knowledge proof, any corrupted information and incorrect results can be detected. And by distributing the sensitive security information across several servers and never reconstructing any key at a single location, the compromise of a few servers will not compromise the privacy of any key. Analysis shows that under the assumption of a Diffie-Hellman decisional problem, a passive adversary gets zero knowledge about the conference key, and in the random oracle model, an active adversary cannot impersonate successfully. We have implemented the scheme in a distributed environment. By conducting a number of experiments in the fault-free case and various fault scenarios, we show that it has an acceptable performance of practicability.

Silvio Micali, M. O. Rabin, Joe Kilian

We show how a polynomial-time prover can commit to an arbitrary finite set S of strings so that, later on, he can, for any string x, reveal with a proof whether x /spl isin/ S or x /spl notin/ S, without revealing any knowledge beyond the verity of these membership assertions. Our method is non interactive. Given a public random string, the prover commits to a set by simply posting a short and easily computable message. After that, each time it wants to prove whether a given element is in the set, it simply posts another short and easily computable proof, whose correctness can be verified by any one against the public random string. Our scheme is very efficient; no reasonable prior way to achieve our desiderata existed. Our new primitive immediately extends to providing zero-knowledge databases.

Chunming Tang, Dingyi Pei, Zhuojun Liu

A delegateable signature scheme is a signature scheme where the owner of the signing key(Alice) can securely delegate to another party(Bob) the ability to sign on Alice’s behalf on a restricted subset S of the message space. Barak first defined and constructed this signature scheme using non-interactive zero-knowledge proof of knowledge(NIZKPK)[1]. In his delegateable signature scheme, the function of NIZKPK is to prevent the signing verifier from tell which witness(i.e. restricted subset) is being used. Witness indistinguishable(WI) and witness hiding(WH) proof systems are weaker proof model than zero-knowledge proof and were proposed by Feige and Shamir in [2], however, the verifier cannot also distinguish the witness which is being used in these two protocols. In this paper, we construct delegateable signature scheme using WI and WH proof protocols.

Toru Nakanishi, Daisuke Yamamoto, Yuji Sugiyama

No abstract is available for this record.

Anderson C. A. Nascimento, Joern Mueller-Quade, Akira Otsuka, Goichiro Hanaoka · 5 authors

No abstract is available for this record.

Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He

A publicly verifiable secret sharing scheme is more applicable than a verifiable secret sharing because of the property that the validity of the shares distributed by the dealer can be verified by any party. In this paper, we construct a non-interactive and informationtheoretic publicly verifiable secret sharing by a computationally binding and unconditionally hiding commitment scheme and zero-knowledge proof of knowledge.

Cynthia Dwork, Ronen Shaltiel, Adam Smith, Luca Trevisan

No abstract is available for this record.