Kleptographic attacks on a cascade of mix servers

ABSTRACT

A cascade of mix servers is a crucial part of e-voting protocols and other schemes which aim for user's anonymity. We present kleptographic attacks on such cascades. In order to show interesting consequences, we focus on a cascade used as a building block of a Prêt à Voter e-voting protocol. However, the attacks might be generalized to any cascade of probabilistic mix servers.

REFERENCES

• 1: M. R. Best. Perfect codes hardly exist. IEEE Trans. Inform. Theory, 29(3):349--351, 1983.
• 2: Piotr Borzecki , Jedrzej Kabarowski , Przemyslaw Kubiak , Miroslaw Kutylowski , Filip Zagorski, Kleptographic Weaknesses in Benaloh-Tuinstra Protocol, Proceedings of the International Conference on Systems and Networks Communication, p.26, October 29-November 03, 2006 [doi>10.1109/ICSNC.2006.50]
• 3: Certicom Inc. The Certicom ECC challenge. {online}. Available from: http://www.certicom.com/index.php?action=ecc, ecc_challenge.
• 4: D. Chaum. Secret-ballot receipts: True voter-verifiable elections. IEEE Security and Privacy Magazine, 2(1):38--47, Jan./Feb. 2004.
• 5: J. Y. Choi, P. Golle, and M. Jakobsson. Auditable privacy: On tamper-evident mix networks. In: Financial Cryptography, LNCS 4107, pages 126--141. Springer, 2006.
• 6: W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Inform. Theory, 22(6):644--654, Nov. 1976.
• 7: W. M. Duckworth II. Codes, Designs, and Distance. PhD thesis, University of North Carolina at Chapel Hill, 1998.
• 8: I. Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. Electronic Colloquium on Computational Complexity (ECCC), 6(29), 1999.
• 9: M. Gogolewski, M. Klonowski, P. Kubiak, M. Kutyłowski, A. Lauks, and F. Zagórski. Kleptographic attacks on e-voting schemes. In: ETRICS, LNCS 3995, pages 494--508. Springer, 2006.
• 10: Philippe Golle , Markus Jakobsson, Reusable anonymous return channels, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC [doi>10.1145/1005140.1005155]
• 11: S. Har-Peled. Class notes for randomized algorithms, Dec. 2005.
• 12: Markus Jakobsson , Ari Juels, Mix and Match: Secure Function Evaluation via Ciphertexts, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.162-177, December 03-07, 2000
• 13: Markus Jakobsson , Ari Juels , Ronald L. Rivest, Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, Proceedings of the 11th USENIX Security Symposium, p.339-353, August 05-09, 2002
• 14: M. Klonowski, M. Kutyłowski, M. Ren, and K. Rybarczyk. Forward-secure key evolution protocol in wireless sensor networks. Nov. 2006. Manuscript.
• 15: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 16: D. Lundin, H. Treharne, P. Y. Ryan, S. Schneider, and J. Heather. Distributed creation of the ballot form in Prêt à Voter using an element of visual encryption. IAVoSS Workshop On Trustworthy Elections (WOTE 2006).
• 17: S. McKinley. The Hamming codes and Delsarte's linear programming bound. Master's thesis, Portland State University, May 2003.
• 18: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 19: B. Möller. A public-key encryption scheme with pseudo-random ciphertexts. In: ESORICS, LNCS 3193, pages 335--351. Springer, 2004.
• 20: Michael Navon , Alex Samorodnitsky, On Delsarte"s Linear Programming Bounds for Binary Codes, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.327-338, October 23-25, 2005 [doi>10.1109/SFCS.2005.55]
• 21: C. Neff. Verifiable mixing (shuffling) of ElGamal pairs., Apr. 2004.
• 22: P. Ryan. Socio-technical trade-offs in cryptographic voting schemes. Workshop on Electronic Voting and e-Government in the UK, 27th-28th Feb. 2006.
• 23: P. Y. Ryan and T. Peacock. Prêt à Voter: a systems perspective. Technical Report 929, University of Newcastle upon Tyne, School of Computing Science, Sept. 2005.
• 24: P. Y. A. Ryan and S. A. Schneider. Prêt à Voter with re-encryption mixes. In: ESORICS, LNCS 4189, pages 313--326. Springer, 2006.
• 25: P. Y. A. Ryan and S. A. Schneider. Prêt à Voter with re-encryption mixes. Technical Report 956, University of Newcastle upon Tyne, School of Computing Science, Apr. 2006.
• 26: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 27: A. Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6): 1757--1766, 1997.
• 28: Adam Young , Moti Yung, The Dark Side of "Black-Box" Cryptography, or: Should We Trust Capstone?, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.89-103, August 18-22, 1996
• 29: A. Young and M. Yung. Kleptography: Using cryptography against cryptography. In: EUROCRYPT, LNCS 1233, pages 62--74. Springer, 1997.
• 30: Adam Young , Moti Yung, Bandwidth-Optimal Kleptographic Attacks, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.235-250, May 14-16, 2001
• 31: A. Young and M. Yung. A subliminal channel in secret block ciphers. In: Selected Areas in Cryptography, LNCS 3357, pages 198--211. Springer, 2004.
• 32: A. Young and M. Yung. Malicious cryptography: Kleptographic aspects. In: CT-RSA, LNCS 3376, pages 7--18. Springer, 2005.
• 33: A. Young and M. Yung. A space efficient backdoor in RSA and its applications. In: Selected Areas in Cryptography, LNCS 3897, pages 128--143. Springer, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Abuse and crime involving computers
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

General Terms:
Security, Verification

Keywords:
anonymity, cascade of mix servers, electronic voting, kleptography