1. bookVolume 2022 (2022): Issue 1 (January 2022)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

(∈, δ)-Indistinguishable Mixing for Cryptocurrencies

Published Online: 20 Nov 2021
Page range: 49 - 74
Received: 31 May 2021
Accepted: 16 Sep 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

We propose a new theoretical approach for building anonymous mixing mechanisms for cryptocurrencies. Rather than requiring a fully uniform permutation during mixing, we relax the requirement, insisting only that neighboring permutations are similarly likely. This is defined formally by borrowing from the definition of differential privacy. This relaxed privacy definition allows us to greatly reduce the amount of interaction and computation in the mixing protocol. Our construction achieves O(polylog(n)) computation time for mixing n addresses, whereas all other mixing schemes require O(n2) total computation across all parties. Additionally, we support a smooth tolerance of fail-stop adversaries and do not require any trusted setup. We analyze the security of our generic protocol under the UC framework, and under a stand-alone, game-based definition. We finally describe an instantiation using ring signatures and confidential transactions.

Keywords

[1] Masayuki Abe. Mix-networks on permutation networks. In Kwok-Yan Lam, Eiji Okamoto, and Chaoping Xing, editors, Advances in Cryptology – ASIACRYPT’99, volume 1716 of Lecture Notes in Computer Science, pages 258–273, Singapore, November 14–18, 1999. Springer, Heidelberg, Germany. Search in Google Scholar

[2] Elli Androulaki, Ghassan Karame, Marc Roeschlin, Tobias Scherer, and Srdjan Capkun. Evaluating user privacy in bitcoin. In FC, 2013. Search in Google Scholar

[3] Michael Backes, Praveen Manoharan, and Esfandiar Mohammadi. TUC: time-sensitive and modular analysis of anonymous communication. In CSF, 2014. Search in Google Scholar

[4] Christian Badertscher, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. Bitcoin as a transaction ledger: A composable treatment. In CRYPTO, 2017. Search in Google Scholar

[5] Amos Beimel, Kobbi Nissim, and Mohammad Zaheri. Exploring differential obliviousness. CoRR, abs/1905.01373, 2019. Search in Google Scholar

[6] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. IACR ePrint, 2018. Search in Google Scholar

[7] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In IEEE-SP, 2014. Search in Google Scholar

[8] Alex Biryukov and Sergei Tikhomirov. Deanonymization and linkability of cryptocurrency transactions based on network analysis. In EuroS&P, 2019. Search in Google Scholar

[9] Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark, Joshua A. Kroll, and Edward W. Felten. Mixcoin: Anonymity for bitcoin with accountable mixes. In FC, 2014. Search in Google Scholar

[10] Elette Boyle, Saleet Klein, Alon Rosen, and Gil Segev. Securing abe’s mix-net against malicious verifiers via witness indistinguishability. In Dario Catalano and Roberto De Prisco, editors, SCN 18: 11th International Conference on Security in Communication Networks, volume 11035 of Lecture Notes in Computer Science, pages 274–291, Amalfi, Italy, September 5–7, 2018. Springer, Heidelberg, Germany. Search in Google Scholar

[11] Benedikt Bünz, Shashank Agrawal, Mahdi Zamani, and Dan Boneh. Zether: Towards privacy in a smart contract world. In International Conference on Financial Cryptography and Data Security, pages 423–443. Springer, 2020. Search in Google Scholar

[12] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In IEEE-SP, 2018. Search in Google Scholar

[13] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2000. http://eprint.iacr.org/2000/067. Search in Google Scholar

[14] Ran Canetti. Universally composable signature, certification, and authentication. In CSFW-17, 2004. Search in Google Scholar

[15] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. In Salil P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, pages 61–85, Amsterdam, The Netherlands, February 21–24, 2007. Springer, Heidelberg, Germany. Search in Google Scholar

[16] Ran Canetti, Kyle Hogan, Aanchal Malhotra, and Mayank Varia. A universally composable treatment of network time. In CSF, 2017. Search in Google Scholar

[17] Ran Canetti, Daniel Shahaf, and Margarita Vald. Universally composable authentication and key-exchange with global PKI. In PKC, pages 265–296, 2016. Search in Google Scholar

[18] T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, and Elaine Shi. Foundations of differentially oblivious algorithms. In SODA, 2019. Search in Google Scholar

[19] David Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptology, 1:65–75, 1988. Search in Google Scholar

[20] Coinmarketcap https://coinmarketcap.com/. Accessed 2/25/2021. Search in Google Scholar

[21] Adrian Zmudzinski (Cointelegraph). Chainalysis rolls out real-time threat detector for 15 major cryptos), 2019. Accessed 9/23/2020. Search in Google Scholar

[22] Joshua Mapperson (Cointelegraph). Understanding litecoin’s dusting attack: What happened and why), 2019. Accessed 9/23/2020. Search in Google Scholar

[23] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, TCC 2006: 3rd Theory of Cryptography Conference, volume 3876 of Lecture Notes in Computer Science, pages 265–284, New York, NY, USA, March 4–7, 2006. Springer, Heidelberg, Germany. Search in Google Scholar

[24] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9:211–407, August 2014. Search in Google Scholar

[25] Prastudy Fauzi, Sarah Meiklejohn, Rebekah Mercer, and Claudio Orlandi. Quisquis: A new design for anonymous cryptocurrencies. In Asiacrypt, 2019. Search in Google Scholar

[26] Steven Goldfeder, Harry A. Kalodner, Dillon Reisman, and Arvind Narayanan. When the cookie meets the blockchain: Privacy risks of web payments via cryptocurrencies. Proc. Priv. Enhancing Technol., 2018(4):179–199, 2018. Search in Google Scholar

[27] Brandon Goodell, Sarang Noether, and RandomRun. Concise linkable ring signatures and forgery against adversarial keys. Cryptology ePrint Archive, Report 2019/654, 2019. https://eprint.iacr.org/2019/654. Search in Google Scholar

[28] Jens Groth. On the size of pairing-based non-interactive arguments. In Eurocrypt, pages 305–326. Springer, 2016. Search in Google Scholar

[29] Andrey Gubichev. Online-routing on the butterfly network: probabilistic analysis, 2008. Accessed 9/26/2020. Search in Google Scholar

[30] Xi He, Ashwin Machanavajjhala, Cheryl J. Flynn, and Divesh Srivastava. Composing differential privacy and secure computation: A case study on scaling private record linkage. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017: 24th Conference on Computer and Communications Security, pages 1389–1406, Dallas, TX, USA, October 31 – November 2, 2017. ACM Press. Search in Google Scholar

[31] Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro, and Sharon Goldberg. Tumblebit: An untrusted bitcoin-compatible anonymous payment hub. In NDSS, 2017. Search in Google Scholar

[32] Shiva Prasad Kasiviswanathan and Adam D. Smith. A note on differential privacy: Defining resistance to arbitrary side information. CoRR, abs/0803.3946, 2008. Search in Google Scholar

[33] Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. Universally composable synchronous computation. In TCC, 2013. Search in Google Scholar

[34] Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O’Neill. Accessing data while preserving privacy. CoRR, abs/1706.01552, 2017. Search in Google Scholar

[35] Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas. Fair and robust multi-party computation using a global transaction ledger. In EUROCRYPT, 2016. Search in Google Scholar

[36] Robin Klusman and Tim Dijkhuizen. Deanonymisation in ethereum using existing methods for bitcoin, 2018. Technical Report, https://delaat.net/rp/2017-2018/p61/report.pdf. Search in Google Scholar

[37] Russell WF Lai, Viktoria Ronge, Tim Ruffing, Dominique Schröder, Sri Aravinda Krishnan Thyagarajan, and Jiafan Wang. Omniring: Scaling up private payments without trusted setup. IACR Cryptology ePrint Archive, 2019:580, 2019. Search in Google Scholar

[38] David Lazar, Yossi Gilad, and Nickolai Zeldovich. Karaoke: Distributed private messaging immune to passive traffic analysis. In USENIX, 2018. Search in Google Scholar

[39] Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-knowledge snarks from linear-size universal and updateable structured reference strings. IACR Cryptology ePrint Archive, 2019:99, 2019. Search in Google Scholar

[40] Felix Konstantin Maurer, Till Neudecker, and Martin Florian. Anonymous coinjoin transactions with arbitrary values. In 2017 IEEE Trustcom/BigDataSE/ICESS, pages 522–529. IEEE, 2017. Search in Google Scholar

[41] Sahar Mazloom and S. Dov Gordon. Secure computation with differentially private access patterns. In ACM-CCS, 2018. Search in Google Scholar

[42] Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker, and Stefan Savage. A fistful of bitcoins: characterizing payments among men with no names. In IMC, 2013. Search in Google Scholar

[43] Monero, https://getmonero.org/home. Accessed 2/25/2021. Search in Google Scholar

[44] Pedro Moreno-Sanchez, Tim Ruffing, and Aniket Kate. Pathshuffle: Credit mixing and anonymous payments for ripple. PoPETS, 2017. Search in Google Scholar

[45] Pedro Moreno-Sanchez, Muhammad Bilal Zafar, and Aniket Kate. Listening to whispers of ripple: Linking wallets and deanonymizing transactions in the ripple network. PoPETs, 2016(4):436–453, 2016. Search in Google Scholar

[46] Malte Möser, Kyle Soska, Ethan Heilman, Kevin Lee, Henry Heffan, Shashvat Srivastava, Kyle Hogan, Jason Hennessey, Andrew Miller, Arvind Narayanan, and Nicolas Christin. An empirical analysis of traceability in the monero blockchain. PoPETs, 2018(3):143–163, 2018. Search in Google Scholar

[47] Mahnush Movahedi, Jared Saia, and Mahdi Zamani. Secure multi-party shuffling. In Christian Scheideler, editor, Structural Information and Communication Complexity, pages 459–473, Cham, 2015. Springer International Publishing. Search in Google Scholar

[48] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review, page 21260, 2008. Search in Google Scholar

[49] Sarang Noether and Brandon Goodell. Triptych: Logarithmic-sized linkable ring signatures with applications. In Joaquin Garcia-Alfaro, Guillermo Navarro-Arribas, and Jordi Herrera-Joancomarti, editors, Data Privacy Management, Cryptocurrencies and Blockchain Technology, pages 337–354, Cham, 2020. Springer International Publishing. Search in Google Scholar

[50] Shen Noether, Adam Mackenzie, et al. Ring confidential transactions. Ledger, 1:1–18, 2016. Search in Google Scholar

[51] Ronald L. Rivest, Adi Shamir, and Yael Tauman. How to leak a secret. In ASIACRYPT, 2001. Search in Google Scholar

[52] Dorit Ron and Adi Shamir. Quantitative analysis of the full bitcoin transaction graph. In FC. Springer, 2013. Search in Google Scholar

[53] Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. Coinshuffle: Practical decentralized coin mixing for bitcoin. In ESORICS, 2014. Search in Google Scholar

[54] Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. P2P mixing and unlinkable bitcoin transactions. In NDSS, 2017. Search in Google Scholar

[55] Amitabh Saxena, Janardan Misra, and Aritra Dhar. Increasing anonymity in bitcoin. In FC, pages 122–139. Springer, 2014. Search in Google Scholar

[56] Various sources (Coin Metrics). Average number of daily cryptocurrency transactions in 1st quarter of 2019, by type (in thousand transactions), 2019. Accessed 9/23/2020. Search in Google Scholar

[57] Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. Stadium: A distributed metadata-private messaging system. In SOSP, pages 423–440, New York, NY, USA, 2017. ACM. Search in Google Scholar

[58] Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, 2017. Search in Google Scholar

[59] István Vajda. On the analysis of time-aware protocols in universal composability framework. Int. J. Inf. Sec., 15(4):403–412, 2016. Search in Google Scholar

[60] Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. Vuvuzela: Scalable private messaging resistant to traffic analysis. In SOSP, New York, NY, USA, 2015. ACM. Search in Google Scholar

[61] Nicolas van Saberhagen. Cryptonote v 2.0. Whitepaper, 2013. Search in Google Scholar

[62] Sameer Wagh, Paul Cuff, and Prateek Mittal. Differentially private oblivious RAM. PoPETs, 2018(4):64–84, 2018. Search in Google Scholar

[63] Tsz Hon Yuen, Shi-Feng Sun, Joseph K. Liu, Man Ho Au, Muhammed F. Esgin, Qingzhao Zhang, and Dawu Gu. Ringct 3.0 for blockchain confidential transaction: Shorter size and stronger security. In Joseph Bonneau and Nadia Heninger, editors, Financial Cryptography and Data Security, pages 464–483, Cham, 2020. Springer International Publishing. Search in Google Scholar

[64] Zcash, https://z.cash/. Accessed 2/25/2021. Search in Google Scholar

[65] ZCash Foundation. GrantProposals-2018Q2. https://github.com/ZcashFoundation/GrantProposals-2018Q2, 2018. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo