Follow blockchain research across journals, conferences, and preprint repositories.
9,005 results · page 364 of 376
Cynthia Dwork, Ronen Shaltiel, Adam Smith, Luca Trevisan
No abstract is available for this record.
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano
No abstract is available for this record.
Dalu Zhang
A zero-knowledge proof of identity protocol on conic is proposed in this paper.The security of this protocol is based on the discrete logarithm problem on conic over finite fields.These kinds of identity protocols can be designed and implemented easier than those on elliptic curve,and faster than those based on discrete logarithm.Security and feasibility are discussed.A simple solution is proposed to a potential leak of this protocol.
Masayuki Abe, Serge Fehr
Abstract. We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the nonerasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the singleinconsistent-player UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As an application, we propose a fully UC threshold Schnorr signature scheme. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a sender non-committing encryption scheme, a distributed trapdoor-key generation protocol for Pedersen’s commitment scheme, or distributed-verifier proofs for proving relations among commitments or even any NP relations in general. 1
Ning Chen, Jiawei Rong
Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system,which is extended from the original definition of interactive proof and is more applicable in reality.
Ronald Cramer, Ivan Damgård
No abstract is available for this record.
Rafail Ostrovsky, Charles Rackoff, Adam Smith
No abstract is available for this record.
Boaz Barak, Rafael Pass
No abstract is available for this record.
Luo Wen
In the paper, we present a notion about two directional zero knowledge proof, and study the relation between two directional zero knowledge proof and traditional one directional zero knowledge proof. We propose several simple two directional zero knowledge problem proof protocols. We introduce the two directional zero knowledge proof is to study secure multi party computation. Based on the two directional zero knowledge, we have designed some special function secure two party computation protocols, including exponential function problem, power function problem, logarithmic function problem, trigonometric function problem, and propose some concern protocols.
Aggelos Kiayias, Yiannis Tsiounis, Moti Yung
No abstract is available for this record.
Boaz Barak, Yehuda Lindell, Salil Vadhan
We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of auxiliary-input zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge strong proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin proof system for a nontrivial language that is resettable zero knowledge. This result also extends to bounded-resettable zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication.
Shangping Wang
Zero-knowledge proof schemes of possessing a RSA digital signature are proposed. The schemes give a new method of preventing arbitrary propagation of digital signature. By which the prover does not need to give directly the signature of the message, but to give a zero-knowledge proof of possessing a digital signature. The schemes are the improvement of confirm signature, and is much simpler in practice and of significant feature that it does not need the third party to take part in the scheme. The schemes can be used in copyright protection.
Sultan Almuhammadi, Nien T. Sui, Donald C. McLeod
We propose an approach using elliptic curve-based zero-knowledge proofs in e-commerce applications. We demonstrate that using elliptic curved-based zero-knowledge proofs provide privacy and more security than other existing techniques. The improvement of security is due to the complexity of solving the discrete logarithm problem over elliptic curves.
Ivan Damgård, Serge Fehr, Louis Salvail
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting.<br /> <br />We propose new techniques for building <em>quantum</em> zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK.<br /> <br />As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks.<br /> <br />Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, <em>non-oblivious verifier</em> QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
Alon Rosen
No abstract is available for this record.
Emmanuel Godard, Yves Métivier
No abstract is available for this record.
Hsiang‐An Wen, Chein-Min Lo, Tzonelih Hwang
Ma and Chen have proposed an authenticated encryption scheme with public verifiability. The scheme claims that the TTP can publicly verify the sender's signature without running a zero knowledge proof protocol. The problem in verification which causes the TTP to reject a valid signature with non-negligible probability is pointed out.
Oded Goldreich
No abstract is available for this record.
Jung Min Park, Edwin K. P. Chong, Howard Jay Siegel
Applications such as e-commerce payment protocols, elec-tronic contract signing, and certified e-mail delivery require that fair exchange be assured. A fair-exchange protocol al-lows two parties to exchange items in a fair way so that either each party gets the other's item, or neither party does. We describe a novel method of constructing very ef-ficient fair-exchange protocols by distributing the computa-tion of RSA signatures. Specifically, we employ multisig-natures based on the RSA-signature scheme. To date, the vast majority of fair-exchange protocols require the use of zero-knowledge proofs, which is the most computationally intensive part of the exchange protocol. Using the intrinsic features of our multisignature model, we construct protocols that require no zero-knowledge proofs in the exchange proto-col. Use of zero-knowledge proofs is needed only in the pro-tocol setup phase--this is a one-time cost. Furthermore, our scheme uses multisignatures that are compatible with the underlying standard (single-signer) signature scheme, which makes it possible to readily integrate the fair-exchange fea-ture with existing e-commerce systems.
Boaz Barak
We present the first constant-round non-malleable commitment scheme and the first constant-round non-malleable zero-knowledge argument system, as defined by Dolev, Dwork and Naor (1991). Previous constructions either used a non-constant number of rounds, or were only secure under stronger setup assumptions. An example of such an assumption is the shared random string model where we assume all parties have access to a reference string that was chosen uniformly at random by a trusted dealer. We obtain these results by defining an adequate notion of non-malleable coin-tossing, and presenting a constant-round protocol that satisfies it. This protocol allows us to transform protocols that are non-malleable in (a modified notion of) the shared random string model into protocols that are non-malleable in the plain model (without any trusted dealer or setup assumptions). Observing that known constructions of a non-interactive non-malleable zero-knowledge argument systems in the shared random string model (De Santis et. al., 2001) are in fact non-malleable in the modified model, and combining them with our coin-tossing protocol we obtain the results mentioned above. The techniques we use are different from those used in previous constructions of non-malleable protocols. In particular our protocol uses diagonalization and a non-black-box proof of security (in a sense similar to Barak's zero-knowledge argument (2001)).
John Watrous
In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZK/sub HV/. We prove several facts regarding this class, including: the following problem is a complete promise problem for QSZKHV: given instructions for preparing two mixed quantum states, are the states close together or far apart in the trace norm metric? This problem is a quantum generalization of the complete promise problem of Sahai and Vadhan (1997) for (classical) statistical zero-knowledge; QSZK/sub HV/ is closed under complement; QSZK/sub HV//spl sube/PSPACE. (At present it is not known if arbitrary quantum interactive proof systems can be simulated in PSPACE even for one-round proof systems); any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a two-message (i.e., one-round) honest verifier quantum statistical zero-knowledge proof system. Similarly, any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a three-message public-coin honest verifier quantum statistical zero-knowledge proof system. These facts establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems. The relationship between our definition and possible definitions of general (i.e., not necessarily honest) quantum statistical zero-knowledge are also discussed.
Manoj Prabhakaran, Alon Rosen, Arun Sahai
We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using O/spl tilde/(log n) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP requires at least /spl Omega//spl tilde/(log n) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw free functions. Assuming only the existence of one-way functions, we show the existence of O/spl tilde/(log n)-round concurrent zero-knowledge arguments for all languages in NP.
Boaz Barak, Oded Goldreich
We put forward a new type of computationally-sound proof systems, called universal-arguments, which are related but different from both CS-proofs (as defined by Micali, 2000) and arguments (as defined by Brassard et al., 1986). In particular, we adopt the instance-based prover-efficiency paradigm of CS-proofs, but follow the computational-soundness condition of argument systems (i.e., we consider only cheating strategies that are implementable by polynomial-size circuits). We show that universal-arguments can be constructed based on standard intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to subexponential-size circuits as used in the construction of CS-proofs). As an application of universal-arguments, we weaken the intractability assumptions used in the recent non-black-box zero-knowledge arguments of Barak (2001). Specifically, we only utilize intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to circuits of some "nice" super-polynomial size).
André Adelsbach, Ahmad‐Reza Sadeghi
Digital watermarking is a promising technology for protecting intellectual property rights on digital content. Resolving authorship-disputes was one of the first and most propelling applications of robust digital watermarks, and much research effort has gone into protocols for resolving authorship-disputes by means of digital watermarks. Unfortunately, previous proposals lack formal definitions of their trust model, their assumptions, and requirements they should fulfill. This lack of formal definitions makes security proofs for such protocols impossible and many dispute resolving protocols, claimed to be secure, can be shown to be insecure. In this paper we set off to rigorously defining dispute resolving schemes based on a reasonable formal definition of "authorship." Building on this formal fundament, we analyze the most important proposals for dispute resolving, and discuss their connection to our authorship model. We show that existing proposals suffer from two major problems: First, they require an unnecessary high level of trust in the dispute resolving party. The second and even more serious is that the winner of the dispute is not guaranteed to be the rightful author of the disputed work (conclusiveness problem). As solutions, we propose dispute resolving schemes based on zero-knowledge watermark detection and asymmetric watermarking schemes.