Tree-Homomorphic Encryption and Scalable Hierarchical Secret-Ballot Elections

Aggelos Kiayias and Moti Yung
Financial Cryptography and Data Security, 14th International Conference (FC 2010)
Revised Selected Papers. Springer 2010 Lecture Notes in Computer Science, pp. 257-271
January 25-28, 2010, Tenerife, Canary Islands, Spain


In this work we present a new paradigm for trust and work distribution in a hierarchy of servers to achieve scalability of work and trust properties. The paradigm is implemented with a decryption capability which is distributed and forces a workflow along a tree structure, enforcing distribution of the workload as well as fairness and partial disclosure (privacy) properties. We call the methods “tree-homomorphic” since they extend traditional homomorphic encryption and we exemplify its usage within a large scale election scheme, showing how it contributes to the properties that such a scheme needs. We note that existing design models over which e-voting schemes have been designed for do not adapt to scale with respect to a combination of privacy and trust (fairness); thus we present a model emphasizing the scaling of privacy and fairness in parallel to the growth and distribution of the election structure. We present two instantiations of e-voting schemes that are robust, publicly verifiable, and support multiple candidate ballot casting employing tree-homomorphic encryption schemes. We extend the scheme to allow the voters in a smallest administrated election unit to employ a security mechanism that protects their privacy even if all authorities are corrupt.