[{"title":"CoCoA: Concurrent continuous group key agreement","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2022/251"}],"article_processing_charge":"No","doi":"10.1007/978-3-031-07085-3_28","date_created":"2022-06-30T16:48:00Z","oa_version":"Preprint","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"place":"Cham","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783031070853"],"isbn":["9783031070846"]},"corr_author":"1","acknowledgement":"We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful feedback on an earlier draft of this paper.","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"}],"month":"05","type":"conference","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","grant_number":"665385","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"external_id":{"isi":["000832305300028"]},"date_published":"2022-05-25T00:00:00Z","_id":"11476","related_material":{"record":[{"status":"public","id":"18088","relation":"dissertation_contains"}]},"isi":1,"publication_status":"published","intvolume":"     13276","language":[{"iso":"eng"}],"volume":13276,"alternative_title":["LNCS"],"day":"25","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa":1,"date_updated":"2026-04-07T13:01:26Z","year":"2022","author":[{"first_name":"Joël","last_name":"Alwen","full_name":"Alwen, Joël"},{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","first_name":"Benedikt","full_name":"Auerbach, Benedikt"},{"orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pascual Perez","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter"}],"publication":"Advances in Cryptology – EUROCRYPT 2022","status":"public","page":"815–844","citation":{"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>","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>.","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.","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: Theory and Applications of Cryptology and Information Security, LNCS, vol. 13276, 815–844.","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>.","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."},"ec_funded":1,"scopus_import":"1","conference":{"location":"Trondheim, Norway","name":"EUROCRYPT: Theory and Applications of Cryptology and Information Security","start_date":"2022-05-30","end_date":"2022-06-03"},"publisher":"Springer Nature"},{"year":"2022","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Goharshady","first_name":"Amir Kafshdar","full_name":"Goharshady, Amir Kafshdar","id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584"},{"full_name":"Meggendorfer, Tobias","first_name":"Tobias","last_name":"Meggendorfer","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1"},{"orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","full_name":"Zikelic, Dorde","last_name":"Zikelic","first_name":"Dorde"}],"date_updated":"2026-04-07T13:27:55Z","has_accepted_license":"1","ec_funded":1,"scopus_import":"1","conference":{"end_date":"2022-08-10","start_date":"2022-08-07","name":"CAV: Computer Aided Verification","location":"Haifa, Israel"},"publisher":"Springer","file":[{"file_size":505094,"content_type":"application/pdf","checksum":"24e0f810ec52735a90ade95198bc641d","date_updated":"2022-08-29T09:17:01Z","access_level":"open_access","date_created":"2022-08-29T09:17:01Z","success":1,"creator":"alisjak","file_name":"2022_LNCS_Chatterjee.pdf","relation":"main_file","file_id":"12003"}],"publication":"Proceedings of the 34th International Conference on Computer Aided Verification","status":"public","page":"55-78","ddc":["000"],"citation":{"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>.","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.","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.","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.","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>","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>."},"alternative_title":["LNCS"],"day":"07","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","volume":13371,"quality_controlled":"1","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"_id":"12000","isi":1,"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"14539"}]},"date_published":"2022-08-07T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"     13371","department":[{"_id":"KrCh"}],"title":"Sound and complete certificates for auantitative termination analysis of probabilistic programs","article_processing_charge":"Yes (in subscription journal)","doi":"10.1007/978-3-031-13185-1_4","date_created":"2022-08-28T22:02:02Z","oa_version":"Published Version","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"}],"type":"conference","file_date_updated":"2022-08-29T09:17:01Z","month":"08","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","name":"International IST Doctoral Program"}],"external_id":{"isi":["000870304500004"]},"publication_identifier":{"isbn":["9783031131844"],"issn":["0302-9743"],"eissn":["1611-3349"]},"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."},{"date_updated":"2026-04-16T09:13:43Z","author":[{"last_name":"Bartocci","first_name":"Ezio","full_name":"Bartocci, Ezio"},{"id":"40960E6E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5199-3143","full_name":"Ferrere, Thomas","last_name":"Ferrere","first_name":"Thomas"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","full_name":"Nickovic, Dejan","last_name":"Nickovic","first_name":"Dejan"},{"last_name":"Da Costa","first_name":"Ana Oliveira","full_name":"Da Costa, Ana Oliveira"}],"year":"2022","status":"public","publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","page":"1-19","citation":{"mla":"Bartocci, Ezio, et al. “Flavors of Sequential Information Flow.” <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, vol. 13182, Springer Nature, 2022, pp. 1–19, doi:<a href=\"https://doi.org/10.1007/978-3-030-94583-1_1\">10.1007/978-3-030-94583-1_1</a>.","ieee":"E. Bartocci, T. Ferrere, T. A. Henzinger, D. Nickovic, and A. O. Da Costa, “Flavors of sequential information flow,” in <i>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, Philadelphia, PA, United States, 2022, vol. 13182, pp. 1–19.","ama":"Bartocci E, Ferrere T, Henzinger TA, Nickovic D, Da Costa AO. Flavors of sequential information flow. In: <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>. Vol 13182. Springer Nature; 2022:1-19. doi:<a href=\"https://doi.org/10.1007/978-3-030-94583-1_1\">10.1007/978-3-030-94583-1_1</a>","apa":"Bartocci, E., Ferrere, T., Henzinger, T. A., Nickovic, D., &#38; Da Costa, A. O. (2022). Flavors of sequential information flow. In <i>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i> (Vol. 13182, pp. 1–19). Philadelphia, PA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-94583-1_1\">https://doi.org/10.1007/978-3-030-94583-1_1</a>","short":"E. Bartocci, T. Ferrere, T.A. Henzinger, D. Nickovic, A.O. Da Costa, in:, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Nature, 2022, pp. 1–19.","chicago":"Bartocci, Ezio, Thomas Ferrere, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira Da Costa. “Flavors of Sequential Information Flow.” In <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, 13182:1–19. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-030-94583-1_1\">https://doi.org/10.1007/978-3-030-94583-1_1</a>.","ista":"Bartocci E, Ferrere T, Henzinger TA, Nickovic D, Da Costa AO. 2022. Flavors of sequential information flow. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 13182, 1–19."},"conference":{"location":"Philadelphia, PA, United States","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","start_date":"2022-01-16","end_date":"2022-01-18"},"publisher":"Springer Nature","scopus_import":"1","volume":13182,"day":"14","alternative_title":["LNCS"],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","quality_controlled":"1","oa":1,"date_published":"2022-01-14T00:00:00Z","isi":1,"_id":"10774","intvolume":"     13182","publication_status":"published","language":[{"iso":"eng"}],"title":"Flavors of sequential information flow","date_created":"2022-02-20T23:01:34Z","doi":"10.1007/978-3-030-94583-1_1","oa_version":"Preprint","article_processing_charge":"No","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2105.02013","open_access":"1"}],"department":[{"_id":"ToHe"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783030945831"],"isbn":["9783030945824"]},"acknowledgement":"This work was funded in part by the Wittgenstein Award Z211-N23 of the Austrian Science Fund (FWF) and by the FWF project W1255-N23.","type":"conference","month":"01","arxiv":1,"abstract":[{"lang":"eng","text":"We study the problem of specifying sequential information-flow properties of systems. Information-flow properties are hyperproperties, as they compare different traces of a system. Sequential information-flow properties can express changes, over time, in the information-flow constraints. For example, information-flow constraints during an initialization phase of a system may be different from information-flow constraints that are required during the operation phase. We formalize several variants of interpreting sequential information-flow constraints, which arise from different assumptions about what can be observed of the system. For this purpose, we introduce a first-order logic, called Hypertrace Logic, with both trace and time quantifiers for specifying linear-time hyperproperties. We prove that HyperLTL, which corresponds to a fragment of Hypertrace Logic with restricted quantifier prefixes, cannot specify the majority of the studied variants of sequential information flow, including all variants in which the transition between sequential phases (such as initialization and operation) happens asynchronously. Our results rely on new equivalences between sets of traces that cannot be distinguished by certain classes of formulas from Hypertrace Logic. This presents a new approach to proving inexpressiveness results for HyperLTL."}],"external_id":{"isi":["001059208500001"],"arxiv":["2105.02013"]},"project":[{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","grant_number":"Z211"}]},{"publication_identifier":{"isbn":["9783030835071"],"eisbn":["9783030835088"],"issn":["0302-9743"],"eissn":["1611-3349"]},"external_id":{"arxiv":["1910.03332"]},"abstract":[{"text":"Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. [7] introduced retroactive data structures (RDS). A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. While efficient RDS have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied.\r\n\r\nIn this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]), there does not exist fully RDS maintaining connectivity or MSF, or incremental fully RDS maintaining the maximum degree with 𝑂(𝑛1−𝜖) time per operation, for any constant 𝜖>0. Furthermore, We provide RDS with almost tight time per operation. We give fully RDS for maintaining the maximum degree, connectivity and MSF in 𝑂̃ (𝑛) time per operation. We also give an algorithm for the incremental (insertion-only) fully retroactive connectivity with 𝑂̃ (1) time per operation, showing that the lower bound cannot be extended to this setting.\r\n\r\nWe also study a restricted version of RDS, where the only change to S is the swap of neighboring updates and show that for this problem we can beat the above hardness result. This also implies the first non-trivial dynamic Reeb graph computation algorithm.","lang":"eng"}],"month":"08","type":"conference","arxiv":1,"article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/1910.03332","open_access":"1"}],"oa_version":"Preprint","date_created":"2022-08-08T13:01:29Z","doi":"10.1007/978-3-030-83508-8_34","title":"Upper and lower bounds for fully retroactive graph problems","publication_status":"published","intvolume":"     12808","language":[{"iso":"eng"}],"date_published":"2021-08-09T00:00:00Z","_id":"11771","oa":1,"quality_controlled":"1","volume":12808,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"day":"09","page":"471–484","citation":{"chicago":"Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” In <i>17th International Symposium on Algorithms and Data Structures</i>, 12808:471–484. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">https://doi.org/10.1007/978-3-030-83508-8_34</a>.","short":"M. Henzinger, X. Wu, in:, 17th International Symposium on Algorithms and Data Structures, Springer Nature, 2021, pp. 471–484.","ista":"Henzinger M, Wu X. 2021. Upper and lower bounds for fully retroactive graph problems. 17th International Symposium on Algorithms and Data Structures. WADS: Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.","ama":"Henzinger M, Wu X. Upper and lower bounds for fully retroactive graph problems. In: <i>17th International Symposium on Algorithms and Data Structures</i>. Vol 12808. Springer Nature; 2021:471–484. doi:<a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">10.1007/978-3-030-83508-8_34</a>","mla":"Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” <i>17th International Symposium on Algorithms and Data Structures</i>, vol. 12808, Springer Nature, 2021, pp. 471–484, doi:<a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">10.1007/978-3-030-83508-8_34</a>.","apa":"Henzinger, M., &#38; Wu, X. (2021). Upper and lower bounds for fully retroactive graph problems. In <i>17th International Symposium on Algorithms and Data Structures</i> (Vol. 12808, pp. 471–484). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">https://doi.org/10.1007/978-3-030-83508-8_34</a>","ieee":"M. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph problems,” in <i>17th International Symposium on Algorithms and Data Structures</i>, Virtual, 2021, vol. 12808, pp. 471–484."},"status":"public","publication":"17th International Symposium on Algorithms and Data Structures","scopus_import":"1","conference":{"location":"Virtual","name":"WADS: Workshop on Algorithms and Data Structures","start_date":"2021-08-09","end_date":"2021-08-11"},"publisher":"Springer Nature","extern":"1","date_updated":"2024-11-06T12:10:14Z","year":"2021","author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"first_name":"Xiaowei","last_name":"Wu","full_name":"Wu, Xiaowei"}]},{"quality_controlled":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"19","alternative_title":["LNCS"],"issue":"Part I","volume":12858,"conference":{"name":"APWeb-WAIM: International Joint Conference on Asia-Pacific Web and Web-Age Information Management","end_date":"2021-08-25","start_date":"2021-08-23","location":"Guangzhou, China"},"publisher":"Springer Nature","scopus_import":"1","page":"44 - 52","citation":{"short":"J. Hermanns, A. Tsitsulin, M. Munkhoeva, A.M. Bronstein, D. Mottin, P. Karras, in:, International Joint Conference on Asia-Pacific Web and Web-Age Information Management, Springer Nature, 2021, pp. 44–52.","chicago":"Hermanns, Judith, Anton Tsitsulin, Marina Munkhoeva, Alex M. Bronstein, Davide Mottin, and Panagiotis Karras. “GRASP: Graph Alignment through Spectral Signatures.” In <i>International Joint Conference on Asia-Pacific Web and Web-Age Information Management</i>, 12858:44–52. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-85896-4_4\">https://doi.org/10.1007/978-3-030-85896-4_4</a>.","ista":"Hermanns J, Tsitsulin A, Munkhoeva M, Bronstein AM, Mottin D, Karras P. 2021. GRASP: Graph alignment through spectral signatures. International Joint Conference on Asia-Pacific Web and Web-Age Information Management. APWeb-WAIM: International Joint Conference on Asia-Pacific Web and Web-Age Information Management, LNCS, vol. 12858, 44–52.","mla":"Hermanns, Judith, et al. “GRASP: Graph Alignment through Spectral Signatures.” <i>International Joint Conference on Asia-Pacific Web and Web-Age Information Management</i>, vol. 12858, no. Part I, Springer Nature, 2021, pp. 44–52, doi:<a href=\"https://doi.org/10.1007/978-3-030-85896-4_4\">10.1007/978-3-030-85896-4_4</a>.","ieee":"J. Hermanns, A. Tsitsulin, M. Munkhoeva, A. M. Bronstein, D. Mottin, and P. Karras, “GRASP: Graph alignment through spectral signatures,” in <i>International Joint Conference on Asia-Pacific Web and Web-Age Information Management</i>, Guangzhou, China, 2021, vol. 12858, no. Part I, pp. 44–52.","ama":"Hermanns J, Tsitsulin A, Munkhoeva M, Bronstein AM, Mottin D, Karras P. GRASP: Graph alignment through spectral signatures. In: <i>International Joint Conference on Asia-Pacific Web and Web-Age Information Management</i>. Vol 12858. Springer Nature; 2021:44-52. doi:<a href=\"https://doi.org/10.1007/978-3-030-85896-4_4\">10.1007/978-3-030-85896-4_4</a>","apa":"Hermanns, J., Tsitsulin, A., Munkhoeva, M., Bronstein, A. M., Mottin, D., &#38; Karras, P. (2021). GRASP: Graph alignment through spectral signatures. In <i>International Joint Conference on Asia-Pacific Web and Web-Age Information Management</i> (Vol. 12858, pp. 44–52). Guangzhou, China: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-85896-4_4\">https://doi.org/10.1007/978-3-030-85896-4_4</a>"},"publication":"International Joint Conference on Asia-Pacific Web and Web-Age Information Management","status":"public","author":[{"first_name":"Judith","last_name":"Hermanns","full_name":"Hermanns, Judith"},{"full_name":"Tsitsulin, Anton","last_name":"Tsitsulin","first_name":"Anton"},{"first_name":"Marina","last_name":"Munkhoeva","full_name":"Munkhoeva, Marina"},{"first_name":"Alexander","last_name":"Bronstein","full_name":"Bronstein, Alexander","orcid":"0000-0001-9699-8730","id":"58f3726e-7cba-11ef-ad8b-e6e8cb3904e6"},{"full_name":"Mottin, Davide","first_name":"Davide","last_name":"Mottin"},{"full_name":"Karras, Panagiotis","first_name":"Panagiotis","last_name":"Karras"}],"year":"2021","extern":"1","date_updated":"2025-01-29T09:57:31Z","type":"conference","month":"08","abstract":[{"text":"What is the best way to match the nodes of two graphs? This graph alignment problem generalizes graph isomorphism and arises in applications from social network analysis to bioinformatics. Existing solutions either require auxiliary information such as node attributes, or provide a single-scale view of the graph by translating the problem into aligning node embeddings.\r\n\r\nIn this paper, we transfer the shape-analysis concept of functional maps from the continuous to the discrete case, and treat the graph alignment problem as a special case of the problem of finding a mapping between functions on graphs. We present GRASP, a method that captures multiscale structural characteristics from the eigenvectors of the graph’s Laplacian and uses this information to align two graphs.Our experimental study, featuring noise levels higher than anything used in previous studies, shows that GRASP outperforms state-of-the-art methods for graph alignment across noise levels and graph types.","lang":"eng"}],"publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783030858957","9783030858964"]},"doi":"10.1007/978-3-030-85896-4_4","date_created":"2024-10-08T13:03:44Z","oa_version":"None","article_processing_charge":"No","title":"GRASP: Graph alignment through spectral signatures","language":[{"iso":"eng"}],"intvolume":"     12858","publication_status":"published","_id":"18243","date_published":"2021-08-19T00:00:00Z"},{"department":[{"_id":"KrCh"}],"title":"On satisficing in quantitative games","doi":"10.1007/978-3-030-72016-2_2","oa_version":"Published Version","date_created":"2023-03-26T22:01:09Z","article_processing_charge":"No","file_date_updated":"2023-03-28T11:00:33Z","month":"03","type":"conference","arxiv":1,"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"]},"project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030720155"]},"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.","_id":"12767","date_published":"2021-03-21T00:00:00Z","language":[{"iso":"eng"}],"intvolume":"     12651","publication_status":"published","day":"21","alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":12651,"quality_controlled":"1","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"author":[{"last_name":"Bansal","first_name":"Suguman","full_name":"Bansal, Suguman"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Vardi, Moshe Y.","last_name":"Vardi","first_name":"Moshe Y."}],"year":"2021","date_updated":"2025-07-10T13:18:02Z","conference":{"location":"Luxembourg City, Luxembourg","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2021-03-27","end_date":"2021-04-01"},"publisher":"Springer Nature","file":[{"file_id":"12777","relation":"main_file","file_name":"2021_LNCS_Bansal.pdf","creator":"dernst","date_created":"2023-03-28T11:00:33Z","success":1,"date_updated":"2023-03-28T11:00:33Z","access_level":"open_access","checksum":"b020b78b23587ce7610b1aafb4e63438","content_type":"application/pdf","file_size":747418}],"ec_funded":1,"scopus_import":"1","has_accepted_license":"1","publication":"27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","status":"public","page":"20-37","citation":{"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.","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_2\">10.1007/978-3-030-72016-2_2</a>.","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_2\">https://doi.org/10.1007/978-3-030-72016-2_2</a>","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_2\">10.1007/978-3-030-72016-2_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_2\">https://doi.org/10.1007/978-3-030-72016-2_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."},"ddc":["000"]},{"date_updated":"2025-04-14T07:22:06Z","author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","full_name":"Chakraborty, Suvradip","last_name":"Chakraborty","first_name":"Suvradip"},{"full_name":"Ganesh, Chaya","last_name":"Ganesh","first_name":"Chaya"},{"full_name":"Pancholi, Mahak","last_name":"Pancholi","first_name":"Mahak"},{"full_name":"Sarkar, Pratik","last_name":"Sarkar","first_name":"Pratik"}],"year":"2021","status":"public","publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","page":"335-364","citation":{"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.","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>.","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>","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>","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>.","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.","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."},"publisher":"Springer Nature","conference":{"location":"Virtual, Singapore","name":"ASIACRYPT: International Conference on Cryptology in Asia","end_date":"2021-12-10","start_date":"2021-12-06"},"ec_funded":1,"scopus_import":"1","volume":13091,"day":"01","alternative_title":["LNCS"],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","quality_controlled":"1","oa":1,"date_published":"2021-12-01T00:00:00Z","_id":"10609","isi":1,"intvolume":"     13091","publication_status":"published","language":[{"iso":"eng"}],"title":"Reverse firewalls for adaptively secure MPC without setup","oa_version":"Preprint","doi":"10.1007/978-3-030-92075-3_12","date_created":"2022-01-09T23:01:27Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1262"}],"article_processing_charge":"No","department":[{"_id":"KrPi"}],"publication_identifier":{"isbn":["978-3-030-92074-6"],"eisbn":["978-3-030-92075-3"],"eissn":["1611-3349"],"issn":["0302-9743"]},"type":"conference","month":"12","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"]},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"17","alternative_title":["LNCS"],"volume":"12676 ","oa":1,"quality_controlled":"1","author":[{"last_name":"Blackshear","first_name":"Sam","full_name":"Blackshear, Sam"},{"full_name":"Chalkias, Konstantinos","last_name":"Chalkias","first_name":"Konstantinos"},{"full_name":"Chatzigiannis, Panagiotis","first_name":"Panagiotis","last_name":"Chatzigiannis"},{"full_name":"Faizullabhoy, Riyaz","first_name":"Riyaz","last_name":"Faizullabhoy"},{"full_name":"Khaburzaniya, Irakliy","last_name":"Khaburzaniya","first_name":"Irakliy"},{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios"},{"first_name":"Joshua","last_name":"Lind","full_name":"Lind, Joshua"},{"full_name":"Wong, David","last_name":"Wong","first_name":"David"},{"full_name":"Zakian, Tim","last_name":"Zakian","first_name":"Tim"}],"year":"2021","date_updated":"2025-07-10T11:49:40Z","publisher":"Springer Nature","conference":{"name":"FC: Financial Cryptography and Data Security","end_date":"2021-03-05","start_date":"2021-03-01","location":"Virtual"},"scopus_import":"1","citation":{"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.","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>.","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>","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>","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.","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: Financial Cryptography and Data Security, LNCS, vol. 12676, 431–450."},"page":"431-450","status":"public","publication":"FC 2021 Workshops","department":[{"_id":"ElKo"}],"date_created":"2021-10-03T22:01:24Z","oa_version":"Preprint","doi":"10.1007/978-3-662-63958-0_34","article_processing_charge":"No","main_file_link":[{"url":"https://research.fb.com/publications/reactive-key-loss-protection-in-blockchains/","open_access":"1"}],"title":"Reactive key-loss protection in blockchains","external_id":{"isi":["000713005000034"]},"month":"09","type":"conference","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"}],"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.","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-662-63958-0"],"isbn":["978-3-6626-3957-3"]},"_id":"10076","isi":1,"date_published":"2021-09-17T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published"},{"language":[{"iso":"eng"}],"intvolume":"     12974","publication_status":"published","keyword":["run-time verification","software engineering","implicit specification"],"related_material":{"record":[{"relation":"extended_version","id":"9946","status":"public"}]},"_id":"10108","isi":1,"date_published":"2021-10-06T00:00:00Z","external_id":{"isi":["000719383800012"]},"project":[{"grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"type":"conference","month":"10","file_date_updated":"2021-10-07T23:32:18Z","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."}],"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.","corr_author":"1","place":"Cham","publication_identifier":{"isbn":["978-3-030-88493-2"],"eisbn":["978-3-030-88494-9"],"eissn":["1611-3349"],"issn":["0302-9743"]},"department":[{"_id":"ToHe"}],"oa_version":"Preprint","date_created":"2021-10-07T23:30:10Z","doi":"10.1007/978-3-030-88494-9_12","article_processing_charge":"No","title":"Differential monitoring","publisher":"Springer Nature","file":[{"date_updated":"2021-10-07T23:32:18Z","access_level":"open_access","success":1,"date_created":"2021-10-07T23:32:18Z","file_size":350632,"checksum":"554c7fdb259eda703a8b6328a6dad55a","content_type":"application/pdf","creator":"fmuehlbo","file_name":"differentialmonitoring-cameraready-openaccess.pdf","relation":"main_file","file_id":"10109"}],"conference":{"name":"RV: Runtime Verification","end_date":"2021-10-14","start_date":"2021-10-11","location":"Virtual"},"scopus_import":"1","has_accepted_license":"1","page":"231-243","citation":{"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.","short":"F. Mühlböck, T.A. Henzinger, in:, International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 231–243.","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>","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>","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>."},"ddc":["005"],"publication":"International Conference on Runtime Verification","status":"public","author":[{"orcid":"0000-0003-1548-0177","id":"6395C5F6-89DF-11E9-9C97-6BDFE5697425","last_name":"Mühlböck","first_name":"Fabian","full_name":"Mühlböck, Fabian"},{"first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"year":"2021","date_updated":"2025-04-15T06:26:12Z","oa":1,"quality_controlled":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"06","alternative_title":["LNCS"],"volume":12974},{"article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/2009.06429","open_access":"1"}],"date_created":"2021-10-31T23:01:31Z","oa_version":"Preprint","doi":"10.1007/978-3-030-88494-9_3","title":"Into the unknown: active monitoring of neural networks","department":[{"_id":"ToHe"}],"corr_author":"1","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.","place":"Cham","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-88494-9"],"isbn":["9-783-0308-8493-2"]},"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"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."}],"type":"conference","arxiv":1,"month":"10","date_published":"2021-10-06T00:00:00Z","keyword":["monitoring","neural networks","novelty detection"],"isi":1,"_id":"10206","related_material":{"record":[{"relation":"extended_version","id":"13234","status":"public"}]},"publication_status":"published","language":[{"iso":"eng"}],"volume":"12974 ","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","alternative_title":["LNCS"],"day":"06","oa":1,"quality_controlled":"1","date_updated":"2025-04-15T06:26:14Z","year":"2021","author":[{"id":"CBA4D1A8-0FE8-11E9-BDE6-07BFE5697425","full_name":"Lukina, Anna","first_name":"Anna","last_name":"Lukina"},{"id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3658-1065","full_name":"Schilling, Christian","first_name":"Christian","last_name":"Schilling"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724"}],"page":"42-61","citation":{"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>.","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.","short":"A. Lukina, C. Schilling, T.A. Henzinger, in:, 21st International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 42–61.","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>","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>","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>.","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."},"status":"public","publication":"21st International Conference on Runtime Verification","scopus_import":"1","ec_funded":1,"conference":{"end_date":"2021-10-14","start_date":"2021-10-11","name":"RV: Runtime Verification","location":"Virtual"},"publisher":"Springer Nature"},{"oa":1,"quality_controlled":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"23","alternative_title":["LNCS"],"volume":"12675 ","publisher":"Springer Nature","conference":{"location":"Virtual","end_date":"2021-03-05","start_date":"2021-03-01","name":"FC: Financial Cryptography"},"scopus_import":"1","page":"209-230","citation":{"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.","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.","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>.","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.","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>.","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>","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>"},"status":"public","publication":"25th International Conference on Financial Cryptography and Data Security","author":[{"first_name":"Zeta","last_name":"Avarikioti","full_name":"Avarikioti, Zeta"},{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","first_name":"Eleftherios","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios"},{"last_name":"Wattenhofer","first_name":"Roger","full_name":"Wattenhofer, Roger"},{"last_name":"Zindros","first_name":"Dionysis","full_name":"Zindros, Dionysis"}],"year":"2021","date_updated":"2023-08-14T12:59:58Z","external_id":{"arxiv":["1905.11360"],"isi":["000712016200011"]},"type":"conference","arxiv":1,"month":"10","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"}],"acknowledgement":"We would like to thank Kaoutar Elkhiyaoui for her valuable feedback as well as Jakub Sliwinski for his impactful contribution to this work.","publication_identifier":{"isbn":["9-783-6626-4330-3"],"eisbn":["978-3-662-64331-0"],"eissn":["1611-3349"],"issn":["0302-9743"]},"department":[{"_id":"ElKo"}],"doi":"10.1007/978-3-662-64331-0_11","oa_version":"Preprint","date_created":"2021-11-21T23:01:29Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1905.11360"}],"article_processing_charge":"No","title":"Brick: Asynchronous incentive-compatible payment channels","language":[{"iso":"eng"}],"publication_status":"published","_id":"10324","isi":1,"date_published":"2021-10-23T00:00:00Z"},{"isi":1,"_id":"10325","date_published":"2021-10-23T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","department":[{"_id":"ElKo"}],"title":"SoK: Communication across distributed ledgers","date_created":"2021-11-21T23:01:29Z","oa_version":"Preprint","doi":"10.1007/978-3-662-64331-0_1","main_file_link":[{"url":"https://eprint.iacr.org/2019/1128","open_access":"1"}],"article_processing_charge":"No","month":"10","type":"conference","abstract":[{"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.","lang":"eng"}],"external_id":{"isi":["000712016200001"]},"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-6626-4330-3"],"eisbn":["978-3-662-64331-0"]},"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.","author":[{"first_name":"Alexei","last_name":"Zamyatin","full_name":"Zamyatin, Alexei"},{"full_name":"Al-Bassam, Mustafa","last_name":"Al-Bassam","first_name":"Mustafa"},{"full_name":"Zindros, Dionysis","first_name":"Dionysis","last_name":"Zindros"},{"last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"full_name":"Moreno-Sanchez, Pedro","first_name":"Pedro","last_name":"Moreno-Sanchez"},{"first_name":"Aggelos","last_name":"Kiayias","full_name":"Kiayias, Aggelos"},{"last_name":"Knottenbelt","first_name":"William J.","full_name":"Knottenbelt, William J."}],"year":"2021","date_updated":"2023-08-14T12:59:26Z","conference":{"name":"FC: Financial Cryptography","start_date":"2021-03-01","end_date":"2021-03-05","location":"Virtual"},"publisher":"Springer Nature","scopus_import":"1","publication":"25th International Conference on Financial Cryptography and Data Security","status":"public","page":"3-36","citation":{"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.","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>.","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>","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>","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.","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."},"day":"23","alternative_title":["LNCS"],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","volume":"12675 ","quality_controlled":"1","oa":1},{"citation":{"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.","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.","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>","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.","mla":"Chakraborty, Suvradip, et al. <i>Trojan-Resilience without Cryptography</i>. Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>.","ama":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>"},"page":"397-428","status":"public","conference":{"start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","location":"Raleigh, NC, United States"},"publisher":"Springer Nature","ec_funded":1,"scopus_import":"1","date_updated":"2025-04-14T07:22:05Z","author":[{"first_name":"Suvradip","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"first_name":"Stefan","last_name":"Dziembowski","full_name":"Dziembowski, Stefan"},{"full_name":"Gałązka, Małgorzata","last_name":"Gałązka","first_name":"Małgorzata"},{"last_name":"Lizurej","first_name":"Tomasz","full_name":"Lizurej, Tomasz"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","last_name":"Yeo","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"year":"2021","oa":1,"quality_controlled":"1","volume":13043,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"04","alternative_title":["LNCS"],"intvolume":"     13043","publication_status":"published","language":[{"iso":"eng"}],"date_published":"2021-11-04T00:00:00Z","isi":1,"_id":"10407","publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"external_id":{"isi":["000728364000014"]},"project":[{"call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"type":"conference","month":"11","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."}],"date_created":"2021-12-05T23:01:42Z","oa_version":"Preprint","doi":"10.1007/978-3-030-90453-1_14","main_file_link":[{"url":"https://eprint.iacr.org/2021/1224","open_access":"1"}],"article_processing_charge":"No","title":"Trojan-resilience without cryptography","department":[{"_id":"KrPi"}]},{"publication_status":"published","language":[{"iso":"eng"}],"date_published":"2021-11-04T00:00:00Z","_id":"10409","isi":1,"related_material":{"record":[{"relation":"earlier_version","id":"10044","status":"public"}]},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"]},"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.","abstract":[{"lang":"eng","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."}],"month":"11","type":"conference","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"external_id":{"isi":["000728364000017"]},"title":"On treewidth, separators and Yao’s garbling","article_processing_charge":"No","main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"oa_version":"Preprint","date_created":"2021-12-05T23:01:43Z","doi":"10.1007/978-3-030-90453-1_17","department":[{"_id":"KrPi"}],"status":"public","publication":"19th International Conference","page":"486-517","citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517.","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.","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>.","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>.","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>","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>","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."},"ec_funded":1,"scopus_import":"1","conference":{"name":"TCC: Theory of Cryptography","end_date":"2021-11-11","start_date":"2021-11-08","location":"Raleigh, NC, United States"},"publisher":"Springer Nature","date_updated":"2025-04-15T08:32:06Z","year":"2021","author":[{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"quality_controlled":"1","oa":1,"volume":"13043 ","alternative_title":["LNCS"],"day":"04","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"quality_controlled":"1","oa":1,"day":"04","alternative_title":["LNCS"],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","volume":13043,"publisher":"Springer Nature","conference":{"location":"Raleigh, NC, United States","start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography"},"ec_funded":1,"scopus_import":"1","publication":"19th International Conference","status":"public","citation":{"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.","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>.","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.","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>","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>","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>."},"page":"550-581","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","full_name":"Walter, Michael"}],"year":"2021","date_updated":"2025-04-14T07:22:05Z","month":"11","type":"conference","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."}],"external_id":{"isi":["000728364000019"]},"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"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).","department":[{"_id":"KrPi"}],"title":"The cost of adaptivity in security games on graphs","oa_version":"Preprint","date_created":"2021-12-05T23:01:43Z","doi":"10.1007/978-3-030-90453-1_19","article_processing_charge":"No","main_file_link":[{"url":"https://ia.cr/2021/059","open_access":"1"}],"language":[{"iso":"eng"}],"intvolume":"     13043","publication_status":"published","related_material":{"record":[{"status":"public","id":"10048","relation":"earlier_version"}]},"_id":"10410","isi":1,"date_published":"2021-11-04T00:00:00Z"},{"oa":1,"quality_controlled":"1","volume":12544,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","series_title":"LNCS","day":"17","page":"246-259","ddc":["510"],"citation":{"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>","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>","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>.","short":"V. Volhejn, C. Lampert, in:, 42nd German Conference on Pattern Recognition, Springer, 2021, pp. 246–259.","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."},"status":"public","publication":"42nd German Conference on Pattern Recognition","has_accepted_license":"1","scopus_import":"1","conference":{"end_date":"2020-10-01","start_date":"2020-09-28","name":"DAGM GCPR: German Conference on Pattern Recognition ","location":"Tübingen, Germany"},"publisher":"Springer","file":[{"relation":"main_file","file_id":"11820","creator":"dernst","file_name":"2020_GCPR_submitted_Volhejn.pdf","checksum":"3e3628ab1cf658d82524963f808004ea","content_type":"application/pdf","file_size":420234,"date_created":"2022-08-12T07:27:58Z","success":1,"access_level":"open_access","date_updated":"2022-08-12T07:27:58Z"}],"date_updated":"2025-09-10T10:00:33Z","year":"2021","author":[{"id":"d5235fb4-7a6d-11eb-b254-f25d12d631a8","last_name":"Volhejn","first_name":"Vaclav","full_name":"Volhejn, Vaclav"},{"full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887"}],"publication_identifier":{"isbn":["9783030712778"],"eissn":["1611-3349"],"issn":["0302-9743"]},"external_id":{"isi":["001500603200018"]},"abstract":[{"lang":"eng","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."}],"type":"conference","month":"03","file_date_updated":"2022-08-12T07:27:58Z","article_processing_charge":"No","doi":"10.1007/978-3-030-71278-5_18","oa_version":"Submitted Version","date_created":"2021-03-01T09:01:16Z","title":"Does SGD implicitly optimize for smoothness?","department":[{"_id":"ChLa"}],"publication_status":"published","intvolume":"     12544","language":[{"iso":"eng"}],"date_published":"2021-03-17T00:00:00Z","isi":1,"_id":"9210"},{"year":"2021","author":[{"full_name":"Bloch-Hansen, Andrew","first_name":"Andrew","last_name":"Bloch-Hansen"},{"full_name":"Samei, Nasim","last_name":"Samei","first_name":"Nasim","id":"C1531CAE-36E9-11EA-845F-33AA3DDC885E"},{"last_name":"Solis-Oba","first_name":"Roberto","full_name":"Solis-Oba, Roberto"}],"date_updated":"2025-09-10T10:01:54Z","scopus_import":"1","conference":{"location":"Rupnagar, India","name":"CALDAM: Conference on Algorithms and Discrete Applied Mathematics","start_date":"2021-02-11","end_date":"2021-02-13"},"publisher":"Springer Nature","page":"346-358","citation":{"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>","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>","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>.","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.","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>.","short":"A. Bloch-Hansen, N. Samei, R. Solis-Oba, in:, Conference on Algorithms and Discrete Applied Mathematics, Springer Nature, 2021, pp. 346–358."},"publication":"Conference on Algorithms and Discrete Applied Mathematics","status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","alternative_title":["LNCS"],"day":"28","volume":12601,"quality_controlled":"1","_id":"9227","isi":1,"date_published":"2021-01-28T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"     12601","department":[{"_id":"VlKo"}],"article_processing_charge":"No","doi":"10.1007/978-3-030-67899-9_28","oa_version":"None","date_created":"2021-03-07T23:01:25Z","title":"Experimental evaluation of a local search approximation algorithm for the multiway cut problem","external_id":{"isi":["001433483100028"]},"abstract":[{"lang":"eng","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."}],"type":"conference","month":"01","publication_identifier":{"isbn":["9783030678982"],"eissn":["1611-3349"],"issn":["0302-9743"]}},{"acknowledgement":"Peter Davies is supported by the European Union’s Horizon2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.","publication_identifier":{"isbn":["9783030795269"],"eisbn":["9783030795276"],"issn":["0302-9743"],"eissn":["1611-3349"]},"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"external_id":{"isi":["001292788400001"]},"abstract":[{"text":"In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).\r\n\r\nWe provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.","lang":"eng"}],"type":"conference","file_date_updated":"2021-07-01T11:21:40Z","month":"06","article_processing_charge":"No","oa_version":"Preprint","doi":"10.1007/978-3-030-79527-6_1","date_created":"2021-07-01T11:04:43Z","title":"Collecting coupons is faster with friends","department":[{"_id":"DaAl"}],"publication_status":"published","intvolume":"     12810","language":[{"iso":"eng"}],"date_published":"2021-06-20T00:00:00Z","isi":1,"_id":"9620","oa":1,"quality_controlled":"1","volume":12810,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","alternative_title":["LNCS"],"day":"20","page":"3-12","citation":{"short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 3–12.","chicago":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In <i>Structural Information and Communication Complexity</i>, 12810:3–12. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>.","ista":"Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends. Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.","apa":"Alistarh, D.-A., &#38; Davies, P. (2021). Collecting coupons is faster with friends. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>","ama":"Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:3-12. doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>","mla":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>.","ieee":"D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 3–12."},"ddc":["000"],"publication":"Structural Information and Communication Complexity","status":"public","has_accepted_license":"1","scopus_import":"1","ec_funded":1,"conference":{"end_date":"2021-07-01","start_date":"2021-06-28","name":"SIROCCO: International Colloquium on Structural Information and Communication Complexity","location":"Wrocław, Poland"},"file":[{"relation":"main_file","file_id":"9621","creator":"pdavies","file_name":"Population_Coupon_Collector.pdf","content_type":"application/pdf","checksum":"fe37fb9af3f5016c1084af9d6e7109bd","file_size":319728,"date_created":"2021-07-01T11:21:40Z","date_updated":"2021-07-01T11:21:40Z","access_level":"open_access"}],"publisher":"Springer Nature","date_updated":"2025-09-10T10:04:46Z","year":"2021","author":[{"orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian"},{"orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter","last_name":"Davies","first_name":"Peter"}]},{"language":[{"iso":"eng"}],"intvolume":"     13044","publication_status":"published","related_material":{"record":[{"relation":"dissertation_contains","id":"18088","status":"public"}]},"_id":"10408","isi":1,"date_published":"2021-11-04T00:00:00Z","month":"11","type":"conference","abstract":[{"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.","lang":"eng"}],"external_id":{"isi":["000728363700008"]},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"},{"grant_number":"665385","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["978-3-030-90456-2"],"isbn":["9-783-0309-0455-5"]},"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).","department":[{"_id":"KrPi"}],"title":"Grafting key trees: Efficient key management for overlapping groups","oa_version":"Preprint","doi":"10.1007/978-3-030-90456-2_8","date_created":"2021-12-05T23:01:42Z","article_processing_charge":"No","main_file_link":[{"url":"https://eprint.iacr.org/2021/1158","open_access":"1"}],"conference":{"start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography","location":"Raleigh, NC, United States"},"publisher":"Springer Nature","ec_funded":1,"scopus_import":"1","status":"public","publication":"19th International Conference","citation":{"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.","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>","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>","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>.","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."},"page":"222-253","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"last_name":"Auerbach","first_name":"Benedikt","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606"},{"full_name":"Baig, Mirza Ahad","last_name":"Baig","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"first_name":"Miguel","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen"},{"orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","first_name":"Michael","last_name":"Walter","full_name":"Walter, Michael"}],"year":"2021","date_updated":"2026-04-07T13:01:26Z","quality_controlled":"1","oa":1,"day":"04","alternative_title":["LNCS"],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","volume":13044},{"oa":1,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"day":"10","volume":13047,"ec_funded":1,"scopus_import":"1","conference":{"location":"Virtual","name":"FM: Formal Methods","start_date":"2021-11-20","end_date":"2021-11-26"},"publisher":"Springer Nature","citation":{"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>.","ieee":"K. Chatterjee, E. 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.","ama":"Chatterjee K, Goharshady E, 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>","apa":"Chatterjee, K., Goharshady, E., 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>","ista":"Chatterjee K, Goharshady E, 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.","short":"K. Chatterjee, E. Goharshady, P. Novotný, J. Zárevúcky, D. Zikelic, in:, 24th International Symposium on Formal Methods, Springer Nature, 2021, pp. 619–639.","chicago":"Chatterjee, Krishnendu, Ehsan 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>."},"page":"619-639","status":"public","publication":"24th International Symposium on Formal Methods","year":"2021","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kafshdar Goharshadi, Ehsan","first_name":"Ehsan","last_name":"Kafshdar Goharshadi","orcid":"0000-0002-8595-0587","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d"},{"first_name":"Petr","last_name":"Novotný","full_name":"Novotný, Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Zárevúcky","first_name":"Jiří","full_name":"Zárevúcky, Jiří"},{"first_name":"Dorde","last_name":"Zikelic","full_name":"Zikelic, Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699"}],"date_updated":"2026-04-07T13:27:55Z","project":[{"call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","grant_number":"665385","call_identifier":"H2020"}],"external_id":{"isi":["000758218600033"],"arxiv":["2108.02188"]},"abstract":[{"lang":"eng","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."}],"arxiv":1,"month":"11","type":"conference","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.","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-90870-6"],"isbn":["9-783-0309-0869-0"]},"department":[{"_id":"KrCh"}],"article_processing_charge":"No","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2108.02188"}],"doi":"10.1007/978-3-030-90870-6_33","date_created":"2021-12-05T23:01:45Z","oa_version":"Preprint","title":"On lexicographic proof rules for probabilistic termination","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"     13047","isi":1,"_id":"10414","related_material":{"record":[{"id":"14778","relation":"later_version","status":"public"},{"status":"public","relation":"dissertation_contains","id":"14539"}]},"date_published":"2021-11-10T00:00:00Z"}]