[{"date_created":"2022-05-08T22:01:44Z","citation":{"apa":"Bartocci, E., Ferrere, T., Henzinger, T. A., Nickovic, D., &#38; Da Costa, A. O. (2022). Information-flow interfaces. In <i>Fundamental Approaches to Software Engineering</i> (Vol. 13241, pp. 3–22). Munich, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-99429-7_1\">https://doi.org/10.1007/978-3-030-99429-7_1</a>","chicago":"Bartocci, Ezio, Thomas Ferrere, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira Da Costa. “Information-Flow Interfaces.” In <i>Fundamental Approaches to Software Engineering</i>, 13241:3–22. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-030-99429-7_1\">https://doi.org/10.1007/978-3-030-99429-7_1</a>.","mla":"Bartocci, Ezio, et al. “Information-Flow Interfaces.” <i>Fundamental Approaches to Software Engineering</i>, vol. 13241, Springer Nature, 2022, pp. 3–22, doi:<a href=\"https://doi.org/10.1007/978-3-030-99429-7_1\">10.1007/978-3-030-99429-7_1</a>.","ista":"Bartocci E, Ferrere T, Henzinger TA, Nickovic D, Da Costa AO. 2022. Information-flow interfaces. Fundamental Approaches to Software Engineering. FASE: Fundamental Approaches to Software Engineering, LNCS, vol. 13241, 3–22.","ieee":"E. Bartocci, T. Ferrere, T. A. Henzinger, D. Nickovic, and A. O. Da Costa, “Information-flow interfaces,” in <i>Fundamental Approaches to Software Engineering</i>, Munich, Germany, 2022, vol. 13241, pp. 3–22.","ama":"Bartocci E, Ferrere T, Henzinger TA, Nickovic D, Da Costa AO. Information-flow interfaces. In: <i>Fundamental Approaches to Software Engineering</i>. Vol 13241. Springer Nature; 2022:3-22. doi:<a href=\"https://doi.org/10.1007/978-3-030-99429-7_1\">10.1007/978-3-030-99429-7_1</a>","short":"E. Bartocci, T. Ferrere, T.A. Henzinger, D. Nickovic, A.O. Da Costa, in:, Fundamental Approaches to Software Engineering, Springer Nature, 2022, pp. 3–22."},"acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 956123 and was funded in part by the FWF project W1255-N23 and by the ERC-2020-AdG 101020093.","year":"2022","ec_funded":1,"file_date_updated":"2022-05-09T06:52:44Z","_id":"11355","doi":"10.1007/978-3-030-99429-7_1","publication_status":"published","external_id":{"isi":["000782393600001"]},"abstract":[{"text":"Contract-based design is a promising methodology for taming the complexity of developing sophisticated systems. A formal contract distinguishes between assumptions, which are constraints that the designer of a component puts on the environments in which the component can be used safely, and guarantees, which are promises that the designer asks from the team that implements the component. A theory of formal contracts can be formalized as an interface theory, which supports the composition and refinement of both assumptions and guarantees.\r\nAlthough there is a rich landscape of contract-based design methods that address functional and extra-functional properties, we present the first interface theory that is designed for ensuring system-wide security properties. Our framework provides a refinement relation and a composition operation that support both incremental design and independent implementability. We develop our theory for both stateless and stateful interfaces. We illustrate the applicability of our framework with an example inspired from the automotive domain.","lang":"eng"}],"ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"department":[{"_id":"ToHe"}],"page":"3-22","volume":13241,"quality_controlled":"1","publisher":"Springer Nature","date_published":"2022-03-29T00:00:00Z","title":"Information-flow interfaces","date_updated":"2023-08-03T07:03:40Z","oa":1,"article_processing_charge":"No","scopus_import":"1","has_accepted_license":"1","intvolume":"     13241","isi":1,"language":[{"iso":"eng"}],"publication":"Fundamental Approaches to Software Engineering","author":[{"first_name":"Ezio","full_name":"Bartocci, Ezio","last_name":"Bartocci"},{"first_name":"Thomas","full_name":"Ferrere, Thomas","orcid":"0000-0001-5199-3143","id":"40960E6E-F248-11E8-B48F-1D18A9856A87","last_name":"Ferrere"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"full_name":"Nickovic, Dejan","first_name":"Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","last_name":"Nickovic"},{"full_name":"Da Costa, Ana Oliveira","first_name":"Ana Oliveira","last_name":"Da Costa"}],"oa_version":"Published Version","day":"29","file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":479146,"file_name":"2022_LNCS_Bartocci.pdf","checksum":"7f6f860b20b8de2a249e9c1b4eee15cf","file_id":"11357","success":1,"date_updated":"2022-05-09T06:52:44Z","date_created":"2022-05-09T06:52:44Z"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"name":"FASE: Fundamental Approaches to Software Engineering","start_date":"2022-04-02","location":"Munich, Germany","end_date":"2022-04-07"},"publication_identifier":{"issn":["0302-9743"],"isbn":["9783030994280"],"eissn":["1611-3349"]},"month":"03","alternative_title":["LNCS"],"status":"public","type":"conference"},{"doi":"10.1007/978-3-031-06245-2","language":[{"iso":"eng"}],"_id":"11429","editor":[{"full_name":"Karimipour, Farid","first_name":"Farid","id":"2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425","last_name":"Karimipour","orcid":"0000-0001-6746-4174"},{"first_name":"Sabine","full_name":"Storandt, Sabine","last_name":"Storandt"}],"intvolume":"     13238","year":"2022","article_processing_charge":"No","date_updated":"2022-06-02T05:56:22Z","title":"Web and Wireless Geographical Information Systems","citation":{"apa":"Karimipour, F., &#38; Storandt, S. (Eds.). (2022). <i>Web and Wireless Geographical Information Systems</i> (1st ed., Vol. 13238). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-06245-2\">https://doi.org/10.1007/978-3-031-06245-2</a>","chicago":"Karimipour, Farid, and Sabine Storandt, eds. <i>Web and Wireless Geographical Information Systems</i>. 1st ed. Vol. 13238. Cham: Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-031-06245-2\">https://doi.org/10.1007/978-3-031-06245-2</a>.","mla":"Karimipour, Farid, and Sabine Storandt, editors. <i>Web and Wireless Geographical Information Systems</i>. 1st ed., vol. 13238, Springer Nature, 2022, doi:<a href=\"https://doi.org/10.1007/978-3-031-06245-2\">10.1007/978-3-031-06245-2</a>.","ista":"Karimipour F, Storandt S eds. 2022. Web and Wireless Geographical Information Systems 1st ed., Cham: Springer Nature, 153p.","short":"F. Karimipour, S. Storandt, eds., Web and Wireless Geographical Information Systems, 1st ed., Springer Nature, Cham, 2022.","ama":"Karimipour F, Storandt S, eds. <i>Web and Wireless Geographical Information Systems</i>. Vol 13238. 1st ed. Cham: Springer Nature; 2022. doi:<a href=\"https://doi.org/10.1007/978-3-031-06245-2\">10.1007/978-3-031-06245-2</a>","ieee":"F. Karimipour and S. Storandt, Eds., <i>Web and Wireless Geographical Information Systems</i>, 1st ed., vol. 13238. Cham: Springer Nature, 2022."},"date_created":"2022-06-02T05:40:53Z","date_published":"2022-05-01T00:00:00Z","type":"book_editor","status":"public","publisher":"Springer Nature","alternative_title":["LNCS"],"quality_controlled":"1","volume":13238,"department":[{"_id":"HeEd"}],"edition":"1","page":"153","month":"05","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031062445"],"eissn":["1611-3349"],"eisbn":["9783031062452"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"This book constitutes the refereed proceedings of the 18th International Symposium on Web and Wireless Geographical Information Systems, W2GIS 2022, held in Konstanz, Germany, in April 2022.\r\nThe 7 full papers presented together with 6 short papers in the volume were carefully reviewed and selected from 16 submissions.  The papers cover topics that range from mobile GIS and Location-Based Services to Spatial Information Retrieval and Wireless Sensor Networks.","lang":"eng"}],"oa_version":"None","day":"01","place":"Cham","publication_status":"published"},{"publisher":"Springer Nature","date_published":"2022-05-25T00:00:00Z","page":"815–844","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"volume":13276,"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"},{"call_identifier":"H2020","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385"}],"external_id":{"isi":["000832305300028"]},"abstract":[{"text":"Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can efficiently scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security.\r\n\r\nIn current proposals – most notably in TreeKEM (which is part of the IETF’s Messaging Layer Security (MLS) protocol draft) – for users in a group of size n to rotate their keys, they must each craft a message of size log(n) to be broadcast to the group using an (untrusted) delivery server.\r\n\r\nIn larger groups, having users sequentially rotate their keys requires too much bandwidth (or takes too long), so variants allowing any T≤n users to simultaneously rotate their keys in just 2 communication rounds have been suggested (e.g. “Propose and Commit” by MLS). Unfortunately, 2-round concurrent updates are either damaging or expensive (or both); i.e. they either result in future operations being more costly (e.g. via “blanking” or “tainting”) or are costly themselves requiring Ω(T) communication for each user [Bienstock et al., TCC’20].\r\n\r\nIn this paper we propose CoCoA; a new scheme that allows for T concurrent updates that are neither damaging nor costly. That is, they add no cost to future operations yet they only require Ω(log2(n)) communication per user. To circumvent the [Bienstock et al.] lower bound, CoCoA increases the number of rounds needed to complete all updates from 2 up to (at most) log(n); though typically fewer rounds are needed.\r\n\r\nThe key insight of our protocol is the following: in the (non-concurrent version of) TreeKEM, a delivery server which gets T concurrent update requests will approve one and reject the remaining T−1. In contrast, our server attempts to apply all of them. If more than one user requests to rotate the same key during a round, the server arbitrarily picks a winner. Surprisingly, we prove that regardless of how the server chooses the winners, all previously compromised users will recover after at most log(n) such update rounds.\r\n\r\nTo keep the communication complexity low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly forwards packets, but instead actively computes individualized packets tailored to each user. As the server is untrusted, this change requires us to develop new mechanisms ensuring robustness of the protocol.","lang":"eng"}],"place":"Cham","publication_status":"published","doi":"10.1007/978-3-031-07085-3_28","_id":"11476","ec_funded":1,"acknowledgement":"We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful feedback on an earlier draft of this paper.","year":"2022","date_created":"2022-06-30T16:48:00Z","citation":{"apa":"Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak, K. Z., &#38; Walter, M. (2022). CoCoA: Concurrent continuous group key agreement. In <i>Advances in Cryptology – EUROCRYPT 2022</i> (Vol. 13276, pp. 815–844). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-07085-3_28\">https://doi.org/10.1007/978-3-031-07085-3_28</a>","ista":"Alwen J, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2022. CoCoA: Concurrent continuous group key agreement. Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT: Annual International Conference on the Theory and Applications of Cryptology and Information Security, LNCS, vol. 13276, 815–844.","mla":"Alwen, Joël, et al. “CoCoA: Concurrent Continuous Group Key Agreement.” <i>Advances in Cryptology – EUROCRYPT 2022</i>, vol. 13276, Springer Nature, 2022, pp. 815–844, doi:<a href=\"https://doi.org/10.1007/978-3-031-07085-3_28\">10.1007/978-3-031-07085-3_28</a>.","chicago":"Alwen, Joël, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “CoCoA: Concurrent Continuous Group Key Agreement.” In <i>Advances in Cryptology – EUROCRYPT 2022</i>, 13276:815–844. Cham: Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-031-07085-3_28\">https://doi.org/10.1007/978-3-031-07085-3_28</a>.","ieee":"J. Alwen <i>et al.</i>, “CoCoA: Concurrent continuous group key agreement,” in <i>Advances in Cryptology – EUROCRYPT 2022</i>, Trondheim, Norway, 2022, vol. 13276, pp. 815–844.","ama":"Alwen J, Auerbach B, Cueto Noval M, et al. CoCoA: Concurrent continuous group key agreement. In: <i>Advances in Cryptology – EUROCRYPT 2022</i>. Vol 13276. Cham: Springer Nature; 2022:815–844. doi:<a href=\"https://doi.org/10.1007/978-3-031-07085-3_28\">10.1007/978-3-031-07085-3_28</a>","short":"J. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2022, Springer Nature, Cham, 2022, pp. 815–844."},"alternative_title":["LNCS"],"status":"public","type":"conference","conference":{"location":"Trondheim, Norway","end_date":"2022-06-03","name":"EUROCRYPT: Annual International Conference on the Theory and Applications of Cryptology and Information Security","start_date":"2022-05-30"},"publication_identifier":{"issn":["0302-9743"],"isbn":["9783031070846"],"eissn":["1611-3349"],"eisbn":["9783031070853"]},"month":"05","day":"25","main_file_link":[{"url":"https://eprint.iacr.org/2022/251","open_access":"1"}],"oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"last_name":"Alwen","full_name":"Alwen, Joël","first_name":"Joël"},{"last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","first_name":"Benedikt"},{"first_name":"Miguel","full_name":"Cueto Noval, Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval"},{"full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Walter","full_name":"Walter, Michael","first_name":"Michael"}],"publication":"Advances in Cryptology – EUROCRYPT 2022","language":[{"iso":"eng"}],"isi":1,"scopus_import":"1","intvolume":"     13276","oa":1,"date_updated":"2023-08-03T07:25:02Z","article_processing_charge":"No","title":"CoCoA: Concurrent continuous group key agreement"},{"external_id":{"isi":["000876977400001"],"arxiv":["2102.08703"]},"abstract":[{"lang":"eng","text":"In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs the structure is much more diverse."}],"series_title":"LNCS","publication_status":"published","department":[{"_id":"DaAl"}],"page":"1-20","volume":13298,"quality_controlled":"1","publisher":"Springer Nature","date_published":"2022-06-25T00:00:00Z","project":[{"name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"date_created":"2022-07-31T22:01:49Z","citation":{"short":"A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:, M. Parter (Ed.), International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2022, pp. 1–20.","ama":"Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending. In: Parter M, ed. <i>International Colloquium on Structural Information and Communication Complexity</i>. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:<a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">10.1007/978-3-031-09993-9_1</a>","ieee":"A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela, “Local mending,” in <i>International Colloquium on Structural Information and Communication Complexity</i>, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.","ista":"Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local mending. International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol. 13298, 1–20.","chicago":"Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. “Local Mending.” In <i>International Colloquium on Structural Information and Communication Complexity</i>, edited by Merav Parter, 13298:1–20. LNCS. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">https://doi.org/10.1007/978-3-031-09993-9_1</a>.","mla":"Balliu, Alkida, et al. “Local Mending.” <i>International Colloquium on Structural Information and Communication Complexity</i>, edited by Merav Parter, vol. 13298, Springer Nature, 2022, pp. 1–20, doi:<a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">10.1007/978-3-031-09993-9_1</a>.","apa":"Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., &#38; Suomela, J. (2022). Local mending. In M. Parter (Ed.), <i>International Colloquium on Structural Information and Communication Complexity</i> (Vol. 13298, pp. 1–20). Paderborn, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-09993-9_1\">https://doi.org/10.1007/978-3-031-09993-9_1</a>"},"acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605. This work was supported in part by the Academy of Finland, Grants 314888 and 333837. The authors would also like to thank David Harris, Neven Villani, and the anonymous reviewers for their very helpful comments and feedback on previous versions of this work.","year":"2022","doi":"10.1007/978-3-031-09993-9_1","_id":"11707","day":"25","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.08703"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"name":"SIROCCO: Structural Information and Communication Complexity","start_date":"2022-06-27","location":"Paderborn, Germany","end_date":"2022-06-29"},"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031099922"],"issn":["0302-9743"]},"month":"06","author":[{"first_name":"Alkida","full_name":"Balliu, Alkida","last_name":"Balliu"},{"last_name":"Hirvonen","full_name":"Hirvonen, Juho","first_name":"Juho"},{"full_name":"Melnyk, Darya","first_name":"Darya","last_name":"Melnyk"},{"last_name":"Olivetti","first_name":"Dennis","full_name":"Olivetti, Dennis"},{"orcid":"0000-0002-6432-6646","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","full_name":"Rybicki, Joel"},{"full_name":"Suomela, Jukka","first_name":"Jukka","last_name":"Suomela"}],"arxiv":1,"type":"conference","status":"public","scopus_import":"1","intvolume":"     13298","isi":1,"editor":[{"full_name":"Parter, Merav","first_name":"Merav","last_name":"Parter"}],"title":"Local mending","oa":1,"date_updated":"2023-08-03T12:16:29Z","article_processing_charge":"No","publication":"International Colloquium on Structural Information and Communication Complexity","language":[{"iso":"eng"}]},{"file_date_updated":"2022-08-29T09:17:01Z","_id":"12000","doi":"10.1007/978-3-031-13185-1_4","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt), the HKUST-Kaisa Joint Research Institute Project Grant HKJRI3A-055, the HKUST Startup Grant R9272 and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.","year":"2022","date_created":"2022-08-28T22:02:02Z","citation":{"mla":"Chatterjee, Krishnendu, et al. “Sound and Complete Certificates for Auantitative Termination Analysis of Probabilistic Programs.” <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, vol. 13371, Springer, 2022, pp. 55–78, doi:<a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">10.1007/978-3-031-13185-1_4</a>.","ista":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. 2022. Sound and complete certificates for auantitative termination analysis of probabilistic programs. Proceedings of the 34th International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13371, 55–78.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Tobias Meggendorfer, and Dorde Zikelic. “Sound and Complete Certificates for Auantitative Termination Analysis of Probabilistic Programs.” In <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, 13371:55–78. Springer, 2022. <a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">https://doi.org/10.1007/978-3-031-13185-1_4</a>.","ama":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. Sound and complete certificates for auantitative termination analysis of probabilistic programs. In: <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>. Vol 13371. Springer; 2022:55-78. doi:<a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">10.1007/978-3-031-13185-1_4</a>","ieee":"K. Chatterjee, A. K. Goharshady, T. Meggendorfer, and D. Zikelic, “Sound and complete certificates for auantitative termination analysis of probabilistic programs,” in <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, Haifa, Israel, 2022, vol. 13371, pp. 55–78.","short":"K. Chatterjee, A.K. Goharshady, T. Meggendorfer, D. Zikelic, in:, Proceedings of the 34th International Conference on Computer Aided Verification, Springer, 2022, pp. 55–78.","apa":"Chatterjee, K., Goharshady, A. K., Meggendorfer, T., &#38; Zikelic, D. (2022). Sound and complete certificates for auantitative termination analysis of probabilistic programs. In <i>Proceedings of the 34th International Conference on Computer Aided Verification</i> (Vol. 13371, pp. 55–78). Haifa, Israel: Springer. <a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">https://doi.org/10.1007/978-3-031-13185-1_4</a>"},"ec_funded":1,"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"14539"}]},"project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"publisher":"Springer","date_published":"2022-08-07T00:00:00Z","department":[{"_id":"KrCh"}],"page":"55-78","quality_controlled":"1","volume":13371,"publication_status":"published","ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"isi":["000870304500004"]},"abstract":[{"text":"We consider the quantitative problem of obtaining lower-bounds on the probability of termination of a given non-deterministic probabilistic program. Specifically, given a non-termination threshold p∈[0,1], we aim for certificates proving that the program terminates with probability at least 1−p. The basic idea of our approach is to find a terminating stochastic invariant, i.e. a subset SI of program states such that (i) the probability of the program ever leaving SI is no more than p, and (ii) almost-surely, the program either leaves SI or terminates.\r\n\r\nWhile stochastic invariants are already well-known, we provide the first proof that the idea above is not only sound, but also complete for quantitative termination analysis. We then introduce a novel sound and complete characterization of stochastic invariants that enables template-based approaches for easy synthesis of quantitative termination certificates, especially in affine or polynomial forms. Finally, by combining this idea with the existing martingale-based methods that are relatively complete for qualitative termination analysis, we obtain the first automated, sound, and relatively complete algorithm for quantitative termination analysis. Notably, our completeness guarantees for quantitative termination analysis are as strong as the best-known methods for the qualitative variant.\r\n\r\nOur prototype implementation demonstrates the effectiveness of our approach on various probabilistic programs. We also demonstrate that our algorithm certifies lower bounds on termination probability for probabilistic programs that are beyond the reach of previous methods.","lang":"eng"}],"language":[{"iso":"eng"}],"publication":"Proceedings of the 34th International Conference on Computer Aided Verification","date_updated":"2025-07-14T09:09:58Z","oa":1,"article_processing_charge":"Yes (in subscription journal)","title":"Sound and complete certificates for auantitative termination analysis of probabilistic programs","isi":1,"scopus_import":"1","intvolume":"     13371","has_accepted_license":"1","alternative_title":["LNCS"],"status":"public","type":"conference","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar","orcid":"0000-0003-1702-6584","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Meggendorfer, Tobias","first_name":"Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","orcid":"0000-0002-1712-2165"},{"first_name":"Dorde","full_name":"Zikelic, Dorde","last_name":"Zikelic","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699"}],"conference":{"end_date":"2022-08-10","location":"Haifa, Israel","start_date":"2022-08-07","name":"CAV: Computer Aided Verification"},"month":"08","publication_identifier":{"isbn":["9783031131844"],"eissn":["1611-3349"],"issn":["0302-9743"]},"day":"07","oa_version":"Published Version","file":[{"date_created":"2022-08-29T09:17:01Z","date_updated":"2022-08-29T09:17:01Z","success":1,"checksum":"24e0f810ec52735a90ade95198bc641d","file_name":"2022_LNCS_Chatterjee.pdf","file_id":"12003","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_size":505094,"creator":"alisjak"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"date_published":"2021-03-21T00:00:00Z","publisher":"Springer Nature","quality_controlled":"1","volume":12651,"page":"20-37","department":[{"_id":"KrCh"}],"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"abstract":[{"lang":"eng","text":"Several problems in planning and reactive synthesis can be reduced to the analysis of two-player quantitative graph games. Optimization is one form of analysis. We argue that in many cases it may be better to replace the optimization problem with the satisficing problem, where instead of searching for optimal solutions, the goal is to search for solutions that adhere to a given threshold bound.\r\nThis work defines and investigates the satisficing problem on a two-player graph game with the discounted-sum cost model. We show that while the satisficing problem can be solved using numerical methods just like the optimization problem, this approach does not render compelling benefits over optimization. When the discount factor is, however, an integer, we present another approach to satisficing, which is purely based on automata methods. We show that this approach is algorithmically more performant – both theoretically and empirically – and demonstrates the broader applicability of satisficing over optimization."}],"external_id":{"arxiv":["2101.02594"]},"publication_status":"published","doi":"10.1007/978-3-030-72016-2","_id":"12767","file_date_updated":"2023-03-28T11:00:33Z","ec_funded":1,"year":"2021","acknowledgement":"We thank anonymous reviewers for valuable inputs. This work is supported in part by NSF grant 2030859 to the CRA for the CIFellows Project, NSF grants IIS-1527668, CCF-1704883, IIS-1830549, the ERC CoG 863818 (ForM-SMArt), and an award from the Maryland Procurement Office.","date_created":"2023-03-26T22:01:09Z","citation":{"apa":"Bansal, S., Chatterjee, K., &#38; Vardi, M. Y. (2021). On satisficing in quantitative games. In <i>27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 12651, pp. 20–37). Luxembourg City, Luxembourg: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-72016-2\">https://doi.org/10.1007/978-3-030-72016-2</a>","short":"S. Bansal, K. Chatterjee, M.Y. Vardi, in:, 27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2021, pp. 20–37.","ieee":"S. Bansal, K. Chatterjee, and M. Y. Vardi, “On satisficing in quantitative games,” in <i>27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Luxembourg City, Luxembourg, 2021, vol. 12651, pp. 20–37.","ama":"Bansal S, Chatterjee K, Vardi MY. On satisficing in quantitative games. In: <i>27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 12651. Springer Nature; 2021:20-37. doi:<a href=\"https://doi.org/10.1007/978-3-030-72016-2\">10.1007/978-3-030-72016-2</a>","mla":"Bansal, Suguman, et al. “On Satisficing in Quantitative Games.” <i>27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 12651, Springer Nature, 2021, pp. 20–37, doi:<a href=\"https://doi.org/10.1007/978-3-030-72016-2\">10.1007/978-3-030-72016-2</a>.","ista":"Bansal S, Chatterjee K, Vardi MY. 2021. On satisficing in quantitative games. 27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 12651, 20–37.","chicago":"Bansal, Suguman, Krishnendu Chatterjee, and Moshe Y. Vardi. “On Satisficing in Quantitative Games.” In <i>27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 12651:20–37. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-72016-2\">https://doi.org/10.1007/978-3-030-72016-2</a>."},"status":"public","type":"conference","alternative_title":["LNCS"],"month":"03","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030720155"],"eissn":["1611-3349"]},"conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2021-03-27","location":"Luxembourg City, Luxembourg","end_date":"2021-04-01"},"file":[{"date_updated":"2023-03-28T11:00:33Z","date_created":"2023-03-28T11:00:33Z","checksum":"b020b78b23587ce7610b1aafb4e63438","file_id":"12777","file_name":"2021_LNCS_Bansal.pdf","success":1,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_size":747418,"creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"21","arxiv":1,"author":[{"last_name":"Bansal","full_name":"Bansal, Suguman","first_name":"Suguman"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Vardi","full_name":"Vardi, Moshe Y.","first_name":"Moshe Y."}],"publication":"27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","language":[{"iso":"eng"}],"intvolume":"     12651","has_accepted_license":"1","scopus_import":"1","article_processing_charge":"No","date_updated":"2025-07-14T09:09:51Z","oa":1,"title":"On satisficing in quantitative games"},{"has_accepted_license":"1","intvolume":"     12544","scopus_import":"1","title":"Does SGD implicitly optimize for smoothness?","article_processing_charge":"No","oa":1,"date_updated":"2022-08-12T07:28:47Z","publication":"42nd German Conference on Pattern Recognition","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_size":420234,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2022-08-12T07:27:58Z","date_updated":"2022-08-12T07:27:58Z","success":1,"checksum":"3e3628ab1cf658d82524963f808004ea","file_id":"11820","file_name":"2020_GCPR_submitted_Volhejn.pdf"}],"oa_version":"Submitted Version","day":"17","month":"03","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030712778"],"issn":["0302-9743"]},"conference":{"start_date":"2020-09-28","name":"DAGM GCPR: German Conference on Pattern Recognition ","end_date":"2020-10-01","location":"Tübingen, Germany"},"author":[{"id":"d5235fb4-7a6d-11eb-b254-f25d12d631a8","last_name":"Volhejn","full_name":"Volhejn, Vaclav","first_name":"Vaclav"},{"last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","first_name":"Christoph"}],"type":"conference","status":"public","date_created":"2021-03-01T09:01:16Z","citation":{"short":"V. Volhejn, C. Lampert, in:, 42nd German Conference on Pattern Recognition, Springer, 2021, pp. 246–259.","ieee":"V. Volhejn and C. Lampert, “Does SGD implicitly optimize for smoothness?,” in <i>42nd German Conference on Pattern Recognition</i>, Tübingen, Germany, 2021, vol. 12544, pp. 246–259.","ama":"Volhejn V, Lampert C. Does SGD implicitly optimize for smoothness? In: <i>42nd German Conference on Pattern Recognition</i>. Vol 12544. LNCS. Springer; 2021:246-259. doi:<a href=\"https://doi.org/10.1007/978-3-030-71278-5_18\">10.1007/978-3-030-71278-5_18</a>","mla":"Volhejn, Vaclav, and Christoph Lampert. “Does SGD Implicitly Optimize for Smoothness?” <i>42nd German Conference on Pattern Recognition</i>, vol. 12544, Springer, 2021, pp. 246–59, doi:<a href=\"https://doi.org/10.1007/978-3-030-71278-5_18\">10.1007/978-3-030-71278-5_18</a>.","chicago":"Volhejn, Vaclav, and Christoph Lampert. “Does SGD Implicitly Optimize for Smoothness?” In <i>42nd German Conference on Pattern Recognition</i>, 12544:246–59. LNCS. Springer, 2021. <a href=\"https://doi.org/10.1007/978-3-030-71278-5_18\">https://doi.org/10.1007/978-3-030-71278-5_18</a>.","ista":"Volhejn V, Lampert C. 2021. Does SGD implicitly optimize for smoothness? 42nd German Conference on Pattern Recognition. DAGM GCPR: German Conference on Pattern Recognition LNCS vol. 12544, 246–259.","apa":"Volhejn, V., &#38; Lampert, C. (2021). Does SGD implicitly optimize for smoothness? In <i>42nd German Conference on Pattern Recognition</i> (Vol. 12544, pp. 246–259). Tübingen, Germany: Springer. <a href=\"https://doi.org/10.1007/978-3-030-71278-5_18\">https://doi.org/10.1007/978-3-030-71278-5_18</a>"},"year":"2021","doi":"10.1007/978-3-030-71278-5_18","_id":"9210","file_date_updated":"2022-08-12T07:27:58Z","abstract":[{"text":"Modern neural networks can easily fit their training set perfectly. Surprisingly, despite being “overfit” in this way, they tend to generalize well to future data, thereby defying the classic bias–variance trade-off of machine learning theory. Of the many possible explanations, a prevalent one is that training by stochastic gradient descent (SGD) imposes an implicit bias that leads it to learn simple functions, and these simple functions generalize well. However, the specifics of this implicit bias are not well understood.\r\nIn this work, we explore the smoothness conjecture which states that SGD is implicitly biased towards learning functions that are smooth. We propose several measures to formalize the intuitive notion of smoothness, and we conduct experiments to determine whether SGD indeed implicitly optimizes for these measures. Our findings rule out the possibility that smoothness measures based on first-order derivatives are being implicitly enforced. They are supportive, though, of the smoothness conjecture for measures based on second-order derivatives.","lang":"eng"}],"series_title":"LNCS","ddc":["510"],"publication_status":"published","quality_controlled":"1","volume":12544,"page":"246-259","department":[{"_id":"ChLa"}],"date_published":"2021-03-17T00:00:00Z","publisher":"Springer"},{"date_published":"2021-01-28T00:00:00Z","type":"conference","status":"public","alternative_title":["LNCS"],"publisher":"Springer Nature","volume":12601,"quality_controlled":"1","page":"346-358","department":[{"_id":"VlKo"}],"month":"01","publication_identifier":{"isbn":["9783030678982"],"eissn":["1611-3349"],"issn":["0302-9743"]},"conference":{"name":"CALDAM: Conference on Algorithms and Discrete Applied Mathematics","start_date":"2021-02-11","location":"Rupnagar, India","end_date":"2021-02-13"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"In the multiway cut problem we are given a weighted undirected graph   G=(V,E)  and a set   T⊆V  of k terminals. The goal is to find a minimum weight set of edges   E′⊆E  with the property that by removing   E′  from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio   2−2k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem.","lang":"eng"}],"day":"28","oa_version":"None","author":[{"first_name":"Andrew","full_name":"Bloch-Hansen, Andrew","last_name":"Bloch-Hansen"},{"last_name":"Samei","id":"C1531CAE-36E9-11EA-845F-33AA3DDC885E","full_name":"Samei, Nasim","first_name":"Nasim"},{"full_name":"Solis-Oba, Roberto","first_name":"Roberto","last_name":"Solis-Oba"}],"publication_status":"published","publication":"Conference on Algorithms and Discrete Applied Mathematics","doi":"10.1007/978-3-030-67899-9_28","_id":"9227","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"     12601","article_processing_charge":"No","year":"2021","date_updated":"2023-10-10T09:29:08Z","citation":{"ista":"Bloch-Hansen A, Samei N, Solis-Oba R. 2021. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. Conference on Algorithms and Discrete Applied Mathematics. CALDAM: Conference on Algorithms and Discrete Applied Mathematics, LNCS, vol. 12601, 346–358.","chicago":"Bloch-Hansen, Andrew, Nasim Samei, and Roberto Solis-Oba. “Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.” In <i>Conference on Algorithms and Discrete Applied Mathematics</i>, 12601:346–58. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-67899-9_28\">https://doi.org/10.1007/978-3-030-67899-9_28</a>.","mla":"Bloch-Hansen, Andrew, et al. “Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.” <i>Conference on Algorithms and Discrete Applied Mathematics</i>, vol. 12601, Springer Nature, 2021, pp. 346–58, doi:<a href=\"https://doi.org/10.1007/978-3-030-67899-9_28\">10.1007/978-3-030-67899-9_28</a>.","short":"A. Bloch-Hansen, N. Samei, R. Solis-Oba, in:, Conference on Algorithms and Discrete Applied Mathematics, Springer Nature, 2021, pp. 346–358.","ieee":"A. Bloch-Hansen, N. Samei, and R. Solis-Oba, “Experimental evaluation of a local search approximation algorithm for the multiway cut problem,” in <i>Conference on Algorithms and Discrete Applied Mathematics</i>, Rupnagar, India, 2021, vol. 12601, pp. 346–358.","ama":"Bloch-Hansen A, Samei N, Solis-Oba R. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In: <i>Conference on Algorithms and Discrete Applied Mathematics</i>. Vol 12601. Springer Nature; 2021:346-358. doi:<a href=\"https://doi.org/10.1007/978-3-030-67899-9_28\">10.1007/978-3-030-67899-9_28</a>","apa":"Bloch-Hansen, A., Samei, N., &#38; Solis-Oba, R. (2021). Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In <i>Conference on Algorithms and Discrete Applied Mathematics</i> (Vol. 12601, pp. 346–358). Rupnagar, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-67899-9_28\">https://doi.org/10.1007/978-3-030-67899-9_28</a>"},"title":"Experimental evaluation of a local search approximation algorithm for the multiway cut problem","date_created":"2021-03-07T23:01:25Z"},{"publication":"41st Annual International Cryptology Conference, Part II ","language":[{"iso":"eng"}],"intvolume":"     12826","oa":1,"date_updated":"2023-09-07T13:32:11Z","article_processing_charge":"No","title":"Limits on the Adaptive Security of Yao’s Garbling","alternative_title":["LCNS"],"type":"conference","status":"public","conference":{"name":"CRYPTO: Annual International Cryptology Conference","start_date":"2021-08-16","location":"Virtual","end_date":"2021-08-20"},"month":"08","publication_identifier":{"isbn":["978-3-030-84244-4"],"eissn":["1611-3349"],"eisbn":["978-3-030-84245-1"],"issn":["0302-9743"]},"main_file_link":[{"url":"https://eprint.iacr.org/2021/945","open_access":"1"}],"day":"11","oa_version":"Preprint","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"last_name":"Wichs","first_name":"Daniel","full_name":"Wichs, Daniel"}],"doi":"10.1007/978-3-030-84245-1_17","_id":"10041","ec_funded":1,"related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"}]},"acknowledgement":"We would like to thank the anonymous reviewers of Crypto’21 whose detailed comments helped us considerably improve the presentation of the paper.","year":"2021","date_created":"2021-09-23T14:06:15Z","citation":{"apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Wichs, D. (2021). Limits on the Adaptive Security of Yao’s Garbling. In <i>41st Annual International Cryptology Conference, Part II </i> (Vol. 12826, pp. 486–515). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the Adaptive Security of Yao’s Garbling,” in <i>41st Annual International Cryptology Conference, Part II </i>, Virtual, 2021, vol. 12826, pp. 486–515.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security of Yao’s Garbling. In: <i>41st Annual International Cryptology Conference, Part II </i>. Vol 12826. Cham: Springer Nature; 2021:486-515. doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.","mla":"Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.” <i>41st Annual International Cryptology Conference, Part II </i>, vol. 12826, Springer Nature, 2021, pp. 486–515, doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In <i>41st Annual International Cryptology Conference, Part II </i>, 12826:486–515. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>."},"publisher":"Springer Nature","date_published":"2021-08-11T00:00:00Z","department":[{"_id":"KrPi"}],"page":"486-515","volume":12826,"quality_controlled":"1","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"abstract":[{"lang":"eng","text":"Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth   δ , the loss in security is at most exponential in   δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth  δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in   δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security."}],"place":"Cham","publication_status":"published"},{"publication_status":"published","abstract":[{"text":"We present a novel approach for blockchain asset owners to reclaim their funds in case of accidental private-key loss or transfer to a mistyped address. Our solution can be deployed upon failure or absence of proactively implemented backup mechanisms, such as secret sharing and cold storage. The main advantages against previous proposals is it does not require any prior action from users and works with both single-key and multi-sig accounts. We achieve this by a 3-phase   Commit()→Reveal()→Claim()−or−Challenge()  smart contract that enables accessing funds of addresses for which the spending key is not available. We provide an analysis of the threat and incentive models and formalize the concept of reactive KEy-Loss Protection (KELP).","lang":"eng"}],"external_id":{"isi":["000713005000034"]},"date_published":"2021-09-17T00:00:00Z","publisher":"Springer Nature","quality_controlled":"1","volume":"12676 ","page":"431-450","department":[{"_id":"ElKo"}],"year":"2021","acknowledgement":"The authors would like to thank all anonymous reviewers of FC21 WTSC workshop for comments and suggestions that greatly improved the quality of this paper.","citation":{"ama":"Blackshear S, Chalkias K, Chatzigiannis P, et al. Reactive key-loss protection in blockchains. In: <i>FC 2021 Workshops</i>. Vol 12676. Springer Nature; 2021:431-450. doi:<a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">10.1007/978-3-662-63958-0_34</a>","ieee":"S. Blackshear <i>et al.</i>, “Reactive key-loss protection in blockchains,” in <i>FC 2021 Workshops</i>, Virtual, 2021, vol. 12676, pp. 431–450.","short":"S. Blackshear, K. Chalkias, P. Chatzigiannis, R. Faizullabhoy, I. Khaburzaniya, E. Kokoris Kogias, J. Lind, D. Wong, T. Zakian, in:, FC 2021 Workshops, Springer Nature, 2021, pp. 431–450.","mla":"Blackshear, Sam, et al. “Reactive Key-Loss Protection in Blockchains.” <i>FC 2021 Workshops</i>, vol. 12676, Springer Nature, 2021, pp. 431–50, doi:<a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">10.1007/978-3-662-63958-0_34</a>.","chicago":"Blackshear, Sam, Konstantinos Chalkias, Panagiotis Chatzigiannis, Riyaz Faizullabhoy, Irakliy Khaburzaniya, Eleftherios Kokoris Kogias, Joshua Lind, David Wong, and Tim Zakian. “Reactive Key-Loss Protection in Blockchains.” In <i>FC 2021 Workshops</i>, 12676:431–50. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">https://doi.org/10.1007/978-3-662-63958-0_34</a>.","ista":"Blackshear S, Chalkias K, Chatzigiannis P, Faizullabhoy R, Khaburzaniya I, Kokoris Kogias E, Lind J, Wong D, Zakian T. 2021. Reactive key-loss protection in blockchains. FC 2021 Workshops. FC: International Conference on Financial Cryptography and Data Security, LNCS, vol. 12676, 431–450.","apa":"Blackshear, S., Chalkias, K., Chatzigiannis, P., Faizullabhoy, R., Khaburzaniya, I., Kokoris Kogias, E., … Zakian, T. (2021). Reactive key-loss protection in blockchains. In <i>FC 2021 Workshops</i> (Vol. 12676, pp. 431–450). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">https://doi.org/10.1007/978-3-662-63958-0_34</a>"},"date_created":"2021-10-03T22:01:24Z","_id":"10076","doi":"10.1007/978-3-662-63958-0_34","author":[{"first_name":"Sam","full_name":"Blackshear, Sam","last_name":"Blackshear"},{"last_name":"Chalkias","first_name":"Konstantinos","full_name":"Chalkias, Konstantinos"},{"last_name":"Chatzigiannis","first_name":"Panagiotis","full_name":"Chatzigiannis, Panagiotis"},{"first_name":"Riyaz","full_name":"Faizullabhoy, Riyaz","last_name":"Faizullabhoy"},{"last_name":"Khaburzaniya","full_name":"Khaburzaniya, Irakliy","first_name":"Irakliy"},{"last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios"},{"last_name":"Lind","first_name":"Joshua","full_name":"Lind, Joshua"},{"first_name":"David","full_name":"Wong, David","last_name":"Wong"},{"last_name":"Zakian","full_name":"Zakian, Tim","first_name":"Tim"}],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-662-63958-0"],"isbn":["978-3-6626-3957-3"]},"month":"09","conference":{"location":"Virtual","end_date":"2021-03-05","name":"FC: International Conference on Financial Cryptography and Data Security","start_date":"2021-03-01"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","day":"17","main_file_link":[{"open_access":"1","url":"https://research.fb.com/publications/reactive-key-loss-protection-in-blockchains/"}],"status":"public","type":"conference","alternative_title":["LNCS"],"article_processing_charge":"No","date_updated":"2023-08-14T07:06:16Z","oa":1,"title":"Reactive key-loss protection in blockchains","isi":1,"scopus_import":"1","language":[{"iso":"eng"}],"publication":"FC 2021 Workshops"},{"doi":"10.1007/978-3-030-88494-9_12","_id":"10108","file_date_updated":"2021-10-07T23:32:18Z","related_material":{"record":[{"status":"public","id":"9946","relation":"extended_version"}]},"keyword":["run-time verification","software engineering","implicit specification"],"citation":{"apa":"Mühlböck, F., &#38; Henzinger, T. A. (2021). Differential monitoring. In <i>International Conference on Runtime Verification</i> (Vol. 12974, pp. 231–243). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-88494-9_12\">https://doi.org/10.1007/978-3-030-88494-9_12</a>","mla":"Mühlböck, Fabian, and Thomas A. Henzinger. “Differential Monitoring.” <i>International Conference on Runtime Verification</i>, vol. 12974, Springer Nature, 2021, pp. 231–43, doi:<a href=\"https://doi.org/10.1007/978-3-030-88494-9_12\">10.1007/978-3-030-88494-9_12</a>.","chicago":"Mühlböck, Fabian, and Thomas A Henzinger. “Differential Monitoring.” In <i>International Conference on Runtime Verification</i>, 12974:231–43. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-88494-9_12\">https://doi.org/10.1007/978-3-030-88494-9_12</a>.","ista":"Mühlböck F, Henzinger TA. 2021. Differential monitoring. International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 12974, 231–243.","ieee":"F. Mühlböck and T. A. Henzinger, “Differential monitoring,” in <i>International Conference on Runtime Verification</i>, Virtual, 2021, vol. 12974, pp. 231–243.","ama":"Mühlböck F, Henzinger TA. Differential monitoring. In: <i>International Conference on Runtime Verification</i>. Vol 12974. Cham: Springer Nature; 2021:231-243. doi:<a href=\"https://doi.org/10.1007/978-3-030-88494-9_12\">10.1007/978-3-030-88494-9_12</a>","short":"F. Mühlböck, T.A. Henzinger, in:, International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 231–243."},"date_created":"2021-10-07T23:30:10Z","year":"2021","acknowledgement":"The authors would like to thank Borzoo Bonakdarpour, Derek Dreyer, Adrian Francalanza, Owolabi Legunsen, Mae Milano, Manuel Rigger, Cesar Sanchez, and the members of the IST Verification Seminar for their helpful comments and insights on various stages of this work, as well as the reviewers of RV’21 for their helpful suggestions on the actual paper.","volume":12974,"quality_controlled":"1","page":"231-243","department":[{"_id":"ToHe"}],"date_published":"2021-10-06T00:00:00Z","publisher":"Springer Nature","project":[{"call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"abstract":[{"lang":"eng","text":"We argue that the time is ripe to investigate differential monitoring, in which the specification of a program's behavior is implicitly given by a second program implementing the same informal specification. Similar ideas have been proposed before, and are currently implemented in restricted form for testing and specialized run-time analyses, aspects of which we combine. We discuss the challenges of implementing differential monitoring as a general-purpose, black-box run-time monitoring framework, and present promising results of a preliminary implementation, showing low monitoring overheads for diverse programs."}],"external_id":{"isi":["000719383800012"]},"ddc":["005"],"publication_status":"published","place":"Cham","publication":"International Conference on Runtime Verification","language":[{"iso":"eng"}],"has_accepted_license":"1","intvolume":"     12974","scopus_import":"1","isi":1,"title":"Differential monitoring","article_processing_charge":"No","oa":1,"date_updated":"2023-08-14T07:20:30Z","type":"conference","status":"public","alternative_title":["LNCS"],"file":[{"file_name":"differentialmonitoring-cameraready-openaccess.pdf","checksum":"554c7fdb259eda703a8b6328a6dad55a","file_id":"10109","success":1,"date_updated":"2021-10-07T23:32:18Z","date_created":"2021-10-07T23:32:18Z","creator":"fmuehlbo","access_level":"open_access","content_type":"application/pdf","file_size":350632,"relation":"main_file"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"06","oa_version":"Preprint","month":"10","publication_identifier":{"isbn":["978-3-030-88493-2"],"eissn":["1611-3349"],"eisbn":["978-3-030-88494-9"],"issn":["0302-9743"]},"conference":{"start_date":"2021-10-11","name":"RV: Runtime Verification","end_date":"2021-10-14","location":"Virtual"},"author":[{"first_name":"Fabian","full_name":"Mühlböck, Fabian","last_name":"Mühlböck","id":"6395C5F6-89DF-11E9-9C97-6BDFE5697425","orcid":"0000-0003-1548-0177"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A"}]},{"alternative_title":["LNCS"],"status":"public","type":"conference","author":[{"first_name":"Anna","full_name":"Lukina, Anna","id":"CBA4D1A8-0FE8-11E9-BDE6-07BFE5697425","last_name":"Lukina"},{"first_name":"Christian","full_name":"Schilling, Christian","orcid":"0000-0003-3658-1065","id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87","last_name":"Schilling"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"}],"arxiv":1,"conference":{"location":"Virtual","end_date":"2021-10-14","name":"RV: Runtime Verification","start_date":"2021-10-11"},"publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0308-8493-2"],"eissn":["1611-3349"],"eisbn":["978-3-030-88494-9"]},"month":"10","main_file_link":[{"url":"https://arxiv.org/abs/2009.06429","open_access":"1"}],"day":"06","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","language":[{"iso":"eng"}],"publication":"21st International Conference on Runtime Verification","date_updated":"2024-01-30T12:06:56Z","oa":1,"article_processing_charge":"No","title":"Into the unknown: active monitoring of neural networks","isi":1,"scopus_import":"1","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF"}],"publisher":"Springer Nature","date_published":"2021-10-06T00:00:00Z","page":"42-61","department":[{"_id":"ToHe"}],"volume":"12974 ","quality_controlled":"1","place":"Cham","publication_status":"published","external_id":{"arxiv":["2009.06429"],"isi":["000719383800003"]},"abstract":[{"lang":"eng","text":"Neural-network classifiers achieve high accuracy when predicting the class of an input that they were trained to identify. Maintaining this accuracy in dynamic environments, where inputs frequently fall outside the fixed set of initially known classes, remains a challenge. The typical approach is to detect inputs from novel classes and retrain the classifier on an augmented dataset. However, not only the classifier but also the detection mechanism needs to adapt in order to distinguish between newly learned and yet unknown input classes. To address this challenge, we introduce an algorithmic framework for active monitoring of a neural network. A monitor wrapped in our framework operates in parallel with the neural network and interacts with a human user via a series of interpretable labeling queries for incremental adaptation. In addition, we propose an adaptive quantitative monitor to improve precision. An experimental evaluation on a diverse set of benchmarks with varying numbers of classes confirms the benefits of our active monitoring framework in dynamic scenarios."}],"_id":"10206","doi":"10.1007/978-3-030-88494-9_3","acknowledgement":"We thank Christoph Lampert and Alex Greengold for fruitful discussions. This research was supported in part by the Simons Institute for the Theory of Computing, the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award), and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.","year":"2021","citation":{"apa":"Lukina, A., Schilling, C., &#38; Henzinger, T. A. (2021). Into the unknown: active monitoring of neural networks. In <i>21st International Conference on Runtime Verification</i> (Vol. 12974, pp. 42–61). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-88494-9_3\">https://doi.org/10.1007/978-3-030-88494-9_3</a>","short":"A. Lukina, C. Schilling, T.A. Henzinger, in:, 21st International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 42–61.","ama":"Lukina A, Schilling C, Henzinger TA. Into the unknown: active monitoring of neural networks. In: <i>21st International Conference on Runtime Verification</i>. Vol 12974. Cham: Springer Nature; 2021:42-61. doi:<a href=\"https://doi.org/10.1007/978-3-030-88494-9_3\">10.1007/978-3-030-88494-9_3</a>","ieee":"A. Lukina, C. Schilling, and T. A. Henzinger, “Into the unknown: active monitoring of neural networks,” in <i>21st International Conference on Runtime Verification</i>, Virtual, 2021, vol. 12974, pp. 42–61.","chicago":"Lukina, Anna, Christian Schilling, and Thomas A Henzinger. “Into the Unknown: Active Monitoring of Neural Networks.” In <i>21st International Conference on Runtime Verification</i>, 12974:42–61. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-88494-9_3\">https://doi.org/10.1007/978-3-030-88494-9_3</a>.","mla":"Lukina, Anna, et al. “Into the Unknown: Active Monitoring of Neural Networks.” <i>21st International Conference on Runtime Verification</i>, vol. 12974, Springer Nature, 2021, pp. 42–61, doi:<a href=\"https://doi.org/10.1007/978-3-030-88494-9_3\">10.1007/978-3-030-88494-9_3</a>.","ista":"Lukina A, Schilling C, Henzinger TA. 2021. Into the unknown: active monitoring of neural networks. 21st International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 12974, 42–61."},"date_created":"2021-10-31T23:01:31Z","keyword":["monitoring","neural networks","novelty detection"],"ec_funded":1,"related_material":{"record":[{"status":"public","id":"13234","relation":"extended_version"}]}},{"alternative_title":["LNCS"],"type":"conference","status":"public","day":"23","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1905.11360"}],"oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"start_date":"2021-03-01","name":"FC: Financial Cryptography","end_date":"2021-03-05","location":"Virtual"},"month":"10","publication_identifier":{"issn":["0302-9743"],"eisbn":["978-3-662-64331-0"],"eissn":["1611-3349"],"isbn":["9-783-6626-4330-3"]},"author":[{"full_name":"Avarikioti, Zeta","first_name":"Zeta","last_name":"Avarikioti"},{"full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"full_name":"Wattenhofer, Roger","first_name":"Roger","last_name":"Wattenhofer"},{"last_name":"Zindros","full_name":"Zindros, Dionysis","first_name":"Dionysis"}],"arxiv":1,"publication":"25th International Conference on Financial Cryptography and Data Security","language":[{"iso":"eng"}],"scopus_import":"1","isi":1,"title":"Brick: Asynchronous incentive-compatible payment channels","date_updated":"2023-08-14T12:59:58Z","oa":1,"article_processing_charge":"No","page":"209-230","department":[{"_id":"ElKo"}],"quality_controlled":"1","volume":"12675 ","publisher":"Springer Nature","date_published":"2021-10-23T00:00:00Z","external_id":{"isi":["000712016200011"],"arxiv":["1905.11360"]},"abstract":[{"text":"Off-chain protocols (channels) are a promising solution to the scalability and privacy challenges of blockchain payments. Current proposals, however, require synchrony assumptions to preserve the safety of a channel, leaking to an adversary the exact amount of time needed to control the network for a successful attack. In this paper, we introduce Brick, the first payment channel that remains secure under network asynchrony and concurrently provides correct incentives. The core idea is to incorporate the conflict resolution process within the channel by introducing a rational committee of external parties, called wardens. Hence, if a party wants to close a channel unilaterally, it can only get the committee’s approval for the last valid state. Additionally, Brick provides sub-second latency because it does not employ heavy-weight consensus. Instead, Brick uses consistent broadcast to announce updates and close the channel, a light-weight abstraction that is powerful enough to preserve safety and liveness to any rational parties. We formally define and prove for Brick the properties a payment channel construction should fulfill. We also design incentives for Brick such that honest and rational behavior aligns. Finally, we provide a reference implementation of the smart contracts in Solidity.","lang":"eng"}],"publication_status":"published","doi":"10.1007/978-3-662-64331-0_11","_id":"10324","date_created":"2021-11-21T23:01:29Z","citation":{"chicago":"Avarikioti, Zeta, Eleftherios Kokoris Kogias, Roger Wattenhofer, and Dionysis Zindros. “Brick: Asynchronous Incentive-Compatible Payment Channels.” In <i>25th International Conference on Financial Cryptography and Data Security</i>, 12675:209–30. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-662-64331-0_11\">https://doi.org/10.1007/978-3-662-64331-0_11</a>.","ista":"Avarikioti Z, Kokoris Kogias E, Wattenhofer R, Zindros D. 2021. Brick: Asynchronous incentive-compatible payment channels. 25th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography, LNCS, vol. 12675, 209–230.","mla":"Avarikioti, Zeta, et al. “Brick: Asynchronous Incentive-Compatible Payment Channels.” <i>25th International Conference on Financial Cryptography and Data Security</i>, vol. 12675, Springer Nature, 2021, pp. 209–30, doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_11\">10.1007/978-3-662-64331-0_11</a>.","short":"Z. Avarikioti, E. Kokoris Kogias, R. Wattenhofer, D. Zindros, in:, 25th International Conference on Financial Cryptography and Data Security, Springer Nature, 2021, pp. 209–230.","ama":"Avarikioti Z, Kokoris Kogias E, Wattenhofer R, Zindros D. Brick: Asynchronous incentive-compatible payment channels. In: <i>25th International Conference on Financial Cryptography and Data Security</i>. Vol 12675. Springer Nature; 2021:209-230. doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_11\">10.1007/978-3-662-64331-0_11</a>","ieee":"Z. Avarikioti, E. Kokoris Kogias, R. Wattenhofer, and D. Zindros, “Brick: Asynchronous incentive-compatible payment channels,” in <i>25th International Conference on Financial Cryptography and Data Security</i>, Virtual, 2021, vol. 12675, pp. 209–230.","apa":"Avarikioti, Z., Kokoris Kogias, E., Wattenhofer, R., &#38; Zindros, D. (2021). Brick: Asynchronous incentive-compatible payment channels. In <i>25th International Conference on Financial Cryptography and Data Security</i> (Vol. 12675, pp. 209–230). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-64331-0_11\">https://doi.org/10.1007/978-3-662-64331-0_11</a>"},"acknowledgement":"We would like to thank Kaoutar Elkhiyaoui for her valuable feedback as well as Jakub Sliwinski for his impactful contribution to this work.","year":"2021"},{"publication_status":"published","abstract":[{"lang":"eng","text":"Since the inception of Bitcoin, a plethora of distributed ledgers differing in design and purpose has been created. While by design, blockchains provide no means to securely communicate with external systems, numerous attempts towards trustless cross-chain communication have been proposed over the years. Today, cross-chain communication (CCC) plays a fundamental role in cryptocurrency exchanges, scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence in their correctness and composability. We provide the first systematic exposition of cross-chain communication protocols. We formalize the underlying research problem and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. With this result in mind, we develop a framework to design new and evaluate existing CCC protocols, focusing on the inherent trust assumptions thereof, and derive a classification covering the field of cross-chain communication to date. We conclude by discussing open challenges for CCC research and the implications of interoperability on the security and privacy of blockchains."}],"external_id":{"isi":["000712016200001"]},"date_published":"2021-10-23T00:00:00Z","publisher":"Springer Nature","volume":"12675 ","quality_controlled":"1","page":"3-36","department":[{"_id":"ElKo"}],"year":"2021","acknowledgement":"We would like express our gratitude to Georgia Avarikioti, Daniel Perez and Dominik Harz for helpful comments and feedback on earlier versions of this manuscript. We also thank Nicholas Stifter, Aljosha Judmayer, Philipp Schindler, Edgar Weippl, and Alistair Stewart for insightful discussions during the early stages of this research. We also wish to thank the anonymous reviewers for their valuable comments that helped improve the presentation of our results. This research was funded by Bridge 1 858561 SESC; Bridge 1 864738 PR4DLT (all FFG); the Christian Doppler Laboratory for Security and Quality Improvement in the Production System Lifecycle (CDL-SQI); the competence center SBA-K1 funded by COMET; Chaincode Labs through the project SLN: Scalability for the Lightning Network; and by the Austrian Science Fund (FWF) through the Meitner program (project M-2608). Mustafa Al-Bassam is funded by a scholarship from the Alan Turing Institute. Alexei Zamyatin conducted the early stages of this work during his time at SBA Research, and was supported by a Binance Research Fellowship.","citation":{"apa":"Zamyatin, A., Al-Bassam, M., Zindros, D., Kokoris Kogias, E., Moreno-Sanchez, P., Kiayias, A., &#38; Knottenbelt, W. J. (2021). SoK: Communication across distributed ledgers. In <i>25th International Conference on Financial Cryptography and Data Security</i> (Vol. 12675, pp. 3–36). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">https://doi.org/10.1007/978-3-662-64331-0_1</a>","mla":"Zamyatin, Alexei, et al. “SoK: Communication across Distributed Ledgers.” <i>25th International Conference on Financial Cryptography and Data Security</i>, vol. 12675, Springer Nature, 2021, pp. 3–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">10.1007/978-3-662-64331-0_1</a>.","chicago":"Zamyatin, Alexei, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J. Knottenbelt. “SoK: Communication across Distributed Ledgers.” In <i>25th International Conference on Financial Cryptography and Data Security</i>, 12675:3–36. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">https://doi.org/10.1007/978-3-662-64331-0_1</a>.","ista":"Zamyatin A, Al-Bassam M, Zindros D, Kokoris Kogias E, Moreno-Sanchez P, Kiayias A, Knottenbelt WJ. 2021. SoK: Communication across distributed ledgers. 25th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography, LNCS, vol. 12675, 3–36.","short":"A. Zamyatin, M. Al-Bassam, D. Zindros, E. Kokoris Kogias, P. Moreno-Sanchez, A. Kiayias, W.J. Knottenbelt, in:, 25th International Conference on Financial Cryptography and Data Security, Springer Nature, 2021, pp. 3–36.","ama":"Zamyatin A, Al-Bassam M, Zindros D, et al. SoK: Communication across distributed ledgers. In: <i>25th International Conference on Financial Cryptography and Data Security</i>. Vol 12675. Springer Nature; 2021:3-36. doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">10.1007/978-3-662-64331-0_1</a>","ieee":"A. Zamyatin <i>et al.</i>, “SoK: Communication across distributed ledgers,” in <i>25th International Conference on Financial Cryptography and Data Security</i>, Virtual, 2021, vol. 12675, pp. 3–36."},"date_created":"2021-11-21T23:01:29Z","_id":"10325","doi":"10.1007/978-3-662-64331-0_1","author":[{"full_name":"Zamyatin, Alexei","first_name":"Alexei","last_name":"Zamyatin"},{"first_name":"Mustafa","full_name":"Al-Bassam, Mustafa","last_name":"Al-Bassam"},{"last_name":"Zindros","first_name":"Dionysis","full_name":"Zindros, Dionysis"},{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios"},{"full_name":"Moreno-Sanchez, Pedro","first_name":"Pedro","last_name":"Moreno-Sanchez"},{"first_name":"Aggelos","full_name":"Kiayias, Aggelos","last_name":"Kiayias"},{"last_name":"Knottenbelt","first_name":"William J.","full_name":"Knottenbelt, William J."}],"month":"10","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-6626-4330-3"],"eisbn":["978-3-662-64331-0"],"eissn":["1611-3349"]},"conference":{"start_date":"2021-03-01","name":"FC: Financial Cryptography","end_date":"2021-03-05","location":"Virtual"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"23","main_file_link":[{"url":"https://eprint.iacr.org/2019/1128","open_access":"1"}],"oa_version":"Preprint","status":"public","type":"conference","alternative_title":["LNCS"],"article_processing_charge":"No","oa":1,"date_updated":"2023-08-14T12:59:26Z","title":"SoK: Communication across distributed ledgers","isi":1,"scopus_import":"1","language":[{"iso":"eng"}],"publication":"25th International Conference on Financial Cryptography and Data Security"},{"doi":"10.1007/978-3-030-90453-1_14","_id":"10407","ec_funded":1,"date_created":"2021-12-05T23:01:42Z","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>.","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.","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>.","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","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>","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>"},"year":"2021","volume":13043,"quality_controlled":"1","department":[{"_id":"KrPi"}],"page":"397-428","date_published":"2021-11-04T00:00:00Z","publisher":"Springer Nature","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"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."}],"external_id":{"isi":["000728364000014"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"     13043","isi":1,"title":"Trojan-resilience without cryptography","article_processing_charge":"No","oa":1,"date_updated":"2023-08-14T13:07:46Z","type":"conference","status":"public","alternative_title":["LNCS"],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1224"}],"day":"04","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"month":"11","conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08"},"author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip"},{"full_name":"Dziembowski, Stefan","first_name":"Stefan","last_name":"Dziembowski"},{"full_name":"Gałązka, Małgorzata","first_name":"Małgorzata","last_name":"Gałązka"},{"last_name":"Lizurej","full_name":"Lizurej, Tomasz","first_name":"Tomasz"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","first_name":"Michelle X","full_name":"Yeo, Michelle X"}]},{"doi":"10.1007/978-3-030-90456-2_8","_id":"10408","ec_funded":1,"citation":{"apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In <i>19th International Conference</i> (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>","short":"J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 222–253.","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: <i>19th International Conference</i>. Vol 13044. Springer Nature; 2021:222-253. doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>","ieee":"J. F. Alwen <i>et al.</i>, “Grafting key trees: Efficient key management for overlapping groups,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” <i>19th International Conference</i>, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>.","ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.","chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In <i>19th International Conference</i>, 13044:222–53. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>."},"date_created":"2021-12-05T23:01:42Z","acknowledgement":"B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","year":"2021","page":"222-253","department":[{"_id":"KrPi"}],"quality_controlled":"1","volume":13044,"publisher":"Springer Nature","date_published":"2021-11-04T00:00:00Z","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"},{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","call_identifier":"H2020"}],"external_id":{"isi":["000728363700008"]},"abstract":[{"lang":"eng","text":"Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds   log(N)  keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting   2log(N)  ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks."}],"publication_status":"published","publication":"19th International Conference","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"     13044","isi":1,"title":"Grafting key trees: Efficient key management for overlapping groups","date_updated":"2023-08-14T13:19:39Z","oa":1,"article_processing_charge":"No","alternative_title":["LNCS"],"type":"conference","status":"public","oa_version":"Preprint","day":"04","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"name":"TCC: Theory of Cryptography","start_date":"2021-11-08","location":"Raleigh, NC, United States","end_date":"2021-11-11"},"publication_identifier":{"isbn":["9-783-0309-0455-5"],"eissn":["1611-3349"],"eisbn":["978-3-030-90456-2"],"issn":["0302-9743"]},"month":"11","author":[{"full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen"},{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","first_name":"Benedikt"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig","first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"orcid":"0000-0001-8630-415X","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}]},{"publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"month":"11","conference":{"name":"TCC: Theory of Cryptography","start_date":"2021-11-08","location":"Raleigh, NC, United States","end_date":"2021-11-11"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"04","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"oa_version":"Preprint","author":[{"last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan"},{"full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"status":"public","type":"conference","alternative_title":["LNCS"],"isi":1,"scopus_import":"1","article_processing_charge":"No","oa":1,"date_updated":"2023-08-17T06:21:38Z","title":"On treewidth, separators and Yao’s garbling","publication":"19th International Conference","language":[{"iso":"eng"}],"abstract":[{"text":"We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size   S  and treewidth   w  with only a   SO(w)  loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly   O(δwlog(S)) ,   δ  being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.  with only a   SO(w)  loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly   O(δwlog(S)) ,   δ  being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.","lang":"eng"}],"external_id":{"isi":["000728364000017"]},"publication_status":"published","date_published":"2021-11-04T00:00:00Z","publisher":"Springer Nature","quality_controlled":"1","volume":"13043 ","department":[{"_id":"KrPi"}],"page":"486-517","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"id":"10044","relation":"earlier_version","status":"public"}]},"ec_funded":1,"year":"2021","acknowledgement":"We are grateful to Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021 and TCC 2021 reviewers for their detailed review and suggestions, which helped improve presentation considerably.","date_created":"2021-12-05T23:01:43Z","citation":{"ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: <i>19th International Conference</i>. Vol 13043. Springer Nature; 2021:486-517. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">10.1007/978-3-030-90453-1_17</a>","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13043, pp. 486–517.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In <i>19th International Conference</i>, 13043:486–517. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">https://doi.org/10.1007/978-3-030-90453-1_17</a>.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 486–517.","mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” <i>19th International Conference</i>, vol. 13043, Springer Nature, 2021, pp. 486–517, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">10.1007/978-3-030-90453-1_17</a>.","apa":"Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In <i>19th International Conference</i> (Vol. 13043, pp. 486–517). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">https://doi.org/10.1007/978-3-030-90453-1_17</a>"},"doi":"10.1007/978-3-030-90453-1_17","_id":"10409"},{"ec_funded":1,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10048"}]},"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13043, pp. 550–581.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: <i>19th International Conference</i>. Vol 13043. Springer Nature; 2021:550-581. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">10.1007/978-3-030-90453-1_19</a>","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <i>19th International Conference</i>, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">10.1007/978-3-030-90453-1_19</a>.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In <i>19th International Conference</i>, 13043:550–81. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">https://doi.org/10.1007/978-3-030-90453-1_19</a>.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2021). The cost of adaptivity in security games on graphs. In <i>19th International Conference</i> (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">https://doi.org/10.1007/978-3-030-90453-1_19</a>"},"date_created":"2021-12-05T23:01:43Z","acknowledgement":"C. Kamath—Supported by Azrieli International Postdoctoral Fellowship. Most of the work was done while the author was at Northeastern University and Charles University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9, respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work was done while the author was at IST Austria funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","year":"2021","doi":"10.1007/978-3-030-90453-1_19","_id":"10410","external_id":{"isi":["000728364000019"]},"abstract":[{"lang":"eng","text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques."}],"publication_status":"published","page":"550-581","department":[{"_id":"KrPi"}],"quality_controlled":"1","volume":13043,"publisher":"Springer Nature","date_published":"2021-11-04T00:00:00Z","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"intvolume":"     13043","scopus_import":"1","isi":1,"title":"The cost of adaptivity in security games on graphs","date_updated":"2023-10-17T09:24:07Z","oa":1,"article_processing_charge":"No","publication":"19th International Conference","language":[{"iso":"eng"}],"day":"04","main_file_link":[{"url":"https://ia.cr/2021/059","open_access":"1"}],"oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","name":"TCC: Theory of Cryptography","start_date":"2021-11-08"},"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"]},"month":"11","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"alternative_title":["LNCS"],"type":"conference","status":"public"},{"related_material":{"record":[{"status":"public","id":"14539","relation":"dissertation_contains"},{"relation":"later_version","id":"14778","status":"public"}]},"ec_funded":1,"date_created":"2021-12-05T23:01:45Z","citation":{"apa":"Chatterjee, K., Goharshady, E. K., Novotný, P., Zárevúcky, J., &#38; Zikelic, D. (2021). On lexicographic proof rules for probabilistic termination. In <i>24th International Symposium on Formal Methods</i> (Vol. 13047, pp. 619–639). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90870-6_33\">https://doi.org/10.1007/978-3-030-90870-6_33</a>","short":"K. Chatterjee, E.K. Goharshady, P. Novotný, J. Zárevúcky, D. Zikelic, in:, 24th International Symposium on Formal Methods, Springer Nature, 2021, pp. 619–639.","ama":"Chatterjee K, Goharshady EK, Novotný P, Zárevúcky J, Zikelic D. On lexicographic proof rules for probabilistic termination. In: <i>24th International Symposium on Formal Methods</i>. Vol 13047. Springer Nature; 2021:619-639. doi:<a href=\"https://doi.org/10.1007/978-3-030-90870-6_33\">10.1007/978-3-030-90870-6_33</a>","ieee":"K. Chatterjee, E. K. Goharshady, P. Novotný, J. Zárevúcky, and D. Zikelic, “On lexicographic proof rules for probabilistic termination,” in <i>24th International Symposium on Formal Methods</i>, Virtual, 2021, vol. 13047, pp. 619–639.","ista":"Chatterjee K, Goharshady EK, Novotný P, Zárevúcky J, Zikelic D. 2021. On lexicographic proof rules for probabilistic termination. 24th International Symposium on Formal Methods. FM: Formal Methods, LNCS, vol. 13047, 619–639.","mla":"Chatterjee, Krishnendu, et al. “On Lexicographic Proof Rules for Probabilistic Termination.” <i>24th International Symposium on Formal Methods</i>, vol. 13047, Springer Nature, 2021, pp. 619–39, doi:<a href=\"https://doi.org/10.1007/978-3-030-90870-6_33\">10.1007/978-3-030-90870-6_33</a>.","chicago":"Chatterjee, Krishnendu, Ehsan Kafshdar Goharshady, Petr Novotný, Jiří Zárevúcky, and Dorde Zikelic. “On Lexicographic Proof Rules for Probabilistic Termination.” In <i>24th International Symposium on Formal Methods</i>, 13047:619–39. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90870-6_33\">https://doi.org/10.1007/978-3-030-90870-6_33</a>."},"year":"2021","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt), the Czech Science Foundation grant No. GJ19-15134Y, and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.","doi":"10.1007/978-3-030-90870-6_33","_id":"10414","abstract":[{"text":"We consider the almost-sure (a.s.) termination problem for probabilistic programs, which are a stochastic extension of classical imperative programs. Lexicographic ranking functions provide a sound and practical approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via lexicographic ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous work have a limitation that impedes their automation: all of their components have to be non-negative in all reachable states. This might result in LexRSM not existing even for simple terminating programs. Our contributions are twofold: First, we introduce a generalization of LexRSMs which allows for some components to be negative. This standard feature of non-probabilistic termination proofs was hitherto not known to be sound in the probabilistic setting, as the soundness proof requires a careful analysis of the underlying stochastic process. Second, we present polynomial-time algorithms using our generalized LexRSMs for proving a.s. termination in broad classes of linear-arithmetic programs.","lang":"eng"}],"external_id":{"isi":["000758218600033"],"arxiv":["2108.02188"]},"publication_status":"published","quality_controlled":"1","volume":13047,"department":[{"_id":"KrCh"}],"page":"619-639","date_published":"2021-11-10T00:00:00Z","publisher":"Springer Nature","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385"}],"scopus_import":"1","intvolume":"     13047","isi":1,"title":"On lexicographic proof rules for probabilistic termination","article_processing_charge":"No","oa":1,"date_updated":"2025-07-14T09:10:11Z","publication":"24th International Symposium on Formal Methods","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"10","main_file_link":[{"url":"https://arxiv.org/abs/2108.02188","open_access":"1"}],"oa_version":"Preprint","month":"11","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0869-0"],"eisbn":["978-3-030-90870-6"],"eissn":["1611-3349"]},"conference":{"location":"Virtual","end_date":"2021-11-26","name":"FM: Formal Methods","start_date":"2021-11-20"},"arxiv":1,"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Goharshady","first_name":"Ehsan Kafshdar","full_name":"Goharshady, Ehsan Kafshdar"},{"first_name":"Petr","full_name":"Novotný, Petr","last_name":"Novotný","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Zárevúcky","full_name":"Zárevúcky, Jiří","first_name":"Jiří"},{"full_name":"Zikelic, Dorde","first_name":"Dorde","orcid":"0000-0002-4681-1699","last_name":"Zikelic","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","status":"public","alternative_title":["LNCS"]},{"project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"volume":13091,"quality_controlled":"1","department":[{"_id":"KrPi"}],"page":"335-364","date_published":"2021-12-01T00:00:00Z","publisher":"Springer Nature","publication_status":"published","abstract":[{"lang":"eng","text":"We study Multi-party computation (MPC) in the setting of subversion, where the adversary tampers with the machines of honest parties. Our goal is to construct actively secure MPC protocols where parties are corrupted adaptively by an adversary (as in the standard adaptive security setting), and in addition, honest parties’ machines are compromised.\r\nThe idea of reverse firewalls (RF) was introduced at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting protocols against corruption of honest parties’ devices. Intuitively, an RF for a party   P  is an external entity that sits between   P  and the outside world and whose scope is to sanitize   P ’s incoming and outgoing messages in the face of subversion of their computer. Mironov and Stephens-Davidowitz constructed a protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty, Dziembowski and Nielsen constructed a protocol for secure computation with firewalls that improved on this result, both by extending it to multi-party computation protocol, and considering active security in the presence of static corruptions. In this paper, we initiate the study of RF for MPC in the adaptive setting. We put forward a definition for adaptively secure MPC in the reverse firewall setting, explore relationships among the security notions, and then construct reverse firewalls for MPC in this stronger setting of adaptive security. We also resolve the open question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted setup in constructing RF for MPC. Towards this end, we construct reverse firewalls for adaptively secure augmented coin tossing and adaptively secure zero-knowledge protocols and obtain a constant round adaptively secure MPC protocol in the reverse firewall setting without setup. Along the way, we propose a new multi-party adaptively secure coin tossing protocol in the plain model, that is of independent interest."}],"external_id":{"isi":["000927876200012"]},"_id":"10609","doi":"10.1007/978-3-030-92075-3_12","date_created":"2022-01-09T23:01:27Z","citation":{"apa":"Chakraborty, S., Ganesh, C., Pancholi, M., &#38; Sarkar, P. (2021). Reverse firewalls for adaptively secure MPC without setup. In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i> (Vol. 13091, pp. 335–364). Virtual, Singapore: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC without Setup.” <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, vol. 13091, Springer Nature, 2021, pp. 335–64, doi:<a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">10.1007/978-3-030-92075-3_12</a>.","ista":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for adaptively secure MPC without setup. 27th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: International Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364.","chicago":"Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar. “Reverse Firewalls for Adaptively Secure MPC without Setup.” In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, 13091:335–64. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>.","ieee":"S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls for adaptively secure MPC without setup,” in <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, Virtual, Singapore, 2021, vol. 13091, pp. 335–364.","ama":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively secure MPC without setup. In: <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>. Vol 13091. Springer Nature; 2021:335-364. doi:<a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">10.1007/978-3-030-92075-3_12</a>","short":"S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2021, pp. 335–364."},"year":"2021","ec_funded":1,"type":"conference","status":"public","alternative_title":["LNCS"],"author":[{"last_name":"Chakraborty","id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip","full_name":"Chakraborty, Suvradip"},{"first_name":"Chaya","full_name":"Ganesh, Chaya","last_name":"Ganesh"},{"last_name":"Pancholi","first_name":"Mahak","full_name":"Pancholi, Mahak"},{"last_name":"Sarkar","first_name":"Pratik","full_name":"Sarkar, Pratik"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"01","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1262"}],"oa_version":"Preprint","month":"12","publication_identifier":{"eisbn":["978-3-030-92075-3"],"eissn":["1611-3349"],"isbn":["978-3-030-92074-6"],"issn":["0302-9743"]},"conference":{"name":"ASIACRYPT: International Conference on Cryptology in Asia","start_date":"2021-12-06","location":"Virtual, Singapore","end_date":"2021-12-10"},"language":[{"iso":"eng"}],"publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","title":"Reverse firewalls for adaptively secure MPC without setup","article_processing_charge":"No","oa":1,"date_updated":"2023-08-17T06:34:41Z","intvolume":"     13091","scopus_import":"1","isi":1}]