Thesis



implementing a

paillier threshold cryptography scheme

as a web service

by

Brett Wilson

A Master’s project

submitted in partial fulfillment

of the requirements

for the degree of

Master of Science in Computer Science

University of Colorado – Colorado Springs

Fall 2006

Approved by

Chairperson of Supervisory Committee

Date

UNiversity of colorado – colorado springs

Abstract

implementing a paillier threshold cryptography scheme as a web service

BY

Brett Wilson

Chairperson of the Supervisory Committee

Professor C. Edward Chow

Department of Computer Science

Much recent cryptography research has been focused on solving problems that pertain to secure electronic voting. Specifically, different forms of cryptography are being applied in order to achieve the all-important voting system properties of privacy/anonymity, accuracy, verifiability, receipt-freeness, in-coercibility, and robustness. The Paillier cryptosystem [[i]] based on the composite residuosity class problem has received much of the research interest due to possessing some important properties useful in the e-voting application. In [[ii]], the authors present a verifiably secure threshold variant of Paillier’s scheme, which enables the distribution of trust across a number of system participants, further enabling it’s use in the e-voting application. This paper presents an implementation of that scheme as a web service. In this implementation, the web service serves as the “trusted dealer” and thus removes the requirement for picking the “trusted dealer” from among the users of the cryptosystem. It is envisioned that such a web service could be commercially operated by a universally trusted organization similar to modern public key certificate authorities.

INTRODUCTION 1

Paillier Cryptosystem 1

Threshold Cryptography 3

Paillier Threshold Cryptography 4

PAILLIER THRESHOLD CRYPTOSERVICE IMPLEMENTATION 6

General Architecture 6

Tools 6

General Use Case Descriptions 7

PaillierThresholdCryptoServiceProvider (PTCSP) 7

PTCSP constructor 8

Encrypting a Message 8

Decrypting a Message 8

Combining Decryption Shares 9

Paillier Threshold Cryptography Web Service (PTC Web Service) 9

Obtaining Paillier Threshold Cryptography Parameters 10

Using the Paillier Threshold Parameters 10

DESIGN DISCUSSION 12

Problems and Solutions 12

Generating Large Safe Primes 12

Implementing Shamir Secret Sharing 13

Software Choices 14

Big Integer Support 14

C# BigInteger Class 14

Microsoft Visual J# BigInteger Class 14

GNU Multiprecision Library (GMP) 15

Compiling GMP under Visual Studio 2005 15

Accessing GMP from Visual Basic .NET 15

Generating Test X.509 Certificates 16

Suggested Enhancements and Optimizations 16

Generating Large Safe Primes 16

Web Service Signing of Parameter Data 16

Cryptosystem Optimizations 17

A Non-Interactive Proof That a Given CipherText Encrypts One of a Set of Plaintexts 17

APPENDIX 18

Data Type Descriptions 18

Demonstration E-Voting Application 22

E-Voting System Overview 22

Election Set-Up 22

Obtaining Election Encryption Parameters 23

Creating Ballots 23

Adding Ballots to an Election 24

Vote Format 24

Chapter 1

INTRODUCTION

Paillier Cryptosystem

Pascal Paillier first introduced a cryptosystem based on the composite residuosity class problem in [1]. Paillier described 3 different cryptosystems in [1]. We will only discuss the first of these here. The cryptosystem public parameters n and g, and the secret key SK are obtained as follows: Let n be a modulus n=pq where p and q are prime integers. Let g be an integer of order nα mod n2. The public key is PK=(n,g) and the secret key is SK = λ(n) = lcm((p-1),(q-1)).

To encrypt a message m Є Zn , randomly choose r in Zn* and compute

C=gMrn mod n2

To decrypt c, compute

[pic]

Since 1999 there has been much research into investigating the scheme’s security, extending it’s functionality, and improving it’s efficiency. This interest is due primarily to some unique properties of Paillier’s scheme. Namely, Paillier’s scheme is “homomorphic”, “self-blinding”, and “probabilistic”. The scheme is classified as a homomorphic scheme which in general means that there are certain arithmetic operations that when carried out in the ciphertext space correspond to a known arithmetic operation occurring in the cleartext space. In the case of Paillier’s cryptosystem, the following homomorphisms apply [1]:

For m1; m2 Є Zn and k Є N

D(E(m1) E(m2) mod n2) = m1 +m2 mod n

D(E(m)k mod n2) = km mod n

D(E(m1) gm2 mod n2) = m1 +m2 mod n

D(E(m1)m2 mod n2) = m1m2 mod n

D(E(m2)m1 mod n2)) = m1m2 mod n

Paillier’s cryptosystem also possesses a unique property termed “self-blinding”. This property is defined as follows:

For m Є Zn and r Є N

D(E(m) rn mod n2) = m or D(E(m) gnr mod n2) = m

Essentially what this means is that a ciphertext can be “re-encrypted” with a random parameter without changing the underlying cleartext and without changing the ability to decrypt the ciphertext using the original keypair. This property could be very useful in implementing mix-nets.

Cryptosystems in general fall into two categories: deterministic or probabilistic. A deterministic system produces the same ciphertext for the same cleartext message and key every time. A probabilistic system, such as Paillier’s, includes a randomizing element so that a given cleartext message can be encrypted into any one of a very large set of possible encryption values.

All of these properties could be very useful in implementing secure electronic voting applications. The homomorphic property could help in securing a voter’s privacy as well as greatly reducing the number of decryption operations required in the system (essentially to 1). The property of “self-blinding” could be applied in a mix-net scheme to protect a voter’s anonymity. And finally, the probabilistic property is very important for protecting a voter’s privacy, since no two votes, even if they are identical votes, will be encrypted to an identical ciphertext.

Threshold Cryptography

Threshold Cryptography is a term used to describe a cryptosystem in which the ability to perform a cryptographic function can be distributed amongst several participants in such a way that only through cooperation of a specified subset of the participants can the operation be performed. In addition, if less than the required number of participants attempt to perform the action, no useful information can be constructed or obtained. The threshold value is typically denoted by the letter t. In a threshold system as defined here, only t+1 cooperating authorities can perform the desired cryptographic operation.

[2] describes the essential components of a threshold cryptography system as a key generation algorithm, an encryption algorithm, a share decryption algorithm, and a combining algorithm. First, the key generation algorithm generates the public key parameters, a set of secret key “shares”, and a set of “verifier keys”. The secret key shares are distributed to the participants in a secure manner. The encryption algorithm provides encryption services for an appropriately-sized message m by applying the public key parameters and an encryption algorithm to generate the ciphertext c. The share decryption algorithm is used by each participant with a secret key share to “partially decrypt” the encrypted message c. Each participant also uses the verifier key corresponding to the secret key share to generate a proof of correct encryption. The combining algorithm takes all of the “partial decryptions” or “decryption shares”, verifies their corresponding proofs, and combines the decryption shares to reveal the original message m. The combining step only succeeds if t+1 valid decryption shares are used.

Paillier Threshold Cryptography

To further enable Paillier’s system for use in scenarios where it is desirable to distribute trust between numerous interested parties, other parties have developed threshold versions of Paillier’s system [2][[iii]]. This paper documents an implementation of the scheme as described in [2]. Both [2] and [3] use Shamir’s Secret Sharing Scheme [[iv]] as the method of sharing the secret key among the system participants. They only differ slightly in their encryption and decryption algorithms, in that [3] restricts the selection of the original system parameter g in order to achieve slightly more efficient algorithms. [3] also defines a generalization of Paillier’s scheme which also increases the efficiency of encryption and decryption, especially for larger-sized messages.

The system parameters are chosen in [2]as follows: Choose an integer n, product of two strong primes p and q, such that p=2p’ + 1 and q=2q’ + 1. Let m = p’q’. Let Β be random element in Zn*. Also choose (a,b) Є Zn* x Zn*. Set g = (1 + n)a x bn mod n2. The secret key Β x m is shared with the Shamir scheme: Let a0 = Bm, and randomly choose ai in {0,…n x m – 1} and set f(X) = Σti=0 aiXi. The share si of the ith server Pi is f(i) mod nm. The public key PK consists of g, n, and the value θ = L(gmB) = amB mod n. The verification keys are generated by first finding VK = v as a square that generates the cyclic group of squares in Zn2*. The verification keys VKi can then be obtained with the formulat v(si mod n2.

To encrypt a message M Є Zn , randomly choose r Є Zn* and compute

C=gMrn mod n2

To decrypt C, each participant Pi computes the decryption share ci=c2(si mod n2 using his/her secret share si. He/she also makes a proof of correct decryption which assures that c4( mod n2 and v have been raised to the same power si in order to obtain ci2 and VKi.

And finally, if t + 1 valid shares are available, they can be combined to recover M as follows: Let S be a set of t + 1 valid shares. Compute

[pic]

where [pic]

See [2] for more details on the correctness of the scheme and for proofs of security.

Chapter 2

PAILLIER THRESHOLD CRYPTOSERVICE IMPLEMENTATION

General Architecture

The threshold implementation of Paillier’s cryptosystem uses the algorithms proposed in [2] and described above. It consists of two main software pieces and many small supporting pieces. The main piece is named PaillierThresholdCryptoServiceProvider (PTCSP). It contains all of the algorithms and data handling methods required to fully implement the Paillier Threshold scheme. The second piece is the Paillier Threshold Cryptography Web Service (PTC Web Service) itself, which uses the PTCSP to generate the requested system parameters, properly secure them, and return them to the requestor.

A simple voting application which demonstrates the critical pieces of the threshold cryptosystem was also created. It provides a simple user interface in which to set up and conduct an election using the PTC Web Service to provide the cryptosystem parameters. The voting application as presented here is not fully complete or secure, but what is not should be trivial to complete and is left to an interested reader.

Tools

The entire implementation was written in Microsoft using Microsoft Visual Studio 2005 as the development environment. The PTC Web Service is implemented as an 2.0 Web Service hosted on Microsoft Internet Information Services (IIS) Server. And lastly, the simple e-voting application is a Windows .NET Forms application that also uses an Web Service as a front-end to a Microsoft SQL Server database that is used to store and retrieve election data.

General Use Case Descriptions

The Paillier Threshold Cryptosystem consists of two main pieces. In addition, there are numerous other classes and structures primarily used for organizing and passing data. This section will discuss each piece in more detail and provide more information on the services each piece can provide. All data structures and their constituent types are defined in an XSD format in the Appendix.

PaillierThresholdCryptoServiceProvider (PTCSP)

The class PaillierThresholdCryptoServiceProvider implements all of the necessary algorithms to generate the threshold parameters, encrypt a message, partially decrypt a ciphertext, and combine the partial decryptions to reveal the original message. It is modeled after the Microsoft .NET cryptoserviceprovider model and implements the .NET ICSPAsymmetricAlgorithm interface. Even though it does implement this interface, not all of the required methods are functionally implemented, as they were not required for implementing the desired functionality for this project.

The PTCSP holds two main pieces of data. The first of these is the cryptosystem parameters of type PaillierThresholdParameters. This structure can hold both the public and private keys, the secret key shares, and the system parameters specifying the number of shares and the threshold value. This structure can be initialized with new parameters upon instantiation of the PTCSP class, or imported into an existing PTCSP object. Most of the methods of the PTCSP class utilize various values in the parameters structure, so it is important that these parameters are initialized correctly.

The other main data piece is the DecryptionShares list, exposed as a public property of generic type List(Of ThresholdDecryptionShares). This list can either be populated by “importing” decryption shares obtained from participants in the system, or generated from a given ciphertext and the secret key shares present in the parameters data structure. This list is used by the combining algorithm when reconstructing the original message.

PTCSP constructor

The PTCSP constructor is overloaded four times. The default constructor does not initialize any parameters. A second constructor takes a keysize parameter and creates a public key of the specified size and a private set of parameters with only one decryption share and the threshold value set at 0. This provides for a standard (non-threshold) Paillier cryptosystem. A third constructor takes as a parameter a PaillierThresholdParameters structure and initializes the PTCSP with this set of parameters. A fourth constructor takes as parameters the keysize, the desired number of keyshares, and the desired threshold value and creates a set of parameters with these values.

Encrypting a Message

To encrypt a message, two overloads of the Encrypt method are provided. The first method takes as input a message consisting of an array of bytes, and a random array of bytes. It uses the internal public key and the provided random value to encrypt the given message. The second overload is also “shared” or “static” and takes as input a message array of bytes, a public key of type PaillierPublicKey, and a random array of bytes. It is provided as a shortcut method to encrypt a message without having to fully instantiate the class, load a public key, and then call the encrypt method.

Decrypting a Message

Once again, there are two overloads provided for decrypting a message. In the decryption case, however, the results are significantly different. The first overload takes as input only the ciphertext as an array of bytes. It then uses the internally stored secret key shares to generate decryption shares and validity proofs, and then combines these shares to recover the cleartext message. This process assumes that a sufficient number of secret key shares are available in the PaillierThresholdParameters structure, or it will fail with an exception.

The other overload would be used by an individual system participant to partially decrypt a ciphertext using his/her decryption share. This overloaded method takes as parameters the ciphertext as a byte array, the secret key share as type PaillierThresholdKeyShare, and a verifier key as type PaillierThresholdVerificationKey. It computes the partial decryption, the proof of correct decryption, inserts them both into a PaillierThresholdDecryptionShare type and then inserts it into the DecryptionShares list. A user application could then serialize the resulting decryption share to an XML file for transmission to a combining authority who would combine shares from all the participants to recover the message.

Combining Decryption Shares

Once the DecryptionShares list has been populated with the required t + 1 decryption shares, calling the CombineDecryptionShares method with return a byte array with the reconstructed cleartext message. CombineDecryptionShares iterates through the DecryptionShares list, verifies each proof of correct decryption, and then combines the valid shares to obtain the unencrypted message. The combining algorithm will throw an exception if t + 1 valid decryption shares are not available.

Paillier Threshold Cryptography Web Service (PTC Web Service)

The PTCSP class by itself can be used by a trusted party to generate the Paillier threshold parameters and distribute them to the participants. In many situations, it may be difficult to identify a “trusted dealer” acceptable to all parties. For this reason, the Paillier Threshold Cryptography Web Service was created. The idea is that the Web Service would be run (and secured) by a completely disinterested party in much the same manner as a Certification Authority in the modern Public Key Infrastructure. In this manner, the trust is removed from the “participants” and placed with the web service.

Obtaining Paillier Threshold Cryptography Parameters

A user wishing to obtain Paillier threshold parameters calls the GeneratePaillierThresholdParameters method of the web service with the appropriate parameters. The parameters are supplied as an XML serialization of the ThresholdParameterRequest structure. The parameters include the desired keysize, the number of key shares to generate, the system threshold value, and an array of OwnerInfo types that each contain the key share owner’s name and, optionally, his/her X.509 certificate.

Upon receiving a request, the web service instantiates a PTCSP object by calling the appropriate constructor to generate the parameters as requested. Once the parameters are obtained, the web service iterates through the secret key shares and encrypts each key share with the target owner’s RSA public key and sets the “encrypted” flag true for each key share (if X.509 certificates are provided). If no X.509 certificates are provided, the key shares are returned un-encrypted, which basically invalidates the use of the web service since the requestor must now be trusted not to access the secret key shares.

Using the Paillier Threshold Parameters

The parameters are returned by the web service as an XML serialization of the PaillierThresholdParameters structure. The contents of this structure are defined in the Appendix. The client must deserialize the returned XML into a PaillierThresholdParameters structure in order to pass it to the constructor of a PTCSP object. This is typically done by a web service client in the web service’s proxy class implementation.

Once deserialized, the PaillierThresholdParameters structure is then ready for use by the client. A PTCSP object can be created by passing the PaillierThresholdParameters structure to the PTCSP constructor. Once the PTCSP is created, it can be used to encrypt and decrypt messages.

Chapter 3

DESIGN DISCUSSION

Problems and Solutions

Generating Large Safe Primes

The generation of the Paillier Threshold parameters requires a set of two very large safe prime numbers. The GMP software and .NET both provide methods for generating large random numbers, and the GMP software provides the capability to check a number for probable prime. However, there are no known fast algorithms for directly generating large safe primes. [[v]] details a basic algorithm that involves randomly generating numbers of the desired size, testing for primeness, and then, if prime, testing for safe primality. [[vi]] specifies a simple method to double the speed of the safe prime generation. The ideas of [6] were used in this implementation to help speed up the generation of the safe primes. First, a prime number p of the desired size was found, and then both 2p+1 and (p-1)/2 were checked for primeness. If 2p+1 is prime, then p is the safe prime. If (p-1)/2 is prime then (p-1)/2 is the safe prime.

|Algorithm | |128 |256 |512 |1024 |

| | |bit |bit |bit |bit |

|2x speed |Avg |0.2728 |1.75315 |39.85 |705.5993 |

| |Max |0.885 |4.025 |152.248 |1754.158 |

| |Min |0.052 |0.285 |1.524 |84.523 |

|Regular |Avg |0.3247 |2.34 |50.3496 |1950.934 |

| |Max |0.949 |11.672 |110.558 |9426.193 |

| |Min |0.065 |0.08 |2.103 |57.191 |

Figure 1 – Speed Comparison of prime number generation algorithms

Further speed improvements may be achieved by using the ideas of [[vii]], however, considerably time will still be required to generate 1024 bit and larger safe primes. An acceptable solution to this problem would be to develop a background application that constantly generates safe primes and writes them to a file. The web service could then obtain a safe prime directly from this file, achieving very significant time improvements. This would be a trivial enhancement to the existing web service. This solution is of course only acceptable if the rate of requests does not exceed the rate at which the background application can generate them.

Implementing Shamir Secret Sharing

In the threshold scheme, the secret keys s0,…,si are distributed to the participants with the Shamir Secret Sharing scheme (see Chapter 1). From the algorithm equations given in [2], it is not immediately clear that the share index is a critical piece of the re-assembly of the secret. In other words, the index of each of the secret shares generated during the parameter creation must be saved with the secret share. For example, suppose 5 secret key shares s0,…s4 are generated during the parameter creation and distributed to the 5 participants p0,…p4. Suppose the threshold value of the cryptosystem is 2 and that only 3 of the 5 participants (p0, p2, p3) provide a decryption share as part of the decryption process. The combining algorithm requires knowledge of the share indexes being used (0, 2, 3) in order for the algorithm to work. These indexes are used as the j and j’ indexes in the combining algorithm.

[pic]

where [pic]

In addition, these index values are required to properly index the verification keys in order for the participants to correctly construct the proof of correct decryption. The verification keys must be properly matched to the secret key shares for correct generation and verification of the proof. For these reasons, the share index was included in the data structure defining a secret key share (ShamirShare).

Software Choices

Big Integer Support

The decision to use Microsoft technology was made based on the extensive support for handling XML data, creating web services, and debugging as well as the author’s familiarity with the language and Visual Studio environment. In general, the platform allowed rapid development of the project. However, the one critical component not addressed in the language is the support for handling very large integers necessary for implementing the encryption algorithms. A significant effort was undertaken researching the available solutions, downloading them, and getting them to work in the .NET environment. A short description of each of these options is presented in the next paragraphs.

C# BigInteger Class

This software is a freeware library written by Chew Keong Tan and is available for download at . The goal of the software is to implement the JAVA BigInteger class in C# so as to make it available to other .NET projects. Since it was found that Microsoft has provided this same class functionality this software was never downloaded or used.

Microsoft Visual J# BigInteger Class

Microsoft has implemented the Java BigInteger Class as part of it’s Visual J# runtime library. It can be downloaded from Microsoft. This class provides much of the functionality needed in this implementation. However, one drawback is that many of the methods use the SByte data type as parameters or return types. Since this is not a .NET CLR data type, it is more difficult to work with during conversions for I/O and when using with other .NET classes.

GNU Multiprecision Library (GMP)

The GMP library is a full-featured multiprecision library supporting big integers as well as unlimited precision rational and floating point numbers. It has the most extensive support for different operations on big integers of the solutions researched. It also claims to be the fastest library available. The drawback to using it in a .NET environment is that it is written exclusively in ANSI C, making it impossible to call directly from .NET managed code. Fortunately, two other solutions were found that allowed compiling of GMP in Visual Studio and exposing it to . GMP can be downloaded at .

Compiling GMP under Visual Studio 2005

Research revealed that Brian Gladman has made available a Visual Studio 2005 solution for compiling GMP. It can be found at . The solution involves downloading GMP, and then extracting Brian’s solution into the GMP source code directory structure. A few configuration steps, and you can then compile directly from within VS2005 for several different optimizations of GMP.

Accessing GMP from Visual Basic .NET

A binding of the Win32 GMP .dll has been made available as the NGMP project. NGMP can be downloaded from SourceForge at . Much thanks to the author for making this available. It was somewhat more difficult to set up, as it requires modifying several include and reference paths in the C# and C++ projects. Once compiled, however, the library made it extremely easy to access the GMP functionality from .

Generating Test X.509 Certificates

In order to test the web service’s ability to properly encrypt the secret key shares, a set of test X.509 certificates needed to be generated. At first, a Win32 version of OpenSSL was downloaded and tested. The tool properly generated a test certificate with no problems. However, the process of inserting the certificates into a Windows certificate store is manual and cumbersome. While researching how to do this using .NET, the Visual Studio tool makecert.exe was discovered. This tool will quickly and easily generate X.509 certificates and install them into a designated certificate store (machine or user) automatically. OpenSSL was then abandoned and the MakeCert.exe tool was used to generate the required test certificates.

Suggested Enhancements and Optimizations

Generating Large Safe Primes

The generation of the Paillier Threshold parameters requires a set of two very large safe prime numbers. As discussed above, this process is very slow for 512 bit and larger safe primes. A definite improvement would be to implement the background safe prime generator as recommended.

Web Service Signing of Parameter Data

In the current implementation, it would be easy for a corrupt individual to use the PTCSP to create a set of Paillier threshold cryptosystem parameters, properly encrypt the resulting secret key shares with the participants’ public keys, and distribute the parameters as if they were generated by the web service. The corrupted party would then have the ability to decrypt messages as desired. In order to prevent this, there must be a way for a participant to verify that the web service did indeed generate the parameters in question. This could be accomplished by adding the web service’s digital signature to the returned parameters. Further work could be undertaken to determine exactly what data should be signed and where the signatures should be included in the PaillierThresholdParameters structure. It will be necessary to include in the signed data a unique value differentiating the parameter set from others generated by the web service.

Cryptosystem Optimizations

In [3], the authors present an extended version of Paillier’s cryptosystem that allows for larger message block sizes and greatly increases the efficiency of encrypting and decrypting larger messages. In addition, several optimizations are presented to improve the efficiency of the original system. The implementation presented in this paper could be enhanced by incorporating some of these ideas.

A Non-Interactive Proof That a Given CipherText Encrypts One of a Set of Plaintexts

In order for the implementation presented here to be useful in the secure e-voting application, there must be a method to prove the validity of a vote. Otherwise, a corrupt voter could create an invalid vote that corrupts the final tally. In [3], the authors present an interactive proof that proves a given ciphertext encrypts one of a set of plaintexts. This proof could be verified prior to including a vote in the final tally to ensure that the encrypted vote is a valid one. However, a non-interactive version of the proof would decrease the communication complexity, as a voter could construct the proof, and the tallier could verify the proof without requiring interaction between them.

Generation of such a non-interactive proof could be accomplished by applying the Fiat-Shamir heuristic in which the random challenge by the verifier is replaced by a hashed commitment generated by the prover. The details of this proof would be a useful addition to the e-voting application.

APPENDIX

Data Type Descriptions

In addition to the two main software elements (the PaillierThresholdCryptoServiceProvider class and the Paillier Threshold Cryptography Web Service), the implementation includes many other classes and structures primarily used for organizing and transferring data. The following is an XSD schema of those classes generated by running the Visual Studio tool xsd.exe on the ThresholdCryptoLibrary.dll assembly.

Demonstration E-Voting Application

In order to demonstrate the capabilities of the Paillier Threshold Cryptography system, a simple e-voting application was created. The voting system implemented is not fully secure and should not be used for a real voting scenario. However, it does demonstrate the use of the Paillier Threshold Cryptography Web Service and Paillier Threshold CryptoServiceProvider in such a scenario, and how these services can provide the critical components for securing such an application.

E-Voting System Overview

The e-voting system allows for 1 out of L candidate ballots. No options are provided for n out of L ballots or write-in ballots. An “election” may consist of more than one ballot. An election administrator creates the ballots and other election parameters. The administrator requests the Paillier threshold encryption parameters from the PTC Web Service during the initial election set-up. The administrator submits the election parameters to a VotingService web service, and saves the election parameters (including the cryptosystem parameters) to an XML file. Voters then load the election parameters by opening the XML file, make their selection(s), and cast their encrypted vote(s) to the VotingService web service. During the tally phase, the votes are multiplied together, and, due to the homomorphic properties of the Paillier cryptosystem, the product can be decrypted to reveal the sum total of all the votes.

All of the e-voting system functionality can be accessed through the main form of the application by clicking on the desired function.

Election Set-Up

The election administrator uses the Election Builder form to create or modify an election (before the election is posted to the voting web service). To create a new election, the administrator selects File->New. A new election is created and a unique election id is assigned. The administrator must then enter his/her name and a descriptive title for the election.

Obtaining Election Encryption Parameters

Before ballots can be added to the election, the encryption parameters must be specified and retrieved from the web service. This must occur before the ballots are added or created, since the vote format is dependent on the specified key size. The administrator selects Election->Get Encryption Parameters which opens the Encryption Parameter Request form. Using this form, the administrator specifies the key size and whether or not to encrypt the returned key shares. The administrator can then add the key share owner information for each owner that is to receive a secret key share. If the key shares will be encrypted, the administrator will be required to select the owner’s public X.509 certificate when the owner is added. Once all owners have been added, the administrator selects the cryptosystem threshold value and then clicks “Send Request”, which sends the request to the web service. In the current configuration, a key size of larger than 512 bits will result in such a delay that a “timeout” error is caused, so it is not recommended that key sizes greater than 512 be used. The web service will generate the requested parameters, encrypt the key shares (if specified), and return them. The Encryption Parameter Request form will transfer the returned parameters to the Election Builder form and close automatically. The election crypto parameters are displayed at the bottom of the Election Builder form.

Creating Ballots

Existing ballots can now be added to the election or new ballots can be created using the options under the Election menu. To create a new ballot, the administrator selects Election->Create Ballot to open the Ballot Builder form. A new ballot will be created and the random ballot id displayed in the form. The ballot creator must type in the ballot issue/question, and then enter all of the available choices, one at a time. Each choice is entered by typing the appropriate text, and clicking the “Add” button. A choice can be deleted by selecting the choice in the list, and clicking Ballot->Delete Candidate. When the ballot is complete, the ballot should be saved by clicking File->Save and choosing a known location and filename to save the ballot. The Ballot Builder Form must be closed and then re-opened in order to create another ballot.

Adding Ballots to an Election

Once all desired ballot(s) have been created and saved, it/they can be added to any election by selecting Election->Add Ballot from the Election Builder form. The user will then be prompted to select the ballot file. If the ballot is valid, it will be imported into the election and displayed in the Election Builder form.

Vote Format

When a ballot is added to an election, the format of the vote for that ballot is derived from the key size chosen for the election and the number of “candidate” choices on the ballot. These two values determine the maximum number of voters allowed. The total size of the vote is limited to the key size k (in bits). The vote is split into c bit fields where c is the number of candidates. The size of the bit fields vc= k/c. However, vc is limited to 32 bits so that each candidate’s field will fit into a 32-bit integer (for ease of extraction only). Therefore, if k/c > 32, vc=32 andonly the first 32*c bits of the vote will be used. To cast a vote, a voter votes the value 2^(ic*vc) where ic is the desired candidates ballot index (0,…,c-1). By using votes of this format, the tally can be computed by multiplying all of the votes together and decrypting the product. Due to the homomorphic property of the Paillier cryptosystem, the multiplication carried out in the ciphertext space corresponds to addition in the cleartext space, and thus the decryption of the product will contain the summed votes for each candidate. Each candidate’s bit field can then be extracted and evaluated to determine the total number of votes for that candidate.

Cheating the Vote

The vote format discussed above would be very easy target for a malicious voter. For example, instead of voting the value 2^(ic*vc) for the desired candidate, a malicious voter could simply vote 2^(ic*vc + 5) to vote 2^5 times for the desired candidate. When such an encrypted vote is multiplied with others, it would simply be summed to the target candidate’s decrypted vote total. In order to prevent such a scam, the vote must be checked for validity. This can be done if the voter includes a proof of validity with his/her vote that proves that the vote is one of the c valid vote values. In [3], the authors present an interactive proof that proves a given ciphertext encrypts one of a set of plaintexts. This proof could be made non-interactive using the Fiat-Shamir heuristic, and is left as an exercise for the reader.

Saving and Posting an Election

Once the election has been created, the encryption parameters obtained, and the necessary ballots created and added to the election, the election must be saved as an XML file and it must be posted to the voting web service. First save the election by selecting File->Save in the Election Builder form. Select the desired location and filename and click OK. Posting the election to the voting web service is a non-reversible operation in the demo application. Be sure that the election is complete and saved before posting. To post the election, select Election->Post Election To Voting Service. A web service call will be made that posts the election data to the web service, which then creates the appropriate database entries that are used to manage the election.

Voting

Creating the Vote

Once an election has been created, saved, and posted to the election web service, voters can create and cast votes. To do so, open the VoterForm by clicking the VOTE button on the main menu. Type the voter’s name in the VoterForm, and then open the desired election by selecting Election->Open from the form’s menu. The ballots from the election will be loaded, with each issue being loaded into the issue text box, and it’s corresponding choices loaded into the textbox to the right (the choices textbox). The voter can make his/her choice simply by clicking on the desired choice. To vote on a different ballot issue, simply select the desired issue. That issue’s choices will then be displayed in the choices textbox to the right. Again, select the desired choice by clicking on it in the choices textbox. Once a choice has been selected, the ballot issue and the selected choice will appear in the “Current Votes” textbox. To the right of the issue question and the selected choice is the hex value of the vote to be cast.

Submitting the Vote

Once all choices have been made, the voter can submit his/her vote by selecting Vote->Submit Vote. Doing so posts the vote information to the voting web service, which saves the vote information to the voting database. Once the vote is submitted, no changes can be made. However, if the vote was incomplete (i.e. choices for all ballots in the election were not made), the voter can clear the vote by selecting Vote->Clear, make choices for the unsubmitted ballots, and then submit only those votes. When submitting the vote, a dialog box will appear indicating how many votes were successfully submitted to the voting web service.

Checking the Vote

At any time after submitting his/her vote, a voter can check the posted values of his/her vote by selecting Vote->Check Submitted Vote. This invokes a web service call to the voting web service which retrieves the encrypted vote values posted for that election.

Tally The Vote

At any time during the election process, the demo voting application allows you to tally the vote. To do so, click the “Tally/Decrypt Vote” button on the main menu. The Tally form will open. Select Election->Open, and then browse to and open the election file for which you wish to tally the vote. If the secret key shares were encrypted, you will be prompted to select the owner’s secret RSA key in order to decrypt the owner’s Paillier secret key share. The demo application currently prompts for the owner’s secret RSA key each time it is required (for each ballot). Once all of the owner’s secret RSA keys have been provided for each ballot in the election, the votes are retrieved from the voting web service. The product of the votes for each ballot is then calculated and displayed both encrypted and decrypted, and the candidate’s tallies are extracted from the decrypted bit field and displayed. Select a different ballot issue to view the results for that ballot.

REFERENCES

-----------------------

[[i]] P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt ‘99

[[ii]] P. Fouque, G. Poupard, J.Stern, Sharing Decryption in the Context of Voting or Lotteries, Financial Cryptography 2000 Proceedings

[[iii]] I. Damgard, M. Jurik, J. Nielson, A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting, Aarhus University, Dept. of Computer Science

[[iv]] A. Shamir, How to Share a Secret, Communications of the ACM 1979

[[v]] A.J. Menezes, P. C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997

[[vi]] D. Naccache, Double-Speed Safe Prime Generation, Gemplus Card International

[[vii]] M. Wiener, Safe Prime Generation with a Combined Sieve, Cryptographic Clarity

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download