[{"citation":{"ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in <i>19th Theory of Cryptography Conference 2021</i>, Raleigh, NC, United States, 2021.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research, 2021.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <i>19th Theory of Cryptography Conference 2021</i>, International Association for Cryptologic Research, 2021.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2021). The cost of adaptivity in security games on graphs. In <i>19th Theory of Cryptography Conference 2021</i>. Raleigh, NC, United States: International Association for Cryptologic Research.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research; 2021."},"conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography Conference"},"title":"The cost of adaptivity in security games on graphs","day":"08","year":"2021","oa_version":"Preprint","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael","full_name":"Walter, Michael"}],"type":"conference","related_material":{"record":[{"relation":"later_version","id":"10410","status":"public"},{"id":"10035","relation":"dissertation_contains","status":"public"}]},"language":[{"iso":"eng"}],"date_updated":"2023-10-17T09:24:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"07","date_created":"2021-09-27T12:52:05Z","_id":"10048","abstract":[{"text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower\r\nbounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and\r\nbroadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.\r\n","lang":"eng"}],"date_published":"2021-07-08T00:00:00Z","publication_status":"published","publisher":"International Association for Cryptologic Research","main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"oa":1,"quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"19th Theory of Cryptography Conference 2021","status":"public"},{"day":"26","author":[{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"last_name":"Pascual Perez","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"last_name":"Capretto","first_name":"Margarita","full_name":"Capretto, Margarita"},{"last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"id":"D0CF4148-C985-11E9-8066-0BDEE5697425","full_name":"Markov, Ilia","first_name":"Ilia","last_name":"Markov"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","first_name":"Michelle X","full_name":"Yeo, Michelle X"},{"full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"type":"conference","citation":{"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.","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.","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>.","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>.","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <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>","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>"},"ec_funded":1,"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","conference":{"location":"San Francisco, CA, United States","start_date":"2021-05-24","end_date":"2021-05-27","name":"SP: Symposium on Security and Privacy"},"language":[{"iso":"eng"}],"doi":"10.1109/sp40001.2021.00035","related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"}]},"project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"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.","month":"08","date_created":"2021-09-27T13:46:27Z","page":"268-284","publication":"2021 IEEE Symposium on Security and Privacy ","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"quality_controlled":"1","status":"public","publisher":"IEEE","oa_version":"Preprint","year":"2021","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_updated":"2023-09-07T13:32:11Z","_id":"10049","date_published":"2021-08-26T00:00:00Z","abstract":[{"lang":"eng","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."}],"article_processing_charge":"No","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1489"}],"oa":1},{"volume":13043,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1224"}],"oa":1,"publication_status":"published","_id":"10407","date_published":"2021-11-04T00:00:00Z","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"}],"article_processing_charge":"No","publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"]},"external_id":{"isi":["000728364000014"]},"scopus_import":"1","date_updated":"2023-08-14T13:07:46Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","year":"2021","intvolume":"     13043","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","isi":1,"publisher":"Springer Nature","date_created":"2021-12-05T23:01:42Z","month":"11","page":"397-428","doi":"10.1007/978-3-030-90453-1_14","language":[{"iso":"eng"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"author":[{"last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"first_name":"Stefan","full_name":"Dziembowski, Stefan","last_name":"Dziembowski"},{"first_name":"Małgorzata","full_name":"Gałązka, Małgorzata","last_name":"Gałązka"},{"last_name":"Lizurej","full_name":"Lizurej, Tomasz","first_name":"Tomasz"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","alternative_title":["LNCS"],"day":"04","title":"Trojan-resilience without cryptography","conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography Conference"},"citation":{"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>","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>","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","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>.","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.","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."},"ec_funded":1},{"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90456-2_8","acknowledgement":"B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","grant_number":"665385"}],"day":"04","alternative_title":["LNCS"],"author":[{"last_name":"Alwen","first_name":"Joel F","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","full_name":"Auerbach, Benedikt","first_name":"Benedikt"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","last_name":"Pascual Perez"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Walter","first_name":"Michael","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"type":"conference","ec_funded":1,"citation":{"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>.","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.","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.","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>.","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>","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>","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."},"conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11"},"title":"Grafting key trees: Efficient key management for overlapping groups","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"19th International Conference","intvolume":"     13044","status":"public","publisher":"Springer Nature","isi":1,"month":"11","date_created":"2021-12-05T23:01:42Z","page":"222-253","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-14T13:19:39Z","scopus_import":"1","external_id":{"isi":["000728363700008"]},"publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0455-5"],"issn":["0302-9743"],"eisbn":["978-3-030-90456-2"]},"oa_version":"Preprint","year":"2021","volume":13044,"publication_status":"published","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2021/1158","open_access":"1"}],"_id":"10408","date_published":"2021-11-04T00:00:00Z","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"}],"article_processing_charge":"No"},{"year":"2021","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-17T06:21:38Z","scopus_import":"1","external_id":{"isi":["000728364000017"]},"publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"date_published":"2021-11-04T00:00:00Z","_id":"10409","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"}],"article_processing_charge":"No","volume":"13043 ","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"oa":1,"day":"04","alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"ec_funded":1,"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 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>","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>","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.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 486–517.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In <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>.","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>."},"conference":{"location":"Raleigh, NC, United States","start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography"},"title":"On treewidth, separators and Yao’s garbling","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90453-1_17","acknowledgement":"We are grateful to Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021 and TCC 2021 reviewers for their detailed review and suggestions, which helped improve presentation considerably.","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"status":"public","id":"10044","relation":"earlier_version"}]},"month":"11","date_created":"2021-12-05T23:01:43Z","page":"486-517","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"19th International Conference","status":"public","publisher":"Springer Nature","isi":1},{"oa_version":"Preprint","year":"2021","date_updated":"2023-10-17T09:24:07Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000728364000019"]},"scopus_import":"1","publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"]},"date_published":"2021-11-04T00:00:00Z","_id":"10410","abstract":[{"text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.","lang":"eng"}],"article_processing_charge":"No","volume":13043,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"oa":1,"day":"04","alternative_title":["LNCS"],"author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","ec_funded":1,"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581.","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>","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>.","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.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <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>."},"conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11"},"title":"The cost of adaptivity in security games on graphs","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90453-1_19","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).","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10048"}]},"month":"11","date_created":"2021-12-05T23:01:43Z","page":"550-581","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"19th International Conference","intvolume":"     13043","status":"public","publisher":"Springer Nature","isi":1},{"date_published":"2021-12-01T00:00:00Z","_id":"10609","abstract":[{"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.","lang":"eng"}],"article_processing_charge":"No","volume":13091,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1262"}],"oa":1,"year":"2021","oa_version":"Preprint","date_updated":"2023-08-17T06:34:41Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000927876200012"]},"scopus_import":"1","publication_identifier":{"eisbn":["978-3-030-92075-3"],"issn":["0302-9743"],"isbn":["978-3-030-92074-6"],"eissn":["1611-3349"]},"month":"12","date_created":"2022-01-09T23:01:27Z","page":"335-364","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","status":"public","intvolume":"     13091","publisher":"Springer Nature","isi":1,"day":"01","alternative_title":["LNCS"],"type":"conference","author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip"},{"full_name":"Ganesh, Chaya","first_name":"Chaya","last_name":"Ganesh"},{"first_name":"Mahak","full_name":"Pancholi, Mahak","last_name":"Pancholi"},{"full_name":"Sarkar, Pratik","first_name":"Pratik","last_name":"Sarkar"}],"ec_funded":1,"citation":{"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>","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>","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.","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.","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>."},"conference":{"location":"Virtual, Singapore","start_date":"2021-12-06","end_date":"2021-12-10","name":"ASIACRYPT: International Conference on Cryptology in Asia"},"title":"Reverse firewalls for adaptively secure MPC without setup","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-92075-3_12","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}]},{"volume":12704,"main_file_link":[{"url":"https://eprint.iacr.org/2021/557","open_access":"1"}],"oa":1,"publication_status":"published","_id":"9825","date_published":"2021-05-11T00:00:00Z","abstract":[{"text":"The dual attack has long been considered a relevant attack on lattice-based cryptographic schemes relying on the hardness of learning with errors (LWE) and its structured variants. As solving LWE corresponds to finding a nearest point on a lattice, one may naturally wonder how efficient this dual approach is for solving more general closest vector problems, such as the classical closest vector problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP, and preprocessing versions of these problems. While primal, sieving-based solutions to these problems (with preprocessing) were recently studied in a series of works on approximate Voronoi cells [Laa16b, DLdW19, Laa20, DLvW20], for the dual attack no such overview exists, especially for problems with preprocessing. With one of the take-away messages of the approximate Voronoi cell line of work being that primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one may further wonder if the dual attack suffers the same drawbacks, or if it is perhaps a better solution when trying to solve BDD(P).\r\n\r\nIn this work we provide an overview of cost estimates for dual algorithms for solving these “classical” closest lattice vector problems. Heuristically we expect to solve the search version of average-case CVPP in time and space   20.293𝑑+𝑜(𝑑)  in the single-target model. The distinguishing version of average-case CVPP, where we wish to distinguish between random targets and targets planted at distance (say)   0.99⋅𝑔𝑑  from the lattice, has the same complexity in the single-target model, but can be solved in time and space   20.195𝑑+𝑜(𝑑)  in the multi-target setting, when given a large number of targets from either target distribution. This suggests an inequivalence between distinguishing and searching, as we do not expect a similar improvement in the multi-target setting to hold for search-CVPP. We analyze three slightly different decoders, both for distinguishing and searching, and experimentally obtain concrete cost estimates for the dual attack in dimensions 50 to 80, which confirm our heuristic assumptions, and show that the hidden order terms in the asymptotic estimates are quite small.\r\n\r\nOur main take-away message is that the dual attack appears to mirror the approximate Voronoi cell line of work – whereas using approximate Voronoi cells works well for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales well for BDD(P) instances but performs poorly on approximate CVP(P).","lang":"eng"}],"article_processing_charge":"No","publication_identifier":{"issn":["03029743"],"isbn":["9783030755386"],"eissn":["16113349"]},"date_updated":"2023-02-23T14:09:54Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","scopus_import":"1","year":"2021","oa_version":"Preprint","status":"public","intvolume":"     12704","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Topics in Cryptology – CT-RSA 2021","publisher":"Springer Nature","date_created":"2021-08-08T22:01:30Z","month":"05","page":"478-502","doi":"10.1007/978-3-030-75539-3_20","language":[{"iso":"eng"}],"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.","alternative_title":["LNCS"],"author":[{"full_name":"Laarhoven, Thijs","first_name":"Thijs","last_name":"Laarhoven"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"type":"conference","day":"11","conference":{"location":"Virtual Event","start_date":"2021-05-17","end_date":"2021-05-20","name":"CT-RSA: Cryptographers’ Track at the RSA Conference"},"title":"Dual lattice attacks for closest vector problems (with preprocessing)","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>","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.","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>.","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.","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."}},{"publisher":"Springer Nature","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"quality_controlled":"1","publication":"Topics in Cryptology – CT-RSA 2021","status":"public","intvolume":"     12704","page":"399-421","month":"05","date_created":"2021-08-08T22:01:30Z","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).","project":[{"grant_number":"665385","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-75539-3_17","ec_funded":1,"citation":{"short":"B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 399–421.","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>","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>","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.","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.","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>.","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>."},"conference":{"end_date":"2021-05-20","start_date":"2021-05-17","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","location":"Virtual Event"},"title":"Inverse-Sybil attacks in automated contact tracing","day":"11","alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606"},{"id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","first_name":"Suvradip","full_name":"Chakraborty, Suvradip"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo"}],"publication_status":"published","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"volume":12704,"article_processing_charge":"No","_id":"9826","date_published":"2021-05-11T00:00:00Z","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","date_updated":"2023-02-23T14:09:56Z","scopus_import":"1","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030755386"]},"oa_version":"Submitted Version","year":"2021"},{"month":"06","date_created":"2021-08-29T22:01:16Z","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","publisher":"IEEE","isi":1,"day":"21","author":[{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"first_name":"Iosif","full_name":"Salem, Iosif","last_name":"Salem"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"type":"conference","citation":{"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).","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.","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>.","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>","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>"},"ec_funded":1,"title":"LightPIR: Privacy-preserving route discovery for payment channel networks","conference":{"name":"2021 IFIP Networking Conference (IFIP Networking)","end_date":"2021-06-24","start_date":"2021-06-21","location":"Espoo and Helsinki, Finland"},"language":[{"iso":"eng"}],"doi":"10.23919/IFIPNetworking52078.2021.9472205","related_material":{"record":[{"status":"public","id":"14506","relation":"dissertation_contains"}]},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"abstract":[{"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.","lang":"eng"}],"_id":"9969","date_published":"2021-06-21T00:00:00Z","arxiv":1,"article_processing_charge":"No","publication_status":"published","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2104.04293","open_access":"1"}],"year":"2021","oa_version":"Submitted Version","external_id":{"arxiv":["2104.04293"],"isi":["000853016800008"]},"scopus_import":"1","date_updated":"2023-11-30T10:54:50Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"eisbn":["978-3-9031-7639-3"],"eissn":["1861-2288"],"isbn":["978-1-6654-4501-6"]}},{"project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"related_material":{"record":[{"status":"public","id":"6677","relation":"part_of_dissertation"}]},"ddc":["000"],"doi":"10.15479/AT:ISTA:7896","language":[{"iso":"eng"}],"title":"On the average-case hardness of total search problems","ec_funded":1,"citation":{"short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","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>","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>","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","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>.","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>."},"alternative_title":["ISTA Thesis"],"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"}],"type":"dissertation","day":"25","degree_awarded":"PhD","publisher":"Institute of Science and Technology Austria","status":"public","department":[{"_id":"KrPi"}],"page":"126","date_created":"2020-05-26T14:08:55Z","supervisor":[{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"month":"05","publication_identifier":{"issn":["2663-337X"]},"date_updated":"2023-09-07T13:15:55Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","has_accepted_license":"1","year":"2020","oa":1,"publication_status":"published","license":"https://creativecommons.org/licenses/by/4.0/","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"file_date_updated":"2020-07-14T12:48:04Z","article_processing_charge":"No","date_published":"2020-05-25T00:00:00Z","_id":"7896","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"}],"file":[{"date_created":"2020-05-26T14:08:13Z","content_type":"application/pdf","relation":"main_file","file_id":"7897","date_updated":"2020-07-14T12:48:04Z","access_level":"open_access","checksum":"b39e2e1c376f5819b823fb7077491c64","file_name":"2020_Thesis_Kamath.pdf","file_size":1622742,"creator":"dernst"},{"date_created":"2020-05-26T14:08:23Z","content_type":"application/x-zip-compressed","file_id":"7898","relation":"source_file","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","date_updated":"2020-07-14T12:48:04Z","access_level":"closed","file_name":"Thesis_Kamath.zip","file_size":15301529,"creator":"dernst"}]},{"day":"01","alternative_title":["LNCS"],"author":[{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","first_name":"Benedikt","last_name":"Auerbach"},{"last_name":"Giacon","first_name":"Federico","full_name":"Giacon, Federico"},{"last_name":"Kiltz","first_name":"Eike","full_name":"Kiltz, Eike"}],"type":"conference","ec_funded":1,"citation":{"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>","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>","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>.","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.","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.","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>."},"conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2020-05-11","end_date":"2020-05-15"},"title":"Everybody’s a target: Scalability in public-key encryption","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-45727-3_16","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"month":"05","date_created":"2020-06-15T07:13:37Z","page":"475-506","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"Advances in Cryptology – EUROCRYPT 2020","status":"public","intvolume":"     12107","publisher":"Springer Nature","isi":1,"year":"2020","oa_version":"Submitted Version","date_updated":"2023-09-05T15:06:40Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000828688000016"]},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030457266","9783030457273"]},"_id":"7966","date_published":"2020-05-01T00:00:00Z","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."}],"article_processing_charge":"No","volume":12107,"publication_status":"published","main_file_link":[{"url":"https://eprint.iacr.org/2019/364","open_access":"1"}],"oa":1},{"publisher":"Springer Nature","publication":"Advances in Cryptology – CRYPTO 2020","department":[{"_id":"KrPi"}],"quality_controlled":"1","status":"public","intvolume":"     12171","page":"732-762","month":"08","date_created":"2020-08-30T22:01:12Z","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"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.","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-56880-1_26","citation":{"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>.","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.","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>.","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>","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>","short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 732–762."},"ec_funded":1,"title":"Reverse firewalls for actively secure MPCs","conference":{"end_date":"2020-08-21","start_date":"2020-08-17","name":"CRYPTO: Annual International Cryptology Conference","location":"Santa Barbara, CA, United States"},"day":"10","type":"conference","author":[{"full_name":"Chakraborty, Suvradip","first_name":"Suvradip","last_name":"Chakraborty","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"full_name":"Dziembowski, Stefan","first_name":"Stefan","last_name":"Dziembowski"},{"last_name":"Nielsen","first_name":"Jesper Buus","full_name":"Nielsen, Jesper Buus"}],"alternative_title":["LNCS"],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1317"}],"oa":1,"volume":12171,"article_processing_charge":"No","date_published":"2020-08-10T00:00:00Z","_id":"8322","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"}],"scopus_import":"1","date_updated":"2021-01-12T08:18:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783030568795"],"issn":["03029743"],"eissn":["16113349"]},"year":"2020","oa_version":"Preprint"},{"alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Genise","first_name":"Nicholas","full_name":"Genise, Nicholas"},{"full_name":"Micciancio, Daniele","first_name":"Daniele","last_name":"Micciancio"},{"first_name":"Chris","full_name":"Peikert, Chris","last_name":"Peikert"},{"last_name":"Walter","full_name":"Walter, Michael","first_name":"Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"day":"15","conference":{"name":"PKC: Public-Key Cryptography","end_date":"2020-05-07","start_date":"2020-05-04","location":"Edinburgh, United Kingdom"},"title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","ec_funded":1,"citation":{"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>.","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.","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.","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>.","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>","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>","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."},"doi":"10.1007/978-3-030-45374-9_21","language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"date_created":"2020-09-06T22:01:13Z","month":"05","page":"623-651","status":"public","intvolume":"     12110","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","publisher":"Springer Nature","oa_version":"Preprint","year":"2020","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030453732"]},"date_updated":"2023-02-23T13:31:06Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","_id":"8339","date_published":"2020-05-15T00:00:00Z","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."}],"article_processing_charge":"No","volume":12110,"main_file_link":[{"url":"https://eprint.iacr.org/2020/337","open_access":"1"}],"oa":1,"publication_status":"published"},{"publisher":"Springer Nature","isi":1,"quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Progress in Cryptology","status":"public","intvolume":"     12578","page":"3-15","month":"12","series_title":"LNCS","date_created":"2021-01-03T23:01:23Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-65277-7_1","ec_funded":1,"citation":{"short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","apa":"Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay attacks in private contact tracing. In <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>","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>","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.","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.","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>.","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>."},"conference":{"location":"Bangalore, India","end_date":"2020-12-16","start_date":"2020-12-13","name":"INDOCRYPT: International Conference on Cryptology in India"},"title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing","day":"08","type":"conference","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"publication_status":"published","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2020/418","open_access":"1"}],"volume":12578,"article_processing_charge":"No","_id":"8987","date_published":"2020-12-08T00:00:00Z","abstract":[{"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.","lang":"eng"}],"date_updated":"2023-08-24T11:08:58Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","external_id":{"isi":["000927592800001"]},"publication_identifier":{"isbn":["9783030652760"],"issn":["03029743"],"eissn":["16113349"]},"oa_version":"Preprint","year":"2020"},{"status":"public","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019","department":[{"_id":"KrPi"}],"quality_controlled":"1","isi":1,"publisher":"ACM Press","date_created":"2019-07-24T09:20:53Z","month":"06","page":"1103-1114","doi":"10.1145/3313276.3316400","language":[{"iso":"eng"}],"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"7896"}]},"type":"conference","author":[{"last_name":"Choudhuri","first_name":"Arka Rai","full_name":"Choudhuri, Arka Rai"},{"last_name":"Hubáček","first_name":"Pavel","full_name":"Hubáček, Pavel"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Alon","full_name":"Rosen, Alon","last_name":"Rosen"},{"first_name":"Guy N.","full_name":"Rothblum, Guy N.","last_name":"Rothblum"}],"day":"01","title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","start_date":"2019-06-23","location":"Phoenix, AZ, United States"},"citation":{"chicago":"Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>, 1103–14. ACM Press, 2019. <a href=\"https://doi.org/10.1145/3313276.3316400\">https://doi.org/10.1145/3313276.3316400</a>.","ieee":"A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>, Phoenix, AZ, United States, 2019, pp. 1103–1114.","ista":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.","mla":"Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>, ACM Press, 2019, pp. 1103–14, doi:<a href=\"https://doi.org/10.1145/3313276.3316400\">10.1145/3313276.3316400</a>.","short":"A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N. Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–1114.","ama":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>. ACM Press; 2019:1103-1114. doi:<a href=\"https://doi.org/10.1145/3313276.3316400\">10.1145/3313276.3316400</a>","apa":"Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., &#38; Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i> (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. <a href=\"https://doi.org/10.1145/3313276.3316400\">https://doi.org/10.1145/3313276.3316400</a>"},"ec_funded":1,"oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/549"}],"publication_status":"published","abstract":[{"lang":"eng","text":"The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n)."}],"_id":"6677","date_published":"2019-06-01T00:00:00Z","article_processing_charge":"No","publication_identifier":{"isbn":["9781450367059"]},"external_id":{"isi":["000523199100100"]},"scopus_import":"1","date_updated":"2023-09-07T13:15:55Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","year":"2019","oa_version":"Preprint"},{"page":"157-180","place":"Cham","month":"06","date_created":"2019-07-29T12:25:31Z","series_title":"LNCS","publisher":"Springer Nature","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"Progress in Cryptology – AFRICACRYPT 2019","status":"public","intvolume":"     11627","ec_funded":1,"citation":{"ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. <i>Progress in Cryptology – AFRICACRYPT 2019</i>. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:<a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">10.1007/978-3-030-23696-0_9</a>","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, &#38; T. Rachidi (Eds.), <i>Progress in Cryptology – AFRICACRYPT 2019</i> (Vol. 11627, pp. 157–180). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">https://doi.org/10.1007/978-3-030-23696-0_9</a>","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” <i>Progress in Cryptology – AFRICACRYPT 2019</i>, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:<a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">10.1007/978-3-030-23696-0_9</a>.","chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In <i>Progress in Cryptology – AFRICACRYPT 2019</i>, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">https://doi.org/10.1007/978-3-030-23696-0_9</a>.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.","ieee":"M. Walter, “Sampling the integers with low relative error,” in <i>Progress in Cryptology – AFRICACRYPT 2019</i>, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180."},"conference":{"location":"Rabat, Morocco","start_date":"2019-07-09","end_date":"2019-07-11","name":"AFRICACRYPT: International Conference on Cryptology in Africa"},"title":"Sampling the integers with low relative error","day":"29","type":"book_chapter","author":[{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-23696-0_9","article_processing_charge":"No","date_published":"2019-06-29T00:00:00Z","_id":"6726","abstract":[{"text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so.","lang":"eng"}],"publication_status":"published","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2019/068","open_access":"1"}],"volume":11627,"editor":[{"last_name":"Buchmann","full_name":"Buchmann, J","first_name":"J"},{"first_name":"A","full_name":"Nitaj, A","last_name":"Nitaj"},{"last_name":"Rachidi","full_name":"Rachidi, T","first_name":"T"}],"oa_version":"Preprint","year":"2019","date_updated":"2023-02-23T12:50:15Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","scopus_import":"1","publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["978-3-0302-3695-3"],"eisbn":["978-3-0302-3696-0"]}},{"month":"07","date_created":"2019-11-28T10:19:21Z","publisher":"IEEE","isi":1,"publication":"2019 IEEE International Symposium on Information Theory","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","citation":{"short":"M. Skórski, in:, 2019 IEEE International Symposium on Information Theory, IEEE, 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>","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>","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>.","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.","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.","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>."},"title":"Strong chain rules for min-entropy under few bits spoiled","conference":{"end_date":"2019-07-12","start_date":"2019-07-07","name":"ISIT: International Symposium on Information Theory","location":"Paris, France"},"day":"01","author":[{"last_name":"Skórski","first_name":"Maciej","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"type":"conference","language":[{"iso":"eng"}],"doi":"10.1109/isit.2019.8849240","arxiv":1,"article_processing_charge":"No","article_number":"8849240","_id":"7136","date_published":"2019-07-01T00:00:00Z","abstract":[{"lang":"eng","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. "}],"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1702.08476"}],"year":"2019","oa_version":"Preprint","external_id":{"isi":["000489100301043"],"arxiv":["1702.08476"]},"scopus_import":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_updated":"2023-09-06T11:15:41Z","publication_identifier":{"isbn":["9781538692912"]}},{"scopus_import":"1","external_id":{"isi":["000483516200010"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_updated":"2023-09-06T15:26:06Z","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030176556","9783030176563"]},"oa_version":"Submitted Version","year":"2019","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/252"}],"oa":1,"volume":11477,"article_processing_charge":"No","_id":"7411","date_published":"2019-04-24T00:00:00Z","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"}],"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-17656-3_10","citation":{"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>","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>","short":"H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019, pp. 277–291.","mla":"Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” <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>.","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.","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.","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>."},"ec_funded":1,"title":"Reversible proofs of sequential work","conference":{"end_date":"2019-05-23","start_date":"2019-05-19","name":"International Conference on the Theory and Applications of Cryptographic Techniques","location":"Darmstadt, Germany"},"day":"24","author":[{"last_name":"Abusalah","full_name":"Abusalah, Hamza M","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"type":"conference","alternative_title":["LNCS"],"publisher":"Springer International Publishing","isi":1,"publication":"Advances in Cryptology – EUROCRYPT 2019","quality_controlled":"1","department":[{"_id":"KrPi"}],"intvolume":"     11477","status":"public","page":"277-291","month":"04","date_created":"2020-01-30T09:26:14Z"},{"article_type":"original","year":"2019","oa_version":"Preprint","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:05:08Z","publication_identifier":{"issn":["0926227X"]},"article_processing_charge":"No","issue":"1","_id":"5887","abstract":[{"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.","lang":"eng"}],"date_published":"2019-01-01T00:00:00Z","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/166"}],"volume":27,"citation":{"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>.","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.","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.","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>.","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27 (2019) 75–111.","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>","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>"},"ec_funded":1,"title":"Per-session security: Password-based cryptography revisited","day":"1","author":[{"full_name":"Demay, Gregory","first_name":"Gregory","last_name":"Demay"},{"last_name":"Gazi","full_name":"Gazi, Peter","first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Maurer, Ueli","first_name":"Ueli","last_name":"Maurer"},{"full_name":"Tackmann, Bjorn","first_name":"Bjorn","last_name":"Tackmann"}],"type":"journal_article","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"language":[{"iso":"eng"}],"doi":"10.3233/JCS-181131","page":"75-111","month":"01","date_created":"2019-01-27T22:59:10Z","publisher":"IOS Press","publication":"Journal of Computer Security","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","intvolume":"        27"}]