Blockchain Papers

Jens Groth

No abstract is available for this record.

Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung

We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations.>

Joe Kilian

We consider the basic cryptographic primitive known as zero-knowledge proofs on committed bits. In this primitive, a prover P commits to a set of bits, and then at a later time convinces a verifier V that some property /spl Pscr/ holds for a subset of these bits. It is known how to implement this primitive based on an ordinary bit-committal primitive, but the standard implementations involve a great deal of interaction between the prover and the verifier. We introduce new implementations that require markedly less interaction. We implement bounded-interaction proofs on committed bits, generalizing a model of A. De Micali et al. (1988). For all security parameters, our implementations require only a lg/sup 2/ (n) overhead over the best known circuit-based interactive implementations; for sufficiently large security parameters this gap drops to a lg(n) factor.>

Rafail Ostrovsky

The author studies connections among one-way functions, hard on the average problems, and statistical zero-knowledge proofs. In particular, he shows how these three notions are related and how the third notion can be better characterized, assuming the first one.>

Adi Shamir

It is proved that, when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space. The interactive proofs introduced use only public coins, are accepted with probability one when the prover is honest, require only logarithmic workspace when the verifier is given a two-way access to his or her random tape, and by the use of known techniques can be turned into zero-knowledge proofs under the sole assumption that one-way functions exist.>

Uriel Feige, Dror Lapidot, Adi Shamir

The authors solve the two major open problems associated with noninteractive zero-knowledge proofs: how to enable polynomially many provers to prove in writing polynomially many theorems based on the basis of a single random string, and how to construct such proofs under general (rather than number-theoretic) assumptions. The constructions can be used in cryptographic applications in which the prover is restricted to polynomial time, and they are much simpler than earlier (and less capable) proposals.>

Shafi Goldwasser

Theoretical computer science has found fertile ground in many areas of mathematics. The approach has been to consider classical problems through the prism of computational complexity, where the number of basic computational steps taken to solve a problem is the crucial qualitative parameter. This new approach has led to a sequence of advances, in setting and solving new mathematical challenges as well as in harnessing discrete mathematics to the task of solving real-world problems. In this talk, I will survey the development of modern cryptography -- the mathematics behind secret communications and protocols -- in this light. I will describe the complexity theoretic foundations underlying the cryptographic tasks of encryption, pseudo-randomness number generators and functions, zero knowledge interactive proofs, and multi-party secure protocols. I will attempt to highlight the paradigms and proof techniques which unify these foundations, and which have made their way into the mainstream of complexity theory.

Jörg Rothe

In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing key components of protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol, one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.

DaeHun Nyang, JooSeok Song

Zero-knowledge interactive proof is a useful tool for designing identification and digital signature schemes. We propose a new interactive proof based identification and signature scheme.

Moni Naor, Omer Reingold

We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that factoring (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie--Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC 0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form " y = f s ( x )" and " y ≠ f s ( x )" given a commitment to a key s of a pseudo-random function f s .

Arun Sahai, Salil Vadhan

We present a complete promise problem for SZK, the class of languages possessing statistical zero-knowledge proofs (against an honest verifier). The problem is to decide whether two efficiently samplable distributions are either statistically close or far apart. This characterizes SZK with no reference to interaction or zero-knowledge. From this theorem and its proof we are able to establish several other results about SZK, knowledge complexity, and efficiently samplable distributions.

Sung Jun Park, Tae‐Hoon Kim, Dong Ho Won, Young Hwa An

We propose a new notion of an entrusted undeniable signature which is a variant of the undeniable signature. Also we propose a provably entrusted undeniable signature whose security can be proved. The proposed entrusted undeniable signature is a new type of undeniable signature in which the signer confirms his(her) signature to any verifier without the help of court but the verifier can't run the disavowal protocol in the undeniable signature which only court can run to solve the dispute later. The proposed scheme is constructed by a combination of the undeniable signature and zero-knowledge interactive proof system. The proposed provably entrusted undeniable signature is much the same as our entrusted undeniable signature but using the public key residue cryptosystem, which is polynomially secure, for the commitment scheme.

Mihir Bellare, U. Freige, Joe Kilian

We consider which aspects of the two prover model are necessary for their striking language recognition and zero-knowledge capabilities. We approach this question by looking at an alternative, more symmetric model which we call the double verifier model. We find that in this model the shared randomness of the verifiers is key to the language recognition power: if the verifiers don't share randomness the power is PSPACE; otherwise it is MIP=NEXPTIME. We find that the shared randomness of the provers is necessary for zero-knowledge: if the provers don't share randomness, statistical zero-knowledge is only possible for languages in BPP/sup NP/; else it is possible for all of NEXPTIME. These results have immediate implications for the standard two-prover model. We see that correlations between the verifier's queries is crucial for the language recognition power of two prover proofs. In particular, the natural analog of IP=AM does not hold in the two-prover model unless NEXPTIME=PSPACE. Similarly, we see that shared randomness, or correlation of the provers answers, is necessary for the statistical zero-knowledge of two prover proofs.>

Rajashekar Kailar

A new framework is proposed for the analysis of communication protocols that require accountability, such as those for electronic commerce. Informal arguments are presented to show that a heretofore un-explored property "provability" is pertinent to examine the potential use of communication protocols in the context of litigation, and in the context of audit. A set of postulates which are applicable to the analysis of proofs in general (e.g., zero knowledge proofs), and the proofs of accountability in particular, are proposed. The proposed approach is more natural for the analysis of accountability then the existing belief logics that have been used in the past for the analysis of key distribution protocols. Some recently proposed protocols for electronic commerce and public-key delegation are analyzed to illustrate the use of the new analysis framework in detecting (and suggesting remedies for eliminating) their lack of accountability, and in detecting and eliminating redundancies.>

Cynthia Dwork, Moni Naor

A zap is a 2‐round, public coin witness‐indistinguishable protocol in which the first round, consisting of a message from the verifier to the prover, can be fixed “once and for all” and applied to any instance. We present a zap for every language in NP, based on the existence of noninteractive zero‐knowledge proofs in the shared random string model. The zap is in the standard model and hence requires no common guaranteed random string. We present several applications for zaps, including 3‐round concurrent zero‐knowledge and 2‐round concurrent deniable authentication, in the timing model of Dwork, Naor, and Sahai [J. ACM, 51 (2004), pp. 851–898], using moderately hard functions. We also characterize the existence of zaps in terms of a primitive called verifiable pseudorandom bit generators.

Juan A. Garay, Philip MacKenzie

We consider the problem of designing an efficient oblivious transfer (OT) protocol that is provably secure in a concurrent setting, i.e., where many OT sessions may be running concurrently with their messages interleaved arbitrarily. Known OT protocols use zero-knowledge proofs, and no concurrent zero-knowledge proofs are known that use less than a poly-logarithmic number of rounds (at least without requiring a pre-processing phase, a public random string, an auxiliary string, timing constraints, or pre-distributed public keys). We introduce a model for proving security of concurrent OT protocols, and present a protocol that is proven secure in this model based on the decisional Diffie-Hellman problem. The protocol is efficient, requiring only a slightly non-constant number of rounds.

Ming Zhong

No abstract is available for this record.

Yong-Sork Her, 容碩 許, Kouichi Sakurai, 幸一 櫻井 · 5 authors

The voting plays important roles in a democratic country. Due to the problems of the existed voting m ethod, the new voting methods, electronic voting system, have been developing using the computer net work and cryptographic techniques. Many electronic voting schemes have been introduced for secure electronic voting systems. In this paper, we propose the secure electronic voting for absentee e-voting system. The absentee voting plays the important percentage in the existing voting system. But, the abs entee vote can not look forward to the security because of transmit by mail. The absentee does not kno w whether one’s voting is exactly counted or not. In this paper, we propose the absentee e-voting syste m based on security, completeness and verifiability. We use r-th residue cryptography for homomorphi c encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm. Also, we propose the ne w method of tallying for multi-candidate. The goals of out voting system are the absentee vot ing based on privacy, universal verifiability, reuseability and multi-candidate.

Yong-Sork Her, 容碩 許, キョ, ヨウソク, Kouichi Sakurai · 6 authors

In this paper, we propose the absentee e-voting system based on security, completeness and verifiability. We use r-th residue cryptography for homomorphic encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm for the secure absentee e-voting.

Hirotada Kobayashi

This paper introduces quantum analogues of non-interactive perfect and statistical zero-knowledge proof systems. Similar to the classical cases, it is shown that sharing randomness or entanglement is necessary for non-trivial protocols of non-interactive quantum perfect and statistical zero-knowledge. It is also shown that, with sharing EPR pairs a priori, the class of languages having one-sided bounded error non-interactive quantum perfect zero-knowledge proof systems has a natural complete problem. Non-triviality of such a proof system is based on the fact proved in this paper that the Graph Non-Automorphism problem, which is not known in BQP, can be reduced to our complete problem. Our results may be the first non-trivial quantum zero-knowledge proofs secure even against dishonest quantum verifiers, since our protocols are non-interactive, and thus the zero-knowledge property does not depend on whether the verifier in the protocol is honest or not. A restricted version of our complete problem derives a natural complete problem for BQP.

Michael Maxim, Ashish Venugopal

No abstract is available for this record.

HE Mng-xing, Pingzhi Fan

A new multiple secrets sharing scheme, based on the intractability of the discrete logarithm (DL) and the RSA encryption algorithm is presented, in which the participants' shadows remain secret and can be reused, even if all subshadows are made public. Meanwhile, by using a zero-knowledge proof protocol, the validity verification of shadow and subshadow is also provided to prevent both dealer cheating and other participant cheating, and any freely given secrets without pre-computation by dealer can be reconstructed. The scheme can be applied to many areas such as conference key distribution, secure multi-part-computation, threshold signature etc.

Michael O’Donnell

In this paper we examine the role of Identification Protocols in the field of Cryptography. Firstly, the rationale behind the need for Identification Protocols is discussed. Secondly, we examine, in detail, challenge-response protocols, based upon zero-knowledge proofs, that form a subset of Identification Protocols in general. Thirdly, the mathematical tools necessary for the understanding of how these protocols work is given. Finally, we discuss four main Identification Protocols: Fiat-Shamir, Feige-Fiat-Shamir, Schnorr and Guillou- Quisquater. This discussion includes the theory, practical examples and the security aspects of each protocol.

Vanesa Daza, Javier Herranz, Carles Padró, Germán Sáez

In [16], Naor, Pinkas and Reingold introduced schemes in which some groups of servers distribute keys among a set of users in a distributed way. They gave some specic proposals both in the unconditional and in the computational security framework. Their computationally secure scheme is based on the Decisional DiÆe-Hellman Assumption. This model assumes secure communication between users and servers. Furthermore it requires users to do some expensive computations in order to obtain a key. In this paper we modify the model introduced in [16], requiring au-thenticated channels instead of assuming the existence of secure channels. Our model makes the user's computations easier, because most compu-tations of the protocol are carried out by servers, keeping to a more re-alistic situation. We propose a basic scheme, that makes use of ElGamal cryptosystem, and that ts in with this model in the case of a passive ad-versary. We then add zero-knowledge proofs and veriable secret sharing to prevent from the action of an active adversary. We consider general structures (not only the threshold ones) for those subsets of servers that can provide a key to a user and for those tolerated subsets of servers that can be corrupted by the adversary. We nd necessary combinatorial conditions on these structures in order to provide security to our scheme. 1