Blockchain Papers

V A Belkin

No abstract is available for this record.

Stephen R. Tate, Roopa Vishwanathan

At the heart of many fair exchange problems is verifiable escrow: a sender encrypts some value using the public key of a trusted party (called the recovery agent), and then must convince the receiver of the ciphertext that the corresponding plaintext satisfies some property (e.g., it contains the sender’s signature on a contract). Previous solutions to this problem are interactive, and often rely on communication-intensive cut-and-choose zero-knowledge proofs. In this paper, we provide a solution that uses generic trusted hardware to create an efficient, non-interactive verifiable escrow scheme. Our solution allows the protocol to use a set of recovery agents with a threshold access structure, the verifiable group escrow notion which was informally introduced by Camenisch and Damgard and which is formalized here. Finally, this paper shows how this new non-interactive verifiable escrow scheme can be used to create an efficient optimistic protocol for fair exchange of signatures.

Wenbao Han

A publicly verifiable multi-secret sharing scheme is proposed, using non-interactive zero-knowledge proof protocol and Shamir’s sharing system. The security of the scheme is based on the intractability of integer factorization problem and discrete logarithm problem. The validity of the sharing distributed by the dealer can be verified by anyone. Recovering the secret, participants only need to provide a shadow of the sharing. It is difficult to get the sharing from the shadow. So the sharing can be reused to share the multi-secret. Moreover, the validity of the shadow can also be verified by anyone. So the scheme is secure, efficient, and can prevent both dealer and participant from cheating.

Ivan Damgård, Carolin Lunemann

In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [Wat09] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the combination of coin-flipping with any non-interactive zero-knowledge protocol leads to an easy transformation from non-interactive zero-knowledge to interactive quantum zero-knowledge. Second, we discuss how our protocol can be applied to a recently proposed method for improving the security of quantum protocols [DFL+09], resulting in an implementation without set-up assumptions. Finally, we sketch how to achieve efficient simulation for an extended construction in the common-reference-string model.

Joël Alwen, Abhi Shelat, Ivan Visconti

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.

Aydin Behnad, Taraneh Eghlidos

A Publicly Veriable Secret Sharing (PVSS) scheme, as introduced by Stadler, has a feature where anyone, besides the participants, can verify the validity of the shares distributed by the dealer. Schoenmakers added a new feature, by providing a proof of correctness of the shares released by the players in the reconstruction process. This protocol is claimed to be an improvement on Stadler's and Fujisaki-Okamoto's, both in eciency and in the type of intractability assumptions. However, Young-Yung improved Schoenmakers' PVSS, using a Discrete-Log instead of a Decision Die-Hellman. In this paper, a new PVSS is presented, having an intrinsic dierence with its predecessors, that is, the participants can prove the validity of their given shares, implicitly, proving their membership by a zero-knowledge protocol. This feature prevents cheaters from participating in the reconstruction process to gain valid shares. Hence, the new proposed PVSS is more secure than previous ones. Besides, the dealer only sends the amount of commitments limited to the threshold value, regardless of the number of shareholders; this leads to a more dynamic protocol.

Claude Lopez, Susana Nudelsman, Matias Alfredo Gutierrez Girault, Jose Siaba Serrate

No abstract is available for this record.

Joël Alwen, Jonathan Katz, Yehuda Lindell, Giuseppe Persiano · 6 authors

No abstract is available for this record.

HU Jiang-hong, Jianzhong Zhang

No abstract is available for this record.

André Chailloux, Iordanis Kerenidis

In quantum zero knowledge, the assumption was made that the verifier is only using unitary operations. Under this assumption, many nice properties have been shown about quantum zero knowledge, including the fact that Honest-Verifier Quantum Statistical Zero Knowledge ($HVQSZK$) is equal to Cheating-Verifier Quantum Statistical Zero Knowledge ($QSZK$) (see ~\cite{Wat02,Wat06}). In this paper, we study what happens when we allow an honest verifier to flip some coins in addition to using unitary operations. Flipping a coin is a non-unitary operation but doesn\'t seem at first to enhance the cheating possibilities of the verifier since a classical honest verifier can flip coins. In this setting, we show an unexpected result: any classical Interactive Proof has an Honest-Verifier Quantum Statistical Zero Knowledge proof with coins. Note that in the classical case, honest verifier $SZK$ is no more powerful than $SZK$ and hence it is not believed to contain even $NP$. On the other hand, in the case of cheating verifiers, we show that Quantum Statistical Zero Knowledge where the verifier applies any non-unitary operation is equal to Quantum Zero-Knowledge where the verifier uses only unitaries. One can think of our results in two complementary ways. If we would like to use the honest verifier model as a means to study the general model by taking advantage of their equivalence, then it is imperative to use the unitary definition without coins, since with the general one this equivalence is most probably not true. On the other hand, if we would like to use quantum zero knowledge protocols in a cryptographic scenario where the honest-but-curious model is sufficient, then adding the unitary constraint severely decreases the power of quantum zero knowledge protocols.

Donald Beaver

No abstract is available for this record.

Edward Epsen

No abstract is available for this record.

Toshiya Itoh, Yuji Ohta, Hiroki Shizuya

No abstract is available for this record.

Yvo Desmedt, Moti Yung

No abstract is available for this record.

Bernard Chazelle

No abstract is available for this record.

Yang Yi-xian

Divisibility of e-cash helps expend digital coin exactly.Most divisible e-cash schemes are based on binary tree,but few e-cash schemes offer fairness and divisibility at the same time.Based on binary tree,blind signature and zero-knowledge proof,a new fair indivisible electronic coins scheme was proposed.

Jing Xu

This paper introduces a natural paradigm for fair exchange protocols, called ID-based partial proxy signature scheme. A security model with precise and formal definitions is presented, and an efficient and provably secure partial proxy signature scheme is proposed. This is a full ID-based optimistic fair exchange protocol. Unlike the vast majority of previously proposed protocols, this approach does not use any zero knowledge proofs, and thus avoids most of the costly computations.

Shien Jin Ong, Salil Vadhan

No abstract is available for this record.

Ivan Damgård, Rune Thorbek

We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers a, b, c satisfy ab = c. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.

Sven Laur, Helger Lipmaa

No abstract is available for this record.

Abhilasha Bhargav-Spantzel, Anna Squicciarini, Elisa Bertino

We develop solutions for the security and privacy of user identity information in a federation. By federation we mean a group of organizations or service providers which have built trust among each other and enable sharing of user identity information amongst themselves. We first propose a flexible approach to establish a single sign-on (SSO) ID in the federation. Then we show how a user can leverage this SSO ID to establish certified and un-certified user identity attributes without the dependence on PKI for user authentication. This makes the process more usable and privacy preserving. Our major contribution in this paper is a novel solution for protection against identity theft of these identity attributes. We provide protocols based on cryptographic techniques, namely zero knowledge proofs and distributed hash tables. We show how we can preserve privacy of the user identity without jeopardizing security. We formally prove correctness and provide complexity results for our protocols. The complexity results show that our approach is efficient. In the paper we also show that the protocol is robust enough even in case semi-trusted "honest-yet curious" service providers thus preventing against insider threat. In our analysis we give the desired properties of the cryptographic tools used and identify open problems. We believe that the approach represents a precursor to new and innovative cryptographic techniques which can provide solutions for the security and privacy problems in federated identity management.

John Watrous

This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich–Micali–Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{QSZK}= \mathrm{QSZK}_{\mathrm{HV}}$. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.

Abdelatif Hafid, Abdelhakim Hafid, Abdelhakim Hafid, Abdelhakim Hafid · 5 authors

Blockchain technology has been gaining great interest from a variety of sectors including healthcare, supply chain, and cryptocurrencies. However, Blockchain suffers from a limited ability to scale (i.e., low throughput and high latency). Several solutions have been proposed to tackle this. In particular, sharding has proved to be one of the most promising solutions to Blockchain's scalability issue. Sharding can be divided into two major categories: (1) Sharding-based Proof-of-Work (PoW) Blockchain protocols, and (2) Sharding-based Proof-of-Stake (PoS) Blockchain protocols. The two categories achieve good performances (i.e., good throughput with a reasonable latency), but raise security issues. This article focuses on the second category. In this paper, we start by introducing the key components of sharding-based PoS Blockchain protocols. We then briefly introduce two consensus mechanisms, namely PoS and practical Byzantine Fault Tolerance (pBFT), and discuss their use and limitations in the context of sharding-based Blockchain protocols. Next, we provide a probabilistic model to analyze the security of these protocols. More specifically, we compute the probability of committing a faulty block and measure the security by computing the number of years to fail. We achieve a number of years to fail of approximately 4000 in a network of 4000 nodes, 10 shards, and a shard resiliency of 33%.