SUVS: Secure Unencrypted Voting Scheme

2.1Blind Signatures

Blind signatures were proposed by Chaum (1982), where he presents a method for signing a masked message that cannot be linked to the original content.

In Li et al. (2009), Li et al. introduce a voting system that employs blind signatures to certify the ballot from the multiple authorities involved. The elector obtains a blank ballot from the authentication centre and proceeds to use blind signatures to certify the ballot. Then, the elector removes the blinding factor and the certified ballot is encrypted and sent to a tallying authority. The encryption is used to ensure that the result of the election is kept private until the final tallying. Finally, when the election process finishes, the certification authority reveals the secret key and the tallying authority decrypts, counts and records the votes.

In Nguyen and Dang (2013) the authors present another scheme that uses blind signatures for ballot certification and dynamic ballots to ensure elector’s privacy. Electors register using their personal identification to obtain a digital certificate. Then, to get the signature from the privacy authority, the elector hides his unique id through blind signatures, and sends it together with the serial number of the certificate. To avoid man in the middle attacks, they employ triple DES to encrypt sensible communications. Once the user gets the signature that entitles him to vote, he crafts a dynamic ballot (Cetinkaya and Doganaksoy, 2006) and cast it to the ballot and casting centre. The ballot is encrypted and the elector is required to provide plain-text equivalence tests to proof that the unique identifications are valid.

Another protocol that also employs blind signatures to certify the ballots is described in Larriba et al. (2020). In their work, the authors focus on the efficiency to propose a time-efficient voting scheme that only requires two authorities. In this protocol the elector builds the ballot according some fixed structure. This ballot is blindly signed by an authority that cannot reveal the direction of the vote. The signed ballot is then sent to the authority that plays the role of the polling station. Unless both authorities collude, the method holds all the desired properties.

Plenty of other voting schemes exploit the properties of blind signatures since they provide a flexible method for signing votes and avoiding double voting without compromising elector’s privacy (e.g.: Thi and Dang, 2013; Aziz, 2019; Cruz and Kaji, 2017). Although we also use blind signatures in our scheme, unlike many of the protocols, we do not use them to hide the ballot from unauthorized access.

2.2Homomorphic Cryptography

Homomorphic cryptography allows us to operate with ciphertexts, and obtain, after decryption, the same results as we would obtain working with plain text. This allows to work with sensitive data without needing to know the actual content of the encrypted message. Indeed, blind signatures benefit from the homomorphic cryptography to achieve secure signing. However, please note that homomorphic cryptography allows for many features such as aggregation or proofs-of-inclusion. Many voting protocols employ homomorphic cryptography, usually to aggregate encrypted votes and only decrypt the final result.

In Cramer et al. (1997), the author presents a voting scheme for Yes/No elections based on homomorphic properties. The votes, which are codified as 1 or −1, are encrypted using a threshold El Gamal cryptosystem (ElGamal, 1985). Encrypted votes are then aggregated, since they can be summed as integers, and a final encrypted result is computed. At the end of the election, authorities collaborate to recover the secret key and decrypt the final result.

In Yang et al. (2017, 2018), Yang et al. introduce a homomorphic voting scheme compatible with range voting. Range voting requires electors to assign a numerical score to all candidates for single seat elections. The candidate with the higher score wins. In this system, the votes are structured, and encrypted, as elements in a matrix in which rows represent candidates and columns represent the assigned score. Since votes for the same candidates are placed in the same rows of the matrix, they can be summed altogether to get the final results per candidate. At the end of the election, authorities collaborate to recover the secret key and decrypt the final matrix that agglutinates all the votes.

2.3Ring Signatures

Ring signatures are a special kind of digital signature that allow any user to sign as a member of a collective instead of an individual. The verifier can check that the user who wants to sign belongs to a given group, but cannot identify the signer among the group members.

Tornos et al. (2014) propose a voting scheme that provides signer ambiguity by using ring signatures. A single registration authority is employed to handle proper identification of electors. After the identification process, electors use ring signatures to sign their valid votes privately. To prevent double-voting, they use linking tags in the ring signatures. These tags do not reveal personal information about the signer but prevent her from voting more than once using different rings of users.

In Chen et al. (2008), a voting protocol with custom ring signatures is presented. They propose a ring signature scheme that can only be verified by some designated individuals. These verifiers cannot convince a third party of the integrity of a ring signature without revealing their private key. For the encryption of the vote they employ a threshold scheme in which authorities have to collaborate to recover the secret key at the end of the election. To prevent double voting, electors are required to link the vote with a commitment of their private key. This commitment does not reveal any information about the private key, but prevents malicious electors from voting multiple times. If two, or more, votes with the same commitment are detected, only the one with the latest timestamp will be considered.

2.4Blockchain

Blockchain technology provides a decentralized technology to store and share information. Multiple electronic voting schemes have used blockchain to carry out the election process since they provide a distributed public ledger than can be consulted by anyone. While blockchain is not a cryptographic scheme by itself, and all of these systems use other cryptographic primitives to achieve privacy, it is still a differentiating factor that suffices to make a distinction when studying these protocols.

In Yang et al. (2020), the authors propose a voting protocol for range voting that uses blockchain to structure the election process. In this scheme, each candidate receives a score (e.g.: token on the chain) from the electors and the candidate with the highest score wins the election. To preserve elector’s privacy, they employ an encryption system based on El Gamal and group-based encryption. They employ the homomorphic properties of El Gamal to compute the final tally without compromising individual electors.

In Gao et al. (2019), the authors present an e-voting protocol based on blockchain technology, which also provides anti-quantum resistance properties. To achieve this, they base their method on an NP-complete problem (Niederreiter, 1985) instead of using traditional public key cryptography. Their protocol is equipped with an audit function that allows to detect fraudulent voters while respecting their privacy.

In Larriba et al. (2021), the authors propose a blockchain based scheme that introduces traditional parties inside the election process to raise confidence on the system. To protect elector’s privacy, they employ ring signatures, and to prevent double voting, they employ key images. Key images act as receipts of ring signatures that prevent the malicious elector from creating multiple signatures, without compromising her identity.

In the voting scheme presented here, we do not employ blockchain. However, the public bulletin that is used to communicate the election results, could be implemented using blockchain technology.

2.5System Comparison

Besides the literature review here introduced, we also present a comparison between the reviewed systems. The purpose of this comparison is twofold. First, it allows the reader to directly assess the presented systems. Secondly, it provides a common baseline to later compare the performance of our system, SUVS.

Nonetheless, comparing different systems is not a trivial task. These schemes are based on different cryptographic primitives, with different architectures that involve a custom number of involved parties. The authors not always report, or at least with the same level of detail, the asymptotical complexity of their works. Therefore, we chose the average number of messages sent in the protocol as basic unit for the comparison. Messaging between electors and parties is accessible to minutely measure and network delays can surpass computational times. The results of our analysis are depicted in Table 1.

3.1Shamir Secret Sharing Scheme

The reconstructive approach is based on Shamir’s (j,d)-secret sharing work (Shamir, 1979). This scheme allows to share a secret C among j players, in such a way that any subset of d+1 players can recover C. The secret is encoded as the independent term of a polynomial q(x) and the pieces of information distributed among players are points of the aforementioned polynomial. Any subset d+1 can interpolate their set of points to recover C. Polynomial evaluation operations, as depicted in equation (1), are carried out under modular arithmetic of a prime p:

Given a sufficient set of points (xi,yi), in order to interpolate the polynomial q(x), we suggest Lagrange’s method. The interpolation is depicted in equation (2), and equation (3) computes the Lagrange’s bases:

Please note that employing Shamir’s secret sharing scheme requires the use of modular arithmetic, however, it does not imply the use of encryption.

3.2Perfect Secrecy

Perfect secrecy notion directly derives from information-theory (Shannon, 1949). It implies, as represented in equation (4), that a priori probability of a given message m, in the space of all possible messages M, is equal to the a posteriori probability of the message given the ciphertext c, in the space of all possible ciphertexts C.

4.1System Setup

Before the election process, it is required to arrange and configure the methods that will be used to sign the electors’ ballots. The IA is responsible of the elector identification and ballot certification. For this purpose, the IA must generate the parameters to setup a digital signature scheme.

We employ blind signatures to prevent double voting without compromising electors’ privacy. This allow us to certify ballots from valid electors without being able to link the votes with their identity.

We consider in the description of our proposal a RSA cryptographic scheme to implement blind signatures because of its homomorphic properties under modular exponentiation.22 To carry out the blind signatures, the elector uses the public component of the IA signature key v and public RSA modulus n which will be used to certify the ballots.

The IA also states the hash function to be used, sets up the degree d of the polynomials to create, set the maximum number of points the user can generate l, being l>d, as well as generates the prime p under which modulo operations will be carried out. Please note that the degree of the polynomial d must be, at least, equal to j−1, being j the number of involved parties on the election. This enforces the collaboration of all parties to recover the polynomial. Apart from this consideration, increasing d does not provide greater security. Please note that l is included as a security measure to prevent users generating too many points. Because of the polynomial’s degree d being public, this could give some small set of malicious parties the ability to collude and recover the votes before the tallying phase. While the integrity of the vote is preserved, it would affect the democracy of the scheme.

At the end of the setup phase, the IA publicly distributes v, n, d and p so that every elector can craft her own ballot.

4.2Ballot Crafting

Once an elector has decided on her vote, she encodes it as an integer C. Then, she proceeds to generate a d-degree polynomial as shown in equation (5):

Then, the elector samples from the polynomial a minimum of d+1 points (to a maximum of l points, see equation (6)). For the sake of clarity, we assume in the rest of the article the user generated minimum d+1 points. When necessary, we will order the set of points P taking into account the first coordinate, in order to transform, unequivocally, any set into a sequence of points.

Note that anybody who knows P can interpolate the original polynomial q(x), and therefore recover the vote.

The set is, actually, the ballot to be casted, which will be split in shares to be sent to the parties. In order to allow the reconstruction of the split vote, the elector digests the sorted set of points P using the hash function selected in the system set up phase. Please note the importance of the points being sorted for the hash function to produce consistent outputs. For this reason, we define a function shash, that sorts, accordingly, the received input before applying the hash. The output of the shash functions acts as a commitment of the points. This commitment acts as a receipt that ensures the set P has not been tampered and demonstrates the validity of the ballot when signed.

4.3Ballot Certification

In order to prevent double voting, each elector sends her ballot to the IA to be certified. In order to prevent the possibility of matching the ballot with the elector, our proposal blinds the ballots before sending them to the authority.

To do so, the elector selects a random invertible mask, considers the verification key v published by the IA and computes the ballot b as shown in equation (7):

The IA checks if the identification is valid and the elector is on the census of registered voters. If the identification is correct, the IA proceeds to sign the ballot as referenced in equation (8):

Please note that, unless the IA gets to know the mask, the IA cannot never be aware of what message it is actually certifying. After the signature process, the IA replies the elector through a secure channel with the signed ballot. The IA also publishes on the PBB a tuple of the form ⟨id,b=shash(P)·maskv)s⟩. The purpose of this publication is twofold: first, it allows the elector to check that her ballot was received as intended. Second, it proves that every ballot comes from a valid identity from the public census.

The elector receives the signed ballot and proceeds to recover the signed commitment which will certify her vote. Note that the elector is the only one who knows the mask and its inverse. Thus, the elector obtains the signed commitment as indicated in equation (9):

By following these steps, the elector obtains the certified (signed) commitment that will be used in the next phases. These steps are detailed on Algorithm 1. Note that, despite requiring her identity in order to sign the ballot, the IA has no means to link the commitment with the elector. Also note that the elector is able to check if the signed ballot was tampered during the way, because she is able to independently verify the integrity of the signed commitment.

Algorithm 1

Ballot certification

4.4Vote Casting

In this phase, the elector has a set P that can be used to recover her vote and the signed commitment of the set hash(P)s, which identifies her vote as a valid one.

To finally cast the vote, the elector sends a partition of P (shares of the ballot) together with the certified commitment to all the parties implied in the election tallying. Note that a basic property of polynomial interpolation states the impossibility to recover a d degree polynomial with d or less points of such polynomial. This allows to send different shares of information to different parties with certainty that no information of the original vote will be revealed unless all the parties collaborate to do so.

Thus, taking into account that k parties are implied in the election, the elector partitions P into k non-overlapping subsets SPi, such that P results as the ordered merge of the SPi subsets. See equation (10):

Each one of the parties receive a share SPi of P together with the hash and the certified hash: shash(P),shash(P)s(modn). Please note that the certified hash operates as digital signature of the hash, and that both are sent and needed to check its validity. Also note that the elector can freely decide which subset is sent to each party.

We also note that it is possible to reduce the number of shares to put aside from the process those parties which receive no share of the elector’s ballot. Note also that this does not affect the validity of the vote, but the transparency of the process. However, we force that every party receives one share. By doing this, we ensure that the vote requires the collaboration of all the parties to be recovered. Thus, no subset of malicious parties will be able to recover the vote before the tallying phase.

When all the subsets are sent, the vote has been cast. Note that, unlike what happens in the ballot certification phase, no personal information goes along with the shares of the vote. Thus, parties have no means to associate the received shares with an elector’s identity.33 The casting process is depicted on Algorithm 2.

Algorithm 2

Casting a vote

4.5Tallying

Once the election is over, no new votes are accepted. The parties can proceed to reconstruct the votes and compute the final tally.

In the first place, the parties consider the certification that accompanies the shares to find the set of shares (each one of them received by a different party) that allow to reconstruct each ballot P. Note that the original sequence can be easily obtained, by ordering the set P, and that is possible to check the validity of the certification.

A set of points P such that its certified commitment shash(P)s(modn) is not correct, or that its cardinality exceeds the defined maximum (|P|>l), is discarded. Parties can now, individually, use the points in P to recover the original polynomial q(x) which contains the vote as its independent term C. To recover a polynomial from a set of points:

Please note that the interpolation operations are not carried out modulo p. When we forced, on the ballot crafting, the coefficients of the polynomial ad to be smaller than p, we made sure that we would interpolate the exact same polynomial without the need of modular arithmetic. Otherwise, we could interpolate a different polynomial, congruent mod p, but with a different encoded vote C.

The parties publish on the PBB, a 3-tuple per vote containing: the certification of the ballot (i.e. the signed commitment); the ballot itself (i.e. the set of points P that conceal the ballot); and the reconstructed vote C. The final tally obtained by each party can also be published. The PBB is available to everyone to check that their votes have been counted as intended, and to verify the integrity of the final tally. Algorithm 3 contains the steps to compute the final tally.

Algorithm 3

Tallying votes

Verifiability

Verifiability is a property that ensures that an elector can verify the integrity of her vote at any given phase (casting, recording or tallying). If the audit is extended to any individual (elector or not), then is called universal verifiability.

Privacy

Privacy implies the impossibility of linking an elector’s identity with the direction of her vote, even when some authorities or parties implied in the process maliciously participate.

Democracy

Democracy guarantees that only valid and registered electors are able to cast a vote, and that they only can vote once.

In our protocol, the IA responsibility is twofold: it verifies elector’s identification to check that they are eligible, and, prevents double voting by using blind signatures.

Please note that even if the IA acted maliciously, democracy would be ensured. The received ballots and their associated identity on the public census are published on the PBB for everyone to review. The malicious IA could not forge invalid votes or link valid ones to their elector. However, in a different scenario, an attacker could try to bypass IA’s certification and forge the employed blind signature scheme.

Accuracy

Accuracy requires the final tally to match the actual outcome of the election. In order to achieve this: all valid votes must be counted; no invalid votes are considered; and no cast vote can be modified.

Robustness

Robustness ensures that no coalition of electors and/or parties would be able to disrupt the election process. We first prove that our method is robust with the only condition that one party remains honest. Then, we prove that it is unfeasible a coalition of users could tamper with new votes.

Perfect Secrecy

Perfect secrecy, as defined in Section 3, provides security by uncertainty. The concealing of the vote by partition SUVS is based on provided security derived entirely from information theory, creating a system where partial information does not reveal anything about the scheme’s secrets.

As stated in Lemma 2, there is no mechanism to relate an elector to her vote. By providing perfect secrecy, we also ensure that, even in post-quantum scenarios, it is impossible to reveal any information on any vote unless all the parties are malicious or compromised.

Malicious Elector Resistance

A malicious elector may try to craft a ballot in order to achieve double voting.