Slide rules and electronic voting
Older readers will have been taught at school how to use a slide rule to perform multiplication. Invented in the 17th century, the slide rule is based on the logarithm function. The key property of the logarithms is that it reduces multiplication to addition:
Hence, if we want to compute the product of two numbers a and b without executing a single multiplication, we can proceed as follows. First we determine the logarithms of the two numbers and add them together. Then, by applying the inverse of the logarithm function to the result, we obtain the product of a and b. This way of computing products was in wide use until in the 1970's, when pocket calculators became available.
The logarithm function is one example of a class of functions called 'homomorphic' functions. Recently, homomorphic functions have found a new area of application: electronic voting.
One of the requirements that voting systems need to satisfy, is guaranteeing voter anonymity. In paper based voting systems, anonymity is guaranteed by the ballot box. To prevent a nefarious voting official from being able to match up the paper voting slips with the names on the list of the people who voted, the votes of many voters are collected in one box and the box is shaken before it is opened. The random shuffling ensures that individual paper ballots can't be traced back to the voters.
Two factors make it hard to develop an electronic equivalent of the paper voting system. First, with digital computers, genuine randomness is difficult to achieve. Second, the way digital communication is currently implemented, it is hard to guarantee anonymity. This is where homomorphic encryption comes to our aid.
Much like the logarithm function, a homomorphic encryption algorithm E has the property that
E(vote1) x E(vote2) = E(vote1 + vote2)
An election can then be organized in the following way.
First, the election authorities distribute the encryption mechanism to the voters. Then, each voter decides on his or her vote, encrypts it and sends it to the vote counting authority.
The vote counting authority receives the encrypted votes and produces the encrypted tally. Because of the homomorphism, the vote counting authority doesn't need to be able to encrypt or decrypt, so it is not equipped with decrypting capabilities. The voters are not anonymous towards the vote counting authority, but this doesn't matter because the authority only sees their votes encrypted.
Finally, the vote counting authority submits the encrypted tally to a decryption server. Since this server only receives the encrypted tally, and not the individual votes, it can't link the votes back to the voters.
Add in some additional error detection and recovery capabilities and you obtain a practical e-voting system.
Electronic voting systems based on homomorphic encryption have been field tested on several occasions in the European Union, although at this stage a large scale deployment is not planned.
ABOUT THE AUTHOR: Vincent Rijmen is a professor at the Technical University of Graz in Austria, where he leads the IAIK Krypto Group. After obtaining a degree in electronics engineering at the University of Leuven, Belgium (K.U.Leuven) in 1993, he became a Ph.D. student there, working in the computer security research group COSIC (COmputer Security and Industrial Cryptography). After completing his doctorate on the design and analysis of block ciphers in 1997, he continued to work with the COSIC research group, collaborating on several occasions with Dr. Joan Daemen. One of their joint projects resulted in the algorithm Rijndael, which in October 2000 was selected by the National Institute for Standards and Technology (NIST) to become the Advanced Encryption Standard (AES). From 2001, he has been working with Cryptomathic as chief cryptographer.