[{"oa":1,"publication_identifier":{"isbn":["9783030755386"],"issn":["03029743"],"eissn":["16113349"]},"type":"conference","date_published":"2021-05-11T00:00:00Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2021/557","open_access":"1"}],"month":"05","oa_version":"Preprint","publication":"Topics in Cryptology – CT-RSA 2021","conference":{"name":"CT-RSA: Cryptographers’ Track at the RSA Conference","start_date":"2021-05-17","end_date":"2021-05-20","location":"Virtual Event"},"language":[{"iso":"eng"}],"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)."}],"day":"11","doi":"10.1007/978-3-030-75539-3_20","year":"2021","citation":{"apa":"Laarhoven, T., &#38; Walter, M. (2021). Dual lattice attacks for closest vector problems (with preprocessing). In <i>Topics in Cryptology – CT-RSA 2021</i> (Vol. 12704, pp. 478–502). Virtual Event: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_20\">https://doi.org/10.1007/978-3-030-75539-3_20</a>","ama":"Laarhoven T, Walter M. Dual lattice attacks for closest vector problems (with preprocessing). In: <i>Topics in Cryptology – CT-RSA 2021</i>. Vol 12704. Springer Nature; 2021:478-502. doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_20\">10.1007/978-3-030-75539-3_20</a>","chicago":"Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector Problems (with Preprocessing).” In <i>Topics in Cryptology – CT-RSA 2021</i>, 12704:478–502. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_20\">https://doi.org/10.1007/978-3-030-75539-3_20</a>.","ieee":"T. Laarhoven and M. Walter, “Dual lattice attacks for closest vector problems (with preprocessing),” in <i>Topics in Cryptology – CT-RSA 2021</i>, Virtual Event, 2021, vol. 12704, pp. 478–502.","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).” <i>Topics in Cryptology – CT-RSA 2021</i>, vol. 12704, Springer Nature, 2021, pp. 478–502, doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_20\">10.1007/978-3-030-75539-3_20</a>.","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."},"date_updated":"2023-02-23T14:09:54Z","volume":12704,"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.","intvolume":"     12704","title":"Dual lattice attacks for closest vector problems (with preprocessing)","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"article_processing_charge":"No","date_created":"2021-08-08T22:01:30Z","publication_status":"published","author":[{"full_name":"Laarhoven, Thijs","first_name":"Thijs","last_name":"Laarhoven"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","first_name":"Michael","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"}],"scopus_import":"1","_id":"9825","publisher":"Springer Nature","quality_controlled":"1","page":"478-502"},{"oa":1,"publication_identifier":{"isbn":["9783030755386"],"eissn":["16113349"],"issn":["03029743"]},"type":"conference","date_published":"2021-05-11T00:00:00Z","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"month":"05","project":[{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa_version":"Submitted Version","publication":"Topics in Cryptology – CT-RSA 2021","conference":{"location":"Virtual Event","end_date":"2021-05-20","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","start_date":"2021-05-17"},"language":[{"iso":"eng"}],"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"}],"day":"11","doi":"10.1007/978-3-030-75539-3_17","citation":{"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.” <i>Topics in Cryptology – CT-RSA 2021</i>, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>.","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.","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: <i>Topics in Cryptology – CT-RSA 2021</i>. Vol 12704. Springer Nature; 2021:399-421. doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., &#38; Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In <i>Topics in Cryptology – CT-RSA 2021</i> (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>","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 <i>Topics in Cryptology – CT-RSA 2021</i>, 12704:399–421. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>.","ieee":"B. Auerbach <i>et al.</i>, “Inverse-Sybil attacks in automated contact tracing,” in <i>Topics in Cryptology – CT-RSA 2021</i>, Virtual Event, 2021, vol. 12704, pp. 399–421."},"year":"2021","date_updated":"2023-02-23T14:09:56Z","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,"intvolume":"     12704","title":"Inverse-Sybil attacks in automated contact tracing","alternative_title":["LNCS"],"article_processing_charge":"No","date_created":"2021-08-08T22:01:30Z","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"publication_status":"published","author":[{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","last_name":"Auerbach","first_name":"Benedikt"},{"first_name":"Suvradip","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","_id":"9826","publisher":"Springer Nature","quality_controlled":"1","ec_funded":1,"page":"399-421"}]