[{"date_updated":"2024-02-20T09:13:07Z","status":"public","publication_status":"published","oa_version":"Preprint","page":"339-346","day":"01","ec_funded":1,"abstract":[{"lang":"eng","text":"We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n-1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs."}],"project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183","call_identifier":"H2020"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"}],"citation":{"apa":"Pach, J., Saghafian, M., & Schnider, P. (2024). Decomposition of geometric graphs into star-forests. In 31st International Symposium on Graph Drawing and Network Visualization (Vol. 14465, pp. 339–346). Isola delle Femmine, Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49272-3_23","mla":"Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.” 31st International Symposium on Graph Drawing and Network Visualization, vol. 14465, Springer Nature, 2024, pp. 339–46, doi:10.1007/978-3-031-49272-3_23.","short":"J. Pach, M. Saghafian, P. Schnider, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 339–346.","ista":"Pach J, Saghafian M, Schnider P. 2024. Decomposition of geometric graphs into star-forests. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14465, 339–346.","ama":"Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests. In: 31st International Symposium on Graph Drawing and Network Visualization. Vol 14465. Springer Nature; 2024:339-346. doi:10.1007/978-3-031-49272-3_23","chicago":"Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric Graphs into Star-Forests.” In 31st International Symposium on Graph Drawing and Network Visualization, 14465:339–46. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49272-3_23.","ieee":"J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs into star-forests,” in 31st International Symposium on Graph Drawing and Network Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14465, pp. 339–346."},"arxiv":1,"scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2306.13201","open_access":"1"}],"publication":"31st International Symposium on Graph Drawing and Network Visualization","external_id":{"arxiv":["2306.13201"]},"title":"Decomposition of geometric graphs into star-forests","language":[{"iso":"eng"}],"doi":"10.1007/978-3-031-49272-3_23","publisher":"Springer Nature","year":"2024","type":"conference","author":[{"full_name":"Pach, János","first_name":"János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","last_name":"Pach"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","last_name":"Saghafian","full_name":"Saghafian, Morteza","first_name":"Morteza"},{"last_name":"Schnider","first_name":"Patrick","full_name":"Schnider, Patrick"}],"oa":1,"_id":"15012","date_published":"2024-01-01T00:00:00Z","date_created":"2024-02-18T23:01:03Z","acknowledgement":"János Pach’s Research partially supported by European Research Council (ERC), grant “GeoScape” No. 882971 and by the Hungarian Science Foundation (NKFIH), grant K-131529. Work by Morteza Saghafian is partially supported by the European Research Council (ERC), grant No. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31.","department":[{"_id":"HeEd"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2023-09-22","start_date":"2023-09-20","name":"GD: Graph Drawing and Network Visualization","location":"Isola delle Femmine, Palermo, Italy"},"intvolume":" 14465","month":"01","quality_controlled":"1","publication_identifier":{"eissn":["16113349"],"isbn":["9783031492716"],"issn":["03029743"]},"volume":14465},{"arxiv":1,"citation":{"short":"E. Bartocci, T. Ferrere, T.A. Henzinger, D. Nickovic, A.O. Da Costa, in:, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Nature, 2022, pp. 1–19.","apa":"Bartocci, E., Ferrere, T., Henzinger, T. A., Nickovic, D., & Da Costa, A. O. (2022). Flavors of sequential information flow. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 13182, pp. 1–19). Philadelphia, PA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-94583-1_1","ista":"Bartocci E, Ferrere T, Henzinger TA, Nickovic D, Da Costa AO. 2022. Flavors of sequential information flow. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 13182, 1–19.","mla":"Bartocci, Ezio, et al. “Flavors of Sequential Information Flow.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13182, Springer Nature, 2022, pp. 1–19, doi:10.1007/978-3-030-94583-1_1.","ama":"Bartocci E, Ferrere T, Henzinger TA, Nickovic D, Da Costa AO. Flavors of sequential information flow. In: Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 13182. Springer Nature; 2022:1-19. doi:10.1007/978-3-030-94583-1_1","chicago":"Bartocci, Ezio, Thomas Ferrere, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira Da Costa. “Flavors of Sequential Information Flow.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 13182:1–19. Springer Nature, 2022. https://doi.org/10.1007/978-3-030-94583-1_1.","ieee":"E. Bartocci, T. Ferrere, T. A. Henzinger, D. Nickovic, and A. O. Da Costa, “Flavors of sequential information flow,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Philadelphia, PA, United States, 2022, vol. 13182, pp. 1–19."},"project":[{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z211","call_identifier":"FWF"}],"alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2105.02013"}],"title":"Flavors of sequential information flow","external_id":{"arxiv":["2105.02013"]},"publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","date_updated":"2022-08-05T09:02:56Z","status":"public","abstract":[{"text":"We study the problem of specifying sequential information-flow properties of systems. Information-flow properties are hyperproperties, as they compare different traces of a system. Sequential information-flow properties can express changes, over time, in the information-flow constraints. For example, information-flow constraints during an initialization phase of a system may be different from information-flow constraints that are required during the operation phase. We formalize several variants of interpreting sequential information-flow constraints, which arise from different assumptions about what can be observed of the system. For this purpose, we introduce a first-order logic, called Hypertrace Logic, with both trace and time quantifiers for specifying linear-time hyperproperties. We prove that HyperLTL, which corresponds to a fragment of Hypertrace Logic with restricted quantifier prefixes, cannot specify the majority of the studied variants of sequential information flow, including all variants in which the transition between sequential phases (such as initialization and operation) happens asynchronously. Our results rely on new equivalences between sets of traces that cannot be distinguished by certain classes of formulas from Hypertrace Logic. This presents a new approach to proving inexpressiveness results for HyperLTL.","lang":"eng"}],"day":"14","oa_version":"Preprint","publication_status":"published","page":"1-19","department":[{"_id":"ToHe"}],"acknowledgement":"This work was funded in part by the Wittgenstein Award Z211-N23 of the Austrian Science Fund (FWF) and by the FWF project W1255-N23.","date_created":"2022-02-20T23:01:34Z","intvolume":" 13182","conference":{"end_date":"2022-01-18","start_date":"2022-01-16","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","location":"Philadelphia, PA, United States"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","publication_identifier":{"isbn":["9783030945824"],"issn":["03029743"],"eissn":["16113349"]},"quality_controlled":"1","month":"01","volume":13182,"year":"2022","publisher":"Springer Nature","doi":"10.1007/978-3-030-94583-1_1","language":[{"iso":"eng"}],"type":"conference","_id":"10774","oa":1,"author":[{"full_name":"Bartocci, Ezio","first_name":"Ezio","last_name":"Bartocci"},{"last_name":"Ferrere","id":"40960E6E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5199-3143","full_name":"Ferrere, Thomas","first_name":"Thomas"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","last_name":"Nickovic","full_name":"Nickovic, Dejan","first_name":"Dejan"},{"full_name":"Da Costa, Ana Oliveira","first_name":"Ana Oliveira","last_name":"Da Costa"}],"date_published":"2022-01-14T00:00:00Z"},{"volume":12635,"month":"02","publication_identifier":{"eissn":["16113349"],"isbn":["9783030682101"],"issn":["03029743"]},"quality_controlled":"1","conference":{"start_date":"2021-02-28","end_date":"2021-03-02","name":"WALCOM: Algorithms and Computation","location":"Yangon, Myanmar"},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","article_processing_charge":"No","intvolume":" 12635","date_created":"2021-03-28T22:01:41Z","acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"date_published":"2021-02-16T00:00:00Z","author":[{"last_name":"Aichholzer","first_name":"Oswin","full_name":"Aichholzer, Oswin"},{"first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670"},{"first_name":"Zuzana","full_name":"Masárová, Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"},{"full_name":"Perz, Daniel","first_name":"Daniel","last_name":"Perz"},{"last_name":"Pilz","full_name":"Pilz, Alexander","first_name":"Alexander"},{"first_name":"Josef","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec"},{"last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit","first_name":"Birgit"}],"_id":"9296","oa":1,"type":"conference","doi":"10.1007/978-3-030-68211-8_18","language":[{"iso":"eng"}],"year":"2021","publisher":"Springer Nature","publication":"15th International Conference on Algorithms and Computation","title":"On compatible matchings","related_material":{"record":[{"id":"11938","status":"public","relation":"later_version"}]},"external_id":{"arxiv":["2101.03928"]},"main_file_link":[{"url":"https://arxiv.org/abs/2101.03928","open_access":"1"}],"scopus_import":"1","alternative_title":["LNCS"],"arxiv":1,"citation":{"ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:10.1007/978-3-030-68211-8_18.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: 15th International Conference on Algorithms and Computation. Vol 12635. Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In 15th International Conference on Algorithms and Computation, 12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.","ieee":"O. Aichholzer et al., “On compatible matchings,” in 15th International Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233."},"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"},{"call_identifier":"FWF","grant_number":"Z00342","name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"},{"grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF","grant_number":"S11407"}],"day":"16","publication_status":"published","oa_version":"Preprint","page":"221-233","abstract":[{"lang":"eng","text":" matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge."}],"ec_funded":1,"status":"public","date_updated":"2023-02-21T16:33:44Z"},{"date_published":"2021-05-01T00:00:00Z","oa":1,"_id":"9466","author":[{"first_name":"Michael","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482"}],"type":"conference","publisher":"Springer Nature","year":"2021","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-75245-3_3","volume":12710,"quality_controlled":"1","publication_identifier":{"eissn":["16113349"],"isbn":["9783030752446"],"issn":["03029743"]},"month":"05","intvolume":" 12710","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"file_date_updated":"2022-05-27T09:48:31Z","conference":{"location":"Virtual","start_date":"2021-05-10","end_date":"2021-05-13","name":"PKC: IACR International Conference on Practice and Theory of Public Key Cryptography"},"department":[{"_id":"KrPi"}],"acknowledgement":"This work was initiated in discussions with Léo Ducas, when the author was visiting the Simons Institute for the Theory of Computation during the program “Lattices: Algorithms, Complexity, and Cryptography”. We thank Thomas Espitau for pointing out a bug in a proof in an earlier version of this manuscript.","date_created":"2021-06-06T22:01:29Z","ec_funded":1,"abstract":[{"text":"In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.","lang":"eng"}],"oa_version":"Published Version","publication_status":"published","page":"45-67","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-02-23T13:58:47Z","file":[{"creator":"dernst","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"2021_PKC_Walter.pdf","file_size":489017,"file_id":"11416","checksum":"413e564d645ed93d7318672361d9d470","date_created":"2022-05-27T09:48:31Z","date_updated":"2022-05-27T09:48:31Z","success":1}],"title":"The convergence of slide-type reductions","publication":"Public-Key Cryptography – PKC 2021","alternative_title":["LNCS"],"has_accepted_license":"1","scopus_import":"1","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815"}],"citation":{"ista":"Walter M. 2021. The convergence of slide-type reductions. Public-Key Cryptography – PKC 2021. PKC: IACR International Conference on Practice and Theory of Public Key Cryptography, LNCS, vol. 12710, 45–67.","short":"M. Walter, in:, Public-Key Cryptography – PKC 2021, Springer Nature, 2021, pp. 45–67.","mla":"Walter, Michael. “The Convergence of Slide-Type Reductions.” Public-Key Cryptography – PKC 2021, vol. 12710, Springer Nature, 2021, pp. 45–67, doi:10.1007/978-3-030-75245-3_3.","apa":"Walter, M. (2021). The convergence of slide-type reductions. In Public-Key Cryptography – PKC 2021 (Vol. 12710, pp. 45–67). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-75245-3_3","ama":"Walter M. The convergence of slide-type reductions. In: Public-Key Cryptography – PKC 2021. Vol 12710. Springer Nature; 2021:45-67. doi:10.1007/978-3-030-75245-3_3","chicago":"Walter, Michael. “The Convergence of Slide-Type Reductions.” In Public-Key Cryptography – PKC 2021, 12710:45–67. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75245-3_3.","ieee":"M. Walter, “The convergence of slide-type reductions,” in Public-Key Cryptography – PKC 2021, Virtual, 2021, vol. 12710, pp. 45–67."}},{"external_id":{"arxiv":["2103.08949"]},"title":"Wait-free approximate agreement on graphs","publication":"Structural Information and Communication Complexity","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2103.08949"}],"alternative_title":["LNCS"],"scopus_import":"1","citation":{"ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” in Structural Information and Communication Complexity, Wrocław, Poland, 2021, vol. 12810, pp. 87–105.","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” In Structural Information and Communication Complexity, 12810:87–105. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_6.","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. In: Structural Information and Communication Complexity. Vol 12810. Springer Nature; 2021:87-105. doi:10.1007/978-3-030-79527-6_6","mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Structural Information and Communication Complexity, vol. 12810, Springer Nature, 2021, pp. 87–105, doi:10.1007/978-3-030-79527-6_6.","apa":"Alistarh, D.-A., Ellen, F., & Rybicki, J. (2021). Wait-free approximate agreement on graphs. In Structural Information and Communication Complexity (Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_6","ista":"Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs. Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 12810, 87–105.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 87–105."},"arxiv":1,"abstract":[{"lang":"eng","text":"Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach output value lies on a shortest path between two input values.\r\n\r\nFrom prior work, it is known that there is no wait-free algorithm among 𝑛≥3 processes for this problem on any cycle of length 𝑐≥4 , by reduction from 2-set agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability and complexity of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length 𝑐≥4 , via a generalisation of Sperner’s Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a class of graphs that properly contains the class of chordal graphs."}],"page":"87-105","publication_status":"published","oa_version":"Preprint","day":"20","status":"public","date_updated":"2023-02-23T14:09:49Z","volume":12810,"quality_controlled":"1","publication_identifier":{"isbn":["9783030795269"],"issn":["03029743"],"eissn":["16113349"]},"month":"06","intvolume":" 12810","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","conference":{"location":"Wrocław, Poland","end_date":"2021-07-01","start_date":"2021-06-28","name":"SIROCCO: Structural Information and Communication Complexity"},"department":[{"_id":"DaAl"}],"date_created":"2021-08-08T22:01:29Z","date_published":"2021-06-20T00:00:00Z","oa":1,"_id":"9823","author":[{"first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"last_name":"Ellen","first_name":"Faith","full_name":"Ellen, Faith"},{"first_name":"Joel","full_name":"Rybicki, Joel","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646"}],"type":"conference","publisher":"Springer Nature","year":"2021","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-79527-6_6"},{"month":"05","quality_controlled":"1","publication_identifier":{"isbn":["9783030766566"],"issn":["03029743"],"eissn":["16113349"]},"volume":12708,"date_created":"2021-08-08T22:01:29Z","acknowledgement":"This work has been partially supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia through the project no. 451-03-68/2020-14/200156: “Innovative scientific and artistic research from the FTS (activity) domain” (LČ), the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183 (RB), and the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35 (RB).","department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","conference":{"location":"Uppsala, Sweden","start_date":"2021-05-24","end_date":"2021-05-27","name":"DGMM: International Conference on Discrete Geometry and Mathematical Morphology"},"intvolume":" 12708","author":[{"first_name":"Lidija","full_name":"Čomić, Lidija","last_name":"Čomić"},{"first_name":"Rita","full_name":"Zrour, Rita","last_name":"Zrour"},{"first_name":"Gaëlle","full_name":"Largeteau-Skapin, Gaëlle","last_name":"Largeteau-Skapin"},{"first_name":"Ranita","full_name":"Biswas, Ranita","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","last_name":"Biswas","orcid":"0000-0002-5372-7890"},{"full_name":"Andres, Eric","first_name":"Eric","last_name":"Andres"}],"_id":"9824","date_published":"2021-05-16T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-76657-3_10","publisher":"Springer Nature","year":"2021","type":"conference","publication":"Discrete Geometry and Mathematical Morphology","title":"Body centered cubic grid - coordinate system and discrete analytical plane definition","project":[{"call_identifier":"H2020","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended"},{"call_identifier":"FWF","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes"}],"citation":{"ieee":"L. Čomić, R. Zrour, G. Largeteau-Skapin, R. Biswas, and E. Andres, “Body centered cubic grid - coordinate system and discrete analytical plane definition,” in Discrete Geometry and Mathematical Morphology, Uppsala, Sweden, 2021, vol. 12708, pp. 152–163.","chicago":"Čomić, Lidija, Rita Zrour, Gaëlle Largeteau-Skapin, Ranita Biswas, and Eric Andres. “Body Centered Cubic Grid - Coordinate System and Discrete Analytical Plane Definition.” In Discrete Geometry and Mathematical Morphology, 12708:152–63. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-76657-3_10.","ama":"Čomić L, Zrour R, Largeteau-Skapin G, Biswas R, Andres E. Body centered cubic grid - coordinate system and discrete analytical plane definition. In: Discrete Geometry and Mathematical Morphology. Vol 12708. Springer Nature; 2021:152-163. doi:10.1007/978-3-030-76657-3_10","short":"L. Čomić, R. Zrour, G. Largeteau-Skapin, R. Biswas, E. Andres, in:, Discrete Geometry and Mathematical Morphology, Springer Nature, 2021, pp. 152–163.","ista":"Čomić L, Zrour R, Largeteau-Skapin G, Biswas R, Andres E. 2021. Body centered cubic grid - coordinate system and discrete analytical plane definition. Discrete Geometry and Mathematical Morphology. DGMM: International Conference on Discrete Geometry and Mathematical Morphology, LNCS, vol. 12708, 152–163.","mla":"Čomić, Lidija, et al. “Body Centered Cubic Grid - Coordinate System and Discrete Analytical Plane Definition.” Discrete Geometry and Mathematical Morphology, vol. 12708, Springer Nature, 2021, pp. 152–63, doi:10.1007/978-3-030-76657-3_10.","apa":"Čomić, L., Zrour, R., Largeteau-Skapin, G., Biswas, R., & Andres, E. (2021). Body centered cubic grid - coordinate system and discrete analytical plane definition. In Discrete Geometry and Mathematical Morphology (Vol. 12708, pp. 152–163). Uppsala, Sweden: Springer Nature. https://doi.org/10.1007/978-3-030-76657-3_10"},"scopus_import":"1","alternative_title":["LNCS"],"oa_version":"None","page":"152-163","publication_status":"published","day":"16","ec_funded":1,"abstract":[{"text":"We define a new compact coordinate system in which each integer triplet addresses a voxel in the BCC grid, and we investigate some of its properties. We propose a characterization of 3D discrete analytical planes with their topological features (in the Cartesian and in the new coordinate system) such as the interrelation between the thickness of the plane and the separability constraint we aim to obtain.","lang":"eng"}],"date_updated":"2022-05-31T06:58:21Z","status":"public"},{"publication":"Topics in Cryptology – CT-RSA 2021","title":"Dual lattice attacks for closest vector problems (with preprocessing)","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/557"}],"scopus_import":"1","alternative_title":["LNCS"],"citation":{"ama":"Laarhoven T, Walter M. Dual lattice attacks for closest vector problems (with preprocessing). In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer Nature; 2021:478-502. doi:10.1007/978-3-030-75539-3_20","apa":"Laarhoven, T., & Walter, M. (2021). Dual lattice attacks for closest vector problems (with preprocessing). In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 478–502). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_20","short":"T. Laarhoven, M. Walter, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 478–502.","mla":"Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector Problems (with Preprocessing).” Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021, pp. 478–502, doi:10.1007/978-3-030-75539-3_20.","ista":"Laarhoven T, Walter M. 2021. Dual lattice attacks for closest vector problems (with preprocessing). Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference, LNCS, vol. 12704, 478–502.","ieee":"T. Laarhoven and M. Walter, “Dual lattice attacks for closest vector problems (with preprocessing),” in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704, pp. 478–502.","chicago":"Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector Problems (with Preprocessing).” In Topics in Cryptology – CT-RSA 2021, 12704:478–502. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_20."},"oa_version":"Preprint","page":"478-502","publication_status":"published","day":"11","abstract":[{"lang":"eng","text":"The dual attack has long been considered a relevant attack on lattice-based cryptographic schemes relying on the hardness of learning with errors (LWE) and its structured variants. As solving LWE corresponds to finding a nearest point on a lattice, one may naturally wonder how efficient this dual approach is for solving more general closest vector problems, such as the classical closest vector problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP, and preprocessing versions of these problems. While primal, sieving-based solutions to these problems (with preprocessing) were recently studied in a series of works on approximate Voronoi cells [Laa16b, DLdW19, Laa20, DLvW20], for the dual attack no such overview exists, especially for problems with preprocessing. With one of the take-away messages of the approximate Voronoi cell line of work being that primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one may further wonder if the dual attack suffers the same drawbacks, or if it is perhaps a better solution when trying to solve BDD(P).\r\n\r\nIn this work we provide an overview of cost estimates for dual algorithms for solving these “classical” closest lattice vector problems. Heuristically we expect to solve the search version of average-case CVPP in time and space 20.293𝑑+𝑜(𝑑) in the single-target model. The distinguishing version of average-case CVPP, where we wish to distinguish between random targets and targets planted at distance (say) 0.99⋅𝑔𝑑 from the lattice, has the same complexity in the single-target model, but can be solved in time and space 20.195𝑑+𝑜(𝑑) in the multi-target setting, when given a large number of targets from either target distribution. This suggests an inequivalence between distinguishing and searching, as we do not expect a similar improvement in the multi-target setting to hold for search-CVPP. We analyze three slightly different decoders, both for distinguishing and searching, and experimentally obtain concrete cost estimates for the dual attack in dimensions 50 to 80, which confirm our heuristic assumptions, and show that the hidden order terms in the asymptotic estimates are quite small.\r\n\r\nOur main take-away message is that the dual attack appears to mirror the approximate Voronoi cell line of work – whereas using approximate Voronoi cells works well for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales well for BDD(P) instances but performs poorly on approximate CVP(P)."}],"status":"public","date_updated":"2023-02-23T14:09:54Z","volume":12704,"month":"05","quality_controlled":"1","publication_identifier":{"isbn":["9783030755386"],"issn":["03029743"],"eissn":["16113349"]},"article_processing_charge":"No","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","conference":{"location":"Virtual Event","start_date":"2021-05-17","end_date":"2021-05-20","name":"CT-RSA: Cryptographers’ Track at the RSA Conference"},"intvolume":" 12704","date_created":"2021-08-08T22:01:30Z","acknowledgement":"The authors thank Sauvik Bhattacharya, L´eo Ducas, Rachel Player, and Christine van Vredendaal for early discussions on this topic and on preliminary results. The authors further thank the reviewers of CT-RSA 2021 for their valuable feedback.","department":[{"_id":"KrPi"}],"date_published":"2021-05-11T00:00:00Z","author":[{"last_name":"Laarhoven","first_name":"Thijs","full_name":"Laarhoven, Thijs"},{"full_name":"Walter, Michael","first_name":"Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter"}],"oa":1,"_id":"9825","type":"conference","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-75539-3_20","publisher":"Springer Nature","year":"2021"},{"type":"conference","doi":"10.1007/978-3-030-75539-3_17","language":[{"iso":"eng"}],"year":"2021","publisher":"Springer Nature","date_published":"2021-05-11T00:00:00Z","author":[{"full_name":"Auerbach, Benedikt","first_name":"Benedikt","orcid":"0000-0002-7553-6606","last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen"},{"full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez"},{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","first_name":"Michael"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo"}],"_id":"9826","oa":1,"conference":{"start_date":"2021-05-17","end_date":"2021-05-20","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","location":"Virtual Event"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","intvolume":" 12704","date_created":"2021-08-08T22:01:30Z","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"acknowledgement":"Guillermo Pascual-Perez and Michelle Yeo were funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie Grant Agreement No. 665385; the remaining contributors to this project have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","volume":12704,"month":"05","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030755386"]},"quality_controlled":"1","status":"public","date_updated":"2023-02-23T14:09:56Z","day":"11","page":"399-421","oa_version":"Submitted Version","publication_status":"published","abstract":[{"text":"Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices.\r\n\r\nWe propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.","lang":"eng"}],"ec_funded":1,"scopus_import":"1","alternative_title":["LNCS"],"citation":{"ieee":"B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,” in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704, pp. 399–421.","chicago":"Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021, 12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17.","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17","ista":"Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference, LNCS, vol. 12704, 399–421.","short":"B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 399–421.","mla":"Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:10.1007/978-3-030-75539-3_17."},"project":[{"call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"},{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020"}],"publication":"Topics in Cryptology – CT-RSA 2021","title":"Inverse-Sybil attacks in automated contact tracing","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/670"}]},{"date_created":"2020-05-10T22:00:49Z","department":[{"_id":"ToHe"}],"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","file_date_updated":"2020-07-14T12:48:03Z","conference":{"location":"Dublin, Ireland","start_date":"2020-04-25","end_date":"2020-04-30","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems"},"intvolume":" 12079","month":"04","quality_controlled":"1","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030452360"]},"volume":12079,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-45237-7_5","publisher":"Springer Nature","year":"2020","type":"conference","author":[{"orcid":"0000-0001-8180-0904","last_name":"Giacobbe","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","full_name":"Giacobbe, Mirco","first_name":"Mirco"},{"orcid":"0000-0002-2985-7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"id":"3DC22916-F248-11E8-B48F-1D18A9856A87","last_name":"Lechner","full_name":"Lechner, Mathias","first_name":"Mathias"}],"oa":1,"_id":"7808","date_published":"2020-04-17T00:00:00Z","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"},{"name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF"}],"citation":{"chicago":"Giacobbe, Mirco, Thomas A Henzinger, and Mathias Lechner. “How Many Bits Does It Take to Quantize Your Neural Network?” In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 12079:79–97. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45237-7_5.","ieee":"M. Giacobbe, T. A. Henzinger, and M. Lechner, “How many bits does it take to quantize your neural network?,” in International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Dublin, Ireland, 2020, vol. 12079, pp. 79–97.","short":"M. Giacobbe, T.A. Henzinger, M. Lechner, in:, International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2020, pp. 79–97.","apa":"Giacobbe, M., Henzinger, T. A., & Lechner, M. (2020). How many bits does it take to quantize your neural network? In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (Vol. 12079, pp. 79–97). Dublin, Ireland: Springer Nature. https://doi.org/10.1007/978-3-030-45237-7_5","mla":"Giacobbe, Mirco, et al. “How Many Bits Does It Take to Quantize Your Neural Network?” International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 12079, Springer Nature, 2020, pp. 79–97, doi:10.1007/978-3-030-45237-7_5.","ista":"Giacobbe M, Henzinger TA, Lechner M. 2020. How many bits does it take to quantize your neural network? International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 12079, 79–97.","ama":"Giacobbe M, Henzinger TA, Lechner M. How many bits does it take to quantize your neural network? In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Vol 12079. Springer Nature; 2020:79-97. doi:10.1007/978-3-030-45237-7_5"},"scopus_import":1,"alternative_title":["LNCS"],"has_accepted_license":"1","publication":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","related_material":{"record":[{"id":"11362","status":"public","relation":"dissertation_contains"}]},"file":[{"file_size":2744030,"file_name":"2020_TACAS_Giacobbe.pdf","date_updated":"2020-07-14T12:48:03Z","file_id":"7893","date_created":"2020-05-26T12:48:15Z","checksum":"f19905a42891fe5ce93d69143fa3f6fb","creator":"dernst","relation":"main_file","content_type":"application/pdf","access_level":"open_access"}],"title":"How many bits does it take to quantize your neural network?","date_updated":"2023-06-23T07:01:11Z","status":"public","page":"79-97","oa_version":"Published Version","publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"17","abstract":[{"text":"Quantization converts neural networks into low-bit fixed-point computations which can be carried out by efficient integer-only hardware, and is standard practice for the deployment of neural networks on real-time embedded devices. However, like their real-numbered counterpart, quantized networks are not immune to malicious misclassification caused by adversarial attacks. We investigate how quantization affects a network’s robustness to adversarial attacks, which is a formal verification question. We show that neither robustness nor non-robustness are monotonic with changing the number of bits for the representation and, also, neither are preserved by quantization from a real-numbered network. For this reason, we introduce a verification method for quantized neural networks which, using SMT solving over bit-vectors, accounts for their exact, bit-precise semantics. We built a tool and analyzed the effect of quantization on a classifier for the MNIST dataset. We demonstrate that, compared to our method, existing methods for the analysis of real-numbered networks often derive false conclusions about their quantizations, both when determining robustness and when detecting attacks, and that existing methods for quantized networks often miss attacks. Furthermore, we applied our method beyond robustness, showing how the number of bits in quantization enlarges the gender bias of a predictor for students’ grades.","lang":"eng"}]},{"quality_controlled":"1","publication_identifier":{"issn":["03029743"],"isbn":["9783030449131"],"eissn":["16113349"]},"month":"04","volume":12075,"isi":1,"department":[{"_id":"KrCh"}],"date_created":"2020-05-10T22:00:50Z","intvolume":" 12075","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","ddc":["000"],"file_date_updated":"2020-07-14T12:48:03Z","conference":{"start_date":"2020-04-25","end_date":"2020-04-30","name":"ESOP: Programming Languages and Systems","location":"Dublin, Ireland"},"oa":1,"_id":"7810","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0003-1702-6584","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87","full_name":"Goharshady, Amir Kafshdar","first_name":"Amir Kafshdar"},{"first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis"}],"date_published":"2020-04-18T00:00:00Z","publisher":"Springer Nature","year":"2020","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-44914-8_5","type":"conference","external_id":{"isi":["000681656800005"]},"related_material":{"record":[{"status":"public","id":"8934","relation":"dissertation_contains"}]},"title":"Optimal and perfectly parallel algorithms for on-demand data-flow analysis","file":[{"creator":"dernst","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"2020_LNCS_Chatterjee.pdf","file_size":651250,"checksum":"8618b80f4cf7b39a60e61a6445ad9807","file_id":"7895","date_created":"2020-05-26T13:34:48Z","date_updated":"2020-07-14T12:48:03Z"}],"publication":"European Symposium on Programming","project":[{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"},{"_id":"266EEEC0-B435-11E9-9278-68D0E5697425","name":"Quantitative Game-theoretic Analysis of Blockchain Applications and Smart Contracts"},{"name":"Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies","_id":"267066CE-B435-11E9-9278-68D0E5697425"}],"citation":{"ieee":"K. Chatterjee, A. K. Goharshady, R. Ibsen-Jensen, and A. Pavlogiannis, “Optimal and perfectly parallel algorithms for on-demand data-flow analysis,” in European Symposium on Programming, Dublin, Ireland, 2020, vol. 12075, pp. 112–140.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Optimal and Perfectly Parallel Algorithms for On-Demand Data-Flow Analysis.” In European Symposium on Programming, 12075:112–40. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-44914-8_5.","ama":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In: European Symposium on Programming. Vol 12075. Springer Nature; 2020:112-140. doi:10.1007/978-3-030-44914-8_5","ista":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2020. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. European Symposium on Programming. ESOP: Programming Languages and Systems, LNCS, vol. 12075, 112–140.","short":"K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, European Symposium on Programming, Springer Nature, 2020, pp. 112–140.","apa":"Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2020). Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In European Symposium on Programming (Vol. 12075, pp. 112–140). Dublin, Ireland: Springer Nature. https://doi.org/10.1007/978-3-030-44914-8_5","mla":"Chatterjee, Krishnendu, et al. “Optimal and Perfectly Parallel Algorithms for On-Demand Data-Flow Analysis.” European Symposium on Programming, vol. 12075, Springer Nature, 2020, pp. 112–40, doi:10.1007/978-3-030-44914-8_5."},"alternative_title":["LNCS"],"has_accepted_license":"1","scopus_import":"1","abstract":[{"lang":"eng","text":"Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries.\r\nIn this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques."}],"page":"112-140","publication_status":"published","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"18","date_updated":"2025-06-02T08:53:42Z","status":"public"},{"date_published":"2020-06-24T00:00:00Z","_id":"8194","oa":1,"author":[{"last_name":"Baranowski","full_name":"Baranowski, Marek","first_name":"Marek"},{"full_name":"He, Shaobo","first_name":"Shaobo","last_name":"He"},{"id":"3DC22916-F248-11E8-B48F-1D18A9856A87","last_name":"Lechner","full_name":"Lechner, Mathias","first_name":"Mathias"},{"full_name":"Nguyen, Thanh Son","first_name":"Thanh Son","last_name":"Nguyen"},{"full_name":"Rakamarić, Zvonimir","first_name":"Zvonimir","last_name":"Rakamarić"}],"type":"conference","year":"2020","publisher":"Springer Nature","doi":"10.1007/978-3-030-51074-9_2","language":[{"iso":"eng"}],"volume":12166,"isi":1,"publication_identifier":{"issn":["03029743"],"isbn":["9783030510732"],"eissn":["16113349"]},"quality_controlled":"1","month":"06","intvolume":" 12166","conference":{"location":"Paris, France","start_date":"2020-07-01","end_date":"2020-07-04","name":"IJCAR: International Joint Conference on Automated Reasoning"},"article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"ToHe"}],"date_created":"2020-08-02T22:00:59Z","abstract":[{"lang":"eng","text":"Fixed-point arithmetic is a popular alternative to floating-point arithmetic on embedded systems. Existing work on the verification of fixed-point programs relies on custom formalizations of fixed-point arithmetic, which makes it hard to compare the described techniques or reuse the implementations. In this paper, we address this issue by proposing and formalizing an SMT theory of fixed-point arithmetic. We present an intuitive yet comprehensive syntax of the fixed-point theory, and provide formal semantics for it based on rational arithmetic. We also describe two decision procedures for this theory: one based on the theory of bit-vectors and the other on the theory of reals. We implement the two decision procedures, and evaluate our implementations using existing mature SMT solvers on a benchmark suite we created. Finally, we perform a case study of using the theory we propose to verify properties of quantized neural networks."}],"day":"24","page":"13-31","oa_version":"Published Version","publication_status":"published","status":"public","date_updated":"2023-08-22T08:27:25Z","title":"An SMT theory of fixed-point arithmetic","external_id":{"isi":["000884318000002"]},"publication":"Automated Reasoning","main_file_link":[{"url":"https://doi.org/10.1007/978-3-030-51074-9_2","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","citation":{"chicago":"Baranowski, Marek, Shaobo He, Mathias Lechner, Thanh Son Nguyen, and Zvonimir Rakamarić. “An SMT Theory of Fixed-Point Arithmetic.” In Automated Reasoning, 12166:13–31. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-51074-9_2.","ieee":"M. Baranowski, S. He, M. Lechner, T. S. Nguyen, and Z. Rakamarić, “An SMT theory of fixed-point arithmetic,” in Automated Reasoning, Paris, France, 2020, vol. 12166, pp. 13–31.","mla":"Baranowski, Marek, et al. “An SMT Theory of Fixed-Point Arithmetic.” Automated Reasoning, vol. 12166, Springer Nature, 2020, pp. 13–31, doi:10.1007/978-3-030-51074-9_2.","ista":"Baranowski M, He S, Lechner M, Nguyen TS, Rakamarić Z. 2020. An SMT theory of fixed-point arithmetic. Automated Reasoning. IJCAR: International Joint Conference on Automated Reasoning, LNCS, vol. 12166, 13–31.","short":"M. Baranowski, S. He, M. Lechner, T.S. Nguyen, Z. Rakamarić, in:, Automated Reasoning, Springer Nature, 2020, pp. 13–31.","apa":"Baranowski, M., He, S., Lechner, M., Nguyen, T. S., & Rakamarić, Z. (2020). An SMT theory of fixed-point arithmetic. In Automated Reasoning (Vol. 12166, pp. 13–31). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-030-51074-9_2","ama":"Baranowski M, He S, Lechner M, Nguyen TS, Rakamarić Z. An SMT theory of fixed-point arithmetic. In: Automated Reasoning. Vol 12166. Springer Nature; 2020:13-31. doi:10.1007/978-3-030-51074-9_2"},"project":[{"call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}]},{"intvolume":" 12225","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","ddc":["000"],"article_processing_charge":"No","conference":{"name":"CAV: Computer Aided Verification"},"file_date_updated":"2020-08-17T11:32:44Z","department":[{"_id":"KrCh"}],"date_created":"2020-08-16T22:00:58Z","volume":12225,"isi":1,"quality_controlled":"1","publication_identifier":{"issn":["03029743"],"isbn":["9783030532901"],"eissn":["16113349"]},"month":"07","type":"conference","publisher":"Springer Nature","year":"2020","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-53291-8_21","date_published":"2020-07-14T00:00:00Z","oa":1,"_id":"8272","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Katoen, Joost P","first_name":"Joost P","last_name":"Katoen","id":"4524F760-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Weininger","first_name":"Maximilian","full_name":"Weininger, Maximilian"},{"full_name":"Winkler, Tobias","first_name":"Tobias","last_name":"Winkler"}],"alternative_title":["LNCS"],"has_accepted_license":"1","scopus_import":"1","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification"}],"arxiv":1,"citation":{"mla":"Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Reachability-Safety Objectives.” International Conference on Computer Aided Verification, vol. 12225, Springer Nature, 2020, pp. 398–420, doi:10.1007/978-3-030-53291-8_21.","short":"K. Chatterjee, J.P. Katoen, M. Weininger, T. Winkler, in:, International Conference on Computer Aided Verification, Springer Nature, 2020, pp. 398–420.","ista":"Chatterjee K, Katoen JP, Weininger M, Winkler T. 2020. Stochastic games with lexicographic reachability-safety objectives. International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 12225, 398–420.","apa":"Chatterjee, K., Katoen, J. P., Weininger, M., & Winkler, T. (2020). Stochastic games with lexicographic reachability-safety objectives. In International Conference on Computer Aided Verification (Vol. 12225, pp. 398–420). Springer Nature. https://doi.org/10.1007/978-3-030-53291-8_21","ama":"Chatterjee K, Katoen JP, Weininger M, Winkler T. Stochastic games with lexicographic reachability-safety objectives. In: International Conference on Computer Aided Verification. Vol 12225. Springer Nature; 2020:398-420. doi:10.1007/978-3-030-53291-8_21","chicago":"Chatterjee, Krishnendu, Joost P Katoen, Maximilian Weininger, and Tobias Winkler. “Stochastic Games with Lexicographic Reachability-Safety Objectives.” In International Conference on Computer Aided Verification, 12225:398–420. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-53291-8_21.","ieee":"K. Chatterjee, J. P. Katoen, M. Weininger, and T. Winkler, “Stochastic games with lexicographic reachability-safety objectives,” in International Conference on Computer Aided Verification, 2020, vol. 12225, pp. 398–420."},"external_id":{"isi":["000695272500021"],"arxiv":["2005.04018"]},"related_material":{"record":[{"status":"public","id":"12738","relation":"later_version"}]},"title":"Stochastic games with lexicographic reachability-safety objectives","file":[{"creator":"dernst","relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_size":625056,"file_name":"2020_LNCS_CAV_Chatterjee.pdf","date_updated":"2020-08-17T11:32:44Z","success":1,"date_created":"2020-08-17T11:32:44Z","file_id":"8276","checksum":"093d4788d7d5b2ce0ffe64fbe7820043"}],"publication":"International Conference on Computer Aided Verification","status":"public","date_updated":"2025-07-14T09:10:14Z","ec_funded":1,"abstract":[{"lang":"eng","text":"We study turn-based stochastic zero-sum games with lexicographic preferences over reachability and safety objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as angelic and demonic non-determinism. Lexicographic order allows to consider multiple objectives with a strict preference order over the satisfaction of the objectives. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. We establish determinacy of such games and present strategy and computational complexity results. For strategy complexity, we show that lexicographically optimal strategies exist that are deterministic and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP , matching the current known bound for single objectives; and in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME . We present an algorithm that computes the lexicographically optimal strategies via a reduction to computation of optimal strategies in a sequence of single-objectives games. We have implemented our algorithm and report experimental results on various case studies."}],"publication_status":"published","page":"398-420","oa_version":"Published Version","day":"14","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"date_created":"2020-08-30T22:01:12Z","acknowledgement":"We would like to thank the anonymous reviewers for their helpful comments and suggestions. The work was initiated while the first author was in IIT Madras, India. Part of this work was done while the author was visiting the University of Warsaw. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT) and from the Foundation for Polish Science under grant TEAM/2016-1/4 founded within the UE 2014–2020 Smart Growth Operational Program. The last author was supported by the Independent Research Fund Denmark project BETHE and the Concordium Blockchain Research Center, Aarhus University, Denmark.","department":[{"_id":"KrPi"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Santa Barbara, CA, United States","end_date":"2020-08-21","start_date":"2020-08-17","name":"CRYPTO: Annual International Cryptology Conference"},"intvolume":" 12171","month":"08","quality_controlled":"1","publication_identifier":{"eissn":["16113349"],"isbn":["9783030568795"],"issn":["03029743"]},"volume":12171,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-56880-1_26","publisher":"Springer Nature","year":"2020","type":"conference","author":[{"first_name":"Suvradip","full_name":"Chakraborty, Suvradip","last_name":"Chakraborty","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"full_name":"Dziembowski, Stefan","first_name":"Stefan","last_name":"Dziembowski"},{"first_name":"Jesper Buus","full_name":"Nielsen, Jesper Buus","last_name":"Nielsen"}],"oa":1,"_id":"8322","date_published":"2020-08-10T00:00:00Z","project":[{"grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"}],"citation":{"chicago":"Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.” In Advances in Cryptology – CRYPTO 2020, 12171:732–62. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-56880-1_26.","ieee":"S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,” in Advances in Cryptology – CRYPTO 2020, Santa Barbara, CA, United States, 2020, vol. 12171, pp. 732–762.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.” Advances in Cryptology – CRYPTO 2020, vol. 12171, Springer Nature, 2020, pp. 732–62, doi:10.1007/978-3-030-56880-1_26.","apa":"Chakraborty, S., Dziembowski, S., & Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs. In Advances in Cryptology – CRYPTO 2020 (Vol. 12171, pp. 732–762). Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-56880-1_26","short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 732–762.","ista":"Chakraborty S, Dziembowski S, Nielsen JB. 2020. Reverse firewalls for actively secure MPCs. Advances in Cryptology – CRYPTO 2020. CRYPTO: Annual International Cryptology Conference, LNCS, vol. 12171, 732–762.","ama":"Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs. In: Advances in Cryptology – CRYPTO 2020. Vol 12171. Springer Nature; 2020:732-762. doi:10.1007/978-3-030-56880-1_26"},"scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1317"}],"publication":"Advances in Cryptology – CRYPTO 2020","title":"Reverse firewalls for actively secure MPCs","date_updated":"2021-01-12T08:18:08Z","status":"public","publication_status":"published","oa_version":"Preprint","page":"732-762","day":"10","ec_funded":1,"abstract":[{"lang":"eng","text":"Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to “sanitize” the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a “functionality-preserving way” (i.e. informally speaking, the functionality of the protocol remains unchanged under this attacks). In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question.\r\nIn this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary number n of the parties, and not just for 2). Secondly, it is secure in much stronger corruption settings, namely in the active corruption model. More precisely: we consider an adversary that can fully corrupt up to 𝑛−1 parties, while the remaining parties are corrupt in a functionality-preserving way.\r\nOur core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001)."}]},{"conference":{"end_date":"2020-05-07","start_date":"2020-05-04","name":"PKC: Public-Key Cryptography","location":"Edinburgh, United Kingdom"},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 12110","date_created":"2020-09-06T22:01:13Z","department":[{"_id":"KrPi"}],"volume":12110,"month":"05","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030453732"]},"quality_controlled":"1","type":"conference","doi":"10.1007/978-3-030-45374-9_21","language":[{"iso":"eng"}],"year":"2020","publisher":"Springer Nature","date_published":"2020-05-15T00:00:00Z","author":[{"full_name":"Genise, Nicholas","first_name":"Nicholas","last_name":"Genise"},{"first_name":"Daniele","full_name":"Micciancio, Daniele","last_name":"Micciancio"},{"first_name":"Chris","full_name":"Peikert, Chris","last_name":"Peikert"},{"first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"_id":"8339","oa":1,"scopus_import":"1","alternative_title":["LNCS"],"citation":{"chicago":"Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” In 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, 12110:623–51. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_21.","ieee":"N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian and subgaussian analysis for lattice cryptography,” in 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Edinburgh, United Kingdom, 2020, vol. 12110, pp. 623–651.","short":"N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature, 2020, pp. 623–651.","apa":"Genise, N., Micciancio, D., Peikert, C., & Walter, M. (2020). Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography (Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_21","ista":"Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 12110, 623–651.","mla":"Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, vol. 12110, Springer Nature, 2020, pp. 623–51, doi:10.1007/978-3-030-45374-9_21.","ama":"Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In: 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. Vol 12110. Springer Nature; 2020:623-651. doi:10.1007/978-3-030-45374-9_21"},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815"}],"publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/337"}],"status":"public","date_updated":"2023-02-23T13:31:06Z","day":"15","publication_status":"published","page":"623-651","oa_version":"Preprint","abstract":[{"text":"Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.\r\nIn this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems.","lang":"eng"}],"ec_funded":1},{"conference":{"location":"Bangalore, India","start_date":"2020-12-13","end_date":"2020-12-16","name":"INDOCRYPT: International Conference on Cryptology in India"},"article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 12578","date_created":"2021-01-03T23:01:23Z","department":[{"_id":"KrPi"}],"isi":1,"volume":12578,"month":"12","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030652760"]},"quality_controlled":"1","type":"conference","doi":"10.1007/978-3-030-65277-7_1","language":[{"iso":"eng"}],"year":"2020","publisher":"Springer Nature","date_published":"2020-12-08T00:00:00Z","author":[{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"_id":"8987","oa":1,"scopus_import":"1","citation":{"mla":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” Progress in Cryptology, vol. 12578, Springer Nature, 2020, pp. 3–15, doi:10.1007/978-3-030-65277-7_1.","ista":"Pietrzak KZ. 2020. Delayed authentication: Preventing replay and relay attacks in private contact tracing. Progress in Cryptology. INDOCRYPT: International Conference on Cryptology in IndiaLNCS vol. 12578, 3–15.","short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","apa":"Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay attacks in private contact tracing. In Progress in Cryptology (Vol. 12578, pp. 3–15). Bangalore, India: Springer Nature. https://doi.org/10.1007/978-3-030-65277-7_1","ama":"Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in private contact tracing. In: Progress in Cryptology. Vol 12578. LNCS. Springer Nature; 2020:3-15. doi:10.1007/978-3-030-65277-7_1","chicago":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” In Progress in Cryptology, 12578:3–15. LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-65277-7_1.","ieee":"K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks in private contact tracing,” in Progress in Cryptology, Bangalore, India, 2020, vol. 12578, pp. 3–15."},"project":[{"grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"series_title":"LNCS","publication":"Progress in Cryptology","title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing","external_id":{"isi":["000927592800001"]},"main_file_link":[{"url":"https://eprint.iacr.org/2020/418","open_access":"1"}],"status":"public","date_updated":"2023-08-24T11:08:58Z","day":"08","page":"3-15","oa_version":"Preprint","publication_status":"published","abstract":[{"lang":"eng","text":"Currently several projects aim at designing and implementing protocols for privacy preserving automated contact tracing to help fight the current pandemic. Those proposal are quite similar, and in their most basic form basically propose an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, they upload either the beacons they did broadcast (which is the case in decentralized proposals as DP-3T, east and west coast PACT or Covid watch) or received (as in Popp-PT or ROBERT) during the last two weeks or so.\r\n\r\nVaudenay [eprint 2020/399] observes that this basic scheme (he considers the DP-3T proposal) succumbs to relay and even replay attacks, and proposes more complex interactive schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons. The countermeasures that have been suggested so far are either not practical or give up on key privacy aspects. We propose a simple non-interactive variant of the basic protocol that\r\n(security) Provably prevents replay and (if location data is available) relay attacks.\r\n(privacy) The data of all parties (even jointly) reveals no information on the location or time where encounters happened.\r\n(efficiency) The broadcasted message can fit into 128 bits and uses only basic crypto (commitments and secret key authentication).\r\n\r\nTowards this end we introduce the concept of “delayed authentication”, which basically is a message authentication code where verification can be done in two steps, where the first doesn’t require the key, and the second doesn’t require the message."}],"ec_funded":1},{"oa":1,"_id":"7183","author":[{"full_name":"Brázdil, Tomás","first_name":"Tomás","last_name":"Brázdil"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Antonín","full_name":"Kucera, Antonín","last_name":"Kucera"},{"full_name":"Novotný, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","last_name":"Novotný"},{"full_name":"Velan, Dominik","first_name":"Dominik","last_name":"Velan"}],"date_published":"2019-10-21T00:00:00Z","publisher":"Springer Nature","year":"2019","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-31784-3_27","type":"conference","quality_controlled":"1","publication_identifier":{"issn":["03029743"],"isbn":["9783030317836"],"eissn":["16113349"]},"month":"10","volume":11781,"isi":1,"department":[{"_id":"KrCh"}],"date_created":"2019-12-15T23:00:44Z","intvolume":" 11781","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","conference":{"name":"ATVA: Automated TEchnology for Verification and Analysis","end_date":"2019-10-31","start_date":"2019-10-28","location":"Taipei, Taiwan"},"abstract":[{"lang":"eng","text":"A probabilistic vector addition system with states (pVASS) is a finite state Markov process augmented with non-negative integer counters that can be incremented or decremented during each state transition, blocking any behaviour that would cause a counter to decrease below zero. The pVASS can be used as abstractions of probabilistic programs with many decidable properties. The use of pVASS as abstractions requires the presence of nondeterminism in the model. In this paper, we develop techniques for checking fast termination of pVASS with nondeterminism. That is, for every initial configuration of size n, we consider the worst expected number of transitions needed to reach a configuration with some counter negative (the expected termination time). We show that the problem whether the asymptotic expected termination time is linear is decidable in polynomial time for a certain natural class of pVASS with nondeterminism. Furthermore, we show the following dichotomy: if the asymptotic expected termination time is not linear, then it is at least quadratic, i.e., in Ω(n2)."}],"publication_status":"published","oa_version":"Preprint","page":"462-478","day":"21","date_updated":"2023-09-06T12:40:58Z","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.11010"}],"external_id":{"isi":["000723515700027"],"arxiv":["1907.11010"]},"title":"Deciding fast termination for probabilistic VASS with nondeterminism","publication":"International Symposium on Automated Technology for Verification and Analysis","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"}],"arxiv":1,"citation":{"chicago":"Brázdil, Tomás, Krishnendu Chatterjee, Antonín Kucera, Petr Novotný, and Dominik Velan. “Deciding Fast Termination for Probabilistic VASS with Nondeterminism.” In International Symposium on Automated Technology for Verification and Analysis, 11781:462–78. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-31784-3_27.","ieee":"T. Brázdil, K. Chatterjee, A. Kucera, P. Novotný, and D. Velan, “Deciding fast termination for probabilistic VASS with nondeterminism,” in International Symposium on Automated Technology for Verification and Analysis, Taipei, Taiwan, 2019, vol. 11781, pp. 462–478.","apa":"Brázdil, T., Chatterjee, K., Kucera, A., Novotný, P., & Velan, D. (2019). Deciding fast termination for probabilistic VASS with nondeterminism. In International Symposium on Automated Technology for Verification and Analysis (Vol. 11781, pp. 462–478). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-030-31784-3_27","short":"T. Brázdil, K. Chatterjee, A. Kucera, P. Novotný, D. Velan, in:, International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2019, pp. 462–478.","mla":"Brázdil, Tomás, et al. “Deciding Fast Termination for Probabilistic VASS with Nondeterminism.” International Symposium on Automated Technology for Verification and Analysis, vol. 11781, Springer Nature, 2019, pp. 462–78, doi:10.1007/978-3-030-31784-3_27.","ista":"Brázdil T, Chatterjee K, Kucera A, Novotný P, Velan D. 2019. Deciding fast termination for probabilistic VASS with nondeterminism. International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated TEchnology for Verification and Analysis, LNCS, vol. 11781, 462–478.","ama":"Brázdil T, Chatterjee K, Kucera A, Novotný P, Velan D. Deciding fast termination for probabilistic VASS with nondeterminism. In: International Symposium on Automated Technology for Verification and Analysis. Vol 11781. Springer Nature; 2019:462-478. doi:10.1007/978-3-030-31784-3_27"},"alternative_title":["LNCS"],"scopus_import":"1"},{"date_published":"2019-04-06T00:00:00Z","author":[{"last_name":"Fuchsbauer","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"oa":1,"_id":"6430","type":"conference","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-17259-6_11","publisher":"Springer Nature","year":"2019","volume":11443,"month":"04","quality_controlled":"1","publication_identifier":{"issn":["03029743"],"isbn":["9783030172589"],"eissn":["16113349"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","conference":{"start_date":"2019-04-14","end_date":"2019-04-17","name":"PKC: Public-Key Cryptograhy","location":"Beijing, China"},"intvolume":" 11443","date_created":"2019-05-13T08:13:46Z","department":[{"_id":"KrPi"}],"oa_version":"Preprint","publication_status":"published","page":"317-346","day":"06","ec_funded":1,"abstract":[{"lang":"eng","text":"A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14)."}],"status":"public","date_updated":"2023-09-08T11:33:20Z","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10035"}]},"title":"Adaptively secure proxy re-encryption","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/426"}],"scopus_import":"1","alternative_title":["LNCS"],"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815"}],"citation":{"ieee":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing, China, 2019, vol. 11443, pp. 317–346.","chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-17259-6_11.","ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346.","mla":"Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11.","apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019). Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11","ista":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346."}},{"status":"public","date_updated":"2021-08-12T13:53:17Z","abstract":[{"lang":"eng","text":"In this paper, we establish a correspondence between the incremental algorithm for computing AT-models [8,9] and the one for computing persistent homology [6,14,15]. We also present a decremental algorithm for computing AT-models that allows to extend the persistence computation to a wider setting. Finally, we show how to combine incremental and decremental techniques for persistent homology computation."}],"day":"01","publication_status":"published","oa_version":"Published Version","page":"286-293","alternative_title":["LNCS"],"scopus_import":"1","citation":{"chicago":"Gonzalez-Diaz, Rocio, Adrian Ion, Maria Jose Jimenez, and Regina Poyatos. “Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.” In Computer Analysis of Images and Patterns, 6854:286–93. Springer Nature, 2011. https://doi.org/10.1007/978-3-642-23672-3_35.","ieee":"R. Gonzalez-Diaz, A. Ion, M. J. Jimenez, and R. Poyatos, “Incremental-decremental algorithm for computing AT-models and persistent homology,” in Computer Analysis of Images and Patterns, Seville, Spain, 2011, vol. 6854, pp. 286–293.","apa":"Gonzalez-Diaz, R., Ion, A., Jimenez, M. J., & Poyatos, R. (2011). Incremental-decremental algorithm for computing AT-models and persistent homology. In Computer Analysis of Images and Patterns (Vol. 6854, pp. 286–293). Seville, Spain: Springer Nature. https://doi.org/10.1007/978-3-642-23672-3_35","short":"R. Gonzalez-Diaz, A. Ion, M.J. Jimenez, R. Poyatos, in:, Computer Analysis of Images and Patterns, Springer Nature, 2011, pp. 286–293.","ista":"Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. 2011. Incremental-decremental algorithm for computing AT-models and persistent homology. Computer Analysis of Images and Patterns. CAIP: International Conference on Computer Analysis of Images and Patterns, LNCS, vol. 6854, 286–293.","mla":"Gonzalez-Diaz, Rocio, et al. “Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.” Computer Analysis of Images and Patterns, vol. 6854, Springer Nature, 2011, pp. 286–93, doi:10.1007/978-3-642-23672-3_35.","ama":"Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. Incremental-decremental algorithm for computing AT-models and persistent homology. In: Computer Analysis of Images and Patterns. Vol 6854. Springer Nature; 2011:286-293. doi:10.1007/978-3-642-23672-3_35"},"title":"Incremental-decremental algorithm for computing AT-models and persistent homology","publication":"Computer Analysis of Images and Patterns","main_file_link":[{"open_access":"1","url":"http://hdl.handle.net/11441/30766"}],"type":"conference","year":"2011","publisher":"Springer Nature","doi":"10.1007/978-3-642-23672-3_35","language":[{"iso":"eng"}],"date_published":"2011-08-01T00:00:00Z","_id":"9648","oa":1,"author":[{"last_name":"Gonzalez-Diaz","full_name":"Gonzalez-Diaz, Rocio","first_name":"Rocio"},{"last_name":"Ion","id":"29F89302-F248-11E8-B48F-1D18A9856A87","first_name":"Adrian","full_name":"Ion, Adrian"},{"last_name":"Jimenez","first_name":"Maria Jose","full_name":"Jimenez, Maria Jose"},{"first_name":"Regina","full_name":"Poyatos, Regina","last_name":"Poyatos"}],"intvolume":" 6854","conference":{"start_date":"2011-08-29","end_date":"2011-08-31","name":"CAIP: International Conference on Computer Analysis of Images and Patterns","location":"Seville, Spain"},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","department":[{"_id":"HeEd"}],"date_created":"2021-07-11T22:01:19Z","volume":6854,"publication_identifier":{"eissn":["16113349"],"isbn":["9783642236716"],"issn":["03029743"]},"quality_controlled":"1","month":"08"}]