[{"file_date_updated":"2022-08-29T09:17:01Z","alternative_title":["LNCS"],"isi":1,"has_accepted_license":"1","status":"public","day":"07","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031131844"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"KrCh"}],"article_processing_charge":"Yes (in subscription journal)","publication_status":"published","external_id":{"isi":["000870304500004"]},"intvolume":"     13371","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.","doi":"10.1007/978-3-031-13185-1_4","ddc":["000"],"volume":13371,"scopus_import":"1","year":"2022","publication":"Proceedings of the 34th International Conference on Computer Aided Verification","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","call_identifier":"H2020"}],"date_published":"2022-08-07T00:00:00Z","file":[{"date_updated":"2022-08-29T09:17:01Z","relation":"main_file","content_type":"application/pdf","checksum":"24e0f810ec52735a90ade95198bc641d","file_id":"12003","access_level":"open_access","success":1,"file_name":"2022_LNCS_Chatterjee.pdf","creator":"alisjak","date_created":"2022-08-29T09:17:01Z","file_size":505094}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar","orcid":"0000-0003-1702-6584","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias","first_name":"Tobias"},{"full_name":"Zikelic, Dorde","first_name":"Dorde","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic"}],"date_created":"2022-08-28T22:02:02Z","title":"Sound and complete certificates for auantitative termination analysis of probabilistic programs","ec_funded":1,"oa_version":"Published Version","publisher":"Springer","quality_controlled":"1","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"date_updated":"2026-04-07T13:27:55Z","language":[{"iso":"eng"}],"license":"https://creativecommons.org/licenses/by/4.0/","abstract":[{"lang":"eng","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."}],"_id":"12000","type":"conference","month":"08","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"14539"}]},"citation":{"short":"K. Chatterjee, A.K. Goharshady, T. Meggendorfer, D. Zikelic, in:, Proceedings of the 34th International Conference on Computer Aided Verification, Springer, 2022, pp. 55–78.","apa":"Chatterjee, K., Goharshady, A. K., Meggendorfer, T., &#38; Zikelic, D. (2022). Sound and complete certificates for auantitative termination analysis of probabilistic programs. In <i>Proceedings of the 34th International Conference on Computer Aided Verification</i> (Vol. 13371, pp. 55–78). Haifa, Israel: Springer. <a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">https://doi.org/10.1007/978-3-031-13185-1_4</a>","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>","ista":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. 2022. Sound and complete certificates for auantitative termination analysis of probabilistic programs. Proceedings of the 34th International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13371, 55–78.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Tobias Meggendorfer, and Dorde Zikelic. “Sound and Complete Certificates for Auantitative Termination Analysis of Probabilistic Programs.” In <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, 13371:55–78. Springer, 2022. <a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">https://doi.org/10.1007/978-3-031-13185-1_4</a>.","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>.","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."},"conference":{"start_date":"2022-08-07","name":"CAV: Computer Aided Verification","end_date":"2022-08-10","location":"Haifa, Israel"},"page":"55-78","oa":1},{"isi":1,"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2105.02013","open_access":"1"}],"status":"public","alternative_title":["LNCS"],"publication_identifier":{"isbn":["9783030945824"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783030945831"]},"day":"14","department":[{"_id":"ToHe"}],"article_processing_charge":"No","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","external_id":{"arxiv":["2105.02013"],"isi":["001059208500001"]},"publication_status":"published","intvolume":"     13182","doi":"10.1007/978-3-030-94583-1_1","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.","volume":13182,"year":"2022","publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","scopus_import":"1","project":[{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems"}],"date_published":"2022-01-14T00:00:00Z","author":[{"last_name":"Bartocci","full_name":"Bartocci, Ezio","first_name":"Ezio"},{"first_name":"Thomas","full_name":"Ferrere, Thomas","id":"40960E6E-F248-11E8-B48F-1D18A9856A87","last_name":"Ferrere","orcid":"0000-0001-5199-3143"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724"},{"first_name":"Dejan","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","last_name":"Nickovic"},{"full_name":"Da Costa, Ana Oliveira","first_name":"Ana Oliveira","last_name":"Da Costa"}],"date_created":"2022-02-20T23:01:34Z","title":"Flavors of sequential information flow","oa_version":"Preprint","quality_controlled":"1","publisher":"Springer Nature","language":[{"iso":"eng"}],"date_updated":"2026-04-16T09:13:43Z","arxiv":1,"abstract":[{"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.","lang":"eng"}],"_id":"10774","month":"01","citation":{"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.","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>","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.","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>.","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."},"type":"conference","oa":1,"page":"1-19","conference":{"end_date":"2022-01-18","start_date":"2022-01-16","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","location":"Philadelphia, PA, United States"}},{"publication_status":"published","extern":"1","external_id":{"arxiv":["1910.03332"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","publication_identifier":{"isbn":["9783030835071"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783030835088"]},"day":"09","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.03332"}],"status":"public","scopus_import":"1","year":"2021","publication":"17th International Symposium on Algorithms and Data Structures","volume":12808,"doi":"10.1007/978-3-030-83508-8_34","intvolume":"     12808","author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"full_name":"Wu, Xiaowei","first_name":"Xiaowei","last_name":"Wu"}],"title":"Upper and lower bounds for fully retroactive graph problems","date_created":"2022-08-08T13:01:29Z","date_published":"2021-08-09T00:00:00Z","language":[{"iso":"eng"}],"date_updated":"2024-11-06T12:10:14Z","publisher":"Springer Nature","quality_controlled":"1","oa_version":"Preprint","arxiv":1,"conference":{"location":"Virtual","name":"WADS: Workshop on Algorithms and Data Structures","start_date":"2021-08-09","end_date":"2021-08-11"},"page":"471–484","oa":1,"month":"08","type":"conference","citation":{"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.","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>.","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>","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.","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.","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>"},"_id":"11771","abstract":[{"lang":"eng","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."}]},{"date_published":"2021-03-21T00:00:00Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"title":"On satisficing in quantitative games","date_created":"2023-03-26T22:01:09Z","author":[{"first_name":"Suguman","full_name":"Bansal, Suguman","last_name":"Bansal"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"full_name":"Vardi, Moshe Y.","first_name":"Moshe Y.","last_name":"Vardi"}],"ec_funded":1,"file":[{"date_updated":"2023-03-28T11:00:33Z","relation":"main_file","file_id":"12777","success":1,"access_level":"open_access","content_type":"application/pdf","checksum":"b020b78b23587ce7610b1aafb4e63438","file_name":"2021_LNCS_Bansal.pdf","creator":"dernst","date_created":"2023-03-28T11:00:33Z","file_size":747418}],"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.","doi":"10.1007/978-3-030-72016-2_2","ddc":["000"],"intvolume":"     12651","scopus_import":"1","publication":"27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","year":"2021","volume":12651,"day":"21","publication_identifier":{"isbn":["9783030720155"],"issn":["0302-9743"],"eissn":["1611-3349"]},"alternative_title":["LNCS"],"has_accepted_license":"1","status":"public","publication_status":"published","external_id":{"arxiv":["2101.02594"]},"article_processing_charge":"No","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2023-03-28T11:00:33Z","_id":"12767","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."}],"conference":{"location":"Luxembourg City, Luxembourg","start_date":"2021-03-27","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2021-04-01"},"page":"20-37","oa":1,"month":"03","type":"conference","citation":{"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.","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>","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>.","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.","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>","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>.","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."},"arxiv":1,"publisher":"Springer Nature","quality_controlled":"1","oa_version":"Published Version","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"date_updated":"2025-07-10T13:18:02Z","language":[{"iso":"eng"}]},{"publisher":"Springer Nature","quality_controlled":"1","oa_version":"Preprint","date_updated":"2025-04-14T07:22:06Z","language":[{"iso":"eng"}],"_id":"10609","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."}],"page":"335-364","conference":{"end_date":"2021-12-10","name":"ASIACRYPT: International Conference on Cryptology in Asia","start_date":"2021-12-06","location":"Virtual, Singapore"},"oa":1,"month":"12","citation":{"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>.","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.","ista":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for adaptively secure MPC without setup. 27th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: International Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364.","chicago":"Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar. “Reverse Firewalls for Adaptively Secure MPC without Setup.” In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, 13091:335–64. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>.","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>","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."},"type":"conference","day":"01","publication_identifier":{"eisbn":["978-3-030-92075-3"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["978-3-030-92074-6"]},"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1262"}],"status":"public","isi":1,"publication_status":"published","external_id":{"isi":["000927876200012"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"KrPi"}],"article_processing_charge":"No","doi":"10.1007/978-3-030-92075-3_12","intvolume":"     13091","scopus_import":"1","publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","year":"2021","volume":13091,"date_published":"2021-12-01T00:00:00Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"author":[{"full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty"},{"full_name":"Ganesh, Chaya","first_name":"Chaya","last_name":"Ganesh"},{"full_name":"Pancholi, Mahak","first_name":"Mahak","last_name":"Pancholi"},{"last_name":"Sarkar","full_name":"Sarkar, Pratik","first_name":"Pratik"}],"title":"Reverse firewalls for adaptively secure MPC without setup","date_created":"2022-01-09T23:01:27Z","ec_funded":1},{"conference":{"location":"Virtual","end_date":"2021-03-05","start_date":"2021-03-01","name":"FC: Financial Cryptography and Data Security"},"page":"431-450","oa":1,"month":"09","type":"conference","citation":{"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>.","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.","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.","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.","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>.","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>"},"_id":"10076","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"}],"date_updated":"2025-07-10T11:49:40Z","language":[{"iso":"eng"}],"publisher":"Springer Nature","quality_controlled":"1","oa_version":"Preprint","scopus_import":"1","year":"2021","publication":"FC 2021 Workshops","volume":"12676 ","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.","doi":"10.1007/978-3-662-63958-0_34","title":"Reactive key-loss protection in blockchains","date_created":"2021-10-03T22:01:24Z","author":[{"last_name":"Blackshear","full_name":"Blackshear, Sam","first_name":"Sam"},{"first_name":"Konstantinos","full_name":"Chalkias, Konstantinos","last_name":"Chalkias"},{"last_name":"Chatzigiannis","full_name":"Chatzigiannis, Panagiotis","first_name":"Panagiotis"},{"full_name":"Faizullabhoy, Riyaz","first_name":"Riyaz","last_name":"Faizullabhoy"},{"full_name":"Khaburzaniya, Irakliy","first_name":"Irakliy","last_name":"Khaburzaniya"},{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios"},{"first_name":"Joshua","full_name":"Lind, Joshua","last_name":"Lind"},{"first_name":"David","full_name":"Wong, David","last_name":"Wong"},{"full_name":"Zakian, Tim","first_name":"Tim","last_name":"Zakian"}],"date_published":"2021-09-17T00:00:00Z","publication_status":"published","external_id":{"isi":["000713005000034"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","department":[{"_id":"ElKo"}],"day":"17","publication_identifier":{"eisbn":["978-3-662-63958-0"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["978-3-6626-3957-3"]},"alternative_title":["LNCS"],"main_file_link":[{"url":"https://research.fb.com/publications/reactive-key-loss-protection-in-blockchains/","open_access":"1"}],"status":"public","isi":1},{"quality_controlled":"1","publisher":"Springer Nature","corr_author":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"date_updated":"2025-04-15T06:26:12Z","keyword":["run-time verification","software engineering","implicit specification"],"_id":"10108","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."}],"oa":1,"conference":{"name":"RV: Runtime Verification","start_date":"2021-10-11","end_date":"2021-10-14","location":"Virtual"},"page":"231-243","type":"conference","citation":{"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.","mla":"Mühlböck, Fabian, and Thomas A. Henzinger. “Differential Monitoring.” <i>International Conference on Runtime Verification</i>, vol. 12974, Springer Nature, 2021, pp. 231–43, doi:<a href=\"https://doi.org/10.1007/978-3-030-88494-9_12\">10.1007/978-3-030-88494-9_12</a>.","chicago":"Mühlböck, Fabian, and Thomas A Henzinger. “Differential Monitoring.” In <i>International Conference on Runtime Verification</i>, 12974:231–43. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-88494-9_12\">https://doi.org/10.1007/978-3-030-88494-9_12</a>.","ista":"Mühlböck F, Henzinger TA. 2021. Differential monitoring. International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 12974, 231–243.","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>","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>","short":"F. Mühlböck, T.A. Henzinger, in:, International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 231–243."},"month":"10","related_material":{"record":[{"relation":"extended_version","id":"9946","status":"public"}]},"file_date_updated":"2021-10-07T23:32:18Z","publication_identifier":{"eisbn":["978-3-030-88494-9"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["978-3-030-88493-2"]},"day":"06","status":"public","isi":1,"has_accepted_license":"1","alternative_title":["LNCS"],"external_id":{"isi":["000719383800012"]},"publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"ToHe"}],"article_processing_charge":"No","ddc":["005"],"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.","doi":"10.1007/978-3-030-88494-9_12","intvolume":"     12974","publication":"International Conference on Runtime Verification","year":"2021","scopus_import":"1","volume":12974,"date_published":"2021-10-06T00:00:00Z","project":[{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"date_created":"2021-10-07T23:30:10Z","author":[{"full_name":"Mühlböck, Fabian","first_name":"Fabian","orcid":"0000-0003-1548-0177","id":"6395C5F6-89DF-11E9-9C97-6BDFE5697425","last_name":"Mühlböck"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724"}],"place":"Cham","title":"Differential monitoring","file":[{"file_size":350632,"date_created":"2021-10-07T23:32:18Z","creator":"fmuehlbo","file_name":"differentialmonitoring-cameraready-openaccess.pdf","success":1,"access_level":"open_access","file_id":"10109","content_type":"application/pdf","checksum":"554c7fdb259eda703a8b6328a6dad55a","date_updated":"2021-10-07T23:32:18Z","relation":"main_file"}]},{"language":[{"iso":"eng"}],"date_updated":"2025-04-15T06:26:14Z","corr_author":"1","oa_version":"Preprint","quality_controlled":"1","publisher":"Springer Nature","related_material":{"record":[{"relation":"extended_version","id":"13234","status":"public"}]},"type":"conference","citation":{"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>","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.","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>.","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>","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."},"month":"10","oa":1,"page":"42-61","conference":{"location":"Virtual","name":"RV: Runtime Verification","start_date":"2021-10-11","end_date":"2021-10-14"},"abstract":[{"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.","lang":"eng"}],"keyword":["monitoring","neural networks","novelty detection"],"_id":"10206","arxiv":1,"department":[{"_id":"ToHe"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"isi":["000719383800003"],"arxiv":["2009.06429"]},"publication_status":"published","isi":1,"status":"public","main_file_link":[{"url":"https://arxiv.org/abs/2009.06429","open_access":"1"}],"alternative_title":["LNCS"],"publication_identifier":{"eisbn":["978-3-030-88494-9"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0308-8493-2"]},"day":"06","ec_funded":1,"place":"Cham","date_created":"2021-10-31T23:01:31Z","author":[{"last_name":"Lukina","id":"CBA4D1A8-0FE8-11E9-BDE6-07BFE5697425","first_name":"Anna","full_name":"Lukina, Anna"},{"first_name":"Christian","full_name":"Schilling, Christian","last_name":"Schilling","id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3658-1065"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"}],"title":"Into the unknown: active monitoring of neural networks","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"date_published":"2021-10-06T00:00:00Z","volume":"12974 ","publication":"21st International Conference on Runtime Verification","year":"2021","scopus_import":"1","doi":"10.1007/978-3-030-88494-9_3","acknowledgement":"We thank Christoph Lampert and Alex Greengold for fruitful discussions. This research was supported in part by the Simons Institute for the Theory of Computing, the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award), and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411."},{"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1905.11360"}],"isi":1,"status":"public","publication_identifier":{"isbn":["9-783-6626-4330-3"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-662-64331-0"]},"day":"23","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","department":[{"_id":"ElKo"}],"publication_status":"published","external_id":{"arxiv":["1905.11360"],"isi":["000712016200011"]},"date_published":"2021-10-23T00:00:00Z","date_created":"2021-11-21T23:01:29Z","author":[{"first_name":"Zeta","full_name":"Avarikioti, Zeta","last_name":"Avarikioti"},{"last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios"},{"first_name":"Roger","full_name":"Wattenhofer, Roger","last_name":"Wattenhofer"},{"last_name":"Zindros","full_name":"Zindros, Dionysis","first_name":"Dionysis"}],"title":"Brick: Asynchronous incentive-compatible payment channels","acknowledgement":"We would like to thank Kaoutar Elkhiyaoui for her valuable feedback as well as Jakub Sliwinski for his impactful contribution to this work.","doi":"10.1007/978-3-662-64331-0_11","volume":"12675 ","scopus_import":"1","year":"2021","publication":"25th International Conference on Financial Cryptography and Data Security","oa_version":"Preprint","publisher":"Springer Nature","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2023-08-14T12:59:58Z","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"}],"_id":"10324","citation":{"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>","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.","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.","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>.","ama":"Avarikioti Z, Kokoris Kogias E, Wattenhofer R, Zindros D. Brick: Asynchronous incentive-compatible payment channels. In: <i>25th International Conference on Financial Cryptography and Data Security</i>. Vol 12675. Springer Nature; 2021:209-230. doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_11\">10.1007/978-3-662-64331-0_11</a>","ieee":"Z. Avarikioti, E. Kokoris Kogias, R. Wattenhofer, and D. Zindros, “Brick: Asynchronous incentive-compatible payment channels,” in <i>25th International Conference on Financial Cryptography and Data Security</i>, Virtual, 2021, vol. 12675, pp. 209–230.","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>."},"type":"conference","month":"10","conference":{"location":"Virtual","start_date":"2021-03-01","name":"FC: Financial Cryptography","end_date":"2021-03-05"},"page":"209-230","oa":1,"arxiv":1},{"citation":{"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>.","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.","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>","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.","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>.","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>","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."},"type":"conference","month":"10","page":"3-36","conference":{"name":"FC: Financial Cryptography","start_date":"2021-03-01","end_date":"2021-03-05","location":"Virtual"},"oa":1,"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"}],"_id":"10325","language":[{"iso":"eng"}],"date_updated":"2023-08-14T12:59:26Z","oa_version":"Preprint","publisher":"Springer Nature","quality_controlled":"1","volume":"12675 ","scopus_import":"1","year":"2021","publication":"25th International Conference on Financial Cryptography and Data Security","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.","doi":"10.1007/978-3-662-64331-0_1","author":[{"full_name":"Zamyatin, Alexei","first_name":"Alexei","last_name":"Zamyatin"},{"last_name":"Al-Bassam","full_name":"Al-Bassam, Mustafa","first_name":"Mustafa"},{"first_name":"Dionysis","full_name":"Zindros, Dionysis","last_name":"Zindros"},{"first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"last_name":"Moreno-Sanchez","full_name":"Moreno-Sanchez, Pedro","first_name":"Pedro"},{"first_name":"Aggelos","full_name":"Kiayias, Aggelos","last_name":"Kiayias"},{"full_name":"Knottenbelt, William J.","first_name":"William J.","last_name":"Knottenbelt"}],"date_created":"2021-11-21T23:01:29Z","title":"SoK: Communication across distributed ledgers","date_published":"2021-10-23T00:00:00Z","article_processing_charge":"No","department":[{"_id":"ElKo"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","external_id":{"isi":["000712016200001"]},"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2019/1128","open_access":"1"}],"isi":1,"status":"public","day":"23","publication_identifier":{"isbn":["9-783-6626-4330-3"],"eisbn":["978-3-662-64331-0"],"eissn":["1611-3349"],"issn":["0302-9743"]}},{"intvolume":"     13043","doi":"10.1007/978-3-030-90453-1_14","volume":13043,"year":"2021","scopus_import":"1","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"date_published":"2021-11-04T00:00:00Z","ec_funded":1,"date_created":"2021-12-05T23:01:42Z","title":"Trojan-resilience without cryptography","author":[{"full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty"},{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"full_name":"Gałązka, Małgorzata","first_name":"Małgorzata","last_name":"Gałązka"},{"last_name":"Lizurej","first_name":"Tomasz","full_name":"Lizurej, Tomasz"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","orcid":"0009-0001-3676-4809","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"main_file_link":[{"url":"https://eprint.iacr.org/2021/1224","open_access":"1"}],"status":"public","isi":1,"alternative_title":["LNCS"],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"]},"day":"04","article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"KrPi"}],"external_id":{"isi":["000728364000014"]},"publication_status":"published","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."}],"_id":"10407","type":"conference","citation":{"ista":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. 2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference, LNCS, vol. 13043, 397–428.","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,” 13043:397–428. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>.","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>","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>","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","ieee":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 397–428.","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>."},"month":"11","oa":1,"conference":{"end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08","location":"Raleigh, NC, United States"},"page":"397-428","oa_version":"Preprint","quality_controlled":"1","publisher":"Springer Nature","date_updated":"2025-04-14T07:22:05Z","language":[{"iso":"eng"}]},{"quality_controlled":"1","publisher":"Springer Nature","oa_version":"Preprint","language":[{"iso":"eng"}],"date_updated":"2025-04-15T08:32:06Z","_id":"10409","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."}],"oa":1,"page":"486-517","conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","name":"TCC: Theory of Cryptography","start_date":"2021-11-08"},"month":"11","related_material":{"record":[{"id":"10044","status":"public","relation":"earlier_version"}]},"citation":{"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>.","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.","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>","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>.","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>"},"type":"conference","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"]},"day":"04","isi":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"status":"public","alternative_title":["LNCS"],"external_id":{"isi":["000728364000017"]},"publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"KrPi"}],"article_processing_charge":"No","date_published":"2021-11-04T00:00:00Z","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"ec_funded":1,"title":"On treewidth, separators and Yao’s garbling","date_created":"2021-12-05T23:01:43Z","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"doi":"10.1007/978-3-030-90453-1_17","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.","year":"2021","publication":"19th International Conference","scopus_import":"1","volume":"13043 "},{"type":"conference","related_material":{"record":[{"status":"public","id":"10048","relation":"earlier_version"}]},"citation":{"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>.","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.","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>.","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>","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, 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>"},"month":"11","page":"550-581","conference":{"start_date":"2021-11-08","name":"TCC: Theory of Cryptography","end_date":"2021-11-11","location":"Raleigh, NC, United States"},"oa":1,"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."}],"_id":"10410","date_updated":"2025-04-14T07:22:05Z","language":[{"iso":"eng"}],"oa_version":"Preprint","publisher":"Springer Nature","quality_controlled":"1","volume":13043,"scopus_import":"1","year":"2021","publication":"19th International Conference","intvolume":"     13043","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).","doi":"10.1007/978-3-030-90453-1_19","title":"The cost of adaptivity in security games on graphs","author":[{"first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Karen","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","full_name":"Walter, Michael","first_name":"Michael"}],"date_created":"2021-12-05T23:01:43Z","ec_funded":1,"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","department":[{"_id":"KrPi"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","external_id":{"isi":["000728364000019"]},"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"status":"public","isi":1,"publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"day":"04"},{"date_published":"2021-03-17T00:00:00Z","file":[{"file_name":"2020_GCPR_submitted_Volhejn.pdf","file_id":"11820","access_level":"open_access","success":1,"checksum":"3e3628ab1cf658d82524963f808004ea","content_type":"application/pdf","date_updated":"2022-08-12T07:27:58Z","relation":"main_file","file_size":420234,"date_created":"2022-08-12T07:27:58Z","creator":"dernst"}],"author":[{"full_name":"Volhejn, Vaclav","first_name":"Vaclav","last_name":"Volhejn","id":"d5235fb4-7a6d-11eb-b254-f25d12d631a8"},{"orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","full_name":"Lampert, Christoph","first_name":"Christoph"}],"date_created":"2021-03-01T09:01:16Z","title":"Does SGD implicitly optimize for smoothness?","intvolume":"     12544","ddc":["510"],"doi":"10.1007/978-3-030-71278-5_18","volume":12544,"year":"2021","publication":"42nd German Conference on Pattern Recognition","scopus_import":"1","has_accepted_license":"1","status":"public","isi":1,"day":"17","publication_identifier":{"isbn":["9783030712778"],"issn":["0302-9743"],"eissn":["1611-3349"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"ChLa"}],"article_processing_charge":"No","series_title":"LNCS","external_id":{"isi":["001500603200018"]},"publication_status":"published","file_date_updated":"2022-08-12T07:27:58Z","abstract":[{"text":"Modern neural networks can easily fit their training set perfectly. Surprisingly, despite being “overfit” in this way, they tend to generalize well to future data, thereby defying the classic bias–variance trade-off of machine learning theory. Of the many possible explanations, a prevalent one is that training by stochastic gradient descent (SGD) imposes an implicit bias that leads it to learn simple functions, and these simple functions generalize well. However, the specifics of this implicit bias are not well understood.\r\nIn this work, we explore the smoothness conjecture which states that SGD is implicitly biased towards learning functions that are smooth. We propose several measures to formalize the intuitive notion of smoothness, and we conduct experiments to determine whether SGD indeed implicitly optimizes for these measures. Our findings rule out the possibility that smoothness measures based on first-order derivatives are being implicitly enforced. They are supportive, though, of the smoothness conjecture for measures based on second-order derivatives.","lang":"eng"}],"_id":"9210","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.","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>.","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>","short":"V. Volhejn, C. Lampert, in:, 42nd German Conference on Pattern Recognition, Springer, 2021, 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>","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.","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>."},"type":"conference","month":"03","oa":1,"page":"246-259","conference":{"location":"Tübingen, Germany","end_date":"2020-10-01","start_date":"2020-09-28","name":"DAGM GCPR: German Conference on Pattern Recognition "},"oa_version":"Submitted Version","quality_controlled":"1","publisher":"Springer","language":[{"iso":"eng"}],"date_updated":"2025-09-10T10:00:33Z"},{"date_updated":"2025-09-10T10:01:54Z","language":[{"iso":"eng"}],"quality_controlled":"1","publisher":"Springer Nature","oa_version":"None","page":"346-358","conference":{"name":"CALDAM: Conference on Algorithms and Discrete Applied Mathematics","start_date":"2021-02-11","end_date":"2021-02-13","location":"Rupnagar, India"},"citation":{"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.","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>.","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.","ama":"Bloch-Hansen A, Samei N, Solis-Oba R. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In: <i>Conference on Algorithms and Discrete Applied Mathematics</i>. Vol 12601. Springer Nature; 2021:346-358. doi:<a href=\"https://doi.org/10.1007/978-3-030-67899-9_28\">10.1007/978-3-030-67899-9_28</a>","apa":"Bloch-Hansen, A., Samei, N., &#38; Solis-Oba, R. (2021). Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In <i>Conference on Algorithms and Discrete Applied Mathematics</i> (Vol. 12601, pp. 346–358). Rupnagar, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-67899-9_28\">https://doi.org/10.1007/978-3-030-67899-9_28</a>","short":"A. Bloch-Hansen, N. Samei, R. Solis-Oba, in:, Conference on Algorithms and Discrete Applied Mathematics, Springer Nature, 2021, pp. 346–358."},"month":"01","type":"conference","_id":"9227","abstract":[{"text":"In the multiway cut problem we are given a weighted undirected graph   G=(V,E)  and a set   T⊆V  of k terminals. The goal is to find a minimum weight set of edges   E′⊆E  with the property that by removing   E′  from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio   2−2k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem.","lang":"eng"}],"external_id":{"isi":["001433483100028"]},"publication_status":"published","department":[{"_id":"VlKo"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","publication_identifier":{"isbn":["9783030678982"],"issn":["0302-9743"],"eissn":["1611-3349"]},"day":"28","isi":1,"status":"public","alternative_title":["LNCS"],"year":"2021","publication":"Conference on Algorithms and Discrete Applied Mathematics","scopus_import":"1","volume":12601,"doi":"10.1007/978-3-030-67899-9_28","intvolume":"     12601","author":[{"first_name":"Andrew","full_name":"Bloch-Hansen, Andrew","last_name":"Bloch-Hansen"},{"full_name":"Samei, Nasim","first_name":"Nasim","last_name":"Samei","id":"C1531CAE-36E9-11EA-845F-33AA3DDC885E"},{"first_name":"Roberto","full_name":"Solis-Oba, Roberto","last_name":"Solis-Oba"}],"title":"Experimental evaluation of a local search approximation algorithm for the multiway cut problem","date_created":"2021-03-07T23:01:25Z","date_published":"2021-01-28T00:00:00Z"},{"day":"20","publication_identifier":{"eisbn":["9783030795276"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030795269"]},"alternative_title":["LNCS"],"has_accepted_license":"1","isi":1,"status":"public","publication_status":"published","external_id":{"isi":["001292788400001"]},"department":[{"_id":"DaAl"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","file_date_updated":"2021-07-01T11:21:40Z","date_published":"2021-06-20T00:00:00Z","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"author":[{"first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter","full_name":"Davies, Peter"}],"date_created":"2021-07-01T11:04:43Z","title":"Collecting coupons is faster with friends","ec_funded":1,"file":[{"creator":"pdavies","date_created":"2021-07-01T11:21:40Z","file_size":319728,"date_updated":"2021-07-01T11:21:40Z","relation":"main_file","file_id":"9621","access_level":"open_access","checksum":"fe37fb9af3f5016c1084af9d6e7109bd","content_type":"application/pdf","file_name":"Population_Coupon_Collector.pdf"}],"doi":"10.1007/978-3-030-79527-6_1","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.","ddc":["000"],"intvolume":"     12810","scopus_import":"1","year":"2021","publication":"Structural Information and Communication Complexity","volume":12810,"publisher":"Springer Nature","quality_controlled":"1","oa_version":"Preprint","date_updated":"2025-09-10T10:04:46Z","language":[{"iso":"eng"}],"_id":"9620","abstract":[{"lang":"eng","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."}],"conference":{"location":"Wrocław, Poland","end_date":"2021-07-01","name":"SIROCCO: International Colloquium on Structural Information and Communication Complexity","start_date":"2021-06-28"},"page":"3-12","oa":1,"type":"conference","citation":{"short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 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>","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.","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>.","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."},"month":"06"},{"external_id":{"isi":["000728363700008"]},"publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"KrPi"}],"article_processing_charge":"No","day":"04","publication_identifier":{"isbn":["9-783-0309-0455-5"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-90456-2"]},"isi":1,"main_file_link":[{"url":"https://eprint.iacr.org/2021/1158","open_access":"1"}],"status":"public","alternative_title":["LNCS"],"publication":"19th International Conference","year":"2021","scopus_import":"1","volume":13044,"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).","doi":"10.1007/978-3-030-90456-2_8","intvolume":"     13044","ec_funded":1,"date_created":"2021-12-05T23:01:42Z","title":"Grafting key trees: Efficient key management for overlapping groups","author":[{"full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","orcid":"0000-0002-7553-6606","first_name":"Benedikt","full_name":"Auerbach, Benedikt"},{"full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig"},{"full_name":"Cueto Noval, Miguel","first_name":"Miguel","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482","first_name":"Michael","full_name":"Walter, Michael"}],"date_published":"2021-11-04T00:00:00Z","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"},{"name":"International IST Doctoral Program","call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"date_updated":"2026-04-07T13:01:26Z","language":[{"iso":"eng"}],"quality_controlled":"1","publisher":"Springer Nature","oa_version":"Preprint","oa":1,"conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11"},"page":"222-253","type":"conference","month":"11","related_material":{"record":[{"status":"public","id":"18088","relation":"dissertation_contains"}]},"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.","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>.","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>","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>.","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.","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.","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>"},"_id":"10408","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"}]},{"arxiv":1,"citation":{"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>","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.","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.","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>.","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>","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.","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>."},"related_material":{"record":[{"id":"14778","status":"public","relation":"later_version"},{"status":"public","id":"14539","relation":"dissertation_contains"}]},"month":"11","type":"conference","conference":{"location":"Virtual","name":"FM: Formal Methods","start_date":"2021-11-20","end_date":"2021-11-26"},"page":"619-639","oa":1,"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."}],"_id":"10414","date_updated":"2026-04-07T13:27:55Z","language":[{"iso":"eng"}],"oa_version":"Preprint","publisher":"Springer Nature","quality_controlled":"1","volume":13047,"scopus_import":"1","publication":"24th International Symposium on Formal Methods","year":"2021","intvolume":"     13047","doi":"10.1007/978-3-030-90870-6_33","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.","title":"On lexicographic proof rules for probabilistic termination","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","last_name":"Kafshdar Goharshadi","orcid":"0000-0002-8595-0587","first_name":"Ehsan","full_name":"Kafshdar Goharshadi, Ehsan"},{"last_name":"Novotný","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","full_name":"Novotný, Petr","first_name":"Petr"},{"full_name":"Zárevúcky, Jiří","first_name":"Jiří","last_name":"Zárevúcky"},{"last_name":"Zikelic","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","first_name":"Dorde","full_name":"Zikelic, Dorde"}],"date_created":"2021-12-05T23:01:45Z","ec_funded":1,"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"call_identifier":"H2020","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385"}],"date_published":"2021-11-10T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"article_processing_charge":"No","publication_status":"published","external_id":{"arxiv":["2108.02188"],"isi":["000758218600033"]},"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2108.02188"}],"status":"public","isi":1,"day":"10","publication_identifier":{"eisbn":["978-3-030-90870-6"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0869-0"]}},{"arxiv":1,"conference":{"location":"Virtual","end_date":"2021-07-23","name":"CAV: Computer Aided Verification ","start_date":"2021-07-20"},"page":"341-366","oa":1,"citation":{"ama":"Agarwal P, Chatterjee K, Pathak S, Pavlogiannis A, Toman V. Stateless model checking under a reads-value-from equivalence. In: <i>33rd International Conference on Computer-Aided Verification </i>. Vol 12759. Springer Nature; 2021:341-366. doi:<a href=\"https://doi.org/10.1007/978-3-030-81685-8_16\">10.1007/978-3-030-81685-8_16</a>","ista":"Agarwal P, Chatterjee K, Pathak S, Pavlogiannis A, Toman V. 2021. Stateless model checking under a reads-value-from equivalence. 33rd International Conference on Computer-Aided Verification . CAV: Computer Aided Verification , LNCS, vol. 12759, 341–366.","chicago":"Agarwal, Pratyush, Krishnendu Chatterjee, Shreya Pathak, Andreas Pavlogiannis, and Viktor Toman. “Stateless Model Checking under a Reads-Value-from Equivalence.” In <i>33rd International Conference on Computer-Aided Verification </i>, 12759:341–66. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-81685-8_16\">https://doi.org/10.1007/978-3-030-81685-8_16</a>.","apa":"Agarwal, P., Chatterjee, K., Pathak, S., Pavlogiannis, A., &#38; Toman, V. (2021). Stateless model checking under a reads-value-from equivalence. In <i>33rd International Conference on Computer-Aided Verification </i> (Vol. 12759, pp. 341–366). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-81685-8_16\">https://doi.org/10.1007/978-3-030-81685-8_16</a>","short":"P. Agarwal, K. Chatterjee, S. Pathak, A. Pavlogiannis, V. Toman, in:, 33rd International Conference on Computer-Aided Verification , Springer Nature, 2021, pp. 341–366.","ieee":"P. Agarwal, K. Chatterjee, S. Pathak, A. Pavlogiannis, and V. Toman, “Stateless model checking under a reads-value-from equivalence,” in <i>33rd International Conference on Computer-Aided Verification </i>, Virtual, 2021, vol. 12759, pp. 341–366.","mla":"Agarwal, Pratyush, et al. “Stateless Model Checking under a Reads-Value-from Equivalence.” <i>33rd International Conference on Computer-Aided Verification </i>, vol. 12759, Springer Nature, 2021, pp. 341–66, doi:<a href=\"https://doi.org/10.1007/978-3-030-81685-8_16\">10.1007/978-3-030-81685-8_16</a>."},"month":"07","type":"conference","related_material":{"record":[{"relation":"dissertation_contains","id":"10199","status":"public"}]},"_id":"9987","abstract":[{"text":"Stateless model checking (SMC) is one of the standard approaches to the verification of concurrent programs. As scheduling non-determinism creates exponentially large spaces of thread interleavings, SMC attempts to partition this space into equivalence classes and explore only a few representatives from each class. The efficiency of this approach depends on two factors: (a) the coarseness of the partitioning, and (b) the time to generate representatives in each class. For this reason, the search for coarse partitionings that are efficiently explorable is an active research challenge. In this work we present   RVF-SMC , a new SMC algorithm that uses a novel reads-value-from (RVF) partitioning. Intuitively, two interleavings are deemed equivalent if they agree on the value obtained in each read event, and read events induce consistent causal orderings between them. The RVF partitioning is provably coarser than recent approaches based on Mazurkiewicz and “reads-from” partitionings. Our experimental evaluation reveals that RVF is quite often a very effective equivalence, as the underlying partitioning is exponentially coarser than other approaches. Moreover,   RVF-SMC  generates representatives very efficiently, as the reduction in the partitioning is often met with significant speed-ups in the model checking task.","lang":"eng"}],"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"date_updated":"2026-04-08T07:00:30Z","publisher":"Springer Nature","quality_controlled":"1","oa_version":"Published Version","corr_author":"1","scopus_import":"1","year":"2021","publication":"33rd International Conference on Computer-Aided Verification ","volume":"12759 ","doi":"10.1007/978-3-030-81685-8_16","acknowledgement":"The research was partially funded by the ERC CoG 863818 (ForM-SMArt) and the Vienna Science and Technology Fund (WWTF) through project ICT15-003.","ddc":["000"],"title":"Stateless model checking under a reads-value-from equivalence","author":[{"first_name":"Pratyush","full_name":"Agarwal, Pratyush","last_name":"Agarwal"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Shreya","full_name":"Pathak, Shreya","last_name":"Pathak"},{"orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","first_name":"Andreas"},{"full_name":"Toman, Viktor","first_name":"Viktor","orcid":"0000-0001-9036-063X","id":"3AF3DA7C-F248-11E8-B48F-1D18A9856A87","last_name":"Toman"}],"date_created":"2021-09-05T22:01:24Z","ec_funded":1,"file":[{"file_size":1516756,"creator":"dernst","date_created":"2022-05-13T07:00:20Z","file_name":"2021_LNCS_Agarwal.pdf","relation":"main_file","date_updated":"2022-05-13T07:00:20Z","content_type":"application/pdf","checksum":"4b346e5fbaa8b9bdf107819c7b2aadee","success":1,"access_level":"open_access","file_id":"11368"}],"date_published":"2021-07-15T00:00:00Z","project":[{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"},{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"file_date_updated":"2022-05-13T07:00:20Z","publication_status":"published","external_id":{"isi":["000698732400016"],"arxiv":["2105.06424"]},"article_processing_charge":"Yes","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"KrCh"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["978-3-030-81685-8"],"isbn":["978-3-030-81684-1"]},"day":"15","alternative_title":["LNCS"],"has_accepted_license":"1","isi":1,"status":"public"},{"date_published":"2021-08-11T00:00:00Z","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"title":"Limits on the Adaptive Security of Yao’s Garbling","author":[{"first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","orcid":"0009-0006-6812-7317"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"full_name":"Wichs, Daniel","first_name":"Daniel","last_name":"Wichs"}],"place":"Cham","date_created":"2021-09-23T14:06:15Z","ec_funded":1,"doi":"10.1007/978-3-030-84245-1_17","acknowledgement":"We would like to thank the anonymous reviewers of Crypto’21 whose detailed comments helped us considerably improve the presentation of the paper.","intvolume":"     12826","scopus_import":"1","publication":"41st Annual International Cryptology Conference, Part II ","year":"2021","volume":12826,"publication_identifier":{"isbn":["978-3-030-84244-4"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["978-3-030-84245-1"]},"day":"11","alternative_title":["LCNS"],"status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2021/945","open_access":"1"}],"isi":1,"publication_status":"published","external_id":{"isi":["000696697800017"]},"department":[{"_id":"KrPi"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","_id":"10041","abstract":[{"lang":"eng","text":"Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth   δ , the loss in security is at most exponential in   δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth  δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in   δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security."}],"conference":{"location":"Virtual","start_date":"2021-08-16","name":"CRYPTO: Annual International Cryptology Conference","end_date":"2021-08-20"},"page":"486-515","oa":1,"citation":{"ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security of Yao’s Garbling. In: <i>41st Annual International Cryptology Conference, Part II </i>. Vol 12826. Cham: Springer Nature; 2021:486-515. doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In <i>41st Annual International Cryptology Conference, Part II </i>, 12826:486–515. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Wichs, D. (2021). Limits on the Adaptive Security of Yao’s Garbling. In <i>41st Annual International Cryptology Conference, Part II </i> (Vol. 12826, pp. 486–515). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the Adaptive Security of Yao’s Garbling,” in <i>41st Annual International Cryptology Conference, Part II </i>, Virtual, 2021, vol. 12826, pp. 486–515.","mla":"Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.” <i>41st Annual International Cryptology Conference, Part II </i>, vol. 12826, Springer Nature, 2021, pp. 486–515, doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>."},"month":"08","related_material":{"record":[{"relation":"dissertation_contains","id":"10035","status":"public"}]},"type":"conference","publisher":"Springer Nature","quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"date_updated":"2026-04-08T07:01:43Z"}]