Follow blockchain research across journals, conferences, and preprint repositories.
927 results · page 36 of 39
Gao Ji-zhong
Zero-knowledge proof is a protocol, and ElGamal's digital signature is widely applied. Gives a GMR module of zero-knowledge proof about ElGamal's digital signature which has little computation, high reliability, and easy to implement.
Paulo Mateus, Filipe Moura, João Rasga
The use of quantum correlations to attack security protocols is an important research line deserving growing attention. An important class of cryptographic protocols used as building blocks for several other more complex protocols is zero-knowledge proof systems. One of the properties that zero-knowledge proof systems are assumed to satisfy is that it is impossible for the verifier to show to a third party that he has interacted with the prover (impossibility of transferring proofs). Herein, it is shown how Bell pairs, together with tamper-proofing, can be used to break the impossibility of transferring proofs for an important class of zero-knowledge proof systems.
Xun Zhou
A zero-knowledge proof(ZKP) is a powerful tool which can be used and already be used for many cryptographic applications.But for the completeness property and the soundness property the existing zero-knowledge proofs are iterative in nature.The multiple communication rounds makes ZKPs unsuitable in practice.In this thesis,propose a new ZKP protocol which runs in one-round while ensure the completeness property and the soundness property.On the other hand,extend ZKPs to elliptic curves.At last,proposed a necessary condition which was needed by constructing a one-round zero-knowledge proofs protocol.
Jiangtao Li, Ninghui Li, Rui Xue
No abstract is available for this record.
Sultan Almuhammadi, Clifford Neuman
A zero-knowledge proof (ZKP) is an interactive proof that allows a prover to prove the knowledge of a secret to a verifier without revealing it. ZKPs are powerful tools to deal with critical applications in security e-commerce. Existing ZKPs are iterative in nature; their protocols require multiple communication rounds. The cost of iteration makes ZKPs unsuitable in practice. We propose a new protocol that meets all the requirements of ZKPs, yet runs in one round. The new approach substantially reduces computation and communications costs. It makes ZKPs more suitable for practical cryptographic systems for both government and commercial applications.
Marc Girault, Guillaume Poupard, Jacques Stern
No abstract is available for this record.
Rafael Pass
Two long-standing open problems exist on the fringe of complexity theory and cryptography: (1) Does there exist a reduction from an NP-complete problem to a one-way function? (2) Do parallelized versions of classical constant-round zero-knowledge proofs for NP conceal every "hard" bit of the witness to the statement proved? We show that, unless the polynomial-hierarchy collapses, black-box reductions cannot be used to provide positive answers to both questions
Bent Kristoffer Rosvold Onshus
This thesis describes an electronic voting system based on Damg\\aa rd, Jurik and Nielsen's generalization of Paillier's probabilistic public key system. A threshold variant of this homomorphic cryptosystem is used to provide universally verifiable elections, where zero-knowledge proofs are used for proving correctness of votes.\n\nUsing this cryptosystem, an electronic voting system that supports voting for 1 out of $L$ candidates is described. Two types of encoding may be used to prove the validity of the votes. The number of proofs needed using normal encoding is linear in $L$, while the number of proofs needed using binary encoding is logarithmic in $L$. It is shown how to extend the system to allow casting a vote for $t$ out of $L$ candidates. This method may easily be used to carry out elections with weighted votes without any added complexity to the system.\n\nThe system is shown to satisfy the requirements for elections at The Norwegian University of Science and Technology (NTNU). A fully functional implementation of the electronic voting system as a distributed system, using Java Remote Method Invocation, is presented. The implementation is used to analyze the feasibility of using this voting system for future elections at NTNU. The implementation is tested using various keylengths and various election parameters. With a keylength of 1024 bits, the simulated time for verification of complex elections is small enough to be considered universally verifiable.
Bo Yang
Committed oblivious transfer is the natural fusion of one-out-of-two oblivious transfer and bit commitment. Unfortunately, the protocols proposed before are not only complicated but also very inefficient. This paper describes a new committed oblivious transfer protocol based on a first two round string oblivious transfer and bit commitment with XOR. With a first two round string oblivious transfer, the protocol can avoid performing a large number of bit oblivious transfers. And with bit commitment with XOR, zero knowledge proofs are very easy. The protocol is conceptually simple and more efficient. The security and complexity of the protocol are also discussed in this paper.
Masayuki Abe, Serge Fehr
Abstract The notion of non-interactive zero-knowledge (NIZK) is of fundamental importance incryptography. Despite the vast attention the concept of NIZK has attracted since its introduction, one question has remained very resistant: Is it possible to construct NIZK schemesfor any NP-language with statistical or even perfect ZK? Groth, Ostrovsky and Sahai recently positively answers to the question by presenting a couple of elegant constructions. However,their schemes pose a limitation on the length of the proof statement to achieve adaptive soundness against dishonest provers who may choose the target statement depending on thecommon reference string (CRS). In this work, we first present a very simple and efficient adaptively-sound perfect NIZKargument system for any NP-language. Besides being the first adaptively-sound statistical NIZK argument for all NP that does not pose any restriction on the statements to be proven,it enjoys a number of additional desirable properties: it allows to re-use the CRS, it can handle arithmetic circuits, and the CRS can be set-up very efficiently without the need foran honest party. We then show an application of our techniques in constructing efficient NIZK schemes for proving arithmetic relations among committed secrets, whereas previousmethods required expensive generic NP-reductions. The security of the proposed schemes is based on a strong non-standard assumption,an extended version of the so-called Knowledge-of-Exponent Assumption (KEA) over bilinear groups. We give some justification for using such an assumption by showing that thecommonly-used approach for proving NIZK arguments sound does not allow for adaptivelysound statistical NIZK arguments (unless NP ae P/poly). Furthermore, we show that theassumption used in our construction holds with respect to generic adversaries that do not exploit the specific representation of the group elements. We also discuss how to avoid thenon-standard assumption in a pre-processing model.
Yvo Desmedt, Yongge Wang, Mike Burmester
No abstract is available for this record.
Mihir Bellare, Adriana Palacio
This dissertation studies three cryptographic tools: identification schemes---collections of algorithms that enable a party to identify itself to another without revealing information that would facilitate impersonation; zero-knowledge proofs---interactive protocols that efficiently demonstrate the validity of an assertion without conveying any additional knowledge; and plaintext-aware encryption schemes---public-key encryption protocols with the property that the only way to efficiently produce valid ciphertext is to encrypt a message; hence the creator of a ciphertext must know the corresponding plaintext. We first consider two of the most efficient and best-known identification schemes: GQ and Schnorr. The question of whether they can be proved secure against impersonation under active attack had remained open for over ten years. This dissertation provides such a proof for GQ based on the one-more-RSA-inversion assumption, an extension of the usual one-wayness assumption. It also provides such a proof for Schnorr based on a corresponding discrete-logarithm-related assumption. Both results extend to establish security against impersonation under concurrent attack. Next, we falsify an assumption, here called KEA2, underlying the Hada-Tanaka 3-round negligible-error zero-knowledge protocol for NP . Providing such a protocol is a challenging problem that has attracted considerable research effort. The fact that KEA2 is false means that we lose one of the few positive results on this subject. To recover the result, we propose a modification of KEA2. After removing a small bug in the Hada-Tanaka protocol that renders it unsound, we obtain a 3-round, negligible-error zero-knowledge protocol for NP under the discrete-logarithm assumption and our new, suitably modified, assumption. Finally, we address the problem of defining and achieving plaintext-aware encryption in the standard public-key setting. We provide definitions for three notions of increasing strength: PA0, PA1, PA2, chosen so that security against chosen-plaintext attack (IND-CPA1) coupled with PA1 implies security against non-adaptive chosen-ciphertext attack (IND-CCA1), and IND-CPA coupled with PA2 implies security against adaptive chosen-ciphertext attack (IND-CCA2). Towards achieving the new notions, we show that a scheme due to Damgard, denoted DEG, and Cramer-Shoup lite are both PAO under Damgard's DHK0 assumption, and PAI under an extension of DHK0. DEG is thus the most efficient scheme proved IND-CCA1-secure.
Ronald L. Rivest, Stephen A. Weis
This dissertation presents new constructions and security definitions related to three areas: authentication, cascadable and commutative crytpography, and private set operations. Existing works relevant to each of these areas fall into one of two categories: efficient solutions lacking formal proofs of security or provably-secure, but highly inefficient solutions. This work will bridge this gap by presenting new constructions and definitions that are both practical and provably-secure. The first contribution in the area of efficient authentication is a provably-secure authentication protocol named HB+. The HB+ protocol is efficient enough to be implemented on extremely low-cost devices, or even by a patient human with a coin to flip. The security of HB+ is based on the hardness of a long-standing learning problem that is closely related to coding theory. HB+ is the first authentication protocol that is both practical for low-cost devices, like radio frequency identification (RFID) tags, and provably secure against active adversaries. The second contribution of this work is a new framework for defining and proving the security of cascadable crypt osystems, specifically commutative cryptosystems. This new framework addresses a gap in existing security definitions that fail to handle cryptosystems where ciphertexts produced by cascadable encryption and decryption operations may contain some message-independent history. Several cryptosystems, including a new, practical commutative cryptosystem, are proven secure under this new framework. Finally, a new and efficient private disjointness testing construction named HW is offered. Unlike previous constructions, HW is secure in the face of malicious parties, but without the need for random oracles or expensive zero-knowledge protocols. HW is as efficient as previous constructions and may be implemented using standard software libraries. The security of HW is based on a novel use of subgroup assumptions. These assumptions may prove useful in solving many other private set operation problems. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
Yuen-Yan Chan, Jin Li
No abstract is available for this record.
Goichiro Hanaoka, Hideki Imai
In this paper, we propose a generic construction of chosen-ciphertext secure cryptosystems against adversaries with a bounded number of decrytion queries from arbitrary semantically secure encryption in a black box manner. Our construction is not only an alternative to the previously known technique, i.e. the Naor-Yung paradigm [37, 19, 42], but also has some interesting properties. Especially, (1) it does not require non-interactive zero-knowledge proof, and (2) its component ciphertexts can be compressed into only one if the underlying encryption has a certain homomorphic property. Consequently, when applying our construction to the ElGamal encryption, ciphertext overhead of the resulting scheme will be only one group element which is considered optimal since it is the same as the original ElGamal. Disadvantages to previous schemes are that the upper bound of the number of decryption queries (e.g. 2 30) has to be known before set-up phase, and the size of public key is large. 1
Boaz Barak
No abstract is available for this record.
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).
Giuseppe Persiano, Ivan Visconti
No abstract is available for this record.
J. Hammell, André Weimerskirch, J. Girão, Dirk Westhoff
This paper formally defines recognition as a new security principle closely related to authentication. Low-power sensor networks with no pre-deployment information require the less authoritative security of recognition. We give general properties of recognition protocols based on the method of key disclosure. We examine previously proposed low-power protocols according to the environment and security model presented. Finally, we give measurements from an implementation of a recognition protocol called zero common-knowledge and discuss how well this proof-of-concept satisfies the properties of the environment.
Dalu Zhang, Min Liu, Zhe Yang
A protocol for zero-knowledge proofs of identity based on ElGamal on conic is proposed in this paper. The solution to a hard puzzle is divided into two parts, and the P (prover) provides one of them according to the V (verifier) 's random bit. The eavesdropper cannot obtain any useful knowledge about the P (prover) 's identity during the process of authentication. No adversary in this protocol can cheat each other or get the privacy of each other. The security of this protocol relies on the discrete logarithm problem on conic over finite fields. Compared with those identification protocols implemented on elliptic, these kinds of identification protocols implemented on conic can be designed and implemented easier. Corresponding to the simple version, a parallel version is presented subsequently. The characteristic of ZKp and security of the simple version is proved. The trait of our identification protocol is given. We also analyzed the "soundness ", the "completeness ", before analyzed the amount of computation in the protocol. A simple solution considering t/sub timeout/ is proposed to prevent a potential leak of our protocol. Some problems need to be solved in the future is brought forward at the end of this paper.
Feng Jian
Subliminal channel is proposed by Simmons, he showed a method that a message authentication without secrecy channel transferring secret message. Subsequently, subliminal channel is implemented in ElGamal, DSA which based on the difficulty of discrete logarithms. Zero-knowledge proof is an important tool in cryptology, a digital signature scheme based on zero-knowledge proof or “cut and chose” is regarded as resist subliminal channel. The possibility of constructing subliminal channel in these digital signature scheme is analyzed, the security and application of subliminal channel is discussed also.
Giovanni Di Crescenzo
The need for cryptography has been recognized since ancient times. One of its main goals, private communication in the presence of adversary, is traced back to the ancient Roman empire, whose emperor Julius Ceasar used to communicate to his allies by replacing each letter in his message with the third next letter in the alphabet. Classical cryptography went on until the end of last century focusing on the art of designing and breaking secrecy codes. Modern cryptography has significantly enlarged its scope to the rigorous analysis of any system that is potentially subject to malicious threats and the design of solution that can guarantee the system to withstand such threats. As a consequence, many goals have been added to that of private communication in the presence of adversary, and cryptography has moved from an engineering art built on a number of heuristic techniques to a scientific discipline based on mathematically rigorous design requirements, solution techniques and correctness proofs. We present here an introduction to some basic topics in the foundation of modern cryptography; specifically: one-way functions, pseudo-random generators, pseudo-random functions and zero-knowledge protocols.
Wei Chen
It is shown in this paper that a kind of new cryptographic primitive proposed by Zheng in 1997, Signcryption, may be applied to construct distributed cryptographic protocols. In fact, the protocols based on Signcryption have the following two properties: Each message exchanged between two participants can be transferred in short data packet, and messages that carry key materials are unforgeable and non-repudiatable without the involvement of a trusted key distribution center. Firstly, based on the modified signcryption scheme of Zheng and Verifiable Secret Sharing(VSS) idea, this paper gives a kind of threshold signcryption scheme without any trusted center for the first time. Furthermore, this scheme can gain its ends of both threshold signature and threshold encryption simultaneously and the costs is much cheaper. In addition, non-repudiation is also offered. Secondly, by analyzing recent distributed key generation protocols, especially Naor’s idea, it put forward a new protocol mainly based on signcryption, called SC-DKDS. Compared with others, SC-DKDS does not need any additional costs, such as authentication channels, private channels or any complicated zero knowledge proofs. The security proofs of the protocols mentioned above are given in RO(Random Oracle) model.
Amitabh Saxena, Serguey Priymak, Ben Soh
In identification protocols with public verifier coins (like Fiat-Shamir), a passive adversary watching the communication gains information intended only for the verifier. On the other hand, private coin protocols with fewer than three rounds cannot be zero-knowledge. In this paper, we introduce the notion of bounded-prover zero-knowledge proofs which require only two rounds and can be considered perfectly zero-knowledge under certain intractibility assumptions. Specifically, we exploit the gap between two computational problems to achieve zero-knowledge in a dishonest verifier scenario.