[{"language":[{"iso":"eng"}],"doi":"10.1007/978-3-031-19992-9_22","acknowledgement":"This work was supported in part by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no. 847635, by the ERC-2020-AdG 101020093, by DIREC - Digital Research Centre Denmark, and by the Villum Investigator Grant S4OS.","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"day":"21","alternative_title":["LNCS"],"author":[{"orcid":"0000-0003-2936-5719","id":"4B3207F6-F248-11E8-B48F-1D18A9856A87","first_name":"Miriam","full_name":"Garcia Soto, Miriam","last_name":"Garcia Soto"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724"},{"last_name":"Schilling","full_name":"Schilling, Christian","first_name":"Christian","orcid":"0000-0003-3658-1065","id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","ec_funded":1,"citation":{"mla":"Garcia Soto, Miriam, et al. “Synthesis of Parametric Hybrid Automata from Time Series.” 20th International Symposium on Automated Technology for Verification and Analysis, vol. 13505, Springer Nature, 2022, pp. 337–53, doi:10.1007/978-3-031-19992-9_22.","chicago":"Garcia Soto, Miriam, Thomas A Henzinger, and Christian Schilling. “Synthesis of Parametric Hybrid Automata from Time Series.” In 20th International Symposium on Automated Technology for Verification and Analysis, 13505:337–53. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-19992-9_22.","ista":"Garcia Soto M, Henzinger TA, Schilling C. 2022. Synthesis of parametric hybrid automata from time series. 20th International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 13505, 337–353.","ieee":"M. Garcia Soto, T. A. Henzinger, and C. Schilling, “Synthesis of parametric hybrid automata from time series,” in 20th International Symposium on Automated Technology for Verification and Analysis, Virtual, 2022, vol. 13505, pp. 337–353.","ama":"Garcia Soto M, Henzinger TA, Schilling C. Synthesis of parametric hybrid automata from time series. In: 20th International Symposium on Automated Technology for Verification and Analysis. Vol 13505. Springer Nature; 2022:337-353. doi:10.1007/978-3-031-19992-9_22","apa":"Garcia Soto, M., Henzinger, T. A., & Schilling, C. (2022). Synthesis of parametric hybrid automata from time series. In 20th International Symposium on Automated Technology for Verification and Analysis (Vol. 13505, pp. 337–353). Virtual: Springer Nature. https://doi.org/10.1007/978-3-031-19992-9_22","short":"M. Garcia Soto, T.A. Henzinger, C. Schilling, in:, 20th International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2022, pp. 337–353."},"conference":{"location":"Virtual","end_date":"2022-10-28","start_date":"2022-10-25","name":"ATVA: Automated Technology for Verification and Analysis"},"title":"Synthesis of parametric hybrid automata from time series","department":[{"_id":"ToHe"}],"quality_controlled":"1","publication":"20th International Symposium on Automated Technology for Verification and Analysis","intvolume":" 13505","status":"public","publisher":"Springer Nature","month":"10","date_created":"2023-01-12T12:11:16Z","page":"337-353","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-13T09:27:55Z","external_id":{"arxiv":["2208.06383"]},"scopus_import":"1","publication_identifier":{"eisbn":["9783031199929"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031199912"]},"year":"2022","oa_version":"Preprint","volume":13505,"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2208.06383"}],"abstract":[{"lang":"eng","text":"We propose an algorithmic approach for synthesizing linear hybrid automata from time-series data. Unlike existing approaches, our approach provides a whole family of models with the same discrete structure but different dynamics. Each model in the family is guaranteed to capture the input data up to a precision error ε, in the following sense: For each time series, the model contains an execution that is ε-close to the data points. Our construction allows to effectively choose a model from this family with minimal precision error ε. We demonstrate the algorithm’s efficiency and its ability to find precise models in two case studies."}],"_id":"12171","date_published":"2022-10-21T00:00:00Z","arxiv":1,"article_processing_charge":"No"},{"date_published":"2022-10-12T00:00:00Z","_id":"12175","abstract":[{"lang":"eng","text":"An automaton is history-deterministic (HD) if one can safely resolve its non-deterministic choices on the fly. In a recent paper, Henzinger, Lehtinen and Totzke studied this in the context of Timed Automata [9], where it was conjectured that the class of timed ω-languages recognised by HD-timed automata strictly extends that of deterministic ones. We provide a proof for this fact."}],"article_processing_charge":"No","volume":13608,"oa":1,"main_file_link":[{"url":"https://hal.science/hal-03849398/","open_access":"1"}],"publication_status":"published","oa_version":"Preprint","year":"2022","publication_identifier":{"eisbn":["9783031191350"],"eissn":["1611-3349"],"isbn":["9783031191343"],"issn":["0302-9743"]},"scopus_import":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_updated":"2023-09-05T15:12:08Z","date_created":"2023-01-12T12:11:57Z","month":"10","page":"67-76","status":"public","intvolume":" 13608","publication":"16th International Conference on Reachability Problems","quality_controlled":"1","department":[{"_id":"ToHe"}],"publisher":"Springer Nature","author":[{"last_name":"Bose","first_name":"Sougata","full_name":"Bose, Sougata"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"last_name":"Lehtinen","first_name":"Karoliina","full_name":"Lehtinen, Karoliina"},{"first_name":"Sven","full_name":"Schewe, Sven","last_name":"Schewe"},{"full_name":"Totzke, Patrick","first_name":"Patrick","last_name":"Totzke"}],"type":"conference","alternative_title":["LNCS"],"day":"12","title":"History-deterministic timed automata are not determinizable","conference":{"location":"Kaiserslautern, Germany","start_date":"2022-10-17","end_date":"2022-10-21","name":"RC: Reachability Problems"},"citation":{"ama":"Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. History-deterministic timed automata are not determinizable. In: 16th International Conference on Reachability Problems. Vol 13608. Springer Nature; 2022:67-76. doi:10.1007/978-3-031-19135-0_5","apa":"Bose, S., Henzinger, T. A., Lehtinen, K., Schewe, S., & Totzke, P. (2022). History-deterministic timed automata are not determinizable. In 16th International Conference on Reachability Problems (Vol. 13608, pp. 67–76). Kaiserslautern, Germany: Springer Nature. https://doi.org/10.1007/978-3-031-19135-0_5","short":"S. Bose, T.A. Henzinger, K. Lehtinen, S. Schewe, P. Totzke, in:, 16th International Conference on Reachability Problems, Springer Nature, 2022, pp. 67–76.","mla":"Bose, Sougata, et al. “History-Deterministic Timed Automata Are Not Determinizable.” 16th International Conference on Reachability Problems, vol. 13608, Springer Nature, 2022, pp. 67–76, doi:10.1007/978-3-031-19135-0_5.","chicago":"Bose, Sougata, Thomas A Henzinger, Karoliina Lehtinen, Sven Schewe, and Patrick Totzke. “History-Deterministic Timed Automata Are Not Determinizable.” In 16th International Conference on Reachability Problems, 13608:67–76. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-19135-0_5.","ieee":"S. Bose, T. A. Henzinger, K. Lehtinen, S. Schewe, and P. Totzke, “History-deterministic timed automata are not determinizable,” in 16th International Conference on Reachability Problems, Kaiserslautern, Germany, 2022, vol. 13608, pp. 67–76.","ista":"Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. 2022. History-deterministic timed automata are not determinizable. 16th International Conference on Reachability Problems. RC: Reachability Problems, LNCS, vol. 13608, 67–76."},"ec_funded":1,"doi":"10.1007/978-3-031-19135-0_5","language":[{"iso":"eng"}],"project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093, the EPSRC project EP/V025848/1, and the EPSRC project EP/X017796/1."},{"page":"370-399","month":"10","date_created":"2023-01-12T12:12:07Z","publisher":"Springer Nature","isi":1,"publication":"Advances in Cryptology – CRYPTO 2022","department":[{"_id":"KrPi"}],"quality_controlled":"1","intvolume":" 13508","status":"public","citation":{"ieee":"C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical statistically-sound proofs of exponentiation in any group,” in Advances in Cryptology – CRYPTO 2022, Santa Barbara, CA, United States, 2022, vol. 13508, pp. 370–399.","ista":"Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYYPTO: International Cryptology Conference, LNCS, vol. 13508, 370–399.","chicago":"Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.” In Advances in Cryptology – CRYPTO 2022, 13508:370–99. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-15979-4_13.","mla":"Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.” Advances in Cryptology – CRYPTO 2022, vol. 13508, Springer Nature, 2022, pp. 370–99, doi:10.1007/978-3-031-15979-4_13.","short":"C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.","apa":"Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., & Pietrzak, K. Z. (2022). Practical statistically-sound proofs of exponentiation in any group. In Advances in Cryptology – CRYPTO 2022 (Vol. 13508, pp. 370–399). Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-031-15979-4_13","ama":"Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound proofs of exponentiation in any group. In: Advances in Cryptology – CRYPTO 2022. Vol 13508. Springer Nature; 2022:370-399. doi:10.1007/978-3-031-15979-4_13"},"title":"Practical statistically-sound proofs of exponentiation in any group","conference":{"name":"CRYYPTO: International Cryptology Conference","end_date":"2022-08-18","start_date":"2022-08-15","location":"Santa Barbara, CA, United States"},"day":"13","author":[{"last_name":"Hoffmann","full_name":"Hoffmann, Charlotte","first_name":"Charlotte","orcid":"0000-0003-2027-5549","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7"},{"last_name":"Hubáček","full_name":"Hubáček, Pavel","first_name":"Pavel"},{"first_name":"Chethan","full_name":"Kamath, Chethan","last_name":"Kamath"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"}],"type":"conference","alternative_title":["LNCS"],"acknowledgement":"We would like to thank the authors of [BHR+21] for clarifying several questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19. Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part of this work at Institute of Science and Technology Austria.","language":[{"iso":"eng"}],"doi":"10.1007/978-3-031-15979-4_13","article_processing_charge":"No","_id":"12176","date_published":"2022-10-13T00:00:00Z","abstract":[{"lang":"eng","text":"A proof of exponentiation (PoE) in a group G of unknown order allows a prover to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive has recently found exciting applications in the constructions of verifiable delay functions and succinct arguments of knowledge. The most practical PoEs only achieve soundness either under computational assumptions, i.e., they are arguments (Wesolowski, Journal of Cryptology 2020), or in groups that come with the promise of not having any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in general groups of unknown order is due to Block et al. (CRYPTO 2021), and can be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits of security, say λ=80, the number of repetitions required (and thus the blow-up in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound PoE for the case where the exponent q is the product of all primes up to some bound B. We show that, in this case, it suffices to run only λ/log(B) parallel instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to Block et al. by an order of magnitude. Furthermore, we show that in the known applications where PoEs are used as a building block such structured exponents are viable. Finally, we also discuss batching of our PoE, showing that many proofs (for the same G and q but different x and T) can be batched by adding only a single element to the proof per additional statement."}],"publication_status":"published","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2022/1021","open_access":"1"}],"volume":13508,"oa_version":"Preprint","year":"2022","external_id":{"isi":["000886792700013"]},"scopus_import":"1","date_updated":"2023-09-05T15:12:27Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031159787"],"eissn":["1611-3349"],"eisbn":["9783031159794"]}},{"page":"296-315","date_created":"2023-01-16T10:05:51Z","month":"10","publisher":"Springer Nature","intvolume":" 13411","status":"public","publication":"Financial Cryptography and Data Security","quality_controlled":"1","department":[{"_id":"ElKo"}],"title":"Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback","conference":{"name":"FC: Financial Cryptography","end_date":"2022-05-06","start_date":"2022-05-02","location":"Radisson Grenada Beach Resort, Grenada"},"citation":{"short":"R. Gelashvili, E. Kokoris Kogias, A. Sonnino, A. Spiegelman, Z. Xiang, in:, Financial Cryptography and Data Security, Springer Nature, 2022, pp. 296–315.","ama":"Gelashvili R, Kokoris Kogias E, Sonnino A, Spiegelman A, Xiang Z. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. In: Financial Cryptography and Data Security. Vol 13411. Springer Nature; 2022:296-315. doi:10.1007/978-3-031-18283-9_14","apa":"Gelashvili, R., Kokoris Kogias, E., Sonnino, A., Spiegelman, A., & Xiang, Z. (2022). Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. In Financial Cryptography and Data Security (Vol. 13411, pp. 296–315). Radisson Grenada Beach Resort, Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_14","chicago":"Gelashvili, Rati, Eleftherios Kokoris Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. “Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback.” In Financial Cryptography and Data Security, 13411:296–315. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_14.","ieee":"R. Gelashvili, E. Kokoris Kogias, A. Sonnino, A. Spiegelman, and Z. Xiang, “Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback,” in Financial Cryptography and Data Security, Radisson Grenada Beach Resort, Grenada, 2022, vol. 13411, pp. 296–315.","ista":"Gelashvili R, Kokoris Kogias E, Sonnino A, Spiegelman A, Xiang Z. 2022. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. Financial Cryptography and Data Security. FC: Financial Cryptography, LNCS, vol. 13411, 296–315.","mla":"Gelashvili, Rati, et al. “Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback.” Financial Cryptography and Data Security, vol. 13411, Springer Nature, 2022, pp. 296–315, doi:10.1007/978-3-031-18283-9_14."},"author":[{"full_name":"Gelashvili, Rati","first_name":"Rati","last_name":"Gelashvili"},{"first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"last_name":"Sonnino","full_name":"Sonnino, Alberto","first_name":"Alberto"},{"last_name":"Spiegelman","first_name":"Alexander","full_name":"Spiegelman, Alexander"},{"last_name":"Xiang","full_name":"Xiang, Zhuolun","first_name":"Zhuolun"}],"type":"conference","alternative_title":["LNCS"],"day":"22","acknowledgement":"We thank our shepherd Aniket Kate and the anonymous reviewers at FC 2022 for their helpful feedback. This work is supported by the Novi team at Facebook. We also thank the Novi Research and Engineering teams for valuable feedback, and in particular Mathieu Baudet, Andrey Chursin, George Danezis, Zekun Li, and Dahlia Malkhi for discussions that shaped this work.","doi":"10.1007/978-3-031-18283-9_14","language":[{"iso":"eng"}],"article_processing_charge":"No","arxiv":1,"date_published":"2022-10-22T00:00:00Z","_id":"12298","abstract":[{"lang":"eng","text":"Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off: (1) they either achieve linear communication cost in the steady state, but sacrifice liveness during periods of asynchrony, or (2) they are robust (progress with probability one) but pay quadratic communication cost. We believe this trade-off is unwarranted since existing linear protocols still have asymptotic quadratic cost in the worst case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds: optimal communication on and off the steady state (linear and quadratic, respectively) and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing the view-synchronization of partially synchronous protocols with an asynchronous fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff, a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. We implement and experimentally evaluate all our systems to prove that breaking the robustness-efficiency trade-off is in the realm of practicality."}],"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2106.10362"}],"oa":1,"publication_status":"published","volume":13411,"year":"2022","oa_version":"Preprint","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031182822"],"eissn":["1611-3349"],"eisbn":["9783031182839"]},"scopus_import":"1","external_id":{"arxiv":["2106.10362"]},"date_updated":"2023-09-05T15:13:17Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"conference":{"start_date":"2022-08-07","end_date":"2022-08-10","name":"CAV: Computer Aided Verification","location":"Haifa, Israel"},"title":"FORQ-based language inclusion formal testing","ec_funded":1,"citation":{"short":"K. Doveri, P. Ganty, N.A. Mazzocchi, in:, Computer Aided Verification, Springer Nature, 2022, pp. 109–129.","apa":"Doveri, K., Ganty, P., & Mazzocchi, N. A. (2022). FORQ-based language inclusion formal testing. In Computer Aided Verification (Vol. 13372, pp. 109–129). Haifa, Israel: Springer Nature. https://doi.org/10.1007/978-3-031-13188-2_6","ama":"Doveri K, Ganty P, Mazzocchi NA. FORQ-based language inclusion formal testing. In: Computer Aided Verification. Vol 13372. Springer Nature; 2022:109-129. doi:10.1007/978-3-031-13188-2_6","ista":"Doveri K, Ganty P, Mazzocchi NA. 2022. FORQ-based language inclusion formal testing. Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13372, 109–129.","ieee":"K. Doveri, P. Ganty, and N. A. Mazzocchi, “FORQ-based language inclusion formal testing,” in Computer Aided Verification, Haifa, Israel, 2022, vol. 13372, pp. 109–129.","chicago":"Doveri, Kyveli, Pierre Ganty, and Nicolas Adrien Mazzocchi. “FORQ-Based Language Inclusion Formal Testing.” In Computer Aided Verification, 13372:109–29. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-13188-2_6.","mla":"Doveri, Kyveli, et al. “FORQ-Based Language Inclusion Formal Testing.” Computer Aided Verification, vol. 13372, Springer Nature, 2022, pp. 109–29, doi:10.1007/978-3-031-13188-2_6."},"alternative_title":["LNCS"],"author":[{"full_name":"Doveri, Kyveli","first_name":"Kyveli","last_name":"Doveri"},{"last_name":"Ganty","full_name":"Ganty, Pierre","first_name":"Pierre"},{"last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas Adrien","first_name":"Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85"}],"type":"conference","day":"06","acknowledgement":"This work was partially funded by the ESF Investing in your future, the Madrid regional project S2018/TCS-4339 BLOQUES, the Spanish project PGC2018-102210-B-I00 BOSCO, the Ramón y Cajal fellowship RYC-2016-20281, and the ERC grant PR1001ERC02.","project":[{"name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020"}],"doi":"10.1007/978-3-031-13188-2_6","ddc":["000"],"language":[{"iso":"eng"}],"page":"109-129","date_created":"2023-01-16T10:06:31Z","month":"08","isi":1,"publisher":"Springer Nature","intvolume":" 13372","status":"public","quality_controlled":"1","department":[{"_id":"ToHe"}],"publication":"Computer Aided Verification","has_accepted_license":"1","oa_version":"Published Version","year":"2022","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031131875"],"eissn":["1611-3349"],"eisbn":["9783031131882"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_updated":"2023-09-05T15:13:36Z","scopus_import":"1","external_id":{"arxiv":["2207.13549"],"isi":["000870310500006"]},"article_processing_charge":"No","arxiv":1,"date_published":"2022-08-06T00:00:00Z","_id":"12302","abstract":[{"text":"We propose a novel algorithm to decide the language inclusion between (nondeterministic) Büchi automata, a PSPACE-complete problem. Our approach, like others before, leverage a notion of quasiorder to prune the search for a counterexample by discarding candidates which are subsumed by others for the quasiorder. Discarded candidates are guaranteed to not compromise the completeness of the algorithm. The novelty of our work lies in the quasiorder used to discard candidates. We introduce FORQs (family of right quasiorders) that we obtain by adapting the notion of family of right congruences put forward by Maler and Staiger in 1993. We define a FORQ-based inclusion algorithm which we prove correct and instantiate it for a specific FORQ, called the structural FORQ, induced by the Büchi automaton to the right of the inclusion sign. The resulting implementation, called FORKLIFT, scales up better than the state-of-the-art on a variety of benchmarks including benchmarks from program verification and theorem proving for word combinatorics. Artifact: https://doi.org/10.5281/zenodo.6552870","lang":"eng"}],"file":[{"relation":"main_file","file_id":"12465","content_type":"application/pdf","date_created":"2023-01-30T12:51:02Z","success":1,"file_size":497682,"creator":"dernst","file_name":"2022_LNCS_Doveri.pdf","checksum":"edc363b1be5447a09063e115c247918a","access_level":"open_access","date_updated":"2023-01-30T12:51:02Z"}],"oa":1,"publication_status":"published","volume":13372,"tmp":{"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","short":"CC BY (4.0)"},"file_date_updated":"2023-01-30T12:51:02Z"},{"doi":"10.1007/978-3-031-22365-5_20","language":[{"iso":"eng"}],"acknowledgement":"We are grateful to Devika Sharma and Luca Trevisan for their insight and advice and to an anonymous reviewer for helpful comments.\r\n\r\nThis work was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019547). The first author was additionally supported by RGC GRF CUHK14209920 and the fourth author was additionally supported by ISF grant No. 1399/17, project PROMETHEUS (Grant 780701), and Cariplo CRYPTONOMEX grant.","alternative_title":["LNCS"],"type":"conference","author":[{"full_name":"Bogdanov, Andrej","first_name":"Andrej","last_name":"Bogdanov"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","full_name":"Hoffmann, Charlotte","first_name":"Charlotte","last_name":"Hoffmann"},{"last_name":"Rosen","first_name":"Alon","full_name":"Rosen, Alon"}],"day":"21","conference":{"name":"TCC: Theory of Cryptography","start_date":"2022-11-07","end_date":"2022-11-10","location":"Chicago, IL, United States"},"title":"Public-Key Encryption from Homogeneous CLWE","citation":{"apa":"Bogdanov, A., Cueto Noval, M., Hoffmann, C., & Rosen, A. (2022). Public-Key Encryption from Homogeneous CLWE. In Theory of Cryptography (Vol. 13748, pp. 565–592). Chicago, IL, United States: Springer Nature. https://doi.org/10.1007/978-3-031-22365-5_20","ama":"Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. Public-Key Encryption from Homogeneous CLWE. In: Theory of Cryptography. Vol 13748. Springer Nature; 2022:565-592. doi:10.1007/978-3-031-22365-5_20","short":"A. Bogdanov, M. Cueto Noval, C. Hoffmann, A. Rosen, in:, Theory of Cryptography, Springer Nature, 2022, pp. 565–592.","mla":"Bogdanov, Andrej, et al. “Public-Key Encryption from Homogeneous CLWE.” Theory of Cryptography, vol. 13748, Springer Nature, 2022, pp. 565–92, doi:10.1007/978-3-031-22365-5_20.","ieee":"A. Bogdanov, M. Cueto Noval, C. Hoffmann, and A. Rosen, “Public-Key Encryption from Homogeneous CLWE,” in Theory of Cryptography, Chicago, IL, United States, 2022, vol. 13748, pp. 565–592.","ista":"Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. 2022. Public-Key Encryption from Homogeneous CLWE. Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 13748, 565–592.","chicago":"Bogdanov, Andrej, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. “Public-Key Encryption from Homogeneous CLWE.” In Theory of Cryptography, 13748:565–92. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-22365-5_20."},"status":"public","intvolume":" 13748","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Theory of Cryptography","isi":1,"publisher":"Springer Nature","date_created":"2023-02-05T23:01:00Z","month":"12","page":"565-592","publication_identifier":{"isbn":["9783031223648"],"issn":["0302-9743"],"eissn":["1611-3349"]},"date_updated":"2023-08-04T10:39:30Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000921318200020"]},"scopus_import":"1","year":"2022","oa_version":"Preprint","volume":13748,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2022/093"}],"oa":1,"publication_status":"published","_id":"12516","abstract":[{"text":"The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known.\r\nWe present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.","lang":"eng"}],"date_published":"2022-12-21T00:00:00Z","article_processing_charge":"No"},{"year":"2021","oa_version":"Preprint","date_updated":"2023-02-10T08:31:50Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","external_id":{"arxiv":["1910.03332"]},"publication_identifier":{"eisbn":["9783030835088"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030835071"]},"arxiv":1,"article_processing_charge":"No","_id":"11771","date_published":"2021-08-09T00:00:00Z","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."}],"publication_status":"published","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1910.03332","open_access":"1"}],"volume":12808,"citation":{"short":"M.H. Henzinger, X. Wu, in:, 17th International Symposium on Algorithms and Data Structures, Springer Nature, 2021, pp. 471–484.","apa":"Henzinger, M. H., & Wu, X. (2021). Upper and lower bounds for fully retroactive graph problems. In 17th International Symposium on Algorithms and Data Structures (Vol. 12808, pp. 471–484). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-83508-8_34","ama":"Henzinger MH, Wu X. Upper and lower bounds for fully retroactive graph problems. In: 17th International Symposium on Algorithms and Data Structures. Vol 12808. Springer Nature; 2021:471–484. doi:10.1007/978-3-030-83508-8_34","ista":"Henzinger MH, 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.","ieee":"M. H. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph problems,” in 17th International Symposium on Algorithms and Data Structures, Virtual, 2021, vol. 12808, pp. 471–484.","chicago":"Henzinger, Monika H, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” In 17th International Symposium on Algorithms and Data Structures, 12808:471–484. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-83508-8_34.","mla":"Henzinger, Monika H., and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” 17th International Symposium on Algorithms and Data Structures, vol. 12808, Springer Nature, 2021, pp. 471–484, doi:10.1007/978-3-030-83508-8_34."},"conference":{"location":"Virtual","end_date":"2021-08-11","start_date":"2021-08-09","name":"WADS: Workshop on Algorithms and Data Structures"},"title":"Upper and lower bounds for fully retroactive graph problems","day":"09","alternative_title":["LNCS"],"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Xiaowei","full_name":"Wu, Xiaowei","last_name":"Wu"}],"type":"conference","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-83508-8_34","page":"471–484","extern":"1","month":"08","date_created":"2022-08-08T13:01:29Z","publisher":"Springer Nature","quality_controlled":"1","publication":"17th International Symposium on Algorithms and Data Structures","status":"public","intvolume":" 12808"},{"year":"2021","oa_version":"Submitted Version","has_accepted_license":"1","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2022-08-12T07:28:47Z","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030712778"],"eissn":["1611-3349"]},"file":[{"file_name":"2020_GCPR_submitted_Volhejn.pdf","file_size":420234,"creator":"dernst","date_updated":"2022-08-12T07:27:58Z","access_level":"open_access","checksum":"3e3628ab1cf658d82524963f808004ea","content_type":"application/pdf","relation":"main_file","file_id":"11820","success":1,"date_created":"2022-08-12T07:27:58Z"}],"abstract":[{"lang":"eng","text":"Modern neural networks can easily fit their training set perfectly. Surprisingly, despite being “overfit” in this way, they tend to generalize well to future data, thereby defying the classic bias–variance trade-off of machine learning theory. Of the many possible explanations, a prevalent one is that training by stochastic gradient descent (SGD) imposes an implicit bias that leads it to learn simple functions, and these simple functions generalize well. However, the specifics of this implicit bias are not well understood.\r\nIn this work, we explore the smoothness conjecture which states that SGD is implicitly biased towards learning functions that are smooth. We propose several measures to formalize the intuitive notion of smoothness, and we conduct experiments to determine whether SGD indeed implicitly optimizes for these measures. Our findings rule out the possibility that smoothness measures based on first-order derivatives are being implicitly enforced. They are supportive, though, of the smoothness conjecture for measures based on second-order derivatives."}],"_id":"9210","date_published":"2021-03-17T00:00:00Z","article_processing_charge":"No","file_date_updated":"2022-08-12T07:27:58Z","volume":12544,"publication_status":"published","oa":1,"day":"17","type":"conference","author":[{"id":"d5235fb4-7a6d-11eb-b254-f25d12d631a8","last_name":"Volhejn","full_name":"Volhejn, Vaclav","first_name":"Vaclav"},{"orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert"}],"citation":{"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.","ieee":"V. Volhejn and C. Lampert, “Does SGD implicitly optimize for smoothness?,” in 42nd German Conference on Pattern Recognition, Tübingen, Germany, 2021, vol. 12544, pp. 246–259.","chicago":"Volhejn, Vaclav, and Christoph Lampert. “Does SGD Implicitly Optimize for Smoothness?” In 42nd German Conference on Pattern Recognition, 12544:246–59. LNCS. Springer, 2021. https://doi.org/10.1007/978-3-030-71278-5_18.","mla":"Volhejn, Vaclav, and Christoph Lampert. “Does SGD Implicitly Optimize for Smoothness?” 42nd German Conference on Pattern Recognition, vol. 12544, Springer, 2021, pp. 246–59, doi:10.1007/978-3-030-71278-5_18.","short":"V. Volhejn, C. Lampert, in:, 42nd German Conference on Pattern Recognition, Springer, 2021, pp. 246–259.","apa":"Volhejn, V., & Lampert, C. (2021). Does SGD implicitly optimize for smoothness? In 42nd German Conference on Pattern Recognition (Vol. 12544, pp. 246–259). Tübingen, Germany: Springer. https://doi.org/10.1007/978-3-030-71278-5_18","ama":"Volhejn V, Lampert C. Does SGD implicitly optimize for smoothness? In: 42nd German Conference on Pattern Recognition. Vol 12544. LNCS. Springer; 2021:246-259. doi:10.1007/978-3-030-71278-5_18"},"title":"Does SGD implicitly optimize for smoothness?","conference":{"location":"Tübingen, Germany","name":"DAGM GCPR: German Conference on Pattern Recognition ","start_date":"2020-09-28","end_date":"2020-10-01"},"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-71278-5_18","ddc":["510"],"month":"03","date_created":"2021-03-01T09:01:16Z","series_title":"LNCS","page":"246-259","publication":"42nd German Conference on Pattern Recognition","quality_controlled":"1","department":[{"_id":"ChLa"}],"intvolume":" 12544","status":"public","publisher":"Springer"},{"title":"Experimental evaluation of a local search approximation algorithm for the multiway cut problem","conference":{"location":"Rupnagar, India","start_date":"2021-02-11","end_date":"2021-02-13","name":"CALDAM: Conference on Algorithms and Discrete Applied Mathematics"},"citation":{"ieee":"A. Bloch-Hansen, N. Samei, and R. Solis-Oba, “Experimental evaluation of a local search approximation algorithm for the multiway cut problem,” in Conference on Algorithms and Discrete Applied Mathematics, Rupnagar, India, 2021, vol. 12601, pp. 346–358.","ista":"Bloch-Hansen A, Samei N, Solis-Oba R. 2021. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. Conference on Algorithms and Discrete Applied Mathematics. CALDAM: Conference on Algorithms and Discrete Applied Mathematics, LNCS, vol. 12601, 346–358.","chicago":"Bloch-Hansen, Andrew, Nasim Samei, and Roberto Solis-Oba. “Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.” In Conference on Algorithms and Discrete Applied Mathematics, 12601:346–58. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-67899-9_28.","mla":"Bloch-Hansen, Andrew, et al. “Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.” Conference on Algorithms and Discrete Applied Mathematics, vol. 12601, Springer Nature, 2021, pp. 346–58, doi:10.1007/978-3-030-67899-9_28.","short":"A. Bloch-Hansen, N. Samei, R. Solis-Oba, in:, Conference on Algorithms and Discrete Applied Mathematics, Springer Nature, 2021, pp. 346–358.","apa":"Bloch-Hansen, A., Samei, N., & Solis-Oba, R. (2021). Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In Conference on Algorithms and Discrete Applied Mathematics (Vol. 12601, pp. 346–358). Rupnagar, India: Springer Nature. https://doi.org/10.1007/978-3-030-67899-9_28","ama":"Bloch-Hansen A, Samei N, Solis-Oba R. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In: Conference on Algorithms and Discrete Applied Mathematics. Vol 12601. Springer Nature; 2021:346-358. doi:10.1007/978-3-030-67899-9_28"},"type":"conference","author":[{"first_name":"Andrew","full_name":"Bloch-Hansen, Andrew","last_name":"Bloch-Hansen"},{"id":"C1531CAE-36E9-11EA-845F-33AA3DDC885E","last_name":"Samei","first_name":"Nasim","full_name":"Samei, Nasim"},{"last_name":"Solis-Oba","full_name":"Solis-Oba, Roberto","first_name":"Roberto"}],"oa_version":"None","year":"2021","alternative_title":["LNCS"],"day":"28","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030678982"]},"doi":"10.1007/978-3-030-67899-9_28","scopus_import":"1","language":[{"iso":"eng"}],"date_updated":"2023-10-10T09:29:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","page":"346-358","date_created":"2021-03-07T23:01:25Z","_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"}],"date_published":"2021-01-28T00:00:00Z","month":"01","publication_status":"published","publisher":"Springer Nature","status":"public","intvolume":" 12601","volume":12601,"publication":"Conference on Algorithms and Discrete Applied Mathematics","quality_controlled":"1","department":[{"_id":"VlKo"}]},{"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Davies","full_name":"Davies, Peter","first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","orcid":"0000-0002-5646-9524"}],"type":"conference","alternative_title":["LNCS"],"day":"20","title":"Collecting coupons is faster with friends","conference":{"end_date":"2021-07-01","start_date":"2021-06-28","name":" SIROCCO: International Colloquium on Structural Information and Communication Complexity","location":"Wrocław, Poland"},"citation":{"mla":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” Structural Information and Communication Complexity, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:10.1007/978-3-030-79527-6_1.","chicago":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In Structural Information and Communication Complexity, 12810:3–12. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_1.","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.","ieee":"D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in Structural Information and Communication Complexity, Wrocław, Poland, 2021, vol. 12810, pp. 3–12.","ama":"Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: Structural Information and Communication Complexity. Vol 12810. Springer Nature; 2021:3-12. doi:10.1007/978-3-030-79527-6_1","apa":"Alistarh, D.-A., & Davies, P. (2021). Collecting coupons is faster with friends. In Structural Information and Communication Complexity (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_1","short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 3–12."},"ec_funded":1,"doi":"10.1007/978-3-030-79527-6_1","ddc":["000"],"language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"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.","date_created":"2021-07-01T11:04:43Z","month":"06","page":"3-12","intvolume":" 12810","status":"public","publication":"Structural Information and Communication Complexity","department":[{"_id":"DaAl"}],"quality_controlled":"1","publisher":"Springer Nature","has_accepted_license":"1","oa_version":"Preprint","year":"2021","publication_identifier":{"eisbn":["9783030795276"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030795269"]},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","date_updated":"2023-02-23T14:02:46Z","_id":"9620","abstract":[{"text":"In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).\r\n\r\nWe provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.","lang":"eng"}],"date_published":"2021-06-20T00:00:00Z","file":[{"checksum":"fe37fb9af3f5016c1084af9d6e7109bd","date_updated":"2021-07-01T11:21:40Z","access_level":"open_access","file_name":"Population_Coupon_Collector.pdf","file_size":319728,"creator":"pdavies","date_created":"2021-07-01T11:21:40Z","content_type":"application/pdf","file_id":"9621","relation":"main_file"}],"article_processing_charge":"No","volume":12810,"file_date_updated":"2021-07-01T11:21:40Z","oa":1,"publication_status":"published"},{"conference":{"end_date":"2021-08-20","start_date":"2021-08-16","name":"CRYPTO: Annual International Cryptology Conference","location":"Virtual"},"title":"Limits on the Adaptive Security of Yao’s Garbling","ec_funded":1,"citation":{"mla":"Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.” 41st Annual International Cryptology Conference, Part II , vol. 12826, Springer Nature, 2021, pp. 486–515, doi:10.1007/978-3-030-84245-1_17.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the Adaptive Security of Yao’s Garbling,” in 41st Annual International Cryptology Conference, Part II , Virtual, 2021, vol. 12826, pp. 486–515.","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 41st Annual International Cryptology Conference, Part II , 12826:486–515. Cham: Springer Nature, 2021. https://doi.org/10.1007/978-3-030-84245-1_17.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Wichs, D. (2021). Limits on the Adaptive Security of Yao’s Garbling. In 41st Annual International Cryptology Conference, Part II (Vol. 12826, pp. 486–515). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-84245-1_17","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security of Yao’s Garbling. In: 41st Annual International Cryptology Conference, Part II . Vol 12826. Cham: Springer Nature; 2021:486-515. doi:10.1007/978-3-030-84245-1_17","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."},"alternative_title":["LCNS"],"type":"conference","author":[{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"last_name":"Wichs","full_name":"Wichs, Daniel","first_name":"Daniel"}],"day":"11","acknowledgement":"We would like to thank the anonymous reviewers of Crypto’21 whose detailed comments helped us considerably improve the presentation of the paper.","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"10035","status":"public"}]},"doi":"10.1007/978-3-030-84245-1_17","language":[{"iso":"eng"}],"page":"486-515","date_created":"2021-09-23T14:06:15Z","place":"Cham","month":"08","publisher":"Springer Nature","intvolume":" 12826","status":"public","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"41st Annual International Cryptology Conference, Part II ","year":"2021","oa_version":"Preprint","publication_identifier":{"eisbn":["978-3-030-84245-1"],"eissn":["1611-3349"],"isbn":["978-3-030-84244-4"],"issn":["0302-9743"]},"date_updated":"2023-09-07T13:32:11Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","abstract":[{"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.","lang":"eng"}],"_id":"10041","date_published":"2021-08-11T00:00:00Z","main_file_link":[{"url":"https://eprint.iacr.org/2021/945","open_access":"1"}],"oa":1,"publication_status":"published","volume":12826},{"language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-63958-0_34","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.","day":"17","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"},{"last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"last_name":"Lind","first_name":"Joshua","full_name":"Lind, Joshua"},{"first_name":"David","full_name":"Wong, David","last_name":"Wong"},{"last_name":"Zakian","first_name":"Tim","full_name":"Zakian, Tim"}],"type":"conference","alternative_title":["LNCS"],"citation":{"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.","apa":"Blackshear, S., Chalkias, K., Chatzigiannis, P., Faizullabhoy, R., Khaburzaniya, I., Kokoris Kogias, E., … Zakian, T. (2021). Reactive key-loss protection in blockchains. In FC 2021 Workshops (Vol. 12676, pp. 431–450). Virtual: Springer Nature. https://doi.org/10.1007/978-3-662-63958-0_34","ama":"Blackshear S, Chalkias K, Chatzigiannis P, et al. Reactive key-loss protection in blockchains. In: FC 2021 Workshops. Vol 12676. Springer Nature; 2021:431-450. doi:10.1007/978-3-662-63958-0_34","ieee":"S. Blackshear et al., “Reactive key-loss protection in blockchains,” in FC 2021 Workshops, Virtual, 2021, vol. 12676, 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: International Conference on 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 FC 2021 Workshops, 12676:431–50. Springer Nature, 2021. https://doi.org/10.1007/978-3-662-63958-0_34.","mla":"Blackshear, Sam, et al. “Reactive Key-Loss Protection in Blockchains.” FC 2021 Workshops, vol. 12676, Springer Nature, 2021, pp. 431–50, doi:10.1007/978-3-662-63958-0_34."},"title":"Reactive key-loss protection in blockchains","conference":{"start_date":"2021-03-01","end_date":"2021-03-05","name":"FC: International Conference on Financial Cryptography and Data Security","location":"Virtual"},"publication":"FC 2021 Workshops","quality_controlled":"1","department":[{"_id":"ElKo"}],"status":"public","publisher":"Springer Nature","isi":1,"month":"09","date_created":"2021-10-03T22:01:24Z","page":"431-450","scopus_import":"1","external_id":{"isi":["000713005000034"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-14T07:06:16Z","publication_identifier":{"issn":["0302-9743"],"isbn":["978-3-6626-3957-3"],"eissn":["1611-3349"],"eisbn":["978-3-662-63958-0"]},"year":"2021","oa_version":"Preprint","volume":"12676 ","publication_status":"published","oa":1,"main_file_link":[{"url":"https://research.fb.com/publications/reactive-key-loss-protection-in-blockchains/","open_access":"1"}],"_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_published":"2021-09-17T00:00:00Z","article_processing_charge":"No"},{"publication_status":"published","oa":1,"file_date_updated":"2021-10-07T23:32:18Z","volume":12974,"article_processing_charge":"No","file":[{"date_created":"2021-10-07T23:32:18Z","success":1,"relation":"main_file","file_id":"10109","content_type":"application/pdf","checksum":"554c7fdb259eda703a8b6328a6dad55a","access_level":"open_access","date_updated":"2021-10-07T23:32:18Z","file_size":350632,"creator":"fmuehlbo","file_name":"differentialmonitoring-cameraready-openaccess.pdf"}],"_id":"10108","abstract":[{"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.","lang":"eng"}],"date_published":"2021-10-06T00:00:00Z","external_id":{"isi":["000719383800012"]},"scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-14T07:20:30Z","publication_identifier":{"issn":["0302-9743"],"isbn":["978-3-030-88493-2"],"eissn":["1611-3349"],"eisbn":["978-3-030-88494-9"]},"has_accepted_license":"1","year":"2021","oa_version":"Preprint","publisher":"Springer Nature","isi":1,"publication":"International Conference on Runtime Verification","department":[{"_id":"ToHe"}],"quality_controlled":"1","intvolume":" 12974","status":"public","page":"231-243","month":"10","place":"Cham","date_created":"2021-10-07T23:30:10Z","project":[{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"related_material":{"record":[{"id":"9946","relation":"extended_version","status":"public"}]},"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.","keyword":["run-time verification","software engineering","implicit specification"],"language":[{"iso":"eng"}],"ddc":["005"],"doi":"10.1007/978-3-030-88494-9_12","citation":{"ama":"Mühlböck F, Henzinger TA. Differential monitoring. In: International Conference on Runtime Verification. Vol 12974. Cham: Springer Nature; 2021:231-243. doi:10.1007/978-3-030-88494-9_12","apa":"Mühlböck, F., & Henzinger, T. A. (2021). Differential monitoring. In International Conference on Runtime Verification (Vol. 12974, pp. 231–243). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-88494-9_12","short":"F. Mühlböck, T.A. Henzinger, in:, International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 231–243.","mla":"Mühlböck, Fabian, and Thomas A. Henzinger. “Differential Monitoring.” International Conference on Runtime Verification, vol. 12974, Springer Nature, 2021, pp. 231–43, doi:10.1007/978-3-030-88494-9_12.","chicago":"Mühlböck, Fabian, and Thomas A Henzinger. “Differential Monitoring.” In International Conference on Runtime Verification, 12974:231–43. Cham: Springer Nature, 2021. https://doi.org/10.1007/978-3-030-88494-9_12.","ista":"Mühlböck F, Henzinger TA. 2021. Differential monitoring. International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 12974, 231–243.","ieee":"F. Mühlböck and T. A. Henzinger, “Differential monitoring,” in International Conference on Runtime Verification, Virtual, 2021, vol. 12974, pp. 231–243."},"title":"Differential monitoring","conference":{"name":"RV: Runtime Verification","start_date":"2021-10-11","end_date":"2021-10-14","location":"Virtual"},"day":"06","author":[{"first_name":"Fabian","full_name":"Mühlböck, Fabian","last_name":"Mühlböck","orcid":"0000-0003-1548-0177","id":"6395C5F6-89DF-11E9-9C97-6BDFE5697425"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"}],"type":"conference","alternative_title":["LNCS"]},{"language":[{"iso":"eng"}],"keyword":["monitoring","neural networks","novelty detection"],"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.","related_material":{"record":[{"status":"public","relation":"extended_version","id":"13234"}]},"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z211"}],"day":"06","alternative_title":["LNCS"],"type":"conference","author":[{"id":"CBA4D1A8-0FE8-11E9-BDE6-07BFE5697425","last_name":"Lukina","full_name":"Lukina, Anna","first_name":"Anna"},{"last_name":"Schilling","first_name":"Christian","full_name":"Schilling, Christian","orcid":"0000-0003-3658-1065","id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger"}],"ec_funded":1,"citation":{"ama":"Lukina A, Schilling C, Henzinger TA. Into the unknown: active monitoring of neural networks. In: 21st International Conference on Runtime Verification. Vol 12974. Cham: Springer Nature; 2021:42-61. doi:10.1007/978-3-030-88494-9_3","apa":"Lukina, A., Schilling, C., & Henzinger, T. A. (2021). Into the unknown: active monitoring of neural networks. In 21st International Conference on Runtime Verification (Vol. 12974, pp. 42–61). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-88494-9_3","short":"A. Lukina, C. Schilling, T.A. Henzinger, in:, 21st International Conference on Runtime Verification, Springer Nature, Cham, 2021, pp. 42–61.","mla":"Lukina, Anna, et al. “Into the Unknown: Active Monitoring of Neural Networks.” 21st International Conference on Runtime Verification, vol. 12974, Springer Nature, 2021, pp. 42–61, doi:10.1007/978-3-030-88494-9_3.","chicago":"Lukina, Anna, Christian Schilling, and Thomas A Henzinger. “Into the Unknown: Active Monitoring of Neural Networks.” In 21st International Conference on Runtime Verification, 12974:42–61. Cham: Springer Nature, 2021. https://doi.org/10.1007/978-3-030-88494-9_3.","ieee":"A. Lukina, C. Schilling, and T. A. Henzinger, “Into the unknown: active monitoring of neural networks,” in 21st International Conference on Runtime Verification, Virtual, 2021, vol. 12974, pp. 42–61.","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."},"conference":{"end_date":"2021-10-14","start_date":"2021-10-11","name":"RV: Runtime Verification","location":"Virtual"},"title":"Into the unknown: active monitoring of neural networks","department":[{"_id":"ToHe"}],"quality_controlled":"1","publication":"21st International Conference on Runtime Verification","status":"public","publisher":"Springer Nature","isi":1,"place":"Cham","month":"10","date_created":"2021-10-31T23:01:31Z","page":"42-61","date_updated":"2024-01-30T12:06:56Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","external_id":{"isi":["000719383800003"],"arxiv":["2009.06429"]},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0308-8493-2"],"eisbn":["978-3-030-88494-9"]},"year":"2021","oa_version":"Preprint","volume":"12974 ","publication_status":"published","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2009.06429","open_access":"1"}],"date_published":"2021-10-06T00:00:00Z","_id":"10206","abstract":[{"lang":"eng","text":"Neural-network classifiers achieve high accuracy when predicting the class of an input that they were trained to identify. Maintaining this accuracy in dynamic environments, where inputs frequently fall outside the fixed set of initially known classes, remains a challenge. The typical approach is to detect inputs from novel classes and retrain the classifier on an augmented dataset. However, not only the classifier but also the detection mechanism needs to adapt in order to distinguish between newly learned and yet unknown input classes. To address this challenge, we introduce an algorithmic framework for active monitoring of a neural network. A monitor wrapped in our framework operates in parallel with the neural network and interacts with a human user via a series of interpretable labeling queries for incremental adaptation. In addition, we propose an adaptive quantitative monitor to improve precision. An experimental evaluation on a diverse set of benchmarks with varying numbers of classes confirms the benefits of our active monitoring framework in dynamic scenarios."}],"arxiv":1,"article_processing_charge":"No"},{"article_processing_charge":"No","arxiv":1,"date_published":"2021-10-23T00:00:00Z","_id":"10324","abstract":[{"lang":"eng","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."}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1905.11360","open_access":"1"}],"publication_status":"published","volume":"12675 ","year":"2021","oa_version":"Preprint","publication_identifier":{"eisbn":["978-3-662-64331-0"],"eissn":["1611-3349"],"isbn":["9-783-6626-4330-3"],"issn":["0302-9743"]},"external_id":{"isi":["000712016200011"],"arxiv":["1905.11360"]},"scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-14T12:59:58Z","page":"209-230","date_created":"2021-11-21T23:01:29Z","month":"10","isi":1,"publisher":"Springer Nature","status":"public","publication":"25th International Conference on Financial Cryptography and Data Security","quality_controlled":"1","department":[{"_id":"ElKo"}],"title":"Brick: Asynchronous incentive-compatible payment channels","conference":{"location":"Virtual","name":"FC: Financial Cryptography","start_date":"2021-03-01","end_date":"2021-03-05"},"citation":{"mla":"Avarikioti, Zeta, et al. “Brick: Asynchronous Incentive-Compatible Payment Channels.” 25th International Conference on Financial Cryptography and Data Security, vol. 12675, Springer Nature, 2021, pp. 209–30, doi:10.1007/978-3-662-64331-0_11.","chicago":"Avarikioti, Zeta, Eleftherios Kokoris Kogias, Roger Wattenhofer, and Dionysis Zindros. “Brick: Asynchronous Incentive-Compatible Payment Channels.” In 25th International Conference on Financial Cryptography and Data Security, 12675:209–30. Springer Nature, 2021. https://doi.org/10.1007/978-3-662-64331-0_11.","ieee":"Z. Avarikioti, E. Kokoris Kogias, R. Wattenhofer, and D. Zindros, “Brick: Asynchronous incentive-compatible payment channels,” in 25th International Conference on Financial Cryptography and Data Security, Virtual, 2021, vol. 12675, 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.","ama":"Avarikioti Z, Kokoris Kogias E, Wattenhofer R, Zindros D. Brick: Asynchronous incentive-compatible payment channels. In: 25th International Conference on Financial Cryptography and Data Security. Vol 12675. Springer Nature; 2021:209-230. doi:10.1007/978-3-662-64331-0_11","apa":"Avarikioti, Z., Kokoris Kogias, E., Wattenhofer, R., & Zindros, D. (2021). Brick: Asynchronous incentive-compatible payment channels. In 25th International Conference on Financial Cryptography and Data Security (Vol. 12675, pp. 209–230). Virtual: Springer Nature. https://doi.org/10.1007/978-3-662-64331-0_11","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."},"author":[{"full_name":"Avarikioti, Zeta","first_name":"Zeta","last_name":"Avarikioti"},{"last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"full_name":"Wattenhofer, Roger","first_name":"Roger","last_name":"Wattenhofer"},{"last_name":"Zindros","full_name":"Zindros, Dionysis","first_name":"Dionysis"}],"type":"conference","alternative_title":["LNCS"],"day":"23","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","language":[{"iso":"eng"}]},{"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1128"}],"oa":1,"publication_status":"published","volume":"12675 ","article_processing_charge":"No","_id":"10325","date_published":"2021-10-23T00:00:00Z","abstract":[{"lang":"eng","text":"Since the inception of Bitcoin, a plethora of distributed ledgers differing in design and purpose has been created. While by design, blockchains provide no means to securely communicate with external systems, numerous attempts towards trustless cross-chain communication have been proposed over the years. Today, cross-chain communication (CCC) plays a fundamental role in cryptocurrency exchanges, scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence in their correctness and composability. We provide the first systematic exposition of cross-chain communication protocols. We formalize the underlying research problem and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. With this result in mind, we develop a framework to design new and evaluate existing CCC protocols, focusing on the inherent trust assumptions thereof, and derive a classification covering the field of cross-chain communication to date. We conclude by discussing open challenges for CCC research and the implications of interoperability on the security and privacy of blockchains."}],"publication_identifier":{"eisbn":["978-3-662-64331-0"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-6626-4330-3"]},"date_updated":"2023-08-14T12:59:26Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000712016200001"]},"scopus_import":"1","oa_version":"Preprint","year":"2021","isi":1,"publisher":"Springer Nature","status":"public","department":[{"_id":"ElKo"}],"quality_controlled":"1","publication":"25th International Conference on Financial Cryptography and Data Security","page":"3-36","date_created":"2021-11-21T23:01:29Z","month":"10","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","language":[{"iso":"eng"}],"conference":{"start_date":"2021-03-01","end_date":"2021-03-05","name":"FC: Financial Cryptography","location":"Virtual"},"title":"SoK: Communication across distributed ledgers","citation":{"mla":"Zamyatin, Alexei, et al. “SoK: Communication across Distributed Ledgers.” 25th International Conference on Financial Cryptography and Data Security, vol. 12675, Springer Nature, 2021, pp. 3–36, doi:10.1007/978-3-662-64331-0_1.","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 25th International Conference on Financial Cryptography and Data Security, 12675:3–36. Springer Nature, 2021. https://doi.org/10.1007/978-3-662-64331-0_1.","ieee":"A. Zamyatin et al., “SoK: Communication across distributed ledgers,” in 25th International Conference on Financial Cryptography and Data Security, Virtual, 2021, vol. 12675, pp. 3–36.","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.","ama":"Zamyatin A, Al-Bassam M, Zindros D, et al. SoK: Communication across distributed ledgers. In: 25th International Conference on Financial Cryptography and Data Security. Vol 12675. Springer Nature; 2021:3-36. doi:10.1007/978-3-662-64331-0_1","apa":"Zamyatin, A., Al-Bassam, M., Zindros, D., Kokoris Kogias, E., Moreno-Sanchez, P., Kiayias, A., & Knottenbelt, W. J. (2021). SoK: Communication across distributed ledgers. In 25th International Conference on Financial Cryptography and Data Security (Vol. 12675, pp. 3–36). Virtual: Springer Nature. https://doi.org/10.1007/978-3-662-64331-0_1","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."},"alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Zamyatin","first_name":"Alexei","full_name":"Zamyatin, Alexei"},{"full_name":"Al-Bassam, Mustafa","first_name":"Mustafa","last_name":"Al-Bassam"},{"full_name":"Zindros, Dionysis","first_name":"Dionysis","last_name":"Zindros"},{"full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"last_name":"Moreno-Sanchez","first_name":"Pedro","full_name":"Moreno-Sanchez, Pedro"},{"last_name":"Kiayias","first_name":"Aggelos","full_name":"Kiayias, Aggelos"},{"last_name":"Knottenbelt","first_name":"William J.","full_name":"Knottenbelt, William J."}],"day":"23"},{"oa_version":"Preprint","year":"2021","date_updated":"2023-08-14T13:07:46Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","external_id":{"isi":["000728364000014"]},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"]},"article_processing_charge":"No","date_published":"2021-11-04T00:00:00Z","_id":"10407","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."}],"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1224"}],"volume":13043,"ec_funded":1,"citation":{"short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","apa":"Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z., & 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. https://doi.org/10.1007/978-3-030-90453-1_14","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:10.1007/978-3-030-90453-1_14","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.","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. https://doi.org/10.1007/978-3-030-90453-1_14.","mla":"Chakraborty, Suvradip, et al. Trojan-Resilience without Cryptography. Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:10.1007/978-3-030-90453-1_14."},"conference":{"start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","location":"Raleigh, NC, United States"},"title":"Trojan-resilience without cryptography","day":"04","alternative_title":["LNCS"],"author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","first_name":"Suvradip","full_name":"Chakraborty, Suvradip"},{"last_name":"Dziembowski","first_name":"Stefan","full_name":"Dziembowski, Stefan"},{"first_name":"Małgorzata","full_name":"Gałązka, Małgorzata","last_name":"Gałązka"},{"last_name":"Lizurej","full_name":"Lizurej, Tomasz","first_name":"Tomasz"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90453-1_14","page":"397-428","month":"11","date_created":"2021-12-05T23:01:42Z","publisher":"Springer Nature","isi":1,"department":[{"_id":"KrPi"}],"quality_controlled":"1","status":"public","intvolume":" 13043"},{"external_id":{"isi":["000728363700008"]},"scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-14T13:19:39Z","publication_identifier":{"eisbn":["978-3-030-90456-2"],"eissn":["1611-3349"],"isbn":["9-783-0309-0455-5"],"issn":["0302-9743"]},"oa_version":"Preprint","year":"2021","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"volume":13044,"article_processing_charge":"No","_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"}],"date_published":"2021-11-04T00:00:00Z","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"},{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385"}],"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).","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90456-2_8","citation":{"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 19th International Conference (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: 19th International Conference. Vol 13044. Springer Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8","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.","ieee":"J. F. Alwen et al., “Grafting key trees: Efficient key management for overlapping groups,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:10.1007/978-3-030-90456-2_8."},"ec_funded":1,"title":"Grafting key trees: Efficient key management for overlapping groups","conference":{"name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11","location":"Raleigh, NC, United States"},"day":"04","type":"conference","author":[{"last_name":"Alwen","first_name":"Joel F","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","last_name":"Auerbach","first_name":"Benedikt","full_name":"Auerbach, Benedikt"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","last_name":"Baig"},{"first_name":"Miguel","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","last_name":"Pascual Perez"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"alternative_title":["LNCS"],"publisher":"Springer Nature","isi":1,"publication":"19th International Conference","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","intvolume":" 13044","page":"222-253","month":"11","date_created":"2021-12-05T23:01:42Z"},{"date_created":"2021-12-05T23:01:43Z","month":"11","page":"486-517","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"19th International Conference","isi":1,"publisher":"Springer Nature","alternative_title":["LNCS"],"author":[{"first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"type":"conference","day":"04","conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography"},"title":"On treewidth, separators and Yao’s garbling","ec_funded":1,"citation":{"mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517, doi:10.1007/978-3-030-90453-1_17.","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13043, 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 19th International Conference, 13043:486–517. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17.","apa":"Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In 19th International Conference (Vol. 13043, pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: 19th International Conference. Vol 13043. Springer Nature; 2021:486-517. doi:10.1007/978-3-030-90453-1_17","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517."},"doi":"10.1007/978-3-030-90453-1_17","language":[{"iso":"eng"}],"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.","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"relation":"earlier_version","id":"10044","status":"public"}]},"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."}],"_id":"10409","date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","volume":"13043 ","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"publication_status":"published","oa_version":"Preprint","year":"2021","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-17T06:21:38Z","scopus_import":"1","external_id":{"isi":["000728364000017"]}},{"year":"2021","oa_version":"Preprint","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"]},"scopus_import":"1","external_id":{"isi":["000728364000019"]},"date_updated":"2023-10-17T09:24:07Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"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.","lang":"eng"}],"_id":"10410","date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","volume":13043,"main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"oa":1,"publication_status":"published","type":"conference","author":[{"last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"alternative_title":["LNCS"],"day":"04","title":"The cost of adaptivity in security games on graphs","conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","end_date":"2021-11-11","start_date":"2021-11-08"},"citation":{"mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:10.1007/978-3-030-90453-1_19.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th International Conference, 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 19th International Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The cost of adaptivity in security games on graphs. In 19th International Conference (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th International Conference. Vol 13043. Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581."},"ec_funded":1,"doi":"10.1007/978-3-030-90453-1_19","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"10048","relation":"earlier_version","status":"public"}]},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"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).","date_created":"2021-12-05T23:01:43Z","month":"11","page":"550-581","intvolume":" 13043","status":"public","publication":"19th International Conference","quality_controlled":"1","department":[{"_id":"KrPi"}],"isi":1,"publisher":"Springer Nature"}]