Homomorphic RSA Tallying and Its Randomization for e-Voting

Contemporary e-voting schemes use either mix networks or homomorphic tallying to preserve the anonymity of votes. Homomorphic addition property of a public key encryption algorithm provides anonymity by allowing joint decryption of the vote sums at the tallying office; instead of separate decryption of each encrypted vote. Exponential ElGamal and Paillier algorithms are additively homomorphic that makes them suitable for homomorphic tallying. Alternatively, RSA and ElGamal algorithms are not additively homomorphic but they have the property of homomorphic multiplication, so that decryption of the product of encrypted messages yields the product of messages. In this work, we show that e-voting with multiplicative homomorphic RSA tallying is possible if the algorithm is properly randomized and each candidate is associated with a unique prime number on the electronic ballot. We explain how the unique prime factorization of the vote product can be employed to compute the individual vote counts and discuss the feasibility of such a system. The absence of random parameters in the RSA algorithm is a major disadvantage, especially within the context of e-voting, where each voter uses the public key of the tallying authority and the number of possible messages to be encrypted is equal to the limited number of candidates. Although in different applications, the RSA algorithm is randomized by adding random padding bits to the plaintext; this approach doesn't work for the proposed homomorphic tallying, since a randomization that would change the unique prime factorization in the vote product is not allowable. To solve this problem, we propose new randomizations for homomorphic RSA tallying. We comment on implementation details such as cancellation of the randomization load and size of the RSA modulus with respect to the voter set.