Informatica

Exploring the security requirements of a democratic society, Salazar et al. proposed in (Salazar et al., 2010) a voting system based on short-linkable ring signatures (Tsang and Wei, 2004). These signatures allow for a linking tag that permits to relate votes from the same elector without revealing their identity. The aim of the authors was to reduce the number of the third-parties involved in the voting process. Only a certification authority, responsible of issuing the keys and validating the certificates, and a recount authority are needed. Ring signatures grant signer ambiguity, and linking tags act as receipt and allow the removal of duplicates. Thus, only the public key of the recount authority is used for encryption, which gives too much sway to a single authority. The protocol was later implemented in Tornos et al. (2014), which provided a modular implementation in a multi-platform environment: a desktop client, an android native app and a Firefox extension were developed to boost usability and engagement in the voting process.

In Chen et al. (2008), Chen et al. propose an electronic voting system based on a modified version of linkable ring signatures. In this modification, only designated verifiers can check the validity of the ring signature. Ring signatures are encrypted with the verifier’s public key. Therefore, a designated verifier cannot convince a third party of the integrity of a signature without revealing its private key. This prevents designated verifiers from broadcasting information about a private signature. The system uses a $(k,l)$-threshold sharing scheme to generate and distribute the secrecy of the private key (Gennaro et al., 2007) between l tallying authorities. The public key is made public before the election starts. For an elector to cast a vote, she has to select the direction of her vote and encrypts it using the public key of the election. Then, the ballot is sent through an anonymous channel to an administrator. The administrator signs the ballot, adds a timestamp and returns the ballot to the elector. If the signature returned by the administrator is valid, the elector crafts the linked ring signature, encrypts it with the public key of a tallying authority of her choice and publishes it on the bulletin board. After the election, at least k tallying authorities cooperate to recover the private key. When the private key of the election is recovered, each tallying authority is responsible for checking the validity of the received ring signatures and publishing the votes.

In Noizat (2015), Noizat proposes a voting system based on blockchain and Merkle trees (Merkle, 1980) for elector’s verification. Each elector uses three public keys: a key from the candidate she decided to vote for (KeyC); a key from the election organizers (KeyA), and a key from the voting application (KeyB). The system provides privacy through 2-of-3 multi-signature addresses (Ruffing and Moreno-Sanchez, 2017). To prepare the ballot, the elector prepares a 2-of-3 multi-signature address and a transaction. There is no way to guess the elector nor the candidate from a multi-signature address without knowing all three public keys and knowing to whom they belong. To verify that the ballot is counted as intended, the elector can use block explorers to check whether his vote has been confirmed.

In his proposal Lee et al. (2016) describes a blockchain voting system. For an elector to vote for a candidate, they have to make a transaction to a candidate’s address. To do so, the elector first needs to register as a valid elector. To avoid election organizers from knowing who voted for which candidate, the registration process is decoupled in two organizations (the registration organization itself and a trusted third party (TTP)). To cast a vote, the elector sends a hash of her secret to the registration organization and the TTP. The TTP asks the organization if that hash is linked to a valid elector. If the answer is positive, the TTP asks the elector for the secret and checks if it matches the one received. If they match, the elector is registered as a valid elector. Then, the elector can make the transaction to vote for the candidate of their choice. At the end, transactions are inspected and checked against a permutation of the TTP verified elector’s list. Multiple voting, and unverified electors are removed from the tally.

Ayed describes in Ayed (2017) a simple blockchain based voting protocol. In his system, each candidate has its own blockchain and every block, but the first, represents a vote for the candidate. The first block of each chain contains information about the candidate. To vote, an elector must identify himself or herself as a valid elector using their address and some private information. Then, they can decide the direction of their vote. When the vote is decided, some private elector’s information is hashed alongside the hash of the previous block to constitute the hash of the new block. Finally, the new block is added to the corresponding blockchain. Ayed’s proposal addresses a few of the issues of centralized voting systems, but it fails to properly define some of the crucial parts of the protocol: registration is not supported and identification is assumed to be solved. Also, the encryption and identification is managed by a centralized interface.

Tarasov and Tewari introduce in Tarasov and Tewari (2017) a Zcash based voting protocol. Zcash (Bowe et al., 2018) emerged as a Bitcoin fork with privacy as concern. Zcash supports two different kind of addresses: t-addresses, which work like regular pseudonymous Bitcoin addresses and allow transparent transactions, and z-addresses, which preserve the anonymity and privacy of the transactions. Private-anonymous transactions are based on special zero-knowledge proofs, zk-SNARKS (Bowe et al., 2018). These proofs permit the interchange of the secret values required to establish a private transaction between the sender and the receiver. After registration, the elector can make a transaction to the z-address of the desired candidate. The elector is required to provide also a valid t-address. Thus, the direction of the vote is private, but the transaction is still public. When the voting phase ends, candidates send all the vote tokens to a central pool where the final tally is computed. This requires some trust on the system and the candidates, because the candidates are expected to send the tokens and collaborate, and a malicious candidate could interfere in the voting process.

Yang et al. propose in (Yang et al., 2020) a blockchain voting protocol for range voting, in which each candidate receives a score and the candidate with the highest score wins the election. To preserve elector’s privacy they propose a novel encryption scheme based on ElGamal (1985) and group-based encryption. Each vote is encrypted by using the public key of the elector and the public keys of the candidates. This way, even at the end of the election, when the candidates release their secret keys, the individual votes remain secret. To compute the final tally, they take advantage of the homomorphic properties of El Gamal to compute the final score without decrypting individual votes. Then, the final score is decrypted by the candidates. Each transaction contains a vote, and each vote is formed by a set of scores, one for each candidate. The only drawback of this approach is that each individual score needs to be double encrypted, and accompanied by a zero-knowledge proof, and a partial-knowledge proof to ensure it is a valid score from a valid voter. This affects both the time and spatial complexity of the system. However, the authors are able to provide a performance analysis that proves the validity of their election scheme.

Gao et al. present in (Gao et al., 2019) an anti-quantum e-voting protocol based on blockchain technology. To achieve quantum computing resistance, they base their method on code-based cryptography (Niederreiter, 1985) (a NP complete problem) instead of using traditional public key cryptography based on the difficulty of number theory. Their protocol is equipped with an audit function, based on public key certificates (Al-Riyami and Paterson, 2003; Hua-jie et al., 2014), that allows to detect fraudulent voters. To handle the certificates, the authors introduce the figure of the regulator, who, although does not participate in the election, has the authority to revoke voter’s privacy. The authors report a complete and exhaustive computational time analysis of their protocol.

Follow My Vote (2018) and Bitcongress (Rockwell, 2017) are online projects of blockchain based e-voting. While they are not backed by research papers, they are pioneers of providing remote blockchain based voting to the public, being open source and supplying a real working service as an alternative to traditional voting. FollowMyVote is based on elliptic curves and blind signatures (Chaum, 1982), and requires a central authority to deal with elector registration and ballot lending. BitCongress is another decentralized e-voting proposal, it is based on digital signatures and smart contracts. It is also compatible with distributed legislation which is enforced through the blockchain. It requires a timestamp server for the system to work. The developers provide a front-end wallet called AXIOMITY that handles the working modes of BitCongress.

In Wu (2017), Wu develops a voting system based on ring signatures (Rivest et al., 2001) and Bitcoin’s blockchain. There are two authorities on the protocol: a Registration Authority (RA) and an Election Authority (EA). It is assumed these authorities are trustworthy and will not share information. Before the election starts, the EA is responsible for generating and managing a public pool of Bitcoin addresses. Since Bitcoin is not private, but anonymous, a two-phase registration is carried out by the RA. This process decouples the elector identity from the Bitcoin address and preserves elector’s privacy. As a result of the registration process, the elector gets her public key certified as a valid key. For an elector to create a ballot, they must perform a ring signature, using their private key and a list of public keys, on their desired vote. This results in a signer ambiguous signature that makes impossible to link the vote to their public key. Once the ballot is created, he or she selects a Bitcoin address from the pre-computed pool of addresses. The EA will provide the elector with the associated private key to that address. Then, the elector can send the ballot as a transaction from their own address to the EA’s address, with the ballot encoded in the transaction itself. The EA is responsible for retrieving all the ballots and verifying the integrity of ring signatures to compute the final tally. When the election is over, the list of public keys of electors is released to the public and everyone can verify the correctness of the tally. Since the ring signature used in this method allows double voting, EA checks the transactions coming from the same address. For each address, only the latest transaction will be considered valid. As a drawback of this method, it is to note the great sway of the authorities in the voting process. As a result, one of the requirements of the protocol is that authorities comply with the desired conduct. Wu also developed a complete implementation of the system on Bitcoin’s testnet, with a great definition of classes and cases of use.

Lai and Wu propose in Lai and Wu (2018) an elegant voting system based on Ethereum smart contracts and one-time ring signatures (Van Saberhagen, 2013). A transaction is considered a vote, electors make a transaction to their selected candidate. The privacy of the elector is protected by ring signatures, which also prevent double voting. To keep the election fair and to avoid the leak of information until the tally phase, the electors should consider the stealth addresses of the candidates to cast the vote. This way, until the stealth addresses are revealed, votes are kept secret. To expose the stealth addresses, key managers are needed. Key managers share the first private key of a candidate through a Diffie-Hellman interchange. Key managers store some $\textit{ETH}$ in a deposit previous to the election, to recover it they must open their secret on the tally phase. Once the stealth addresses are exposed, the whole election process is public and auditable on the Ethereum blockchain. All the requirements of the protocol are contained in a smart contract.

In this work, we use both $\mathit{RSA}$ cryptosystem and Elliptic Curve Cryptography ($\textit{ECC}$). The former is used by the electors to encrypt their vote and by the parties to sign the transactions. The latter is used for generating ring signatures in the context of a blockchain in order to allow correct and anonymous identification of electors. We assume some familiarity of the reader with these notions. We recommend (Menezes et al., 1996) to the not accustomed reader. Now, we summarize the notation that will be used in the rest of the paper.

Monero is a cryptocurrency based on the cryptographic protocol described in Van Saberhagen (2013). Its main focus is to achieve private and untraceable transactions over a public ledger. Here, we present a brief description of how Monero achieves those goals and an example of how an untraceable transaction works. For further details, we recommend the review done by Koe et al. (2020) to the interested reader.

In order to anonymize the sender, ring signatures are used to sign transactions with a group of keys, thus giving ambiguity to the sender. To anonymize the receiver, they use stealth addresses. One Time Public Keys ($\textit{OTPK}$s) are derived from the receiver’s stealth address, and allow the sender to use a new public key for each transaction (using a Diffie-Hellman-like (Diffie and Hellman, 1976) exchange). Sending transactions using these keys preserves the anonymity of the receiver. The receiver, and only the receiver, is able to recover the private key of the stealth address and use its funds.

In our proposal, we take advantage of Monero’s $\textit{OTPK}$s in order to allow elector identification. Thus, we here present a brief summary of how $\textit{OTPK}$s are derived. Each user on the blockchain has two public keys $(A,B)$. For any sender to make a transaction, he needs to compute the $\textit{OTPK}$ that will be used in the transaction using the two public keys of the receiver. He also selects a random number r.

The derived $\textit{OTPK}$ is used as the public address of the transaction. Note that R, being $rG$, is also added in the transaction information. Once the transaction is done, the receiver will be able to recover the private key x associated to the $\textit{OTPK}$ using his own private keys $(a,b)$: such that: indeed:

Ring signatures are a special kind of cryptographic signature. They receive this name because they are created using a ring structure, where the public keys of several peers (electors in this framework) are used in order to provide a signer-ambiguous signature. No information about the signer is revealed, only his membership to certain group. Any person involved in a ring signature could be the signer.

Multiple versions of ring signatures exist. Originally, they were proposed by Chaum and van Heyst (1991) as group signatures. They were limited because a group coordinator was required to set up the signing scheme. To overcome this issue, Rivest introduced in Rivest et al. (2001) the first ring signatures. They provided unconditional signer ambiguity without group coordinator. Any user can define a set of possible signers, including themselves, and sign the message using their public and secret key and others’ public keys. Neither a coordinator, nor the permission (or even the knowledge) of the owners of the third party public keys is required.

Ring signatures are a great and solid solution to achieve the anonymity needed in the voting protocols. Nevertheless, since it is impossible to know who is the actual signer, nothing would prevent the use of another ring to vote. In order to prevent that, we will use the Ring Signature Confidential Transaction algorithm described in Noether (2015), Van Saberhagen (2013). This algorithm is the result of combining the modifications for reducing space consumption described by Back (2015) and the introduction of Key Images.

Key images are a public commitment of the signer’s private and public key, they do not reveal information about the signer’s private key. As a result, we can anonymously link the private key of the signer, independently of the public keys on the ring, to the signature. This allows to prevent the use of the same key to sign two different rings, which would imply double spending the same resource.

Algorithm 1 details the steps an elector should perform to apply a ring signature to their vote. Since the ring signature generation has some random coefficients involved and depends on the signer’s private key, votes in the same direction signed with the same ring of public keys are still different. Algorithm 2 specifies the process the authorities must follow in order to verify the correctness of a given signature.

Before the election, parties must collaborate to generate the parameters of the election. To encrypt the votes electors send to the parties, we employ $\mathit{RSA}$, therefore, parties must generate the $\mathit{RSA}$ parameters: the public modulo n, the public verification key v and the private signature key s. Since giving the private key s to a single party would result in giving up too much power, l parties apply the threshold $\mathit{RSA}$ key generation protocol proposed by Damgård and Koprowski (2001). This protocol relies on the work of Frankel et al. (1998) to remove the necessity of a trusted dealer. It introduces a $(k,l)$-threshold $\mathit{RSA}$ sharing scheme in which the parameters are computed in a distributed way and the secret key is generated in l fragments. To recover the secret key, any subset of at least k parties can collaborate to find the original secret s. Even if some parties are corrupt, they would need to collaborate with at least k parties. The same applies to honest parties, only k are needed to recover the private key s. Now, we proceed to give an overview of the aforementioned key generation protocol.

In $\mathit{RSA}$, modulo n is computed as the product of two large primes p and q. To distribute the trust, p and q are computed as the sum of different shares chosen by the parties: $n=({p_{1}}+{p_{2}}+\cdots +{p_{i}}+\cdots +{p_{l}})({q_{1}}+{q_{2}}+\cdots +{q_{i}}+\cdots +{q_{l}})$. To avoid parties maliciously changing its share, they are required to publish a commitment (Pedersen, 1991) during the process. The distributed computation of n is carried out using a variant of Shamir’s secret sharing (Shamir, 1979). This variant (Frankel et al., 1997) also employs random polynomials in which the independent term is the secret, but it allows the computation of n to work outside prime fields.

Once the modulus is agreed, parties can jointly derive the public exponent v in a similar way, a distributed test division is required to test the primality of the candidates. When computing s, to prevent from revealing the shares of the polynomial, the shares ${v_{i}}$ are used as an exponent to compute: ${g^{{v_{i}}}}$, g being a generator of the group defined by v. This way each party gets an additive share of the private key ${s_{i}}$. Then, they proceed to construct a $(k,l)$-threshold polynomial of s. Thus, a distributed generation of $\mathit{RSA}$, in which parties only have partial information of the private key s is achieved. To decrypt or sign a message, parties must collaborate to retrieve the shared private key. The collaboration process can be seen as a graph (see Fig. 1), in which each node represents a party, and each edge represents the interchange of messages. The retrieving protocol is detailed in the following sections.

We require all the traffic of messages as well as the commitments related to any vote to be published as transactions on the blockchain. Hence, the blockchain comprehends all the information related to the election. $\mathit{RSA}$ parameters n and v are also released to the blockchain. Apart from the distributed key, each party has its own personal pair of public/private keys. They are used to sign all the transactions they make. All this information is published on the blockchain as the first block.

Electors must register before the election starts. For this purpose, a local administration (e.g. city hall) defines the census of potential electors. It will also store and manage elector’s keys as well as generate $\textit{OTPK}$s for each elector. The administration will declare the process through which the electors will identify and register their public keys, and the termination of the registration term.

Any elector willing to participate will generate a two pairs of elliptic curve keys ($a,A$), ($b,B$). Then, the elector will follow the process specified by the administration, and, in case of correctly identifying, the administration will link their public keys ($A,B$) to their identity.

Once the elector registration term ends, the administration computes an $\textit{OTPK}$ per elector using their public keys and a different random number r per $\textit{OTPK}$. After this, the administration sends the information to the parties. Parties send a transaction through the blockchain, making public a list with the $\textit{OTPK}$s of each public key pair and the associated R such that $R=rG$. The owners of a given $\textit{OTPK}$ either will be able to recover the corresponding private key computing ${H_{s}}(aR)+b$, or can be notified by the administration in order to save computation time. Administrations can cooperate to compute and group $\textit{OTPK}$s per districts in structure transactions and to simplify the search for the final elector.

The same transaction also includes basic configuration information for the voting such as which are the options in the voting, the codification of the vote. This second transaction contains all the remaining public parameters of the election. Figure 2 illustrates the process electors carry out in order to register themselves.

Once the electors have decided what to vote for, they must follow three steps to cast a valid vote.

First, they must encrypt it to protect its direction until the election is over. To do so, they read the public key v and the modulo n forms the blockchain and apply a modular exponentiation to encrypt it using $\mathit{RSA}$. Before encrypting the vote, the elector must select a fixed length random mask of their choice to concatenate to the vote. Otherwise, all the votes in the same direction will result in the same encryption. The elector will obtain an encrypted value such as $\textit{evote}={(\textit{vote}\| \textit{mask})^{v}}\hspace{2.5pt}\textit{mod}\hspace{2.5pt}n$.

Next, the elector must sign the vote to prove that it has been casted by an eligible elector. To perform the ring signature generation procedure described in Algorithm 1, the electors randomly take N $\textit{OTPK}$s (including their own) from the list of public keys. The elector obtains a ballot confirmed by the encrypted vote and its signature: $\textit{ballot}=\{\textit{evote},\sigma (\textit{evote})=(P,K,{c_{0}},r)\}$. Note that the number of public keys in the ring N is tightly connected with the ambiguity of the signer. N acts as a security parameter, larger values imply more ambiguity, thus more privacy. However, it makes the signature slower and more expensive in terms of computation. It might be beneficial to establish a fixed or a minimum value for this number.

Finally, when the vote has been encrypted and signed, the elector sends the ballot through a blockchain transaction to a party of her choice or a random one. Figure 3 illustrates the casting process.

Parties act like miners, listening to the blockchain network and expecting transactions addressed to them. When a party finds a transaction addressed to himself in the pool of unprocessed transactions, it proceeds to verify the integrity of the ring signature. Figure 4 shows the processing of a vote. When it has received enough transactions, the party creates a block that is added to the blockchain and later broadcasted to the rest of parties:

For a more detailed and technical explanation about how the blocks are created and processed within the blockchain, we refer the reader to Appendix A.

Once the voting phases finish, parties stop accepting transactions from electors. Now they must proceed to compute the final tally.

First, parties must recover the secret key s to decrypt votes. To do so, a subset Λ of at least k honest parties collaborate to compute the original polynomial containing s. To recover a polynomial from k shares, defined as ${s_{0}}=({x_{0}},{y_{0}}),{s_{1}}=({x_{1}},{y_{1}}),\dots ,{s_{k}}=({x_{k}},{y_{k}})$ we employ Lagrange polynomials:

Once we recover the polynomial $\mathcal{L}(x)$, s can be obtained as: being Δ a factor used when generating the RSA key.1 When s is recovered, parties can decrypt the received votes and compute the final tally. Parties must analyse the received votes directly from electors and those received from another parties. This way, each party can compute a global and independent tally. If multiple votes contain the same key image, only the last vote will be considered valid.

When the tally is completed, each party has to publish a new block containing each received transaction, the result of checking the ring signature and the direction of the vote. At the end of the block they must add the results of the election and the private key of the election s. This message has to be signed by the parties. The private key is also published to allow electors to compute their own tally. If all the parties agree with the tally the election is finished. Figure 5 represents the tallying stage.

Unlike modular exponentiation, ring signatures are not an operator. Ring signatures are a quite complex cryptographic construct that includes multiple basic operators, so the comparison is not straightforward and computational time complexity is dominated by ring signatures. Ring signatures time complexity also depends on some parameters apart from the input size such as the size of the ring, or the desired level of security. For these reasons, in Section 5, we chose to leave the computational complexity associated to craft/verify a signature as a variable to provide a clear view of the time complexity. However, now we also provide an implementation of these signatures to present an empirical result of what the real TPS of the system would be.

The code developed for this performance analysis was implemented using Python 3 and it is publicly available on GitHub.2 We provide a framework to test how the different parameters and different elliptic curves affect the performance of ring signatures. Our goal with this framework is to provide a tangible implementation and to obtain real performance time measurements. A low-level implementation in a different language such as C++ would probably benefit the final throughput.

Figures 6a and 6b represent the elapsed time to craft or verify a signature under different parameters respectively. We chose 4 different elliptic curves for the comparative. Each one provides a different level of security: brainpoolP160r1 provides 80 bits of security; Curve-192 provides 91 bits; Curve-224 provides 112 bits and, Curve-256 provides 128 bits. Brainpool curve provides a security level comparable to use RSA with a 1024 bits modulo (Gallagher, 2013), which is more than enough to protect the voter’s privacy.3 As expected, the required time grows linearly when we increase the size of the ring or the complexity of the curve. We believe that using brainpool and a ring size of 64 public keys is more than enough to achieve the security needed for our scheme. Specially due to the short term of security required by our proposal: the votes only need to be secret until the final tally is computed.

The figures here presented were obtained using a personal computer (AMD Ryzen 7 3700X). Since there are no dependencies between transactions, the verification is a parallelizable task. We use multiple cores to take advantage of this aspect. Using a professional server’s processor and decentralizing the task among multiple servers would yield a great performance improvement. Nonetheless, a single personal computer is capable of verifying 3–4 TPS and 200 in a minute, using immoderate high standard security parameters.

Also note that the times for crafting/verification are very similar. This is because the verification algorithm (see Section 3.3) requires to re-create the signature to check its validity.

We devote this section to compare the performance of our proposal with those studied in Section 2. Ring signatures and modular exponentiations determine the time complexity of our approach. Modular exponentiations are a common operator present in most of the related works (except if they are completely based on ECC). For this reason, we consider modular exponentiation, and its associated complexity in bit operations, as the atomic unit in the analysis of the time complexity.

Comparing different e-voting proposals is not trivial: some systems do no disclose all the details, not all the systems are directly comparable and not all the works provide a time complexity analysis. Thus, some of the reviewed works, are left out of the comparison: because they do not provide a performance analysis nor enough information to obtain an asymptotic complexity (Noizat, 2015; Lee et al., 2016; Ayed, 2017; Tarasov and Tewari, 2017; Lai and Wu, 2018); because, despite providing a thorough analysis, they are based on different problems and the analogy would not hold (Gao et al., 2019); or, because they are implementation approaches and the authors only report user timings (Wu, 2017).

Let us note, that despite not providing a time analysis, Wei supplies a complexity analysis of the ring signatures employed under different ring sizes and the associated gas (unit for measuring cost of Ethereum transactions) cost of running their voting protocol on the Ethereum blockchain. Also, Wu provides empirical times and sizes of the ring signatures used with varying ring sizes. Unfortunately, neither of them detail the level of security engaged in those tasks.

We compare the asymptotic time complexity of the remaining works to prove the validity of our approach. When the methods do not specify a part of their protocol or do not provide enough information, we introduce a variable in the complexity analysis. Table 1 summarizes the associated complexity for the elector and for the protocol to process the received votes. For more details, we refer the reader to the original works. Protocols employing different kinds of ring signatures are compared, to provide a fair example we assume the time to craft ${r_{c}}$ or to verify ${r_{v}}$ signature are comparable and can be agglutinated under the same variable despite their different implementations.

Note that the number of votes v and the number of transactions t are semantically equivalent, they both represent the number of processed votes. On the other hand, the number of candidates c and the number of parties p, not always represent the same partners. Not all protocols directly involve the candidates and some systems include extra authorities to handle credentials or distribute responsibility.

In Table 1, the results obtained by our proposal compete with the reviewed systems. Indeed, Chen’s system and our proposal require the minimum effort for the final elector. Regarding system’s complexity; it can be observed that, as for many works, it scales linearly with the number of involved parties and total number of votes. Salazar and Yang’s works are also affected by other factors given that they support round and ranking e-voting respectively. Our proposed e-voting protocol is scalable due to its linear complexity and introduces the blockchain as a distributed public ledger without losing performance with respect to analogous works.