Blockchain Papers

Guomin Yang, Jing Chen, Duncan S. Wong, Xiaotie Deng · 5 authors

No abstract is available for this record.

Martin Döring

Public-key cryptography is a key technology for making the Internet and other IT infrastructures secure. The security of the established public-key cryptosystems relies on the difficulty of factoring large composite integers or computing discrete logarithms. However, it is unclear whether these computational problems remain intractable in the future. For example, Shor showed in 1994 that quantum computers can be used to factor integers and to compute discrete logarithms in polynomial time. It is therefore necessary to develop alternative public-key cryptosystems which do not rely on the difficulty of factoring or computing discrete logarithms and which are secure even against quantum computer attacks. We call such cryptosystems quantum-immune. To prove the security of these quantum-immune cryptosystems, appropriate security models have to be used. Since quantum computers are able to solve problems in polynomial time which are supposed to be intractable for classical computers, the existing security models are inadequate in the presence of quantum adversaries. Therefore, new security models have to be developed to capture quantum adversaries. Properties of these new security models have to be investigated. On a more practical level, the quantum-immune cryptosystems have to be implemented in a way that they can seamlessly replace established cryptosystems. The implementations have to be efficient and suitable for resource-constrained devices. They must easily integrate into existing public-key infrastructures. This thesis contributes to both the theory and practice of quantum-immune cryptography, addressing the above-mentioned challenges. In the theoretical part, we concentrate on the quantum zero-knowledge property of interactive proof systems. We show for the first time that the quantum statistical, perfect, and computational zero-knowledge properties are preserved under sequential composition of interactive proof systems. In the practical part, we provide implementations of the most important quantum-immune cryptosystems. We present efficiency improvements of some of the alternative cryptosystems. The implementations are very efficient and easily integrate into existing public-key infrastructures. We present comprehensive timings that show that the alternative cryptosystems are competitive or even superior compared to established cryptosystems. Finally, we present a new cryptographic API that is particularly well-suited for resource-constrained devices like mobile phones and PDAs. With this API, the alternative cryptosystems can also be used with these devices.

Tatsuaki Okamoto, Kazuo Ohta

No abstract is available for this record.

Yacov Yacobi, Zahava Shmuely

No abstract is available for this record.

Adi Shamir

No abstract is available for this record.

Jens Groth, Steve Lu

No abstract is available for this record.

Éric Filiol

This paper presents a protocol aiming at proving that an encryption system contains structural weaknesses without disclosing any information on those weaknesses. A verifier can check in a polynomial time that a given property of the cipher system output has been effectively realized. This property has been chosen by the prover in such a way that it cannot been achieved by known attacks or exhaustive search but only if the prover indeed knows some undisclosed weaknesses that may effectively endanger the cryptosystem security. This protocol has been denoted zero-knowledge-like proof of cryptanalysis. In this paper, we apply this protocol to the Bluetooth core encryption algorithm E0, used in many mobile environments and thus we suggest that its security can seriously be put into question.

Tatsuaki Okamoto, David Chaum, Kazuo Ohta

No abstract is available for this record.

Marc Girault, Guillaume Poupard, Jacques Stern

No abstract is available for this record.

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.

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.

Jonathan Katz, Yehuda Lindell

No abstract is available for this record.

Jens Groth

Abstract. A shuffle consists of a permutation and re-encryption of a set of input ciphertexts. One application of shuffles is to build mix-nets. We suggest an honest verifier zero-knowledge argument for the correctness of a shuffle of homomorphic encryptions. Our scheme is more efficient than previous schemes both in terms of communication and computation. The honest verifier zero-knowledge argument has a size that is independent of the actual cryptosystem being used and will typically be smaller than the size of the shuffle itself. Moreover, our scheme is well suited for the use of multi-exponentiation and batch-verification techniques. Additionally, we suggest a more efficient honest verifier zero-knowledge argument for a commitment containing a permutation of a set of publicly known messages. We also suggest an honest verifier zero-knowledge argument for the correctness of a combined shuffle-and-decrypt operation that can be used in connection with decrypting mix-nets based on ElGamal encryption. All our honest verifier zero-knowledge arguments can be turned into honest verifier zero-knowledge proofs. We use homomorphic commitments as an essential part of our schemes. When the commitment scheme is statistically hiding we obtain statistical honest verifier zero-knowledge arguments; when the commitment scheme is statistically binding we obtain computational honest verifier zero-knowledge proofs. Key words. Shuffle, Honest verifier zero-knowledge argument, Homomorphic encryption, Mix-net. 1

Matthias Bauer

We present a protocol for verification of ``no such entry'' replies from databases. We introduce a new cryptographic primitive as the underlying structure, the keyed hash tree, which is an extension of Merkle's hash tree. We compare our scheme to Buldas et al.'s Undeniable Attesters and Micali et al.'s Zero Knowledge Sets.

Boaz Barak, Rafael Pass

No abstract is available for this record.

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.

Anna Redz

This thesis is written for the Swedish degree Licentiate ofScience, Teknisk Licentiat.It is a university degree, between that of master andthat of doctor.The main focus of the thesis is on the construction ofsecure protocols for comparing the underlying plain-texts inElGamal encryptions. The protocols make use of the malleabilityof the ElGamal encryption scheme. More specifically they usethe multiplicative homomorphic property of ElGamal.We present fully verifiable protocols for both thetwo-party setting and the multi-party setting. These protocolsare built on sub-protocols, which are specially constructed tofit the present setting. We also present full proofs forcompleteness, soundness, and zero-knowledge for all the givenprotocols, in the random oracle model.

Jens Groth

No abstract is available for this record.

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.

Hervé Sibert, Patrick Dehornoy, Marc Girault

Abstract. Artin’s braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in [2, 3, 18] (see also [22]). A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements. 1.

Ronald Cramer, Victor Shoup

We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier's Decision Composite Residuosity (DCR) assumption, while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model.<br /> <br />We also introduce the notion of a universal hash proof system. Essentially, this is a special kind of non-interactive zero-knowledge proof system for an NP language. We do not show that universal hash proof systems exist for all NP languages, but we do show how to construct very efficient universal hash proof systems for a general class of group-theoretic language membership problems.<br /> <br />Given an efficient universal hash proof system for a language with certain natural cryptographic indistinguishability properties, we show how to construct an efficient public-key encryption schemes secure against adaptive chosen ciphertext attack in the standard model. Our construction only uses the universal hash proof system as a primitive: no other primitives are required, although even more efficient encryption schemes can be obtained by using hash functions with appropriate collision-resistance properties. We show how to construct efficient universal hash proof systems for languages related to the DCR and QR assumptions. From these we get corresponding public-key encryption schemes that are secure under these assumptions. We also show that the Cramer-Shoup encryption scheme (which up until now was the only practical encryption scheme that could be proved secure against adaptive chosen ciphertext attack under a reasonable assumption, namely, the Decision Diffie-Hellman assumption) is also a special case of our general theory.

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

Toshiya Itoh, Yuji Ohta, Hiroki Shizuya

No abstract is available for this record.

Oded Goldreich, Ariel Kahan

No abstract is available for this record.