Blockchain Papers

Markus Rückert

No abstract is available for this record.

Ning Ding, Dawu Gu

Traditionally, the definition of zero-knowledge states that an interactive proof of x ∈ L provides zero (additional) knowledge if the view of any polynomial-time verifier can be reconstructed by a polynomial-time simulator. Since this definition only requires that the worst-case running-time of the verifier and simulator are polynomials, zero-knowledge becomes a worst-case notion. In STOC’06, Micali and Pass proposed a new notion of precise zero-knowledge, which captures the idea that the view of any verifier in every interaction can be reconstructed in (almost) the same time (i.e., the view can be “indistinguishably reconstructed”). This is the strongest notion among the known works towards precislization of the definition of zero-knowledge. However, as we know, there are two kinds of computational resources (i.e. time and space) that every algorithm consumes in computation. Although the view of a verifier in the interaction of a precise zero-knowledge protocol can be reconstructed in almost the same time, the simulator may run in very large space while at the same time the verifier only runs in very small space. In this case it is still doubtful to take indifference for the verifier to take part in the interaction or

Alexandra Boldyreva, David M. Cash, Marc Fischlin, Bogdan Warinschi

No abstract is available for this record.

Chunming Tang, Zheng‐an Yao

Multi-prover zero-knowledge proof is an interesting proof in which a few provers synchronously prove validity of a statement to an verifier, however, the verifier will learn nothing beyond the fact that the statement is correct. We call multi-prover zero-knowledge proof as multi-prover zero-knowledge arguments if all provers are probabilistic polynomial-time participants. In this paper, we give the formal definition of multi-prover zero-knowledge argument and construct it based on discrete logarithm problem (DLP).

Kun Peng, Feng Bao

No abstract is available for this record.

Tsz Hon Yuen, Qiong Huang, Yi Mu, Willy Susilo · 6 authors

No abstract is available for this record.

Hendrik Tews, Bart Jacobs

No abstract is available for this record.

Anguraj Baskar, R. Ramanujam, S. P. Suresh

No abstract is available for this record.

Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya

Abstract. Efficient non-interactive zero-knowledge proofs are a powerful tool for solving many cryptographic problems. We apply the recent Groth-Sahai (GS) proof system for pairing product equations (Eurocrypt 2008) to two related cryptographic problems: compact e-cash (Eurocrypt 2005) and simulatable verifiable random functions (CRYPTO 2007). We present the first efficient compact e-cash scheme that does not rely on a random oracle. To this end we construct efficient GS proofs for signature possession, pseudo randomness and set membership. The GS proofs for pseudorandom functions give rise to a much cleaner and substantially faster construction of simulatable verifiable random functions (sVRF) under a weaker number theoretic assumption. We obtain the first efficient fully simulatable sVRF with a polynomial sized output domain (in the security parameter). 1

Michel Abdalla⋆, Céline Chevalier, David Pointcheval

No abstract is available for this record.

Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström

We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of “resettable soundness” if the verifier picks its random coins using a pseudorandom function.

Ronald Cramer, Ivan Damgård, Marcel Keller

No abstract is available for this record.

Jan Camenisch, Aggelos Kiayias, Moti Yung

No abstract is available for this record.

圭介 田中, Keisuke Tanaka, 恵太 草川, Keita Xagawa

No abstract is available for this record.

Mira Belenkiy, Jan Camenisch, Melissa Chase, Markulf Kohlweiss · 6 authors

No abstract is available for this record.

Chengming Qi

In this paper, we proposed a new signature scheme based on elliptic curve cryptography. We combined the two problems, factoring and logarithm problem into both signing and verifying equations. We also give a kind of algorithm of the zero-knowledge proof of proposed digital signature. The new scheme was shown to be secure against the known attacks for signature schemes. This algorithm has characteristics which has little computation, high reliability, and easy to be realized.

Aggelos Kiayias, Hong-Sheng Zhou

No abstract is available for this record.

Essam Ghadafi, Nigel P. Smart, Bogdan Warinschi

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

Rikke Bendlin, Ivan Damgård

Abstract. We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical re-duction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active ad-versaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge- prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key. 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.

Han Zhu, Xiaohong Wu, Yonggen Gu

As Zero-Knowledge proof plays a more and moreimportant role in modern cryptography, the need for formalanalysis becomes more urgent. In this paper, we make use offormal methods to establish a Zero-Knowledge result. The formalmodel is Probabilistic Applied Pi and the Zero-Knowledge proofis Hamiltonian cycle. By this example, our preliminary workshows how Zero-Knowledge can be modeled in formal modelssuch as process calculi and how to establish a Zero-Knowledgeproof by checking equivalence in the model.

Yanguang Shen, Hui Xie, Sheping Hao, Wei Wang

A new scheme of dynamic group blind signature based on elliptic curve discrete logarithm problem (ECDLP) which extends the dynamic group blind signature and the knowledge signature to the elliptic curve cyclic group is generalized. The scheme runs in time slice manner and can be proved security with zero knowledge proof. It supports the dynamic addition and deletion of the group members freely. And the length of signature and computational effort for signing and verifying are independent on both the number of group members and the deleted members. So the security and efficiency are enhanced.