Kazi Md. Rokibul Alam, Shinsuke Tamura, Shuji Taniguchi, Tatsuro Yanase
This paper proposes a new electronic voting (e-voting) scheme that fulfills all the security requirements of e-voting i.e. privacy, accuracy, universal verifiability, fairness, receipt-freeness, incoercibility, dispute-freeness, robustness, practicality and scalability; usually some of which are found to be traded. When compared with other existing schemes, this scheme requires much more simple computations and weaker assumptions about trustworthiness of individual election authorities. The key mechanism is the one that uses confirmation numbers involved in individual votes to make votes verifiable while disabling all entities including voters themselves to know the linkages between voters and their votes. Many existing e-voting schemes extensively deploy zero-knowledge proof (ZKP) to achieve verifiability. However, ZKP is expensive and complicated. The confirmation numbers attain the verifiability requirement in a much more simple and intuitive way, then the scheme becomes scalable and practical.
Digital signatures are fundamental cryptographic primitives. They are useful as a stand-alone application and building blocks of complex cryptographic systems. Accumulators are another useful cryptographic primitive which provide a way to combine a set of values into one short value. They are useful in improving efficiency of cryptographic systems. In particular, these two primitives are key components in privacy-preserving cryptographic systems. In this thesis, we study the use of digital signatures and accumulators in cryptographic applications. We design digital signature schemes and accumulators with different features that are suitable for a wide range of applications. We are interested in privacy-preserving cryptographic applications including anonymous electronic cash systems, anonymous authentication schemes and anonymous credential systems. We construct three different digital signature schemes, each with distinctive features. We also propose two novel constructions of accumulators. Based on our signature schemes and accumulators, we design two compact electronic cash schemes and a divisible electronic cash scheme. All our schemes are truly anonymous, meaning that privacy of the users is well-protected. We also explore other applications of our newly proposed signatures and accumulators. Specifically, we give a construction of k-times anonymous authentication schemes and attribute-based anonymous credential systems. During the course of the development of the thesis, we generalise existing techniques of zero-knowledge proof-of-knowledge protocol of double-discrete logarithms into zero-knowledge proof-of-knowledge protocol of representation of a committed value. Our protocol is compatible with existing zero-knowledge proof-of-knowledge protocols that demonstrate relationship amongst discrete logarithms. We believe that this protocol, together with the newly introduced primitives, are of independent interest.
Non-interactive zero-knowledge (NIZK) proofs can be an extremely powerful tool, allowing one to prove a statement in a single message without revealing any information besides the truth of the statement. Blum et al. showed that NIZK proof systems exist for all languages in NP. However, in practice, NIZK proofs are rarely used, because existing protocols are extremely inefficient. Here we examine some useful languages for which we can give efficient proof system.
We define two useful building blocks: one for proving that a message has been signed, and a second for proving that a value has been chosen according to a pseudorandom function. We give applications of these building blocks to anonymous credential systems, to electronic cash, and to the design of other efficient NIZK proofs systems.
The current political climate has almost ruled out the use of Internet voting.Many politicians, led by vocal computer scientists, are pushing for voter verified paper receipts; which is likely to push us even further away from even electronic voting systems.On the other hand, cryptographers have created homomorphic encryption and non-interactive zero-knowledge proofs with features that can support Internet voting.Adding a few more protocols, including an extended voting period and repeat voting can solve the remaining problems need to make Internet voting at least as secure as existing systems.
In this paper, we study the opacity property of verifiably encrypted signatures (VES) of Boneh et al. (proposed in Eurocrypt 2003). Informally, opacity implies that although some given aggregate signatures can verified, no useful information about the individual signatures is leaked. However, the very fact that an aggregate signature can be verified leaks certain information- that the individual signature is indeed well-formed. Apart from this, is there any other information leaked? In this paper, we show that there is absolutely no other information leaked about the individual signatures when the aggregation contains only two signatures. In more formal terms, we show that VES are Zero-Knowledge (ZK). We then extend the ZK property of VES to propose efficient Additive Non-Interactive Witness-Indistinguishable (A-NIWI) proofs. Intuitively an A-NIWI proof can be considered as a Proof of Knowledge (PoK) of another A-NIWI proof. 1
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.
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.
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.
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
The voting plays important roles in a democratic country. Due to the problems of the existed voting m ethod, the new voting methods, electronic voting system, have been developing using the computer net work and cryptographic techniques. Many electronic voting schemes have been introduced for secure electronic voting systems. In this paper, we propose the secure electronic voting for absentee e-voting system. The absentee voting plays the important percentage in the existing voting system. But, the abs entee vote can not look forward to the security because of transmit by mail. The absentee does not kno w whether one’s voting is exactly counted or not. In this paper, we propose the absentee e-voting syste m based on security, completeness and verifiability. We use r-th residue cryptography for homomorphi c encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm. Also, we propose the ne w method of tallying for multi-candidate. The goals of out voting system are the absentee vot ing based on privacy, universal verifiability, reuseability and multi-candidate.
In this paper, we propose the absentee e-voting system based on security, completeness and verifiability. We use r-th residue cryptography for homomorphic encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm for the secure absentee e-voting.
Olivier Baudron, Pierre-Alain Fouque, David Pointcheval, Jacques Stern · 5 authors
The aim of electronic voting schemes is to provide a set of protocols that allow voters to cast ballots while a group of authorities collect the votes and output the final tally. In this paper we describe a practical multi-candidate election scheme that guarantees privacy of voters, public verifiability, and robustness against a coalition of malicious authorities. Furthermore, we address the problem of receipt-freeness and incoercibility of voters. Our new scheme is based on the Paillier cryptosystem and on some related zero-knowledge proof techniques. The voting schemes are very practical and can be efficiently implemented in a real system.
We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.
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.