[{"scopus_import":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"month":"01","date_published":"2024-01-18T00:00:00Z","conference":{"start_date":"2023-12-06","end_date":"2023-12-08","location":"Tokyo, Japan","name":"OPODIS: Conference on Principles of Distributed Systems"},"date_created":"2024-02-18T23:01:02Z","file":[{"date_updated":"2024-02-26T10:16:57Z","access_level":"open_access","date_created":"2024-02-26T10:16:57Z","checksum":"2993e810a45e8c8056106834b07aea92","file_name":"2024_LIPICs_Alpos.pdf","file_size":1505994,"file_id":"15031","creator":"dernst","content_type":"application/pdf","relation":"main_file","success":1}],"has_accepted_license":"1","license":"https://creativecommons.org/licenses/by/4.0/","department":[{"_id":"KrPi"}],"intvolume":"       286","status":"public","day":"18","type":"conference","publication":"27th International Conference on Principles of Distributed Systems","file_date_updated":"2024-02-26T10:16:57Z","external_id":{"arxiv":["2307.02954"]},"title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","doi":"10.4230/LIPIcs.OPODIS.2023.12","year":"2024","ddc":["000"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"alternative_title":["LIPIcs"],"article_number":"12","abstract":[{"text":"Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.","lang":"eng"}],"author":[{"full_name":"Alpos, Orestis","last_name":"Alpos","first_name":"Orestis"},{"first_name":"Ignacio","last_name":"Amores-Sesar","full_name":"Amores-Sesar, Ignacio"},{"first_name":"Christian","full_name":"Cachin, Christian","last_name":"Cachin"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"citation":{"chicago":"Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>.","ieee":"O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","apa":"Alpos, O., Amores-Sesar, I., Cachin, C., &#38; Yeo, M. X. (2024). Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>","short":"O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.","mla":"Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>.","ama":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>"},"publication_status":"published","publication_identifier":{"isbn":["9783959773089"],"issn":["1868-8969"]},"_id":"15007","quality_controlled":"1","oa_version":"Published Version","acknowledgement":"We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful discussions. This work has been funded by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"article_processing_charge":"No","volume":286,"oa":1,"date_updated":"2024-02-26T10:18:18Z"},{"publication_status":"published","citation":{"ama":"Avarikioti Z, Lizurej T, Michalak T, Yeo MX. Lightning creation games. In: <i>43rd International Conference on Distributed Computing Systems</i>. Vol 2023. IEEE; 2023:603-613. doi:<a href=\"https://doi.org/10.1109/ICDCS57875.2023.00037\">10.1109/ICDCS57875.2023.00037</a>","mla":"Avarikioti, Zeta, et al. “Lightning Creation Games.” <i>43rd International Conference on Distributed Computing Systems</i>, vol. 2023, IEEE, 2023, pp. 603–13, doi:<a href=\"https://doi.org/10.1109/ICDCS57875.2023.00037\">10.1109/ICDCS57875.2023.00037</a>.","ista":"Avarikioti Z, Lizurej T, Michalak T, Yeo MX. 2023. Lightning creation games. 43rd International Conference on Distributed Computing Systems. ICDCS: International Conference on Distributed Computing Systems vol. 2023, 603–613.","short":"Z. Avarikioti, T. Lizurej, T. Michalak, M.X. Yeo, in:, 43rd International Conference on Distributed Computing Systems, IEEE, 2023, pp. 603–613.","ieee":"Z. Avarikioti, T. Lizurej, T. Michalak, and M. X. Yeo, “Lightning creation games,” in <i>43rd International Conference on Distributed Computing Systems</i>, Hong Kong, China, 2023, vol. 2023, pp. 603–613.","apa":"Avarikioti, Z., Lizurej, T., Michalak, T., &#38; Yeo, M. X. (2023). Lightning creation games. In <i>43rd International Conference on Distributed Computing Systems</i> (Vol. 2023, pp. 603–613). Hong Kong, China: IEEE. <a href=\"https://doi.org/10.1109/ICDCS57875.2023.00037\">https://doi.org/10.1109/ICDCS57875.2023.00037</a>","chicago":"Avarikioti, Zeta, Tomasz Lizurej, Tomasz Michalak, and Michelle X Yeo. “Lightning Creation Games.” In <i>43rd International Conference on Distributed Computing Systems</i>, 2023:603–13. IEEE, 2023. <a href=\"https://doi.org/10.1109/ICDCS57875.2023.00037\">https://doi.org/10.1109/ICDCS57875.2023.00037</a>."},"abstract":[{"text":"Payment channel networks (PCNs) are a promising solution to the scalability problem of cryptocurrencies. Any two users connected by a payment channel in the network can theoretically send an unbounded number of instant, costless transactions between them. Users who are not directly connected can also transact with each other in a multi-hop fashion. In this work, we study the incentive structure behind the creation of payment channel networks, particularly from the point of view of a single user that wants to join the network. We define a utility function for a new user in terms of expected revenue, expected fees, and the cost of creating channels, and then provide constant factor approximation algorithms that optimise the utility function given a certain budget. Additionally, we take a step back from a single user to the whole network and examine the parameter spaces under which simple graph topologies form a Nash equilibrium.","lang":"eng"}],"author":[{"full_name":"Avarikioti, Zeta","last_name":"Avarikioti","first_name":"Zeta"},{"last_name":"Lizurej","full_name":"Lizurej, Tomasz","first_name":"Tomasz"},{"first_name":"Tomasz","last_name":"Michalak","full_name":"Michalak, Tomasz"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"arxiv":1,"date_updated":"2023-11-30T10:54:51Z","volume":2023,"oa":1,"article_processing_charge":"No","_id":"14490","publication_identifier":{"isbn":["9798350339864"],"eissn":["2575-8411"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The work was partially supported by the Austrian Science Fund (FWF) through the project CoRaF (grant 2020388). It was also partially supported by NCN Grant 2019/35/B/ST6/04138 and ERC Grant 885666.","quality_controlled":"1","oa_version":"Preprint","doi":"10.1109/ICDCS57875.2023.00037","year":"2023","external_id":{"arxiv":["2306.16006"]},"title":"Lightning creation games","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2306.16006"}],"related_material":{"record":[{"status":"public","id":"14506","relation":"dissertation_contains"}]},"day":"11","type":"conference","intvolume":"      2023","status":"public","publication":"43rd International Conference on Distributed Computing Systems","page":"603-613","month":"10","date_published":"2023-10-11T00:00:00Z","publisher":"IEEE","scopus_import":"1","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"conference":{"start_date":"2023-07-18","end_date":"2023-07-21","location":"Hong Kong, China","name":"ICDCS: International Conference on Distributed Computing Systems"},"date_created":"2023-11-05T23:00:54Z"},{"project":[{"grant_number":"665385","call_identifier":"H2020","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"oa_version":"Published Version","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication_identifier":{"issn":["2663 - 337X"]},"_id":"14506","article_processing_charge":"No","date_updated":"2025-07-14T09:09:52Z","oa":1,"author":[{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo","orcid":"0009-0001-3676-4809","first_name":"Michelle X"}],"abstract":[{"text":"Payment channel networks are a promising approach to improve the scalability bottleneck\r\nof cryptocurrencies. Two design principles behind payment channel networks are\r\nefficiency and privacy. Payment channel networks improve efficiency by allowing users\r\nto transact in a peer-to-peer fashion along multi-hop routes in the network, avoiding\r\nthe lengthy process of consensus on the blockchain. Transacting over payment channel\r\nnetworks also improves privacy as these transactions are not broadcast to the blockchain.\r\nDespite the influx of recent protocols built on top of payment channel networks and\r\ntheir analysis, a common shortcoming of many of these protocols is that they typically\r\nfocus only on either improving efficiency or privacy, but not both. Another limitation\r\non the efficiency front is that the models used to model actions, costs and utilities of\r\nusers are limited or come with unrealistic assumptions.\r\nThis thesis aims to address some of the shortcomings of recent protocols and algorithms\r\non payment channel networks, particularly in their privacy and efficiency aspects. We\r\nfirst present a payment route discovery protocol based on hub labelling and private\r\ninformation retrieval that hides the route query and is also efficient. We then present\r\na rebalancing protocol that formulates the rebalancing problem as a linear program\r\nand solves the linear program using multiparty computation so as to hide the channel\r\nbalances. The rebalancing solution as output by our protocol is also globally optimal.\r\nWe go on to develop more realistic models of the action space, costs, and utilities of\r\nboth existing and new users that want to join the network. In each of these settings,\r\nwe also develop algorithms to optimise the utility of these users with good guarantees\r\non the approximation and competitive ratios.","lang":"eng"}],"citation":{"chicago":"Yeo, Michelle X. “Advances in Efficiency and Privacy in Payment Channel Network Analysis.” Institute of Science and Technology Austria, 2023. <a href=\"https://doi.org/10.15479/14506\">https://doi.org/10.15479/14506</a>.","apa":"Yeo, M. X. (2023). <i>Advances in efficiency and privacy in payment channel network analysis</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/14506\">https://doi.org/10.15479/14506</a>","ieee":"M. X. Yeo, “Advances in efficiency and privacy in payment channel network analysis,” Institute of Science and Technology Austria, 2023.","short":"M.X. Yeo, Advances in Efficiency and Privacy in Payment Channel Network Analysis, Institute of Science and Technology Austria, 2023.","ista":"Yeo MX. 2023. Advances in efficiency and privacy in payment channel network analysis. Institute of Science and Technology Austria.","mla":"Yeo, Michelle X. <i>Advances in Efficiency and Privacy in Payment Channel Network Analysis</i>. Institute of Science and Technology Austria, 2023, doi:<a href=\"https://doi.org/10.15479/14506\">10.15479/14506</a>.","ama":"Yeo MX. Advances in efficiency and privacy in payment channel network analysis. 2023. doi:<a href=\"https://doi.org/10.15479/14506\">10.15479/14506</a>"},"publication_status":"published","ddc":["000"],"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"9969"},{"status":"public","id":"14490","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"13238","status":"public"}]},"alternative_title":["ISTA Thesis"],"title":"Advances in efficiency and privacy in payment channel network analysis","ec_funded":1,"doi":"10.15479/14506","year":"2023","page":"162","file_date_updated":"2023-11-23T10:30:08Z","status":"public","supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"type":"dissertation","day":"10","file":[{"checksum":"521c72818d720a52b377207b2ee87b6a","date_created":"2023-11-23T10:29:55Z","file_size":3037720,"file_name":"thesis_yeo.zip","access_level":"closed","date_updated":"2023-11-23T10:29:55Z","file_id":"14598","creator":"cchlebak","relation":"source_file","content_type":"application/x-zip-compressed"},{"file_id":"14599","creator":"cchlebak","content_type":"application/pdf","relation":"main_file","success":1,"date_updated":"2023-11-23T10:30:08Z","access_level":"open_access","date_created":"2023-11-23T10:30:08Z","checksum":"0ed5d16899687aecf13d843c9878c9f2","file_name":"thesis_yeo.pdf","file_size":2717256}],"date_created":"2023-11-10T08:10:43Z","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"degree_awarded":"PhD","has_accepted_license":"1","language":[{"iso":"eng"}],"publisher":"Institute of Science and Technology Austria","date_published":"2023-11-10T00:00:00Z","month":"11"},{"day":"01","type":"conference","intvolume":"     13950","status":"public","publication":"27th International Conference on Financial Cryptography and Data Security","page":"309-325","month":"12","date_published":"2023-12-01T00:00:00Z","publisher":"Springer Nature","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"conference":{"location":"Bol, Brac, Croatia","end_date":"2023-05-05","name":"FC: Financial Cryptography and Data Security","start_date":"2023-05-01"},"date_created":"2024-01-08T09:30:22Z","citation":{"chicago":"Bastankhah, Mahsa, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” In <i>27th International Conference on Financial Cryptography and Data Security</i>, 13950:309–25. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">https://doi.org/10.1007/978-3-031-47754-6_18</a>.","ieee":"M. Bastankhah, K. Chatterjee, M. A. Maddah-Ali, S. Schmid, J. Svoboda, and M. X. Yeo, “R2: Boosting liquidity in payment channel networks with online admission control,” in <i>27th International Conference on Financial Cryptography and Data Security</i>, Bol, Brac, Croatia, 2023, vol. 13950, pp. 309–325.","apa":"Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online admission control. In <i>27th International Conference on Financial Cryptography and Data Security</i> (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">https://doi.org/10.1007/978-3-031-47754-6_18</a>","short":"M. Bastankhah, K. Chatterjee, M.A. Maddah-Ali, S. Schmid, J. Svoboda, M.X. Yeo, in:, 27th International Conference on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 309–325.","ista":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. 2023. R2: Boosting liquidity in payment channel networks with online admission control. 27th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 309–325.","ama":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. R2: Boosting liquidity in payment channel networks with online admission control. In: <i>27th International Conference on Financial Cryptography and Data Security</i>. Vol 13950. Springer Nature; 2023:309-325. doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">10.1007/978-3-031-47754-6_18</a>","mla":"Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” <i>27th International Conference on Financial Cryptography and Data Security</i>, vol. 13950, Springer Nature, 2023, pp. 309–25, doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">10.1007/978-3-031-47754-6_18</a>."},"publication_status":"published","abstract":[{"text":"Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain routes may deplete channels in one direction, and hence prevent further transactions. In order to reap the full potential of PCNs, recharging and rebalancing mechanisms are required to provision channels, as well as an admission control logic to decide which transactions to reject in case capacity is insufficient. This paper presents a formal model of this optimisation problem. In particular, we consider an online algorithms perspective, where transactions arrive over time in an unpredictable manner. Our main contributions are competitive online algorithms which come with provable guarantees over time. We empirically evaluate our algorithms on randomly generated transactions to compare the average performance of our algorithms to our theoretical bounds. We also show how this model and approach differs from related problems in classic communication networks.","lang":"eng"}],"author":[{"full_name":"Bastankhah, Mahsa","last_name":"Bastankhah","first_name":"Mahsa"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Mohammad Ali","last_name":"Maddah-Ali","full_name":"Maddah-Ali, Mohammad Ali"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"article_processing_charge":"No","date_updated":"2025-07-14T09:10:01Z","volume":13950,"publication_identifier":{"isbn":["9783031477539"],"issn":["0302-9743"],"eisbn":["9783031477546"],"eissn":["1611-3349"]},"_id":"14736","quality_controlled":"1","oa_version":"None","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Supported by the German Federal Ministry of Education and Research (BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).","year":"2023","doi":"10.1007/978-3-031-47754-6_18","ec_funded":1,"title":"R2: Boosting liquidity in payment channel networks with online admission control","alternative_title":["LNCS"]},{"language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","date_published":"2023-05-25T00:00:00Z","month":"05","date_created":"2023-07-16T22:01:12Z","conference":{"start_date":"2023-06-06","end_date":"2023-06-09","location":"Alcala de Henares, Spain","name":"SIROCCO: Structural Information and Communication Complexity"},"department":[{"_id":"KrPi"},{"_id":"KrCh"}],"status":"public","intvolume":"     13892","type":"conference","day":"25","page":"576-594","publication":"SIROCCO 2023: Structural Information and Communication Complexity ","title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","external_id":{"arxiv":["2204.13459"]},"ec_funded":1,"year":"2023","doi":"10.1007/978-3-031-32733-9_26","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"14506"}]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2204.13459","open_access":"1"}],"alternative_title":["LNCS"],"author":[{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","last_name":"Svoboda","full_name":"Svoboda, Jakub","first_name":"Jakub"},{"orcid":"0009-0001-3676-4809","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how much nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v’s capacity on (u, v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes’ decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+ε)⋅(1+3–√) for some arbitrary ε>0.\r\n."}],"publication_status":"published","citation":{"chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” In <i>SIROCCO 2023: Structural Information and Communication Complexity </i>, 13892:576–94. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">https://doi.org/10.1007/978-3-031-32733-9_26</a>.","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In <i>SIROCCO 2023: Structural Information and Communication Complexity </i> (Vol. 13892, pp. 576–594). Alcala de Henares, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">https://doi.org/10.1007/978-3-031-32733-9_26</a>","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” in <i>SIROCCO 2023: Structural Information and Communication Complexity </i>, Alcala de Henares, Spain, 2023, vol. 13892, pp. 576–594.","ista":"Schmid S, Svoboda J, Yeo MX. 2023. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. SIROCCO 2023: Structural Information and Communication Complexity . SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 13892, 576–594.","short":"S. Schmid, J. Svoboda, M.X. Yeo, in:, SIROCCO 2023: Structural Information and Communication Complexity , Springer Nature, 2023, pp. 576–594.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In: <i>SIROCCO 2023: Structural Information and Communication Complexity </i>. Vol 13892. Springer Nature; 2023:576-594. doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">10.1007/978-3-031-32733-9_26</a>","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>SIROCCO 2023: Structural Information and Communication Complexity </i>, vol. 13892, Springer Nature, 2023, pp. 576–94, doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">10.1007/978-3-031-32733-9_26</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021–2024.","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"oa_version":"Preprint","quality_controlled":"1","_id":"13238","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031327322"],"eissn":["1611-3349"]},"date_updated":"2025-07-14T09:09:53Z","volume":13892,"oa":1,"article_processing_charge":"No","arxiv":1},{"year":"2022","doi":"10.1007/978-3-031-18283-9_17","external_id":{"arxiv":["2110.08848"]},"title":"Hide & Seek: Privacy-preserving rebalancing on payment channel networks","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2110.08848"}],"publication_status":"published","citation":{"apa":"Avarikioti, G., Pietrzak, K. Z., Salem, I., Schmid, S., Tiwari, S., &#38; Yeo, M. X. (2022). Hide &#38; Seek: Privacy-preserving rebalancing on payment channel networks. In <i>Financial Cryptography and Data Security</i> (Vol. 13411, pp. 358–373). Grenada: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-18283-9_17\">https://doi.org/10.1007/978-3-031-18283-9_17</a>","ieee":"G. Avarikioti, K. Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. X. Yeo, “Hide &#38; Seek: Privacy-preserving rebalancing on payment channel networks,” in <i>Financial Cryptography and Data Security</i>, Grenada, 2022, vol. 13411, pp. 358–373.","chicago":"Avarikioti, Georgia, Krzysztof Z Pietrzak, Iosif Salem, Stefan Schmid, Samarth Tiwari, and Michelle X Yeo. “Hide &#38; Seek: Privacy-Preserving Rebalancing on Payment Channel Networks.” In <i>Financial Cryptography and Data Security</i>, 13411:358–73. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-031-18283-9_17\">https://doi.org/10.1007/978-3-031-18283-9_17</a>.","ama":"Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. Hide &#38; Seek: Privacy-preserving rebalancing on payment channel networks. In: <i>Financial Cryptography and Data Security</i>. Vol 13411. Springer Nature; 2022:358-373. doi:<a href=\"https://doi.org/10.1007/978-3-031-18283-9_17\">10.1007/978-3-031-18283-9_17</a>","mla":"Avarikioti, Georgia, et al. “Hide &#38; Seek: Privacy-Preserving Rebalancing on Payment Channel Networks.” <i>Financial Cryptography and Data Security</i>, vol. 13411, Springer Nature, 2022, pp. 358–73, doi:<a href=\"https://doi.org/10.1007/978-3-031-18283-9_17\">10.1007/978-3-031-18283-9_17</a>.","ista":"Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. 2022. Hide &#38; Seek: Privacy-preserving rebalancing on payment channel networks. Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13411, 358–373.","short":"G. Avarikioti, K.Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, M.X. Yeo, in:, Financial Cryptography and Data Security, Springer Nature, 2022, pp. 358–373."},"abstract":[{"text":"Payment channels effectively move the transaction load off-chain thereby successfully addressing the inherent scalability problem most cryptocurrencies face. A major drawback of payment channels is the need to “top up” funds on-chain when a channel is depleted. Rebalancing was proposed to alleviate this issue, where parties with depleting channels move their funds along a cycle to replenish their channels off-chain. Protocols for rebalancing so far either introduce local solutions or compromise privacy.\r\nIn this work, we present an opt-in rebalancing protocol that is both private and globally optimal, meaning our protocol maximizes the total amount of rebalanced funds. We study rebalancing from the framework of linear programming. To obtain full privacy guarantees, we leverage multi-party computation in solving the linear program, which is executed by selected participants to maintain efficiency. Finally, we efficiently decompose the rebalancing solution into incentive-compatible cycles which conserve user balances when executed atomically.","lang":"eng"}],"author":[{"id":"c20482a0-3b89-11eb-9862-88cf6404b88c","first_name":"Georgia","last_name":"Avarikioti","full_name":"Avarikioti, Georgia"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Salem, Iosif","last_name":"Salem","first_name":"Iosif"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"full_name":"Tiwari, Samarth","last_name":"Tiwari","first_name":"Samarth"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X"}],"arxiv":1,"date_updated":"2023-09-05T15:10:57Z","oa":1,"volume":13411,"article_processing_charge":"No","_id":"12167","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031182822"],"issn":["0302-9743"],"eisbn":["9783031182839"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Preprint","quality_controlled":"1","month":"10","date_published":"2022-10-22T00:00:00Z","publisher":"Springer Nature","scopus_import":"1","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"conference":{"start_date":"2022-05-02","end_date":"2022-05-06","name":"FC: Financial Cryptography and Data Security","location":"Grenada"},"date_created":"2023-01-12T12:10:38Z","day":"22","type":"conference","intvolume":"     13411","status":"public","publication":"Financial Cryptography and Data Security","page":"358-373"},{"status":"public","author":[{"id":"e499926b-f6e0-11ea-865d-9c63db0031e8","first_name":"Jonathan A","full_name":"Scott, Jonathan A","last_name":"Scott"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X"},{"first_name":"Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"text":"We present Cross-Client Label Propagation(XCLP), a new method for transductive federated learning. XCLP estimates a data graph jointly from the data of multiple clients and computes labels for the unlabeled data by propagating label information across the graph. To avoid clients having to share their data with anyone, XCLP employs two cryptographically secure protocols: secure Hamming distance computation and secure summation. We demonstrate two distinct applications of XCLP within federated learning. In the first, we use it in a one-shot way to predict labels for unseen test points. In the second, we use it to repeatedly pseudo-label unlabeled training data in a federated semi-supervised setting. Experiments on both real federated and standard benchmark datasets show that in both applications XCLP achieves higher classification accuracy than alternative approaches.","lang":"eng"}],"type":"preprint","citation":{"apa":"Scott, J. A., Yeo, M. X., &#38; Lampert, C. (n.d.). Cross-client Label Propagation for transductive federated learning. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2210.06434\">https://doi.org/10.48550/arXiv.2210.06434</a>","ieee":"J. A. Scott, M. X. Yeo, and C. Lampert, “Cross-client Label Propagation for transductive federated learning,” <i>arXiv</i>. .","chicago":"Scott, Jonathan A, Michelle X Yeo, and Christoph Lampert. “Cross-Client Label Propagation for Transductive Federated Learning.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2210.06434\">https://doi.org/10.48550/arXiv.2210.06434</a>.","mla":"Scott, Jonathan A., et al. “Cross-Client Label Propagation for Transductive Federated Learning.” <i>ArXiv</i>, 2210.06434, doi:<a href=\"https://doi.org/10.48550/arXiv.2210.06434\">10.48550/arXiv.2210.06434</a>.","ama":"Scott JA, Yeo MX, Lampert C. Cross-client Label Propagation for transductive federated learning. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2210.06434\">10.48550/arXiv.2210.06434</a>","ista":"Scott JA, Yeo MX, Lampert C. Cross-client Label Propagation for transductive federated learning. arXiv, 2210.06434.","short":"J.A. Scott, M.X. Yeo, C. Lampert, ArXiv (n.d.)."},"day":"12","publication_status":"submitted","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12660","file_date_updated":"2023-02-20T08:21:35Z","article_processing_charge":"No","date_updated":"2023-02-21T08:20:18Z","oa":1,"publication":"arXiv","arxiv":1,"language":[{"iso":"eng"}],"title":"Cross-client Label Propagation for transductive federated learning","external_id":{"arxiv":["2210.06434"]},"date_published":"2022-10-12T00:00:00Z","month":"10","doi":"10.48550/arXiv.2210.06434","year":"2022","ddc":["004"],"file":[{"date_created":"2023-02-20T08:21:35Z","checksum":"7ab20543fd4393f14fb857ce2e4f03c6","file_name":"2210.06434.pdf","file_size":291893,"date_updated":"2023-02-20T08:21:35Z","access_level":"open_access","success":1,"file_id":"12661","creator":"chl","content_type":"application/pdf","relation":"main_file"}],"date_created":"2023-02-20T08:21:50Z","article_number":"2210.06434","department":[{"_id":"ChLa"}],"has_accepted_license":"1","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"date_published":"2021-08-26T00:00:00Z","month":"08","language":[{"iso":"eng"}],"publisher":"IEEE","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"date_created":"2021-09-27T13:46:27Z","conference":{"location":"San Francisco, CA, United States","end_date":"2021-05-27","name":"SP: Symposium on Security and Privacy","start_date":"2021-05-24"},"type":"conference","day":"26","status":"public","page":"268-284","publication":"2021 IEEE Symposium on Security and Privacy ","ec_funded":1,"year":"2021","doi":"10.1109/sp40001.2021.00035","title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"}]},"citation":{"ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: <i>2021 IEEE Symposium on Security and Privacy </i>. IEEE; 2021:268-284. doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>.","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.","ieee":"K. Klein <i>et al.</i>, “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in <i>2021 IEEE Symposium on Security and Privacy </i>, San Francisco, CA, United States, 2021, pp. 268–284.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In <i>2021 IEEE Symposium on Security and Privacy </i>, 268–84. IEEE, 2021. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>."},"publication_status":"published","author":[{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","first_name":"Guillermo"},{"orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"first_name":"Margarita","last_name":"Capretto","full_name":"Capretto, Margarita"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","first_name":"Miguel"},{"id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia","full_name":"Markov, Ilia","last_name":"Markov"},{"first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Alwen","full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"abstract":[{"text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.","lang":"eng"}],"article_processing_charge":"No","oa":1,"date_updated":"2023-09-07T13:32:11Z","project":[{"grant_number":"665385","call_identifier":"H2020","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","quality_controlled":"1","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","_id":"10049"},{"date_published":"2021-11-04T00:00:00Z","month":"11","language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","department":[{"_id":"KrPi"}],"date_created":"2021-12-05T23:01:42Z","conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography Conference","end_date":"2021-11-11","start_date":"2021-11-08"},"type":"conference","day":"04","status":"public","intvolume":"     13043","page":"397-428","ec_funded":1,"doi":"10.1007/978-3-030-90453-1_14","year":"2021","title":"Trojan-resilience without cryptography","external_id":{"isi":["000728364000014"]},"isi":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1224"}],"alternative_title":["LNCS"],"publication_status":"published","citation":{"mla":"Chakraborty, Suvradip, et al. <i>Trojan-Resilience without Cryptography</i>. Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>.","ama":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>","ista":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. 2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference, LNCS, vol. 13043, 397–428.","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","ieee":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 397–428.","apa":"Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z., &#38; Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp. 397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,” 13043:397–428. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>."},"author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip","full_name":"Chakraborty, Suvradip","last_name":"Chakraborty"},{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"last_name":"Gałązka","full_name":"Gałązka, Małgorzata","first_name":"Małgorzata"},{"last_name":"Lizurej","full_name":"Lizurej, Tomasz","first_name":"Tomasz"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"},{"first_name":"Michelle X","last_name":"Yeo","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as “time bombs”) or on some particular input (known as “cheat codes”). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC) have been proposed. On a high level, to realize a circuit with specification   F  one has more sophisticated circuits   F⋄  manufactured (where   F⋄  specifies a MPC or VC of   F ), and then embeds these   F⋄ ’s into a master circuit which must be trusted but is relatively simple compared to   F . Those solutions impose a significant overhead as   F⋄  is much more complex than   F , also the master circuits are not exactly trivial. In this work, we show that in restricted settings, where   F  has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e.,   F=F⋄ ). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they’re all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to T inputs, the master circuit will catch Trojans that try to deviate on significantly more than a 1/T fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where 12 instantiations of   F  need to be embedded into the master. We also discuss an extremely simple construction with just 2 instantiations for which we conjecture that it already achieves the optimal bound."}],"oa":1,"volume":13043,"date_updated":"2023-08-14T13:07:46Z","article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","quality_controlled":"1","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815"}],"oa_version":"Preprint","_id":"10407","publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]}},{"date_published":"2021-05-11T00:00:00Z","month":"05","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer Nature","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"date_created":"2021-08-08T22:01:30Z","conference":{"start_date":"2021-05-17","location":"Virtual Event","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","end_date":"2021-05-20"},"type":"conference","day":"11","status":"public","intvolume":"     12704","page":"399-421","publication":"Topics in Cryptology – CT-RSA 2021","ec_funded":1,"doi":"10.1007/978-3-030-75539-3_17","year":"2021","title":"Inverse-Sybil attacks in automated contact tracing","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/670"}],"alternative_title":["LNCS"],"citation":{"ista":"Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference, LNCS, vol. 12704, 399–421.","short":"B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 399–421.","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: <i>Topics in Cryptology – CT-RSA 2021</i>. Vol 12704. Springer Nature; 2021:399-421. doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>","mla":"Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” <i>Topics in Cryptology – CT-RSA 2021</i>, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>.","chicago":"Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil Attacks in Automated Contact Tracing.” In <i>Topics in Cryptology – CT-RSA 2021</i>, 12704:399–421. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>.","ieee":"B. Auerbach <i>et al.</i>, “Inverse-Sybil attacks in automated contact tracing,” in <i>Topics in Cryptology – CT-RSA 2021</i>, Virtual Event, 2021, vol. 12704, pp. 399–421.","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., &#38; Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In <i>Topics in Cryptology – CT-RSA 2021</i> (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>"},"publication_status":"published","author":[{"orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","last_name":"Auerbach","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"},{"first_name":"Michelle X","last_name":"Yeo","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"text":"Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices.\r\n\r\nWe propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.","lang":"eng"}],"article_processing_charge":"No","oa":1,"date_updated":"2023-02-23T14:09:56Z","volume":12704,"quality_controlled":"1","oa_version":"Submitted Version","project":[{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","grant_number":"665385"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Guillermo Pascual-Perez and Michelle Yeo were funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie Grant Agreement No. 665385; the remaining contributors to this project have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","publication_identifier":{"issn":["03029743"],"isbn":["9783030755386"],"eissn":["16113349"]},"_id":"9826"},{"related_material":{"record":[{"status":"public","id":"14506","relation":"dissertation_contains"}]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2104.04293"}],"isi":1,"external_id":{"arxiv":["2104.04293"],"isi":["000853016800008"]},"title":"LightPIR: Privacy-preserving route discovery for payment channel networks","doi":"10.23919/IFIPNetworking52078.2021.9472205","year":"2021","ec_funded":1,"publication_identifier":{"eissn":["1861-2288"],"eisbn":["978-3-9031-7639-3"],"isbn":["978-1-6654-4501-6"]},"_id":"9969","quality_controlled":"1","oa_version":"Submitted Version","project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","arxiv":1,"article_processing_charge":"No","date_updated":"2023-11-30T10:54:50Z","oa":1,"abstract":[{"lang":"eng","text":"Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths."}],"author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"first_name":"Iosif","last_name":"Salem","full_name":"Salem, Iosif"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"citation":{"ieee":"K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving route discovery for payment channel networks,” presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.","apa":"Pietrzak, K. Z., Salem, I., Schmid, S., &#38; Yeo, M. X. (2021). LightPIR: Privacy-preserving route discovery for payment channel networks. Presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland: IEEE. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>","chicago":"Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo. “LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE, 2021. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>.","ama":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route discovery for payment channel networks. In: IEEE; 2021. doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>","mla":"Pietrzak, Krzysztof Z., et al. <i>LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks</i>. IEEE, 2021, doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>.","short":"K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.","ista":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving route discovery for payment channel networks. 2021 IFIP Networking Conference (IFIP Networking)."},"publication_status":"published","conference":{"start_date":"2021-06-21","location":"Espoo and Helsinki, Finland","name":"2021 IFIP Networking Conference (IFIP Networking)","end_date":"2021-06-24"},"date_created":"2021-08-29T22:01:16Z","department":[{"_id":"KrPi"}],"scopus_import":"1","publisher":"IEEE","language":[{"iso":"eng"}],"month":"06","date_published":"2021-06-21T00:00:00Z","status":"public","day":"21","type":"conference"}]