Open Access Peer-reviewed

Simplified Verifiable Re-encryption Mix-nets

Shinsuke Tamura1,, Shuji Taniguchi1

1Graduate School of Engineering, University of Fukui, Fukui, Japan

Information Security and Computer Fraud. 2013, 1(1), 1-7. DOI: 10.12691/iscf-1-1-1
Published online: August 25, 2017


Under the assumption that numbers of data that are encrypted and decrypted are sufficiently large and final decryption results of individual data can be publicly disclosed, a simplified mechanism for implementing re-encryption type verifiable mix-nets is proposed. Different from already proposed mechanisms, in which mix-servers prove their honest encryptions while concealing their encryption parameters, mix-servers in the proposed scheme simply disclose their aggregate encryption parameter values. As a consequence anyone can verify encryption results without interacting with mix-servers. Also, its primary verification procedures examine only aggregate behavior of mix-servers, in other words, it does not examine correct encryptions of individual data. Therefore computation volumes required for mix-servers to prove their correct behaviors are reduced substantially. In addition, the proposed scheme can cope with various attacks from malicious entities more effectively than optimistic verifiable mix-nets that also examine only aggregate behaviors of mix-nets.


anonymous communication, privacy, e-voting systems, e-poll systems
[1]  Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Trans. On Information Theory, IT-22(6), 644-654, 1976.
[2]  M. Blum, P. Feldman and S. Micali, “Non-interactive Zero-knowledge and Its Applications,” Proc. of the 20th Annual ACM Symposium on Theory of Computing, 103-112, 1988.
[3]  S. Goldwasser, S. Micali and C. Rackoff, “The Knowledge Complexity of Interactive Proof System,” SIAM Journal on Computing, 18(1), 291-304, 1989.View Article
[4]  B. Pfitzmann, “Breaking an Efficient Anonymous Channel,” Eurocrypt’95, LNCS 950, 332-340, 1995.
[5]  M. Abe, “Universally Verifiable Mix-Net with Verification Work Independent of the Number of Mix-Servers,” IEICE Trans. Fundamentals, E83-A(7), 1431-1440, 2000.
[6]  D. Boneh and P. Golle, “Almost Entirely Correct Mixing with Applications to Voting,” ACM Conference on Computer and Communication Security, 68-77, 2002.
[7]  P. Golle, S. Zhong, D. Boneh, M. Jakobsson and A. Juels, “Optimistic Mixing for Exit-Polls,” Asiacrypt 2002, 451-465, 2002.
[8]  M. Jakobson, A. Juels and R. Rivest, “Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking,” USENIX Security ’02, 339-353, 2002.
[9]  L. Nguen, R. Dafavi-Naini and K. Kurosawa, “Verifiable Shuffles: A Formal Model and a Paillier-based Efficient Construction with Provable Security,” PKC 2004, LNCS 2248, 61-75, 2004.2002.
[10]  J. Furukawa, “Efficient, Verifiable Shuffle Decryption and Its Requirement of Unlinkability,” PKC 2004, LNCS 2248, 319-332, 2004.
[11]  D. Wikstrom, “Five Practical Attacks for Optimistic Mixing for Exit-Polls,” Proceedings of SAC 2003, 160-175, 2004.
[12]  K. Sampigethaya and R. Poovendran, “A Framework and Taxonomy for Comparison of Electronic Voting Schemes,” Elsevier Computers and Security, 25, 137-153, 2006.View Article
[13]  S. Weber, “A Coercion-Resistant Cryptographic Voting Protocol -Evaluation and Prototype Implementation,” Diploma thesis, Darmstadt University of Technology; 2006.
[14]  K. A. Md Rokibul, S. Tamura, S. Taniguchi and T. Yanase, “An Anonymous Voting Scheme based on Confirmation Numbers,” IEEJ Trans. EIS. 130(11), 2065-2073, 2010.View Article
[15]  S. Tamura, “Anonymous Security Systems and Applications: Requirements and Solutions,” Information Science Reference, 2012.View Article