{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:13Z","timestamp":1750308793505,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>Mix-networks, a family of anonymous messaging protocols, have been engineered to withstand a wide range of theoretical internal and external adversaries. An undetectable insider threat\u2014voluntary partial trace disclosures by server administrators\u2014remains a troubling source of vulnerability. An administrator's cooperation could be the resulting coercion, bribery, or a simple change of interests. While eliminating this insider threat is impossible, it is feasible to deter such unauthorized disclosures by bundling them with additional penalties. We abstract these costs with collateral keys, which grant access to customizable resources. This article introduces the notion of trace-deterring mix-networks, which encode collateral keys for every server-node into every end-to-end message trace. The network reveals no keying material when the input-to-output transitions of individual servers remain secret. Two permutation strategies for encoding key information into traces, mix-and-flip and all-or-nothing, are presented. We analyze their trade-offs with respect to computational efficiency, anonymity sets, and colluding message senders. Our techniques have sufficiently low overhead for deployment in large-scale elections, thereby providing a sort of publicly verifiable privacy guarantee.<\/jats:p>","DOI":"10.1145\/1698750.1698758","type":"journal-article","created":{"date-parts":[[2010,3,9]],"date-time":"2010-03-09T16:34:59Z","timestamp":1268152499000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Deterring voluntary trace disclosure in re-encryption mix-networks"],"prefix":"10.1145","volume":"13","author":[{"given":"Xiaofeng","family":"Wang","sequence":"first","affiliation":[{"name":"PARC"}]},{"given":"Philippe","family":"Golle","sequence":"additional","affiliation":[{"name":"PARC"}]},{"given":"Markus","family":"Jakobsson","sequence":"additional","affiliation":[{"name":"Indiana University"}]},{"given":"Alex","family":"Tsow","sequence":"additional","affiliation":[{"name":"Indiana University"}]}],"member":"320","published-online":{"date-parts":[[2010,3,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054144"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/647095.716723"},{"volume-title":"Proceedings of the 7th Annual Financial Cryptography (FC'03)","author":"Acquisti A.","key":"e_1_2_1_3_1","unstructured":"Acquisti , A. , Dingledine , R. , and Syverson , P . 2003. On the economics of anonymity . In Proceedings of the 7th Annual Financial Cryptography (FC'03) . Springer-Verlag, Berlin, 84--102. Acquisti, A., Dingledine, R., and Syverson, P. 2003. On the economics of anonymity. In Proceedings of the 7th Annual Financial Cryptography (FC'03). Springer-Verlag, Berlin, 84--102."},{"volume-title":"Proceedings of the 2002 Digital Rights Management Workshop. 208--220","author":"Boldyreva A.","key":"e_1_2_1_4_1","unstructured":"Boldyreva , A. and Jakobsson , M . 2002. Theft-protected proprietary certificates . In Proceedings of the 2002 Digital Rights Management Workshop. 208--220 . Boldyreva, A. and Jakobsson, M. 2002. Theft-protected proprietary certificates. In Proceedings of the 2002 Digital Rights Management Workshop. 208--220."},{"key":"e_1_2_1_5_1","unstructured":"Camenisch J. and Stadler M. 1997. Proof systems for general statements about discrete logarithms. Tech. rep. TR 260. Dept. of Computer Science ETH Zurich.  Camenisch J. and Stadler M. 1997. Proof systems for general statements about discrete logarithms. Tech. rep. TR 260. Dept. of Computer Science ETH Zurich."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301313"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/358549.358563"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSECP.2004.1264852"},{"volume-title":"Proceedings of the Cryptology Conference (CRYPTO'86)","author":"Chaum D.","key":"e_1_2_1_9_1","unstructured":"Chaum , D. , Evertse , J.-H. , van de Graaf , J. , and Peralta , R . 1987. Demonstrating possession of a discrete logarithm without revealing it . In Proceedings of the Cryptology Conference (CRYPTO'86) . Springer-Verlag, Berlin, 200--212. Chaum, D., Evertse, J.-H., van de Graaf, J., and Peralta, R. 1987. Demonstrating possession of a discrete logarithm without revealing it. In Proceedings of the Cryptology Conference (CRYPTO'86). Springer-Verlag, Berlin, 200--212."},{"volume-title":"Proceedings of 12th Annual International Cryptology Conference (CRYPTO'92)","author":"Chaum D.","key":"e_1_2_1_10_1","unstructured":"Chaum , D. and Pedersen , T. P . 1993. Wallet databases with observers . In Proceedings of 12th Annual International Cryptology Conference (CRYPTO'92) . Springer-Verlag, Berlin, 89--105. Chaum, D. and Pedersen, T. P. 1993. Wallet databases with observers. In Proceedings of 12th Annual International Cryptology Conference (CRYPTO'92). Springer-Verlag, Berlin, 89--105."},{"volume-title":"Proceedings of the 14th Annual International Cryptology Conference (CRYPTO'94)","author":"Cramer R.","key":"e_1_2_1_11_1","unstructured":"Cramer , R. , Damg\u00e5rd , I. , and Schoenmakers , B . 1994. Proofs of partial knowledge and simplified design of witness hiding protocols . In Proceedings of the 14th Annual International Cryptology Conference (CRYPTO'94) . Springer-Verlag, Berlin, 174--187. Cramer, R., Damg\u00e5rd, I., and Schoenmakers, B. 1994. Proofs of partial knowledge and simplified design of witness hiding protocols. In Proceedings of the 14th Annual International Cryptology Conference (CRYPTO'94). Springer-Verlag, Berlin, 174--187."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_23"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30114-1_21"},{"volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'00)","author":"Desmedt Y.","key":"e_1_2_1_14_1","unstructured":"Desmedt , Y. and Kurosawa , K . 2000. How to break a practical MIX and design a new one . In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'00) . Springer-Verlag, Berlin, 557--572. Desmedt, Y. and Kurosawa, K. 2000. How to break a practical MIX and design a new one. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'00). Springer-Verlag, Berlin, 557--572."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237997"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/352600.352606"},{"volume-title":"Proceedings of the Cryptology Conference (CRYPTO'86)","author":"Fiat A.","key":"e_1_2_1_17_1","unstructured":"Fiat , A. and Shamir , A . 1987. How to prove yourself: Practical solutions to identification and signature problems . In Proceedings of the Cryptology Conference (CRYPTO'86) . Springer-Verlag, Berlin, 186--194. Fiat, A. and Shamir, A. 1987. How to prove yourself: Practical solutions to identification and signature problems. In Proceedings of the Cryptology Conference (CRYPTO'86). Springer-Verlag, Berlin, 186--194."},{"volume-title":"Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (AUSCRYPT'92)","author":"Fujioka A.","key":"e_1_2_1_18_1","unstructured":"Fujioka , A. , Okamoto , T. , and Ohta , K . 1992. A practical secret voting scheme for large scale elections . In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (AUSCRYPT'92) . Springer-Verlag, Berlin, 244--251. Fujioka, A., Okamoto, T., and Ohta, K. 1992. A practical secret voting scheme for large scale elections. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (AUSCRYPT'92). Springer-Verlag, Berlin, 244--251."},{"volume-title":"Proceedings of the 21st Annual International Cryptology Conference (CRYPTO'01)","author":"Furukawa J.","key":"e_1_2_1_19_1","unstructured":"Furukawa , J. and Sako , K . 2001. An efficient scheme for proving a shuffling . In Proceedings of the 21st Annual International Cryptology Conference (CRYPTO'01) . Springer-Verlag, Berlin, 368--387. Furukawa, J. and Sako, K. 2001. An efficient scheme for proving a shuffling. In Proceedings of the 21st Annual International Cryptology Conference (CRYPTO'01). Springer-Verlag, Berlin, 368--387."},{"volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'99)","author":"Gennaro R.","key":"e_1_2_1_20_1","unstructured":"Gennaro , R. , Jarecki , S. , Krawczyk , H. , and Rabin , T . 1999. Secure distributed key generation for discrete-log based cryptosystems . In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'99) . Springer-Verlag, Berlin, 295--310. Gennaro, R., Jarecki, S., Krawczyk, H., and Rabin, T. 1999. Secure distributed key generation for discrete-log based cryptosystems. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'99). Springer-Verlag, Berlin, 295--310."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005140.1005155"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography. Springer-Verlag","author":"Groth J.","year":"2002","unstructured":"Groth , J. 2002 . A verifiable secret shuffle of homomorphic encryptions . In Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography. Springer-Verlag , Berlin, 145--160. Groth, J. 2002. A verifiable secret shuffle of homomorphic encryptions. In Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography. Springer-Verlag, Berlin, 145--160."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384046"},{"volume-title":"Proceedings of the Cryptographer's Track at the 2002 RSA Conference on Topics in Cryptology. Springer-Verlag","author":"Jakobsson M.","key":"e_1_2_1_24_1","unstructured":"Jakobsson , M. , Juels , A. , and Nguyen , P. Q . 2002. Proprietary certificates . In Proceedings of the Cryptographer's Track at the 2002 RSA Conference on Topics in Cryptology. Springer-Verlag , Berlin, 164--181. Jakobsson, M., Juels, A., and Nguyen, P. Q. 2002. Proprietary certificates. In Proceedings of the Cryptographer's Track at the 2002 RSA Conference on Topics in Cryptology. Springer-Verlag, Berlin, 164--181."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of USENIX","author":"Jakobsson M.","year":"2002","unstructured":"Jakobsson , M. , Juels , A. , and Rivest , R . 2002. Making mix nets robust for electronic voting by randomized partial checking . In Proceedings of USENIX 2002 . USENIX, Berkeley, CA, 339--353. Jakobsson, M., Juels, A., and Rivest, R. 2002. Making mix nets robust for electronic voting by randomized partial checking. In Proceedings of USENIX 2002. USENIX, Berkeley, CA, 339--353."},{"volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'03)","author":"Katz J.","key":"e_1_2_1_26_1","unstructured":"Katz , J. , Ostrovsky , R. , and Smith , A . 2003. Round efficiency of multi-party computation with a dishonest majority . In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'03) . Springer-Verlag, Berlin, 578--595. Katz, J., Ostrovsky, R., and Smith, A. 2003. Round efficiency of multi-party computation with a dishonest majority. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT'03). Springer-Verlag, Berlin, 578--595."},{"volume-title":"Proceedings of the 5th Information Hiding Workshop. Springer-Verlag","author":"Kesdogan D.","key":"e_1_2_1_27_1","unstructured":"Kesdogan , D. , Agrawal , D. , and Penz , S . 2002. Limits of anonymity in open environments . In Proceedings of the 5th Information Hiding Workshop. Springer-Verlag , Berlin, 53--69. Kesdogan, D., Agrawal, D., and Penz, S. 2002. Limits of anonymity in open environments. In Proceedings of the 5th Information Hiding Workshop. Springer-Verlag, Berlin, 53--69."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27809-2_25"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/501983.502000"},{"key":"e_1_2_1_30_1","unstructured":"Neff A. 2003. Verifiable mixing (shuffling) of ElGamal pairs. Tech. rep. http:\/\/courses.csail.mit.edu\/6.897\/spring04\/Neff-2004-04-21-ElGamalShuffles.pdf.  Neff A. 2003. Verifiable mixing (shuffling) of ElGamal pairs. Tech. rep. http:\/\/courses.csail.mit.edu\/6.897\/spring04\/Neff-2004-04-21-ElGamalShuffles.pdf."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/646277.758922"},{"volume-title":"Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'93)","author":"Park C.","key":"e_1_2_1_32_1","unstructured":"Park , C. , Itoh , K. , and Kurosawa , K . 1993. All\/nothing election scheme and anonymous channel . In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'93) . Springer-Verlag, Berlin, 248--259. Park, C., Itoh, K., and Kurosawa, K. 1993. All\/nothing election scheme and anonymous channel. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'93). Springer-Verlag, Berlin, 248--259."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/646756.705507"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030083.1030114"},{"volume-title":"Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'95)","author":"Sako K.","key":"e_1_2_1_35_1","unstructured":"Sako , K. and Kilian , J . 1995. Receipt-free MIX-type voting scheme: A practical solution to the implementation of a voting booth . In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'95) . Springer-Verlag, Berlin, 393--403. Sako, K. and Kilian, J. 1995. Receipt-free MIX-type voting scheme: A practical solution to the implementation of a voting booth. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'95). Springer-Verlag, Berlin, 393--403."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365745"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698750.1698758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1698750.1698758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:58Z","timestamp":1750278178000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698750.1698758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1698750.1698758"],"URL":"https:\/\/doi.org\/10.1145\/1698750.1698758","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2010,2]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}