[{"status":"public","ec_funded":1,"citation":{"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 <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","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.","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.","ieee":"K. Klein <i>et al.</i>, “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in <i>2021 IEEE Symposium on Security and Privacy </i>, San Francisco, CA, United States, 2021, pp. 268–284.","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>.","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: <i>2021 IEEE Symposium on Security and Privacy </i>. IEEE; 2021:268-284. doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>","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 <i>2021 IEEE Symposium on Security and Privacy </i>, 268–84. IEEE, 2021. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>."},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1489"}],"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","_id":"10049","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","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"}],"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.","conference":{"end_date":"2021-05-27","location":"San Francisco, CA, United States","name":"SP: Symposium on Security and Privacy","start_date":"2021-05-24"},"page":"268-284","author":[{"full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","full_name":"Walter, Michael","last_name":"Walter","orcid":"0000-0003-3186-2482"},{"full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"last_name":"Capretto","first_name":"Margarita","full_name":"Capretto, Margarita"},{"last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"full_name":"Markov, Ilia","first_name":"Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","last_name":"Markov"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo"},{"full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"}],"day":"26","publication_status":"published","date_created":"2021-09-27T13:46:27Z","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"10035"}]},"year":"2021","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"},{"_id":"DaAl"}],"project":[{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"date_published":"2021-08-26T00:00:00Z","type":"conference","oa_version":"Preprint","doi":"10.1109/sp40001.2021.00035","publisher":"IEEE","date_updated":"2023-09-07T13:32:11Z","publication":"2021 IEEE Symposium on Security and Privacy ","article_processing_charge":"No","oa":1,"quality_controlled":"1","month":"08"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"text":"Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as “time bombs”) or on some particular input (known as “cheat codes”). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC) have been proposed. On a high level, to realize a circuit with specification   F  one has more sophisticated circuits   F⋄  manufactured (where   F⋄  specifies a MPC or VC of   F ), and then embeds these   F⋄ ’s into a master circuit which must be trusted but is relatively simple compared to   F . Those solutions impose a significant overhead as   F⋄  is much more complex than   F , also the master circuits are not exactly trivial. In this work, we show that in restricted settings, where   F  has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e.,   F=F⋄ ). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they’re all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to T inputs, the master circuit will catch Trojans that try to deviate on significantly more than a 1/T fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where 12 instantiations of   F  need to be embedded into the master. We also discuss an extremely simple construction with just 2 instantiations for which we conjecture that it already achieves the optimal bound.","lang":"eng"}],"title":"Trojan-resilience without cryptography","_id":"10407","status":"public","ec_funded":1,"intvolume":"     13043","citation":{"ista":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. 2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference, LNCS, vol. 13043, 397–428.","apa":"Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z., &#38; Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp. 397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>","ieee":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 397–428.","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","ama":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>","mla":"Chakraborty, Suvradip, et al. <i>Trojan-Resilience without Cryptography</i>. Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>.","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,” 13043:397–428. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>."},"main_file_link":[{"url":"https://eprint.iacr.org/2021/1224","open_access":"1"}],"scopus_import":"1","isi":1,"publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"article_processing_charge":"No","publisher":"Springer Nature","date_updated":"2023-08-14T13:07:46Z","doi":"10.1007/978-3-030-90453-1_14","month":"11","oa":1,"quality_controlled":"1","type":"conference","date_published":"2021-11-04T00:00:00Z","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"volume":13043,"external_id":{"isi":["000728364000014"]},"oa_version":"Preprint","language":[{"iso":"eng"}],"year":"2021","department":[{"_id":"KrPi"}],"author":[{"full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty"},{"first_name":"Stefan","full_name":"Dziembowski, Stefan","last_name":"Dziembowski"},{"full_name":"Gałązka, Małgorzata","first_name":"Małgorzata","last_name":"Gałązka"},{"full_name":"Lizurej, Tomasz","first_name":"Tomasz","last_name":"Lizurej"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo"}],"conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography Conference"},"page":"397-428","alternative_title":["LNCS"],"date_created":"2021-12-05T23:01:42Z","day":"04","publication_status":"published"},{"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).","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","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"}],"title":"Grafting key trees: Efficient key management for overlapping groups","_id":"10408","citation":{"ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: <i>19th International Conference</i>. Vol 13044. Springer Nature; 2021:222-253. doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” <i>19th International Conference</i>, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>.","chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In <i>19th International Conference</i>, 13044:222–53. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>.","ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.","apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In <i>19th International Conference</i> (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>","ieee":"J. F. Alwen <i>et al.</i>, “Grafting key trees: Efficient key management for overlapping groups,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","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."},"intvolume":"     13044","main_file_link":[{"url":"https://eprint.iacr.org/2021/1158","open_access":"1"}],"status":"public","ec_funded":1,"scopus_import":"1","isi":1,"publication_identifier":{"isbn":["9-783-0309-0455-5"],"eisbn":["978-3-030-90456-2"],"issn":["0302-9743"],"eissn":["1611-3349"]},"month":"11","oa":1,"quality_controlled":"1","article_processing_charge":"No","date_updated":"2023-08-14T13:19:39Z","publisher":"Springer Nature","doi":"10.1007/978-3-030-90456-2_8","publication":"19th International Conference","oa_version":"Preprint","external_id":{"isi":["000728363700008"]},"type":"conference","date_published":"2021-11-04T00:00:00Z","project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"},{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020","name":"International IST Doctoral Program"}],"volume":13044,"department":[{"_id":"KrPi"}],"year":"2021","language":[{"iso":"eng"}],"date_created":"2021-12-05T23:01:42Z","day":"04","publication_status":"published","author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen"},{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","full_name":"Auerbach, Benedikt","last_name":"Auerbach","orcid":"0000-0002-7553-6606"},{"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"},{"full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482"}],"conference":{"name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11","location":"Raleigh, NC, United States"},"page":"222-253","alternative_title":["LNCS"]},{"oa_version":"Preprint","external_id":{"isi":["000728364000017"]},"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"type":"conference","date_published":"2021-11-04T00:00:00Z","volume":"13043 ","month":"11","quality_controlled":"1","oa":1,"article_processing_charge":"No","date_updated":"2023-08-17T06:21:38Z","publisher":"Springer Nature","doi":"10.1007/978-3-030-90453-1_17","publication":"19th International Conference","date_created":"2021-12-05T23:01:43Z","day":"04","publication_status":"published","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg"},{"full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography"},"alternative_title":["LNCS"],"page":"486-517","department":[{"_id":"KrPi"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"10044"}]},"year":"2021","language":[{"iso":"eng"}],"citation":{"ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 486–517.","apa":"Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In <i>19th International Conference</i> (Vol. 13043, pp. 486–517). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">https://doi.org/10.1007/978-3-030-90453-1_17</a>","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13043, pp. 486–517.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: <i>19th International Conference</i>. Vol 13043. Springer Nature; 2021:486-517. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">10.1007/978-3-030-90453-1_17</a>","mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” <i>19th International Conference</i>, vol. 13043, Springer Nature, 2021, pp. 486–517, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">10.1007/978-3-030-90453-1_17</a>.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In <i>19th International Conference</i>, 13043:486–517. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">https://doi.org/10.1007/978-3-030-90453-1_17</a>."},"main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"status":"public","ec_funded":1,"acknowledgement":"We are grateful to Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021 and TCC 2021 reviewers for their detailed review and suggestions, which helped improve presentation considerably.","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"text":"We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size   S  and treewidth   w  with only a   SO(w)  loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly   O(δwlog(S)) ,   δ  being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.  with only a   SO(w)  loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly   O(δwlog(S)) ,   δ  being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.","lang":"eng"}],"title":"On treewidth, separators and Yao’s garbling","_id":"10409","publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"]},"scopus_import":"1","isi":1},{"external_id":{"isi":["000728364000019"]},"oa_version":"Preprint","type":"conference","date_published":"2021-11-04T00:00:00Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"volume":13043,"month":"11","oa":1,"quality_controlled":"1","article_processing_charge":"No","publisher":"Springer Nature","date_updated":"2023-10-17T09:24:07Z","doi":"10.1007/978-3-030-90453-1_19","publication":"19th International Conference","date_created":"2021-12-05T23:01:43Z","day":"04","publication_status":"published","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg"},{"last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","full_name":"Walter, Michael"}],"conference":{"end_date":"2021-11-11","location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","start_date":"2021-11-08"},"alternative_title":["LNCS"],"page":"550-581","department":[{"_id":"KrPi"}],"related_material":{"record":[{"id":"10048","relation":"earlier_version","status":"public"}]},"language":[{"iso":"eng"}],"year":"2021","intvolume":"     13043","citation":{"ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13043, pp. 550–581.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2021). The cost of adaptivity in security games on graphs. In <i>19th International Conference</i> (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">https://doi.org/10.1007/978-3-030-90453-1_19</a>","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In <i>19th International Conference</i>, 13043:550–81. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">https://doi.org/10.1007/978-3-030-90453-1_19</a>.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: <i>19th International Conference</i>. Vol 13043. Springer Nature; 2021:550-581. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">10.1007/978-3-030-90453-1_19</a>","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <i>19th International Conference</i>, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">10.1007/978-3-030-90453-1_19</a>."},"main_file_link":[{"url":"https://ia.cr/2021/059","open_access":"1"}],"status":"public","ec_funded":1,"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).","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"lang":"eng","text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques."}],"title":"The cost of adaptivity in security games on graphs","_id":"10410","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"]},"scopus_import":"1","isi":1},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"lang":"eng","text":"We study Multi-party computation (MPC) in the setting of subversion, where the adversary tampers with the machines of honest parties. Our goal is to construct actively secure MPC protocols where parties are corrupted adaptively by an adversary (as in the standard adaptive security setting), and in addition, honest parties’ machines are compromised.\r\nThe idea of reverse firewalls (RF) was introduced at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting protocols against corruption of honest parties’ devices. Intuitively, an RF for a party   P  is an external entity that sits between   P  and the outside world and whose scope is to sanitize   P ’s incoming and outgoing messages in the face of subversion of their computer. Mironov and Stephens-Davidowitz constructed a protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty, Dziembowski and Nielsen constructed a protocol for secure computation with firewalls that improved on this result, both by extending it to multi-party computation protocol, and considering active security in the presence of static corruptions. In this paper, we initiate the study of RF for MPC in the adaptive setting. We put forward a definition for adaptively secure MPC in the reverse firewall setting, explore relationships among the security notions, and then construct reverse firewalls for MPC in this stronger setting of adaptive security. We also resolve the open question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted setup in constructing RF for MPC. Towards this end, we construct reverse firewalls for adaptively secure augmented coin tossing and adaptively secure zero-knowledge protocols and obtain a constant round adaptively secure MPC protocol in the reverse firewall setting without setup. Along the way, we propose a new multi-party adaptively secure coin tossing protocol in the plain model, that is of independent interest."}],"title":"Reverse firewalls for adaptively secure MPC without setup","_id":"10609","status":"public","ec_funded":1,"citation":{"chicago":"Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar. “Reverse Firewalls for Adaptively Secure MPC without Setup.” In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, 13091:335–64. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC without Setup.” <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, vol. 13091, Springer Nature, 2021, pp. 335–64, doi:<a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">10.1007/978-3-030-92075-3_12</a>.","ama":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively secure MPC without setup. In: <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>. Vol 13091. Springer Nature; 2021:335-364. doi:<a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">10.1007/978-3-030-92075-3_12</a>","ieee":"S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls for adaptively secure MPC without setup,” in <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, Virtual, Singapore, 2021, vol. 13091, pp. 335–364.","short":"S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2021, pp. 335–364.","apa":"Chakraborty, S., Ganesh, C., Pancholi, M., &#38; Sarkar, P. (2021). Reverse firewalls for adaptively secure MPC without setup. In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i> (Vol. 13091, pp. 335–364). Virtual, Singapore: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>","ista":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for adaptively secure MPC without setup. 27th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: International Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364."},"intvolume":"     13091","main_file_link":[{"url":"https://eprint.iacr.org/2021/1262","open_access":"1"}],"scopus_import":"1","isi":1,"publication_identifier":{"issn":["0302-9743"],"eisbn":["978-3-030-92075-3"],"isbn":["978-3-030-92074-6"],"eissn":["1611-3349"]},"article_processing_charge":"No","publisher":"Springer Nature","date_updated":"2023-08-17T06:34:41Z","doi":"10.1007/978-3-030-92075-3_12","publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","month":"12","oa":1,"quality_controlled":"1","date_published":"2021-12-01T00:00:00Z","type":"conference","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"volume":13091,"oa_version":"Preprint","external_id":{"isi":["000927876200012"]},"year":"2021","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"author":[{"full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip","last_name":"Chakraborty"},{"last_name":"Ganesh","first_name":"Chaya","full_name":"Ganesh, Chaya"},{"last_name":"Pancholi","first_name":"Mahak","full_name":"Pancholi, Mahak"},{"full_name":"Sarkar, Pratik","first_name":"Pratik","last_name":"Sarkar"}],"conference":{"name":"ASIACRYPT: International Conference on Cryptology in Asia","start_date":"2021-12-06","end_date":"2021-12-10","location":"Virtual, Singapore"},"alternative_title":["LNCS"],"page":"335-364","date_created":"2022-01-09T23:01:27Z","day":"01","publication_status":"published"},{"intvolume":"     12710","citation":{"mla":"Walter, Michael. “The Convergence of Slide-Type Reductions.” <i>Public-Key Cryptography – PKC 2021</i>, vol. 12710, Springer Nature, 2021, pp. 45–67, doi:<a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">10.1007/978-3-030-75245-3_3</a>.","ama":"Walter M. The convergence of slide-type reductions. In: <i>Public-Key Cryptography – PKC 2021</i>. Vol 12710. Springer Nature; 2021:45-67. doi:<a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">10.1007/978-3-030-75245-3_3</a>","chicago":"Walter, Michael. “The Convergence of Slide-Type Reductions.” In <i>Public-Key Cryptography – PKC 2021</i>, 12710:45–67. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">https://doi.org/10.1007/978-3-030-75245-3_3</a>.","apa":"Walter, M. (2021). The convergence of slide-type reductions. In <i>Public-Key Cryptography – PKC 2021</i> (Vol. 12710, pp. 45–67). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">https://doi.org/10.1007/978-3-030-75245-3_3</a>","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.","ieee":"M. Walter, “The convergence of slide-type reductions,” in <i>Public-Key Cryptography – PKC 2021</i>, Virtual, 2021, vol. 12710, pp. 45–67.","short":"M. Walter, in:, Public-Key Cryptography – PKC 2021, Springer Nature, 2021, pp. 45–67."},"has_accepted_license":"1","status":"public","ec_funded":1,"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.","title":"The convergence of slide-type reductions","_id":"9466","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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"}],"publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030752446"]},"file_date_updated":"2022-05-27T09:48:31Z","scopus_import":"1","oa_version":"Published Version","date_published":"2021-05-01T00:00:00Z","type":"conference","project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"volume":12710,"file":[{"success":1,"file_name":"2021_PKC_Walter.pdf","access_level":"open_access","checksum":"413e564d645ed93d7318672361d9d470","date_updated":"2022-05-27T09:48:31Z","file_size":489017,"content_type":"application/pdf","date_created":"2022-05-27T09:48:31Z","file_id":"11416","relation":"main_file","creator":"dernst"}],"quality_controlled":"1","oa":1,"month":"05","doi":"10.1007/978-3-030-75245-3_3","publisher":"Springer Nature","date_updated":"2023-02-23T13:58:47Z","publication":"Public-Key Cryptography – PKC 2021","article_processing_charge":"No","day":"01","publication_status":"published","date_created":"2021-06-06T22:01:29Z","conference":{"location":"Virtual","end_date":"2021-05-13","start_date":"2021-05-10","name":"PKC: IACR International Conference on Practice and Theory of Public Key Cryptography"},"alternative_title":["LNCS"],"page":"45-67","author":[{"full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482"}],"department":[{"_id":"KrPi"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"year":"2021","ddc":["000"],"language":[{"iso":"eng"}]},{"year":"2021","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"author":[{"last_name":"Laarhoven","first_name":"Thijs","full_name":"Laarhoven, Thijs"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael"}],"page":"478-502","alternative_title":["LNCS"],"conference":{"end_date":"2021-05-20","location":"Virtual Event","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","start_date":"2021-05-17"},"date_created":"2021-08-08T22:01:30Z","publication_status":"published","day":"11","article_processing_charge":"No","publication":"Topics in Cryptology – CT-RSA 2021","publisher":"Springer Nature","date_updated":"2023-02-23T14:09:54Z","doi":"10.1007/978-3-030-75539-3_20","month":"05","oa":1,"quality_controlled":"1","volume":12704,"type":"conference","date_published":"2021-05-11T00:00:00Z","oa_version":"Preprint","scopus_import":"1","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030755386"]},"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)."}],"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","_id":"9825","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.","status":"public","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/557"}],"intvolume":"     12704","citation":{"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>","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>.","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>.","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.","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>","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 <i>Topics in Cryptology – CT-RSA 2021</i>, Virtual Event, 2021, vol. 12704, pp. 478–502."}},{"article_processing_charge":"No","publication":"Topics in Cryptology – CT-RSA 2021","date_updated":"2023-02-23T14:09:56Z","doi":"10.1007/978-3-030-75539-3_17","publisher":"Springer Nature","month":"05","quality_controlled":"1","oa":1,"volume":12704,"date_published":"2021-05-11T00:00:00Z","project":[{"call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"type":"conference","oa_version":"Submitted Version","language":[{"iso":"eng"}],"year":"2021","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"author":[{"orcid":"0000-0002-7553-6606","last_name":"Auerbach","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt"},{"full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip","last_name":"Chakraborty"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein"},{"last_name":"Pascual Perez","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","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"},{"first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo"}],"alternative_title":["LNCS"],"page":"399-421","conference":{"name":"CT-RSA: Cryptographers’ Track at the RSA Conference","start_date":"2021-05-17","end_date":"2021-05-20","location":"Virtual Event"},"date_created":"2021-08-08T22:01:30Z","publication_status":"published","day":"11","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"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"9826","title":"Inverse-Sybil attacks in automated contact tracing","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).","ec_funded":1,"status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"intvolume":"     12704","citation":{"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>","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>.","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>.","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.","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>","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.","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."},"scopus_import":"1","publication_identifier":{"eissn":["16113349"],"isbn":["9783030755386"],"issn":["03029743"]}},{"ec_funded":1,"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2104.04293"}],"citation":{"ieee":"K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving route discovery for payment channel networks,” presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.","short":"K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.","apa":"Pietrzak, K. Z., Salem, I., Schmid, S., &#38; Yeo, M. X. (2021). LightPIR: Privacy-preserving route discovery for payment channel networks. Presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland: IEEE. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>","ista":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving route discovery for payment channel networks. 2021 IFIP Networking Conference (IFIP Networking).","chicago":"Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo. “LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE, 2021. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>.","mla":"Pietrzak, Krzysztof Z., et al. <i>LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks</i>. IEEE, 2021, doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>.","ama":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route discovery for payment channel networks. In: IEEE; 2021. doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>"},"_id":"9969","title":"LightPIR: Privacy-preserving route discovery for payment channel networks","abstract":[{"lang":"eng","text":"Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths."}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"eisbn":["978-3-9031-7639-3"],"isbn":["978-1-6654-4501-6"],"eissn":["1861-2288"]},"isi":1,"scopus_import":"1","type":"conference","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"date_published":"2021-06-21T00:00:00Z","external_id":{"isi":["000853016800008"],"arxiv":["2104.04293"]},"oa_version":"Submitted Version","date_updated":"2023-11-30T10:54:50Z","doi":"10.23919/IFIPNetworking52078.2021.9472205","publisher":"IEEE","article_processing_charge":"No","oa":1,"quality_controlled":"1","month":"06","conference":{"end_date":"2021-06-24","location":"Espoo and Helsinki, Finland","name":"2021 IFIP Networking Conference (IFIP Networking)","start_date":"2021-06-21"},"author":[{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"full_name":"Salem, Iosif","first_name":"Iosif","last_name":"Salem"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"}],"publication_status":"published","day":"21","arxiv":1,"date_created":"2021-08-29T22:01:16Z","language":[{"iso":"eng"}],"year":"2021","related_material":{"record":[{"id":"14506","relation":"dissertation_contains","status":"public"}]},"department":[{"_id":"KrPi"}]},{"date_created":"2020-08-30T22:01:12Z","day":"10","publication_status":"published","author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip","full_name":"Chakraborty, Suvradip","last_name":"Chakraborty"},{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"last_name":"Nielsen","full_name":"Nielsen, Jesper Buus","first_name":"Jesper Buus"}],"conference":{"name":"CRYPTO: Annual International Cryptology Conference","start_date":"2020-08-17","end_date":"2020-08-21","location":"Santa Barbara, CA, United States"},"alternative_title":["LNCS"],"page":"732-762","department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"year":"2020","oa_version":"Preprint","type":"conference","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"date_published":"2020-08-10T00:00:00Z","volume":12171,"month":"08","oa":1,"quality_controlled":"1","article_processing_charge":"No","date_updated":"2021-01-12T08:18:08Z","doi":"10.1007/978-3-030-56880-1_26","publisher":"Springer Nature","publication":"Advances in Cryptology – CRYPTO 2020","publication_identifier":{"isbn":["9783030568795"],"issn":["03029743"],"eissn":["16113349"]},"scopus_import":"1","intvolume":"     12171","citation":{"ieee":"S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,” in <i>Advances in Cryptology – CRYPTO 2020</i>, Santa Barbara, CA, United States, 2020, vol. 12171, pp. 732–762.","short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 732–762.","apa":"Chakraborty, S., Dziembowski, S., &#38; Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs. In <i>Advances in Cryptology – CRYPTO 2020</i> (Vol. 12171, pp. 732–762). Santa Barbara, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">https://doi.org/10.1007/978-3-030-56880-1_26</a>","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.","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.” In <i>Advances in Cryptology – CRYPTO 2020</i>, 12171:732–62. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">https://doi.org/10.1007/978-3-030-56880-1_26</a>.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.” <i>Advances in Cryptology – CRYPTO 2020</i>, vol. 12171, Springer Nature, 2020, pp. 732–62, doi:<a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">10.1007/978-3-030-56880-1_26</a>.","ama":"Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs. In: <i>Advances in Cryptology – CRYPTO 2020</i>. Vol 12171. Springer Nature; 2020:732-762. doi:<a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">10.1007/978-3-030-56880-1_26</a>"},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1317"}],"status":"public","ec_funded":1,"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.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"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).","lang":"eng"}],"title":"Reverse firewalls for actively secure MPCs","_id":"8322"},{"intvolume":"     12110","citation":{"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.","ieee":"N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian and subgaussian analysis for lattice cryptography,” in <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, Edinburgh, United Kingdom, 2020, vol. 12110, pp. 623–651.","apa":"Genise, N., Micciancio, D., Peikert, C., &#38; Walter, M. (2020). Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i> (Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">https://doi.org/10.1007/978-3-030-45374-9_21</a>","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 <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, 12110:623–51. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">https://doi.org/10.1007/978-3-030-45374-9_21</a>.","mla":"Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, vol. 12110, Springer Nature, 2020, pp. 623–51, doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">10.1007/978-3-030-45374-9_21</a>.","ama":"Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In: <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>. Vol 12110. Springer Nature; 2020:623-651. doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">10.1007/978-3-030-45374-9_21</a>"},"main_file_link":[{"url":"https://eprint.iacr.org/2020/337","open_access":"1"}],"status":"public","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","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."}],"title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","_id":"8339","publication_identifier":{"isbn":["9783030453732"],"issn":["03029743"],"eissn":["16113349"]},"scopus_import":"1","oa_version":"Preprint","date_published":"2020-05-15T00:00:00Z","project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"type":"conference","volume":12110,"month":"05","quality_controlled":"1","oa":1,"article_processing_charge":"No","doi":"10.1007/978-3-030-45374-9_21","date_updated":"2023-02-23T13:31:06Z","publisher":"Springer Nature","publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","date_created":"2020-09-06T22:01:13Z","day":"15","publication_status":"published","author":[{"first_name":"Nicholas","full_name":"Genise, Nicholas","last_name":"Genise"},{"full_name":"Micciancio, Daniele","first_name":"Daniele","last_name":"Micciancio"},{"last_name":"Peikert","first_name":"Chris","full_name":"Peikert, Chris"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael"}],"conference":{"location":"Edinburgh, United Kingdom","end_date":"2020-05-07","start_date":"2020-05-04","name":"PKC: Public-Key Cryptography"},"alternative_title":["LNCS"],"page":"623-651","department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"year":"2020"},{"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."}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"8987","title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing","main_file_link":[{"url":"https://eprint.iacr.org/2020/418","open_access":"1"}],"intvolume":"     12578","citation":{"ama":"Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in private contact tracing. In: <i>Progress in Cryptology</i>. Vol 12578. LNCS. Springer Nature; 2020:3-15. doi:<a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">10.1007/978-3-030-65277-7_1</a>","mla":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” <i>Progress in Cryptology</i>, vol. 12578, Springer Nature, 2020, pp. 3–15, doi:<a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">10.1007/978-3-030-65277-7_1</a>.","chicago":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” In <i>Progress in Cryptology</i>, 12578:3–15. LNCS. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">https://doi.org/10.1007/978-3-030-65277-7_1</a>.","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.","apa":"Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay attacks in private contact tracing. In <i>Progress in Cryptology</i> (Vol. 12578, pp. 3–15). Bangalore, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">https://doi.org/10.1007/978-3-030-65277-7_1</a>","short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","ieee":"K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks in private contact tracing,” in <i>Progress in Cryptology</i>, Bangalore, India, 2020, vol. 12578, pp. 3–15."},"ec_funded":1,"status":"public","isi":1,"scopus_import":"1","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030652760"]},"month":"12","series_title":"LNCS","oa":1,"quality_controlled":"1","article_processing_charge":"No","publication":"Progress in Cryptology","publisher":"Springer Nature","date_updated":"2023-08-24T11:08:58Z","doi":"10.1007/978-3-030-65277-7_1","oa_version":"Preprint","external_id":{"isi":["000927592800001"]},"volume":12578,"type":"conference","date_published":"2020-12-08T00:00:00Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"year":"2020","date_created":"2021-01-03T23:01:23Z","publication_status":"published","day":"08","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}],"page":"3-15","conference":{"end_date":"2020-12-16","location":"Bangalore, India","name":"INDOCRYPT: International Conference on Cryptology in India","start_date":"2020-12-13"}},{"status":"public","ec_funded":1,"citation":{"apa":"Kamath Hosdurg, C. (2020). <i>On the average-case hardness of total search problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7896\">https://doi.org/10.15479/AT:ISTA:7896</a>","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","mla":"Kamath Hosdurg, Chethan. <i>On the Average-Case Hardness of Total Search Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7896\">10.15479/AT:ISTA:7896</a>.","ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7896\">10.15479/AT:ISTA:7896</a>","chicago":"Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7896\">https://doi.org/10.15479/AT:ISTA:7896</a>."},"has_accepted_license":"1","title":"On the average-case hardness of total search problems","_id":"7896","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"text":"A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems\r\nlike computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.\r\nHowever, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. ","lang":"eng"}],"publication_identifier":{"issn":["2663-337X"]},"file_date_updated":"2020-07-14T12:48:04Z","date_published":"2020-05-25T00:00:00Z","type":"dissertation","project":[{"call_identifier":"FP7","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668"},{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"oa_version":"Published Version","publisher":"Institute of Science and Technology Austria","doi":"10.15479/AT:ISTA:7896","date_updated":"2023-09-07T13:15:55Z","article_processing_charge":"No","oa":1,"file":[{"content_type":"application/pdf","file_id":"7897","date_created":"2020-05-26T14:08:13Z","relation":"main_file","creator":"dernst","file_name":"2020_Thesis_Kamath.pdf","access_level":"open_access","checksum":"b39e2e1c376f5819b823fb7077491c64","date_updated":"2020-07-14T12:48:04Z","file_size":1622742},{"date_created":"2020-05-26T14:08:23Z","file_id":"7898","content_type":"application/x-zip-compressed","creator":"dernst","relation":"source_file","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","file_name":"Thesis_Kamath.zip","access_level":"closed","file_size":15301529,"date_updated":"2020-07-14T12:48:04Z"}],"month":"05","alternative_title":["ISTA Thesis"],"page":"126","author":[{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"}],"day":"25","publication_status":"published","date_created":"2020-05-26T14:08:55Z","degree_awarded":"PhD","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"6677"}]},"year":"2020","ddc":["000"],"language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}]},{"isi":1,"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030457266","9783030457273"],"issn":["0302-9743"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"lang":"eng","text":"For 1≤m≤n, we consider a natural m-out-of-n multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given n independent instances of PKE, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of PKE schemes, SF, which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor SF=ℓ indicates that breaking m out of n instances is at least ℓ times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).\r\n\r\nFor Hashed ElGamal over elliptic curves, we use the generic group model to argue that the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor SF=m; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor SF=√m. Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.\r\n\r\nAs our main technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n Gap Computational Diffie-Hellman problem over groups of prime order p, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem."}],"title":"Everybody’s a target: Scalability in public-key encryption","_id":"7966","status":"public","ec_funded":1,"intvolume":"     12107","citation":{"ista":"Auerbach B, Giacon F, Kiltz E. 2020. Everybody’s a target: Scalability in public-key encryption. Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 12107, 475–506.","apa":"Auerbach, B., Giacon, F., &#38; Kiltz, E. (2020). Everybody’s a target: Scalability in public-key encryption. In <i>Advances in Cryptology – EUROCRYPT 2020</i> (Vol. 12107, pp. 475–506). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">https://doi.org/10.1007/978-3-030-45727-3_16</a>","ieee":"B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability in public-key encryption,” in <i>Advances in Cryptology – EUROCRYPT 2020</i>, 2020, vol. 12107, pp. 475–506.","short":"B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT 2020, Springer Nature, 2020, pp. 475–506.","ama":"Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key encryption. In: <i>Advances in Cryptology – EUROCRYPT 2020</i>. Vol 12107. Springer Nature; 2020:475-506. doi:<a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">10.1007/978-3-030-45727-3_16</a>","mla":"Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key Encryption.” <i>Advances in Cryptology – EUROCRYPT 2020</i>, vol. 12107, Springer Nature, 2020, pp. 475–506, doi:<a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">10.1007/978-3-030-45727-3_16</a>.","chicago":"Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target: Scalability in Public-Key Encryption.” In <i>Advances in Cryptology – EUROCRYPT 2020</i>, 12107:475–506. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">https://doi.org/10.1007/978-3-030-45727-3_16</a>."},"main_file_link":[{"url":"https://eprint.iacr.org/2019/364","open_access":"1"}],"language":[{"iso":"eng"}],"year":"2020","department":[{"_id":"KrPi"}],"author":[{"last_name":"Auerbach","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","full_name":"Auerbach, Benedikt"},{"full_name":"Giacon, Federico","first_name":"Federico","last_name":"Giacon"},{"first_name":"Eike","full_name":"Kiltz, Eike","last_name":"Kiltz"}],"conference":{"end_date":"2020-05-15","start_date":"2020-05-11","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"alternative_title":["LNCS"],"page":"475-506","date_created":"2020-06-15T07:13:37Z","day":"01","publication_status":"published","article_processing_charge":"No","doi":"10.1007/978-3-030-45727-3_16","date_updated":"2023-09-05T15:06:40Z","publisher":"Springer Nature","publication":"Advances in Cryptology – EUROCRYPT 2020","month":"05","oa":1,"quality_controlled":"1","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"type":"conference","date_published":"2020-05-01T00:00:00Z","volume":12107,"oa_version":"Submitted Version","external_id":{"isi":["000828688000016"]}},{"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1702.08476"}],"citation":{"ista":"Skórski M. 2019. Strong chain rules for min-entropy under few bits spoiled. 2019 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 8849240.","apa":"Skórski, M. (2019). Strong chain rules for min-entropy under few bits spoiled. In <i>2019 IEEE International Symposium on Information Theory</i>. Paris, France: IEEE. <a href=\"https://doi.org/10.1109/isit.2019.8849240\">https://doi.org/10.1109/isit.2019.8849240</a>","short":"M. Skórski, in:, 2019 IEEE International Symposium on Information Theory, IEEE, 2019.","ieee":"M. Skórski, “Strong chain rules for min-entropy under few bits spoiled,” in <i>2019 IEEE International Symposium on Information Theory</i>, Paris, France, 2019.","ama":"Skórski M. Strong chain rules for min-entropy under few bits spoiled. In: <i>2019 IEEE International Symposium on Information Theory</i>. IEEE; 2019. doi:<a href=\"https://doi.org/10.1109/isit.2019.8849240\">10.1109/isit.2019.8849240</a>","mla":"Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.” <i>2019 IEEE International Symposium on Information Theory</i>, 8849240, IEEE, 2019, doi:<a href=\"https://doi.org/10.1109/isit.2019.8849240\">10.1109/isit.2019.8849240</a>.","chicago":"Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.” In <i>2019 IEEE International Symposium on Information Theory</i>. IEEE, 2019. <a href=\"https://doi.org/10.1109/isit.2019.8849240\">https://doi.org/10.1109/isit.2019.8849240</a>."},"_id":"7136","title":"Strong chain rules for min-entropy under few bits spoiled","abstract":[{"text":"It is well established that the notion of min-entropy fails to satisfy the \\emph{chain rule} of the form H(X,Y)=H(X|Y)+H(Y), known for Shannon Entropy. Such a property would help to analyze how min-entropy is split among smaller blocks. Problems of this kind arise for example when constructing extractors and dispersers.\r\nWe show that any sequence of variables exhibits a very strong strong block-source structure (conditional distributions of blocks are nearly flat) when we \\emph{spoil few correlated bits}. This implies, conditioned on the spoiled bits, that \\emph{splitting-recombination properties} hold. In particular, we have many nice properties that min-entropy doesn't obey in general, for example strong chain rules, \"information can't hurt\" inequalities, equivalences of average and worst-case conditional entropy definitions and others. Quantitatively, for any sequence X1,…,Xt of random variables over an alphabet X we prove that, when conditioned on m=t⋅O(loglog|X|+loglog(1/ϵ)+logt) bits of auxiliary information, all conditional distributions of the form Xi|X<i are ϵ-close to be nearly flat (only a constant factor away). The argument is combinatorial (based on simplex coverings).\r\nThis result may be used as a generic tool for \\emph{exhibiting block-source structures}. We demonstrate this by reproving the fundamental converter due to Nisan and Zuckermann (\\emph{J. Computer and System Sciences, 1996}), which shows that sampling blocks from a min-entropy source roughly preserves the entropy rate. Our bound implies, only by straightforward chain rules, an additive loss of o(1) (for sufficiently many samples), which qualitatively meets the first tighter analysis of this problem due to Vadhan (\\emph{CRYPTO'03}), obtained by large deviation techniques. ","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"isbn":["9781538692912"]},"isi":1,"scopus_import":"1","type":"conference","date_published":"2019-07-01T00:00:00Z","external_id":{"arxiv":["1702.08476"],"isi":["000489100301043"]},"oa_version":"Preprint","publication":"2019 IEEE International Symposium on Information Theory","doi":"10.1109/isit.2019.8849240","publisher":"IEEE","date_updated":"2023-09-06T11:15:41Z","article_processing_charge":"No","article_number":"8849240","oa":1,"quality_controlled":"1","month":"07","conference":{"end_date":"2019-07-12","location":"Paris, France","name":"ISIT: International Symposium on Information Theory","start_date":"2019-07-07"},"author":[{"full_name":"Skórski, Maciej","first_name":"Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","last_name":"Skórski"}],"publication_status":"published","day":"01","arxiv":1,"date_created":"2019-11-28T10:19:21Z","language":[{"iso":"eng"}],"year":"2019","department":[{"_id":"KrPi"}]},{"title":"Reversible proofs of sequential work","_id":"7411","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","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"}],"status":"public","ec_funded":1,"intvolume":"     11477","citation":{"ama":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible proofs of sequential work. In: <i>Advances in Cryptology – EUROCRYPT 2019</i>. Vol 11477. Springer International Publishing; 2019:277-291. doi:<a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">10.1007/978-3-030-17656-3_10</a>","mla":"Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” <i>Advances in Cryptology – EUROCRYPT 2019</i>, vol. 11477, Springer International Publishing, 2019, pp. 277–91, doi:<a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">10.1007/978-3-030-17656-3_10</a>.","chicago":"Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “Reversible Proofs of Sequential Work.” In <i>Advances in Cryptology – EUROCRYPT 2019</i>, 11477:277–91. Springer International Publishing, 2019. <a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">https://doi.org/10.1007/978-3-030-17656-3_10</a>.","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.","apa":"Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2019). Reversible proofs of sequential work. In <i>Advances in Cryptology – EUROCRYPT 2019</i> (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">https://doi.org/10.1007/978-3-030-17656-3_10</a>","ieee":"H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “Reversible proofs of sequential work,” in <i>Advances in Cryptology – EUROCRYPT 2019</i>, 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."},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/252"}],"scopus_import":"1","isi":1,"publication_identifier":{"issn":["0302-9743"],"isbn":["9783030176556","9783030176563"],"eissn":["1611-3349"]},"date_updated":"2023-09-06T15:26:06Z","publisher":"Springer International Publishing","doi":"10.1007/978-3-030-17656-3_10","publication":"Advances in Cryptology – EUROCRYPT 2019","article_processing_charge":"No","oa":1,"quality_controlled":"1","month":"04","date_published":"2019-04-24T00:00:00Z","type":"conference","project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"volume":11477,"external_id":{"isi":["000483516200010"]},"oa_version":"Submitted Version","language":[{"iso":"eng"}],"year":"2019","department":[{"_id":"KrPi"}],"conference":{"location":"Darmstadt, Germany","end_date":"2019-05-23","start_date":"2019-05-19","name":"International Conference on the Theory and Applications of Cryptographic Techniques"},"page":"277-291","alternative_title":["LNCS"],"author":[{"last_name":"Abusalah","full_name":"Abusalah, Hamza M","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"},{"full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482"}],"day":"24","publication_status":"published","date_created":"2020-01-30T09:26:14Z"},{"month":"01","quality_controlled":"1","oa":1,"article_processing_charge":"No","publication":"Journal of Computer Security","doi":"10.3233/JCS-181131","publisher":"IOS Press","date_updated":"2021-01-12T08:05:08Z","article_type":"original","oa_version":"Preprint","volume":27,"date_published":"2019-01-01T00:00:00Z","type":"journal_article","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"department":[{"_id":"KrPi"}],"year":"2019","language":[{"iso":"eng"}],"date_created":"2019-01-27T22:59:10Z","publication_status":"published","day":"1","author":[{"last_name":"Demay","first_name":"Gregory","full_name":"Demay, Gregory"},{"last_name":"Gazi","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Gazi, Peter"},{"last_name":"Maurer","full_name":"Maurer, Ueli","first_name":"Ueli"},{"first_name":"Bjorn","full_name":"Tackmann, Bjorn","last_name":"Tackmann"}],"page":"75-111","abstract":[{"lang":"eng","text":"Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5887","title":"Per-session security: Password-based cryptography revisited","main_file_link":[{"url":"https://eprint.iacr.org/2016/166","open_access":"1"}],"citation":{"apa":"Demay, G., Gazi, P., Maurer, U., &#38; Tackmann, B. (2019). Per-session security: Password-based cryptography revisited. <i>Journal of Computer Security</i>. IOS Press. <a href=\"https://doi.org/10.3233/JCS-181131\">https://doi.org/10.3233/JCS-181131</a>","ista":"Demay G, Gazi P, Maurer U, Tackmann B. 2019. Per-session security: Password-based cryptography revisited. Journal of Computer Security. 27(1), 75–111.","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27 (2019) 75–111.","ieee":"G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based cryptography revisited,” <i>Journal of Computer Security</i>, vol. 27, no. 1. IOS Press, pp. 75–111, 2019.","mla":"Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography Revisited.” <i>Journal of Computer Security</i>, vol. 27, no. 1, IOS Press, 2019, pp. 75–111, doi:<a href=\"https://doi.org/10.3233/JCS-181131\">10.3233/JCS-181131</a>.","ama":"Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based cryptography revisited. <i>Journal of Computer Security</i>. 2019;27(1):75-111. doi:<a href=\"https://doi.org/10.3233/JCS-181131\">10.3233/JCS-181131</a>","chicago":"Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session Security: Password-Based Cryptography Revisited.” <i>Journal of Computer Security</i>. IOS Press, 2019. <a href=\"https://doi.org/10.3233/JCS-181131\">https://doi.org/10.3233/JCS-181131</a>."},"intvolume":"        27","ec_funded":1,"status":"public","scopus_import":"1","publication_identifier":{"issn":["0926227X"]},"issue":"1"},{"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"type":"conference","date_published":"2019-04-06T00:00:00Z","volume":11443,"oa_version":"Preprint","doi":"10.1007/978-3-030-17259-6_11","date_updated":"2023-09-08T11:33:20Z","publisher":"Springer Nature","article_processing_charge":"No","quality_controlled":"1","oa":1,"month":"04","conference":{"location":"Beijing, China","end_date":"2019-04-17","start_date":"2019-04-14","name":"PKC: Public-Key Cryptograhy"},"alternative_title":["LNCS"],"page":"317-346","author":[{"last_name":"Fuchsbauer","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg"},{"last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"day":"06","publication_status":"published","date_created":"2019-05-13T08:13:46Z","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10035"}]},"year":"2019","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"status":"public","ec_funded":1,"intvolume":"     11443","citation":{"mla":"Fuchsbauer, Georg, et al. <i>Adaptively Secure Proxy Re-Encryption</i>. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:<a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">10.1007/978-3-030-17259-6_11</a>.","ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:<a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">10.1007/978-3-030-17259-6_11</a>","chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">https://doi.org/10.1007/978-3-030-17259-6_11</a>.","apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., &#38; 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. <a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">https://doi.org/10.1007/978-3-030-17259-6_11</a>","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.","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.","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346."},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/426"}],"title":"Adaptively secure proxy re-encryption","_id":"6430","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","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)."}],"publication_identifier":{"isbn":["9783030172589"],"issn":["03029743"],"eissn":["16113349"]},"scopus_import":"1"},{"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-095-8"]},"scopus_import":1,"file_date_updated":"2020-07-14T12:47:33Z","status":"public","ec_funded":1,"intvolume":"       124","citation":{"ama":"Pietrzak KZ. Simple verifiable delay functions. In: <i>10th Innovations in Theoretical Computer Science Conference</i>. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.60\">10.4230/LIPICS.ITCS.2019.60</a>","mla":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” <i>10th Innovations in Theoretical Computer Science Conference</i>, vol. 124, 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.60\">10.4230/LIPICS.ITCS.2019.60</a>.","chicago":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In <i>10th Innovations in Theoretical Computer Science Conference</i>, Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.60\">https://doi.org/10.4230/LIPICS.ITCS.2019.60</a>.","ista":"Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.","apa":"Pietrzak, K. Z. (2019). Simple verifiable delay functions. In <i>10th Innovations in Theoretical Computer Science Conference</i> (Vol. 124). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.60\">https://doi.org/10.4230/LIPICS.ITCS.2019.60</a>","ieee":"K. Z. Pietrzak, “Simple verifiable delay functions,” in <i>10th Innovations in Theoretical Computer Science Conference</i>, San Diego, CA, United States, 2019, vol. 124.","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019."},"has_accepted_license":"1","main_file_link":[{"url":"https://eprint.iacr.org/2018/627","open_access":"1"}],"title":"Simple verifiable delay functions","_id":"6528","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism.","lang":"eng"}],"conference":{"location":"San Diego, CA, United States","end_date":"2019-01-12","start_date":"2019-01-10","name":"ITCS 2019: Innovations in Theoretical Computer Science"},"alternative_title":["LIPIcs"],"author":[{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"day":"10","publication_status":"published","date_created":"2019-06-06T14:12:36Z","year":"2019","language":[{"iso":"eng"}],"ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"department":[{"_id":"KrPi"}],"date_published":"2019-01-10T00:00:00Z","type":"conference","project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"volume":124,"oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPICS.ITCS.2019.60","date_updated":"2021-01-12T08:07:53Z","publication":"10th Innovations in Theoretical Computer Science Conference","article_processing_charge":"No","quality_controlled":"1","oa":1,"file":[{"content_type":"application/pdf","date_created":"2019-06-06T14:22:04Z","file_id":"6529","creator":"dernst","relation":"main_file","access_level":"open_access","file_name":"2019_LIPIcs_Pietrzak.pdf","checksum":"f0ae1bb161431d9db3dea5ace082bfb5","date_updated":"2020-07-14T12:47:33Z","file_size":558770}],"article_number":"60","month":"01"}]