Blockchain Papers

Anton Štiglić

No abstract is available for this record.

Robert Silverman

With increasing demands for internet security, the demand for distribution of public key certificates and certificate authorities spreads. This brings up the new problem of public key validation. This problem can arise in different contexts and can be adressed in some of them using novel zero knowledge protocols, while in other contexts it can be only poorly solved. The purpose of this paper is to give an overview of the topic of key validation and to discuss the possible solutions to the different instances in which it appears. We also present a new zero knowledge protocol for correctness of an RSA public exponent and a simple protocol (not zero-knowledge) for primality of a discrete logarithm. We use the latter to give a proof protocol (not zero knowledge) that an RSA key is the product of strong primes These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Mark S. Miller, Chip Morningstar, Bill Frantz

No abstract is available for this record.

Takeru Miyazaki

No abstract is available for this record.

Pino Caballero‐Gil, Candelaria Hernández‐Goya

No abstract is available for this record.

Ivan Damgård, Eiichiro Fujisaki

No abstract is available for this record.

Wenbo Mao

Let n be a large composite number. Without factoring n, the computation of a 2 t (mod n)given a, t with gcd(a# n) = 1 and t!n can be done in t squarings modulo n.For t n (e.g., n?2 1024 and t!2 100 ), no lower complexity than t squarings is known to fulfill this task. Rivest et al suggested to use such constructions as good candidates for realising timed-release crypto problems. We argue the necessity for a zero-knowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in log 2 t standard crypto operations, the correctness of (a e ) 2 t (mod n) with respect to a e where e is an RSA encryption exponent. With such a proof, a Timed-release Encryption of a message M can be given as a 2 t M (mod n) with the assertion that the correct decryption of the RSA ciphertext M e (mod n) can be obtained by performing t squarings modulo n starting from a. Timed-release RSA signatures can be constructed analogously. Keywords Timed-release cryptography, Time-lock puzzles, Non-parallelisability, Efficient zero-knowledge protocols. 1

Tzafrir Cohen, Joe Kilian, Erez Petrank

No abstract is available for this record.

Taekyoung Kwon

This paper presents a new password authentication and key agreement protocol called AMP in a provable manner. The intrinsic problem with password authentication is a password, associated with each user, has low entropy so that (1) the password is hard to transmit securely over an insecure channel and (2) the password file is hard to protect. Our solution to this complex problem is the amplified password proof idea along with the amplified password file. A party commits the high entropy information and amplifies her password with that information in the amplified password proof. She never shows any information except that she knows it for her proof. Our amplified password proof idea is similar to the zero-knowledge proof in that sense. A server stores amplified verifiers in the amplified password file that is secure against a server file compromise and a dictionary attack. AMP mainly provides the passwordverifier based authentication and the Diffie-Hellman based key agreement, securely and efficiently. AMP is simple and actually the most efficient protocol among the related protocols.

Tomas Sander, Amnon Ta‐Shma, Moti Yung

No abstract is available for this record.

Oded Goldreich

Following Dwork, Naor, and Sahai (30th STOC, 1998), we consider concurrent execution of protocols in a semi-synchronized network. Specifically, we assume that each party holds a local clock such that a constant bound on the relative rates of these clocks is a-priori known, and consider protocols that employ time-driven operations (i.e., time-out in-coming messages and delay out-going messages). We show that the constant-round zero-knowledge proof for NP of Goldreich and Kahan (Jour. of Crypto., 1996) preserves its security when polynomially-many independent copies are executed concurrently under the above timing model. We stress that our main result establishes zero-knowledge of interactive proofs, whereas the results of Dwork et. al. are either for zero-knowledge arguments or for a weak notion of zero-knowledge (called ffl-knowledge) proofs. Our analysis identifies two extreme schedulings of concurrent executions under the above timing model: the first is the case of parallel execution of polynomially-many copies, and the second is of concurrent execution of polynomially-many copies such the number of copies that are simultaneously active at any time is bounded by a constant (i.e., bounded simultaneity). Dealing with each of these extreme cases is of independent interest, and the general result (regarding concurrent executions under the timing model) is obtained by combining the two treatments.

Yi Yang

A new electronic cash scheme based on zero knowledge proof is proposed Unlike the other proposed schemes,our electronic cash scheme is not based on any specific scheme Thus we have provided an approach to construct electronic cash with any blind signature scheme or zero knowledge proof system The security of our scheme is proved based on some cryptographic assumptions

Boaz Barak, Oded Goldreich, S. Goldwasser, Yehuda Lindell

Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge arguments for NP exist if collision-free hash functions exist. In contrast, resettably-sound zero-knowledge proofs are possible only for languages in P/poly. We present two applications of resettably-sound zero-knowledge arguments. First, we construct resettable zero-knowledge arguments of knowledge for NP, using a natural relaxation of the definition of arguments (and proofs) of knowledge. We note that, under the standard definition of proof of knowledge, it is impossible to obtain resettable zero-knowledge arguments of knowledge for languages outside BPP. Second, we construct a constant-round resettable zero-knowledge argument for NP in the public-key model, under the assumption that collision-free hash functions exist. This improves upon the sub-exponential hardness assumption required by previous constructions. We emphasize that our results use non-black-box zero-knowledge simulations. Indeed, we show that some of the results are impossible to achieve using black-box simulations. In particular, only languages in BPP have resettably-sound arguments that are zero-knowledge with respect to black-box simulation.

Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano · 5 authors

. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last decade and has been used throughout modern cryptography in several essential ways. For example, NIZK plays a central role in building provably secure public-key cryptosystems based on general complexity-theoretic assumptions that achieve security against chosen ciphertext attacks. In essence, in a multi-party setting, given a fixed common random string of polynomial size which is visible to all parties, NIZK allows an arbitrary polynomial number of Provers to send messages to polynomially many Verifiers, where each message constitutes an NIZK proof for an arbitrary polynomial-size NP statement. In this paper, we take a closer look at NIZK in the multi-party setting. First, we consider non-malleable NIZK, and generalizing and substantially strengthening the results of Sahai, we give the first construction of NIZK which remains non-malleable after polynomially-many NIZK proofs. Second, we turn to the definition of standard NIZK itself, and propose a strengthening of it. In particular, one of the concerns in the technical definition of NIZK (as well as non-malleable NIZK) is that the so-called "simulator" of the Zero-Knowledge property is allowed to pick a different "common random string" from the one that Provers must actually use to prove NIZK statements in real executions. In this paper, we propose a new definition for NIZK that eliminates this shortcoming, and where Provers and the simulator use the same common random string. Furthermore, we show that both standard and non-malleable NIZK (as well as NIZK Proofs of Knowledge) can be constructed achieving this stronger definition. We call...

Helger Lipmaa

A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a representing $p$-bounded polynomial $R_{S,t}$, s.t.~$x\\in S_t \\iff (\\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent polynomial. We show that $p$-bounded (resp., unbounded) Diophantine set has a polynomial-size (resp., constant-size) statistical zero-knowledge proof system that a committed tuple $x$ belongs to $S$. We describe efficient SZK proof systems for several cryptographically interesting sets. Finally, we show how to prove in SZK that an encrypted number belongs to $S$.

André Adelsbach, Ahmad‐Reza Sadeghi

No abstract is available for this record.

Glenn Durfee, Matthew Franklin

Digital content distribution systems will enable business models in the near future that cannot be predicted today. In this paper, we identify a new security problem that can be crucial to this enablement. The problem arises from the conflicting privacy and integrity goals of middlemen in digital distribution chains. Our solution is a novel system design that incorporates obfuscated digital contracts, semi-trusted contract certifiers, and zero-knowledge proofs of arithmetic relations. Our implementation and timing experiments demonstrate that our solution is practical and efficient.

Joan Boyar, Ivan Damgård, René Peralta

No abstract is available for this record.

Dae Hun Nyang, Joo Seok Song

We propose a zero-knowledge interactive proof based identification and signature scheme. The protocol is based on Euler's totient function and discrete logarithms over the ring Z/nZ , and can be applied to smart cards. A prover keeps a signed subgroup generator provided by a trusted center as its secret information. Our scheme has symmetricity in the sense that the same computational complexity and the same hardware both for Prover and for Verifier are required. Also, it requires minimal amount of computation and communications for secret information. The protocol is versatile enough to be applicable to digital signature scheme, multiple digital signature scheme and key exchange protocol. We outline those protocols to show the versatility of our protocol.

Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali

We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape. All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting. Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting. Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct:

Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung

Article On zero-knowledge proofs (extended abstract): "from membership to decision" Share on Authors: Giovanni Di Crescenzo Telcordia Technologies Inc., 445 South Street, Morristown, NJ Telcordia Technologies Inc., 445 South Street, Morristown, NJView Profile , Kouichi Sakurai Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, Japan Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, JapanView Profile , Moti Yung CertCo, New York, NY CertCo, New York, NYView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 255–264https://doi.org/10.1145/335305.335336Online:01 May 2000Publication History 3citation509DownloadsMetricsTotal Citations3Total Downloads509Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Taekyoung Kwon

This paper presents a new password authentication and key agreement protocol, AMP, based on the ampli ed password idea. The intrinsic problems with password authentication are the password itself has low entropy and the password le is very hard to protect. We presentthe ampli ed password proof and the ampli ed password le for solving these problems. A party commits the high entropy information and ampli es her password with that information in the amplifed password proof. She never shows any information except that she knows it. Our ampli ed password proof idea is very similar to the zero-knowledge proof in that sense. We adds one more idea � the ampli ed password le for password le protection. Aserver stores the ampli ed veri ers in the ampli ed password le that is secure against a server le compromise and a dictionary attack. AMP mainly provides the password-veri er based authentication and the Di e-Hellman based key agreement, securely and e ciently. AMP is easy to generalize in any other cyclic groups. In spite of those plentiful properties, AMP is actually the most e cient protocol among the related protocols due to the simultaneous multiple exponentiation method. Several variants such as AMPi,AMPn,AMPn+, AMP +,AMP++, and AMPc are also proposed. Among them, AMPn is actually the basic protocol of this paper that describes the ampli ed password proof idea while AMP is the most complete protocol that adds the ampli ed password le. AMPi simply removes the ampli ed password le from AMP.Intheend,wegive a comparison to the related protocols in terms of e ciency. This manuscript is a preliminary version of our paper available from the IACR eprint archive,

Christian Cachin, Jan Camenisch

No abstract is available for this record.

Yevgeniy Dodis, Shai Halevi, Tal Rabin

Abstract. In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing ” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payoffs can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payoffs offered by mediator-assisted strategies. We answer this question affirmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game. The main building block of our solution is an efficient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games. 1