Correction, Optimisation and Secure and Efficient Application of PBD Shuffling

摘要

Shuffling is a useful cryptographic tool to build e-voting schemes. Two shuffling protocols called basic PBD shuffling and double PBD shuffling in this paper are proposed by Peng, Boyd and Dawson at Crypto 2005. Although PBD shuffling and its application to e-voting is one of the most efficient shuffling-based solutions to e-voting, it has three drawbacks: redundant proof mechanism, incorrect implementation and double shuffling, which compromise its correctness and deteriorate its efficiency. Especially, like most other shuffling schemes, it is not efficient enough for large-scale elections. Moreover, like many other shuffling based e-voting schemes, e-voting directly based on (either basic or double) PBD shuffling is vulnerable to some attacks against vote privacy. The existing countermeasures to these attacks are inefficient. In this paper a novel shuffling-based e-voting scheme is proposed to achieve strong security and high efficiency when the majority of the talliers are honest. Firstly, PBD shuffling is corrected and optimised to overcome the first two drawbacks such that the proof mechanism is simpler, more efficient and is correctly implemented. The method to build the e-voting application on shuffling is novel as well and overcomes the third drawback. It only needs the newly proposed simplified PBD shuffling in this paper and does not need double shuffling. However, it still maintains security and prevents those attacks against privacy in large-scale elections. As various attacks are taken into account and prevented, the new e-voting scheme achieves high level of security. As in the new scheme the shuffling proof mechanism is simplified, double shuffling is not employed and the countermeasure to the attacks is much more efficient than the existing countermeasures, it is very efficient.