[{"oa":1,"quality_controlled":"1","publisher":"Springer Nature","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","date_published":"2021-05-01T00:00:00Z","doi":"10.1007/978-3-030-75245-3_3","page":"45-67","publication":"Public-Key Cryptography – PKC 2021","day":"01","year":"2021","has_accepted_license":"1","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"title":"The convergence of slide-type reductions","article_processing_charge":"No","author":[{"full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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","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","ieee":"M. Walter, “The convergence of slide-type reductions,” in Public-Key Cryptography – PKC 2021, Virtual, 2021, vol. 12710, pp. 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.","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.","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."},"intvolume":" 12710","month":"05","scopus_import":"1","alternative_title":["LNCS"],"oa_version":"Published Version","abstract":[{"lang":"eng","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."}],"ec_funded":1,"license":"https://creativecommons.org/licenses/by/4.0/","volume":12710,"language":[{"iso":"eng"}],"file":[{"date_updated":"2022-05-27T09:48:31Z","file_size":489017,"creator":"dernst","date_created":"2022-05-27T09:48:31Z","file_name":"2021_PKC_Walter.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"413e564d645ed93d7318672361d9d470","file_id":"11416","success":1}],"publication_status":"published","publication_identifier":{"eissn":["16113349"],"isbn":["9783030752446"],"issn":["03029743"]},"status":"public","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)"},"conference":{"end_date":"2021-05-13","location":"Virtual","start_date":"2021-05-10","name":"PKC: IACR International Conference on Practice and Theory of Public Key Cryptography"},"type":"conference","_id":"9466","department":[{"_id":"KrPi"}],"file_date_updated":"2022-05-27T09:48:31Z","ddc":["000"],"date_updated":"2023-02-23T13:58:47Z"},{"main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 12704","month":"05","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"}],"oa_version":"Submitted Version","ec_funded":1,"volume":12704,"publication_status":"published","publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783030755386"]},"language":[{"iso":"eng"}],"conference":{"end_date":"2021-05-20","location":"Virtual Event","start_date":"2021-05-17","name":"CT-RSA: Cryptographers’ Track at the RSA Conference"},"type":"conference","status":"public","_id":"9826","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"date_updated":"2023-02-23T14:09:56Z","oa":1,"quality_controlled":"1","publisher":"Springer Nature","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).","page":"399-421","date_created":"2021-08-08T22:01:30Z","doi":"10.1007/978-3-030-75539-3_17","date_published":"2021-05-11T00:00:00Z","year":"2021","publication":"Topics in Cryptology – CT-RSA 2021","day":"11","project":[{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","grant_number":"665385"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"article_processing_charge":"No","author":[{"first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","last_name":"Auerbach"},{"last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"}],"title":"Inverse-Sybil attacks in automated contact tracing","citation":{"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.","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.","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.","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.","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","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"citation":{"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.","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.","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.","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.","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."},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","author":[{"first_name":"Thijs","full_name":"Laarhoven, Thijs","last_name":"Laarhoven"},{"last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael"}],"title":"Dual lattice attacks for closest vector problems (with preprocessing)","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.","oa":1,"quality_controlled":"1","publisher":"Springer Nature","year":"2021","publication":"Topics in Cryptology – CT-RSA 2021","day":"11","page":"478-502","date_created":"2021-08-08T22:01:30Z","doi":"10.1007/978-3-030-75539-3_20","date_published":"2021-05-11T00:00:00Z","_id":"9825","conference":{"name":"CT-RSA: Cryptographers’ Track at the RSA Conference","start_date":"2021-05-17","location":"Virtual Event","end_date":"2021-05-20"},"type":"conference","status":"public","date_updated":"2023-02-23T14:09:54Z","department":[{"_id":"KrPi"}],"abstract":[{"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).","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"https://eprint.iacr.org/2021/557","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 12704","month":"05","publication_status":"published","publication_identifier":{"issn":["03029743"],"isbn":["9783030755386"],"eissn":["16113349"]},"language":[{"iso":"eng"}],"volume":12704},{"date_updated":"2023-08-14T13:19:39Z","department":[{"_id":"KrPi"}],"_id":"10408","conference":{"start_date":"2021-11-08","location":"Raleigh, NC, United States","end_date":"2021-11-11","name":"TCC: Theory of Cryptography"},"type":"conference","status":"public","publication_status":"published","publication_identifier":{"eisbn":["978-3-030-90456-2"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0455-5"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":13044,"abstract":[{"text":"Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds log(N) keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting 2log(N) ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 13044","month":"11","citation":{"chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.","ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:10.1007/978-3-030-90456-2_8.","apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: 19th International Conference. Vol 13044. Springer Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8","ieee":"J. F. Alwen et al., “Grafting key trees: Efficient key management for overlapping groups,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","short":"J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 222–253."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"isi":["000728363700008"]},"author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad","last_name":"Baig"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein"},{"orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael"}],"title":"Grafting key trees: Efficient key management for overlapping groups","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"},{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"year":"2021","isi":1,"publication":"19th International Conference","day":"04","page":"222-253","date_created":"2021-12-05T23:01:42Z","date_published":"2021-11-04T00:00:00Z","doi":"10.1007/978-3-030-90456-2_8","acknowledgement":"B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","oa":1,"quality_controlled":"1","publisher":"Springer Nature"},{"department":[{"_id":"KrPi"},{"_id":"DaAl"}],"date_updated":"2023-09-07T13:32:11Z","type":"conference","conference":{"end_date":"2021-05-27","location":"San Francisco, CA, United States","start_date":"2021-05-24","name":"SP: Symposium on Security and Privacy"},"status":"public","_id":"10049","related_material":{"record":[{"relation":"dissertation_contains","id":"10035","status":"public"}]},"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1489"}],"month":"08","abstract":[{"text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.","lang":"eng"}],"oa_version":"Preprint","author":[{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael"},{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Capretto","full_name":"Capretto, Margarita","first_name":"Margarita"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval"},{"id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia","full_name":"Markov, Ilia","last_name":"Markov"},{"first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo"},{"last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"article_processing_charge":"No","title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","citation":{"mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.","ieee":"K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in 2021 IEEE Symposium on Security and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In 2021 IEEE Symposium on Security and Privacy (pp. 268–284). San Francisco, CA, United States: IEEE. https://doi.org/10.1109/sp40001.2021.00035","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: 2021 IEEE Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","project":[{"name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"page":"268-284","date_published":"2021-08-26T00:00:00Z","doi":"10.1109/sp40001.2021.00035","date_created":"2021-09-27T13:46:27Z","year":"2021","day":"26","publication":"2021 IEEE Symposium on Security and Privacy ","quality_controlled":"1","publisher":"IEEE","oa":1,"acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385."},{"_id":"10410","status":"public","conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography"},"type":"conference","date_updated":"2023-10-17T09:24:07Z","department":[{"_id":"KrPi"}],"oa_version":"Preprint","abstract":[{"text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.","lang":"eng"}],"intvolume":" 13043","month":"11","main_file_link":[{"url":"https://ia.cr/2021/059","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"]},"ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","id":"10048","status":"public"}]},"volume":13043,"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th International Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:10.1007/978-3-030-90453-1_19.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th International Conference. Vol 13043. Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The cost of adaptivity in security games on graphs. In 19th International Conference (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 550–581."},"title":"The cost of adaptivity in security games on graphs","external_id":{"isi":["000728364000019"]},"article_processing_charge":"No","author":[{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"},{"orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"acknowledgement":"C. Kamath—Supported by Azrieli International Postdoctoral Fellowship. Most of the work was done while the author was at Northeastern University and Charles University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9, respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work was done while the author was at IST Austria funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","oa":1,"quality_controlled":"1","publisher":"Springer Nature","publication":"19th International Conference","day":"04","year":"2021","isi":1,"date_created":"2021-12-05T23:01:43Z","date_published":"2021-11-04T00:00:00Z","doi":"10.1007/978-3-030-90453-1_19","page":"550-581"},{"_id":"10048","type":"conference","conference":{"end_date":"2021-11-11","location":"Raleigh, NC, United States","start_date":"2021-11-08","name":"TCC: Theory of Cryptography Conference"},"status":"public","citation":{"mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th Theory of Cryptography Conference 2021, Raleigh, NC, United States, 2021.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The cost of adaptivity in security games on graphs. In 19th Theory of Cryptography Conference 2021. Raleigh, NC, United States: International Association for Cryptologic Research.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research; 2021.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research, 2021.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference."},"date_updated":"2023-10-17T09:24:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"}],"article_processing_charge":"No","department":[{"_id":"KrPi"}],"title":"The cost of adaptivity in security games on graphs","abstract":[{"lang":"eng","text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower\r\nbounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and\r\nbroadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.\r\n"}],"oa_version":"Preprint","quality_controlled":"1","publisher":"International Association for Cryptologic Research","oa":1,"main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"month":"07","year":"2021","publication_status":"published","day":"08","language":[{"iso":"eng"}],"publication":"19th Theory of Cryptography Conference 2021","related_material":{"record":[{"relation":"later_version","id":"10410","status":"public"},{"relation":"dissertation_contains","id":"10035","status":"public"}]},"date_published":"2021-07-08T00:00:00Z","date_created":"2021-09-27T12:52:05Z"},{"date_published":"2020-05-15T00:00:00Z","doi":"10.1007/978-3-030-45374-9_21","date_created":"2020-09-06T22:01:13Z","page":"623-651","day":"15","publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","year":"2020","quality_controlled":"1","publisher":"Springer Nature","oa":1,"title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","author":[{"first_name":"Nicholas","last_name":"Genise","full_name":"Genise, Nicholas"},{"last_name":"Micciancio","full_name":"Micciancio, Daniele","first_name":"Daniele"},{"first_name":"Chris","last_name":"Peikert","full_name":"Peikert, Chris"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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.","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","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","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."},"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"volume":12110,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["16113349"],"isbn":["9783030453732"],"issn":["03029743"]},"publication_status":"published","month":"05","intvolume":" 12110","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/337"}],"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"}],"department":[{"_id":"KrPi"}],"date_updated":"2023-02-23T13:31:06Z","status":"public","type":"conference","conference":{"location":"Edinburgh, United Kingdom","end_date":"2020-05-07","start_date":"2020-05-04","name":"PKC: Public-Key Cryptography"},"_id":"8339"},{"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/068"}],"month":"06","place":"Cham","intvolume":" 11627","abstract":[{"lang":"eng","text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so."}],"oa_version":"Preprint","volume":11627,"ec_funded":1,"publication_identifier":{"eisbn":["978-3-0302-3696-0"],"issn":["0302-9743","1611-3349"],"isbn":["978-3-0302-3695-3"]},"publication_status":"published","language":[{"iso":"eng"}],"type":"book_chapter","conference":{"start_date":"2019-07-09","end_date":"2019-07-11","location":"Rabat, Morocco","name":"AFRICACRYPT: International Conference on Cryptology in Africa"},"status":"public","series_title":"LNCS","_id":"6726","department":[{"_id":"KrPi"}],"date_updated":"2023-02-23T12:50:15Z","publisher":"Springer Nature","quality_controlled":"1","oa":1,"page":"157-180","date_published":"2019-06-29T00:00:00Z","doi":"10.1007/978-3-030-23696-0_9","date_created":"2019-07-29T12:25:31Z","year":"2019","day":"29","publication":"Progress in Cryptology – AFRICACRYPT 2019","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"author":[{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael"}],"article_processing_charge":"No","editor":[{"full_name":"Buchmann, J","last_name":"Buchmann","first_name":"J"},{"first_name":"A","last_name":"Nitaj","full_name":"Nitaj, A"},{"full_name":"Rachidi, T","last_name":"Rachidi","first_name":"T"}],"title":"Sampling the integers with low relative error","citation":{"ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.","chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019 (Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","ieee":"M. Walter, “Sampling the integers with low relative error,” in Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9"},{"abstract":[{"text":"Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since χ\r\n\r\nwas received.\r\n\r\nPoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18].\r\n\r\nIn this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation.\r\nThe fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at).","lang":"eng"}],"oa_version":"Submitted Version","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/252"}],"month":"04","intvolume":" 11477","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783030176556","9783030176563"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":11477,"ec_funded":1,"_id":"7411","type":"conference","conference":{"name":"International Conference on the Theory and Applications of Cryptographic Techniques","location":"Darmstadt, Germany","end_date":"2019-05-23","start_date":"2019-05-19"},"status":"public","date_updated":"2023-09-06T15:26:06Z","department":[{"_id":"KrPi"}],"quality_controlled":"1","publisher":"Springer International Publishing","oa":1,"isi":1,"year":"2019","day":"24","publication":"Advances in Cryptology – EUROCRYPT 2019","page":"277-291","date_published":"2019-04-24T00:00:00Z","doi":"10.1007/978-3-030-17656-3_10","date_created":"2020-01-30T09:26:14Z","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"citation":{"apa":"Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2019). Reversible proofs of sequential work. In Advances in Cryptology – EUROCRYPT 2019 (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International Publishing. https://doi.org/10.1007/978-3-030-17656-3_10","ama":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible proofs of sequential work. In: Advances in Cryptology – EUROCRYPT 2019. Vol 11477. Springer International Publishing; 2019:277-291. doi:10.1007/978-3-030-17656-3_10","ieee":"H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “Reversible proofs of sequential work,” in Advances in Cryptology – EUROCRYPT 2019, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.","short":"H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019, pp. 277–291.","mla":"Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” Advances in Cryptology – EUROCRYPT 2019, vol. 11477, Springer International Publishing, 2019, pp. 277–91, doi:10.1007/978-3-030-17656-3_10.","ista":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 11477, 277–291.","chicago":"Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “Reversible Proofs of Sequential Work.” In Advances in Cryptology – EUROCRYPT 2019, 11477:277–91. Springer International Publishing, 2019. https://doi.org/10.1007/978-3-030-17656-3_10."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Abusalah, Hamza M","last_name":"Abusalah","id":"40297222-F248-11E8-B48F-1D18A9856A87","first_name":"Hamza M"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael"}],"article_processing_charge":"No","external_id":{"isi":["000483516200010"]},"title":"Reversible proofs of sequential work"},{"_id":"300","conference":{"name":"Eurocrypt: Advances in Cryptology","end_date":"2018-05-03","location":"Tel Aviv, Israel","start_date":"2018-04-29"},"type":"conference","status":"public","date_updated":"2023-09-13T09:12:04Z","department":[{"_id":"KrPi"}],"abstract":[{"lang":"eng","text":"We introduce a formal quantitative notion of “bit security” for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with k-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a k-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems."}],"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/077"}],"scopus_import":"1","alternative_title":["LNCS"],"intvolume":" 10820","month":"03","publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"volume":10820,"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"citation":{"mla":"Micciancio, Daniele, and Michael Walter. On the Bit Security of Cryptographic Primitives. Vol. 10820, Springer, 2018, pp. 3–28, doi:10.1007/978-3-319-78381-9_1.","short":"D. Micciancio, M. Walter, in:, Springer, 2018, pp. 3–28.","ieee":"D. Micciancio and M. Walter, “On the bit security of cryptographic primitives,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10820, pp. 3–28.","apa":"Micciancio, D., & Walter, M. (2018). On the bit security of cryptographic primitives (Vol. 10820, pp. 3–28). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78381-9_1","ama":"Micciancio D, Walter M. On the bit security of cryptographic primitives. In: Vol 10820. Springer; 2018:3-28. doi:10.1007/978-3-319-78381-9_1","chicago":"Micciancio, Daniele, and Michael Walter. “On the Bit Security of Cryptographic Primitives,” 10820:3–28. Springer, 2018. https://doi.org/10.1007/978-3-319-78381-9_1.","ista":"Micciancio D, Walter M. 2018. On the bit security of cryptographic primitives. Eurocrypt: Advances in Cryptology, LNCS, vol. 10820, 3–28."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000517097500001"]},"article_processing_charge":"No","publist_id":"7581","author":[{"first_name":"Daniele","full_name":"Micciancio, Daniele","last_name":"Micciancio"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael"}],"title":"On the bit security of cryptographic primitives","acknowledgement":"Research supported in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under the SafeWare program. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views, position or policy of the Government. The second author was also supported by the European Research Council, ERC consolidator grant (682815 - TOCNeT).","oa":1,"publisher":"Springer","quality_controlled":"1","year":"2018","isi":1,"day":"31","page":"3 - 28","date_created":"2018-12-11T11:45:42Z","date_published":"2018-03-31T00:00:00Z","doi":"10.1007/978-3-319-78381-9_1"}]