Blockchain Papers

Marc Girault, Guillaume Poupard, Jacques Stern

No abstract is available for this record.

Mehmet Tahir Sandıkkaya, Bülent Örencik

Many electronic voting systems, classified mainly as homomorphic cryptography based, mix-net based and blind signature based, appear after the eighties when zero knowledge proofs were introduced. The common ground for all these three systems is that none of them works without real time cryptologic calculations that should be held on a server. As far as known, the agent-based approach has not been used in a secure electronic voting system. In this study, an agent-based electronic voting schema, which does not contain real time calculations on the server side, is proposed. Conventional cryptologic methods are used in the proposed schema and some of the requirements of an electronic voting system are constructed within the schema. The schema seems quite secure if the used cryptologic methods and agents are secure. In this paper, proposed schema will be explained and compared with already known electronic voting systems.

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.

Sungho Maeung

Recent studies argue that traditional voting systems do not encourage increased voter participation due to constraints in time, location, accuracy, and, accessibility. To ensure the rights of a democratic society and to enhance and secure the voting rights of citizens by surpassing all the limitations of the traditional voting system, the development of an electronic voting system is an attractive solution. Research on secure electronic voting systems has been conducted for at least the past two decades. We propose to develop an electronic voting system, called the Rochester Institute of Technology Student Government Election System (SGEES) based on Damgard et al. This voting scheme will use efficient honest-verifier zero-knowledge, which, unlike previous election schemes, are both easy to compute and to verify for both voters and authorities. Our proposed electronic voting system will allow convenient and confident voting while maintaining the accuracy of election results. This project will address the security requirements for electronic voting over the Internet, including privacy, completeness, soundness, receipt-freeness, and universal verifiability. In particular, we will research the feasibility of the voting scheme and protocols by studying three related cryptographical theories: homomorphic encryption, efficient honest-verifier zero-knowledge proofs, and threshold decryption cryptosystem.

Serge Abiteboul, Bogdan Cautis, Amos Fiat, T. Milo

The common assumption about digital signatures is that they disallow any kind of modification on signed data. However, a more flexible approach is often needed and has been advocated lately, one in which some restricted modifications may still occur, without invalidating the data. This is made possible by offering signatures which are homomorphic with respect to some operation on the message domain. Starting from the signature(s) of some data instance(s), computed by the data owner, anybody else can derive the signature corresponding to a new data instance, if obtained only via some accepted operation from the previous one(s). More, updated signatures should be indistinguishable from the ones computed by the data owner and this updating step should be applicable as many times as needed. This paper deals with the signing of insert-only collections, in which element insertions are accepted but no removals should occur. Newly inserted elements do not have to be signed or known by the initial signer. We propose two techniques: one which transposes the insert-only problem into a delete-only one (which is already solved), and another technique based on zero-knowledge proofs. We also give performance measures and discuss applications.

Sven Laur, Helger Lipmaa

No abstract is available for this record.

David Wagner

No abstract is available for this record.

Jens Groth, Rafail Ostrovsky, Amit Sahai

No abstract is available for this record.

John Watrous

This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich–Micali–Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{QSZK}= \mathrm{QSZK}_{\mathrm{HV}}$. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.

Theodoros Balopoulos, Stephanos Gritzalis, Sokratis Katsikas

Esoteric protocols, such as electronic cash, electronic voting and selective disclosure protocols, use special message constructors that are not widely used in other types of protocols (for example, in authentication protocols). These message constructors include blind signatures, commitments and zero-knowledge proofs. Furthermore, a standard formalization of the Dolev-Yao intruder [6] does not take into account these message constructors, nor does it consider some types of attacks (such as privacy attacks, brute-force dictionary attacks and known-plaintext attacks) that esoteric as well as other types of protocols are designed to protect against. This paper aims to present an extension of typed MSR [3, 4] in order to formally specify the needed message constructors, as well as the capabilities of a Dolev-Yao intruder designed to attack esoteric protocols.

Endre Bangerter

Diese Dissertation befasst sich mit effizienten zero-knowledge Beweisen von Wissen für Homomorphismen. Einerseits\nuntersuchen wir die Effizienzbeschränkungen bestehender Beweise von Wissen für Homomorphismen, andererseits\nbeschreiben wir neue Protokolle, welche diese Beschränkungen zu überwinden vermögen. Die Hauptresultate der Arbeit\nsind die Folgenden:\n- Alle effizienten Beweise von Wissen wurden, vor unserer Arbeit, mittels des Sigma Protokolls erzielt. Wir zeigen auf,\ndass für das Sigma Protokoll inhärente und demnach prinzipiell nicht überwindbare Effizienzbeschränkungen bestehen.\n- Insbesondere waren für die praktisch bedeutsame Klasse von Exponentiations-Homomorphismen in Gruppen unbekannter\nOrdnung (wie z.B., RSA- oder Klassengruppen) bisher keine effizienten zero-knowledge Beweise von Wissen bekannt. Wir\nbeschreiben neue Protokolle, die erstmalig effiziente zero-knowledge Beweise von Wissen für Exponentiations-\nHomomorphismen in Gruppen unbekannter Ordnung liefern.

Kaoru Kurosawa, Swee‐Huay Heng

Abstract. In undeniable signature schemes, zero-knowledgeness and non-transferability have been identified so far. In this paper, by separating these two notions, we show the first 3-move confirmation and disavowal protocols for Chaum’s undeniable signature scheme which is secure against active and concurrent attacks. Our main observation is that while the signer has one public key and one secret key, there exist two witnesses in the confirmation and disavowal proofs of Chaum’s scheme.

Jonathan Katz, Yehuda Lindell

No abstract is available for this record.

Joël Alwen, Giuseppe Persiano, Ivan Visconti

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

Rafael Pass, Abhi Shelat

No abstract is available for this record.

Matt Lepinski, Silvio Micali, Abhi Shelat

No abstract is available for this record.

Endre Bangerter, Jan Camenisch, Ueli Maurer

No abstract is available for this record.

Craig Gentry, Dávid Molnár, Zulfikar Ramzan

Abstract. Most prior designated confirmer signature schemes either prove security in the random oracle model (ROM) or use general zeroknowledge proofs for NP statements (making them impractical). By slightly modifying the definition of designated confirmer signatures, Goldwasser and Waisbard presented an approach in which the Confirm and ConfirmedSign protocols could be implemented without appealing to general zero-knowledge proofs for NP statements (their Disavow protocol still requires them). The Goldwasser-Waisbard approach could be instantiated using Cramer-Shoup, GMR, or Gennaro-Halevi-Rabin signatures. In this paper, we provide an alternate generic transformation to convert any signature scheme into a designated confirmer signature scheme, without adding random oracles. Our key technique involves the use of a signature on a commitment and a separate encryption of the random string used for commitment. By adding this “layer of indirection, ” the underlying protocols in our schemes admit efficient instantiations (i.e., we can avoid appealing to general zero-knowledge proofs for NP statements) and furthermore the performance of these protocols is not tied to the choice of underlying signature scheme. We illustrate this using the Camenisch-Shoup variation on Paillier’s cryptosystem and Pedersen commitments. The confirm protocol in our resulting scheme requires 10 modular exponentiations (compared to 320 for Goldwasser-Waisbard) and our disavow protocol requires 41 modular exponentiations (compared to using a general zero-knowledge proof for Goldwasser-Waisbard). Previous schemes use the encryption of a signature paradigm, and thus run into problems when trying to implement the confirm and disavow protocols efficiently. 1

Salil Vadhan

We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist. We establish several new characterizations of CZK, and use these characterizations to prove results such as: 1) Honest-verifier CZK equals general CZK. 2) Public-coin CZK equals private-coin CZK. 3) CZK is closed under union (and more generally, "monotone formula closure"). 4) CZK with imperfect completeness equals CZK with perfect completeness. 5) Any problem in CZK /spl cap/ NP can be proven in computational zero knowledge by a BPP/sup NP/ prover. 6) CZK with black-box simulators equals CZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.

Stephen Fenner, Yong Zhang

We study two group theoretic problems, GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, in the setting of black-box groups, where DOUBLE COSET MEMBERSHIP generalizes a set of problems, including GROUP MEMBERSHIP, GROUP FACTORIZATION, and COSET INTERSECTION. No polynomial-time classical algorithms are known for these problems. We show that for solvable groups, there exist efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also study the decision versions of STABILIZER and ORBIT COSET, which generalizes GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, respectively. We show that they reduce to ORBIT COSET under certain conditions. Finally, we show that DOUBLE COSET MEMBERSHIP and DOUBLE COSET NONMEMBERSHIP have zero knowledge proof systems.

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.

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