In this chapter, we will show how to achieve unconditional or information-theoretic security in electronic voting with the following property:#R##N##R##N#Even all voters and tallying authorities have unbounded computing power, the distorted integrity of the voting results can be detected and proved incorrect by every honest voter,#R##N##R##N#If at least one tallying authority is honest, then the privacy of the ballots are protected everlastingly even the other voters and tallying authorities are malicious and have the unbounded computing power.#R##N##R##N#We assume single trusted authority who honestly delivers a particular form of secret key to every voter and tallying authority. This authority can be destroyed before the election is started. Two information-theoretic primitives are introduced based on this pre-distributed secret key, unconditionally secure oblivious polynomial evaluation (US-OPE) and unconditionally secure publicly verifiable secret sharing (US-PVSS). These primitives make the election process unconditionally secure in the above sense and efficient. The resulting scheme requires in a case of 1 million voters, the storage complexity to store private key required for each voter is 300MB. Communication complexity to verify the whole tallying process (the heaviest part) is 27GB in a case of tolerating up to 1000 colluding users, and 220GB in a case of tolerating up to 10,000 colluders.
['Akira Otsuka', 'Hideki Imai']
Unconditionally secure electronic voting