[{"citation":{"ista":"Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost of post-compromise security in concurrent Continuous Group-Key Agreement. 21st International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 14371, 271–300.","chicago":"Auerbach, Benedikt, Miguel Cueto Noval, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “On the Cost of Post-Compromise Security in Concurrent Continuous Group-Key Agreement.” In 21st International Conference on Theory of Cryptography, 14371:271–300. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_10.","short":"B. Auerbach, M. Cueto Noval, G. Pascual Perez, K.Z. Pietrzak, in:, 21st International Conference on Theory of Cryptography, Springer Nature, 2023, pp. 271–300.","ieee":"B. Auerbach, M. Cueto Noval, G. Pascual Perez, and K. Z. Pietrzak, “On the cost of post-compromise security in concurrent Continuous Group-Key Agreement,” in 21st International Conference on Theory of Cryptography, Taipei, Taiwan, 2023, vol. 14371, pp. 271–300.","apa":"Auerbach, B., Cueto Noval, M., Pascual Perez, G., & Pietrzak, K. Z. (2023). On the cost of post-compromise security in concurrent Continuous Group-Key Agreement. In 21st International Conference on Theory of Cryptography (Vol. 14371, pp. 271–300). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_10","ama":"Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. On the cost of post-compromise security in concurrent Continuous Group-Key Agreement. In: 21st International Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:271-300. doi:10.1007/978-3-031-48621-0_10","mla":"Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent Continuous Group-Key Agreement.” 21st International Conference on Theory of Cryptography, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:10.1007/978-3-031-48621-0_10."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","last_name":"Auerbach","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"article_processing_charge":"No","title":"On the cost of post-compromise security in concurrent Continuous Group-Key Agreement","quality_controlled":"1","publisher":"Springer Nature","oa":1,"year":"2023","day":"27","publication":"21st International Conference on Theory of Cryptography","page":"271-300","date_published":"2023-11-27T00:00:00Z","doi":"10.1007/978-3-031-48621-0_10","date_created":"2023-12-17T23:00:53Z","_id":"14691","type":"conference","conference":{"name":"TCC: Theory of Cryptography","location":"Taipei, Taiwan","end_date":"2023-12-02","start_date":"2023-11-29"},"status":"public","date_updated":"2023-12-18T08:36:51Z","department":[{"_id":"KrPi"}],"abstract":[{"text":"Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The most expensive operation provided by CKGA is that which allows for a user to refresh their key material in order to achieve forward secrecy (old messages are secure when a user is compromised) and post-compromise security (users can heal from compromise). One caveat of early CGKA protocols is that these update operations had to be performed sequentially, with any user wanting to update their key material having had to receive and process all previous updates. Late versions of TreeKEM do allow for concurrent updates at the cost of a communication overhead per update message that is linear in the number of updating parties. This was shown to be indeed necessary when achieving PCS in just two rounds of communication by [Bienstock et al. TCC’20].\r\nThe recently proposed protocol CoCoA [Alwen et al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements are relaxed, and only a logarithmic number of rounds is required. The natural question, thus, is whether CoCoA is optimal in this setting.\r\nIn this work we answer this question, providing a lower bound on the cost (concretely, the amount of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary k number of rounds, that shows that CoCoA is very close to optimal. Additionally, we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification of it, with a reduced communication cost for certain k.\r\nWe prove our bound in a combinatorial setting where the state of the protocol progresses in rounds, and the state of the protocol in each round is captured by a set system, each set specifying a set of users who share a secret key. We show this combinatorial model is equivalent to a symbolic model capturing building blocks including PRFs and public-key encryption, related to the one used by Bienstock et al.\r\nOur lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of updates per user the protocol requires to heal. This generalizes the n2 bound for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1) efficiency we get for the variants of the CoCoA protocol also introduced in this paper.","lang":"eng"}],"oa_version":"Preprint","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2023/1123"}],"month":"11","intvolume":" 14371","publication_identifier":{"isbn":["9783031486203"],"eissn":["1611-3349"],"issn":["0302-9743"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":14371},{"volume":14371,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783031486203"],"eissn":["1611-3349"],"issn":["0302-9743"]},"publication_status":"published","month":"11","intvolume":" 14371","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2023/808","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The generic-group model (GGM) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group. In it, it is possible to prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by cryptographic schemes based on such problems. A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt GGM lower bounds for one problem to another, by means of conceptually simple reductions.\r\nIn this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach.\r\nThe main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm, the d-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup’s GGM without additional restrictions on the query behavior of the adversary, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach."}],"department":[{"_id":"KrPi"}],"date_updated":"2023-12-18T09:17:03Z","status":"public","type":"conference","_id":"14692","doi":"10.1007/978-3-031-48621-0_11","date_published":"2023-11-27T00:00:00Z","date_created":"2023-12-17T23:00:54Z","page":"301-330","day":"27","publication":"21st International Conference on Theory of Cryptography","year":"2023","quality_controlled":"1","publisher":"Springer Nature","oa":1,"title":"Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing","author":[{"first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt"},{"id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","first_name":"Charlotte","full_name":"Hoffmann, Charlotte","orcid":"0000-0003-2027-5549","last_name":"Hoffmann"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Auerbach, Benedikt, Charlotte Hoffmann, and Guillermo Pascual Perez. “Generic-Group Lower Bounds via Reductions between Geometric-Search Problems: With and without Preprocessing.” In 21st International Conference on Theory of Cryptography, 14371:301–30. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_11.","ista":"Auerbach B, Hoffmann C, Pascual Perez G. 2023. Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. 21st International Conference on Theory of Cryptography. , LNCS, vol. 14371, 301–330.","mla":"Auerbach, Benedikt, et al. “Generic-Group Lower Bounds via Reductions between Geometric-Search Problems: With and without Preprocessing.” 21st International Conference on Theory of Cryptography, vol. 14371, Springer Nature, 2023, pp. 301–30, doi:10.1007/978-3-031-48621-0_11.","apa":"Auerbach, B., Hoffmann, C., & Pascual Perez, G. (2023). Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. In 21st International Conference on Theory of Cryptography (Vol. 14371, pp. 301–330). Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_11","ama":"Auerbach B, Hoffmann C, Pascual Perez G. Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. In: 21st International Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:301-330. doi:10.1007/978-3-031-48621-0_11","short":"B. Auerbach, C. Hoffmann, G. Pascual Perez, in:, 21st International Conference on Theory of Cryptography, Springer Nature, 2023, pp. 301–330.","ieee":"B. Auerbach, C. Hoffmann, and G. Pascual Perez, “Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing,” in 21st International Conference on Theory of Cryptography, 2023, vol. 14371, pp. 301–330."}},{"status":"public","type":"conference","conference":{"start_date":"2023-05-01","end_date":"2023-05-05","location":"Bol, Brac, Croatia","name":"FC: Financial Cryptography and Data Security"},"_id":"14736","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"date_updated":"2024-01-08T09:36:36Z","month":"12","intvolume":" 13950","alternative_title":["LNCS"],"oa_version":"None","abstract":[{"text":"Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain routes may deplete channels in one direction, and hence prevent further transactions. In order to reap the full potential of PCNs, recharging and rebalancing mechanisms are required to provision channels, as well as an admission control logic to decide which transactions to reject in case capacity is insufficient. This paper presents a formal model of this optimisation problem. In particular, we consider an online algorithms perspective, where transactions arrive over time in an unpredictable manner. Our main contributions are competitive online algorithms which come with provable guarantees over time. We empirically evaluate our algorithms on randomly generated transactions to compare the average performance of our algorithms to our theoretical bounds. We also show how this model and approach differs from related problems in classic communication networks.","lang":"eng"}],"volume":13950,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783031477539"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783031477546"]},"publication_status":"published","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"title":"R2: Boosting liquidity in payment channel networks with online admission control","author":[{"first_name":"Mahsa","last_name":"Bastankhah","full_name":"Bastankhah, Mahsa"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Maddah-Ali, Mohammad Ali","last_name":"Maddah-Ali","first_name":"Mohammad Ali"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” 27th International Conference on Financial Cryptography and Data Security, vol. 13950, Springer Nature, 2023, pp. 309–25, doi:10.1007/978-3-031-47754-6_18.","ieee":"M. Bastankhah, K. Chatterjee, M. A. Maddah-Ali, S. Schmid, J. Svoboda, and M. X. Yeo, “R2: Boosting liquidity in payment channel networks with online admission control,” in 27th International Conference on Financial Cryptography and Data Security, Bol, Brac, Croatia, 2023, vol. 13950, pp. 309–325.","short":"M. Bastankhah, K. Chatterjee, M.A. Maddah-Ali, S. Schmid, J. Svoboda, M.X. Yeo, in:, 27th International Conference on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 309–325.","apa":"Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J., & Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online admission control. In 27th International Conference on Financial Cryptography and Data Security (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer Nature. https://doi.org/10.1007/978-3-031-47754-6_18","ama":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. R2: Boosting liquidity in payment channel networks with online admission control. In: 27th International Conference on Financial Cryptography and Data Security. Vol 13950. Springer Nature; 2023:309-325. doi:10.1007/978-3-031-47754-6_18","chicago":"Bastankhah, Mahsa, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” In 27th International Conference on Financial Cryptography and Data Security, 13950:309–25. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-47754-6_18.","ista":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. 2023. R2: Boosting liquidity in payment channel networks with online admission control. 27th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 309–325."},"publisher":"Springer Nature","quality_controlled":"1","acknowledgement":"Supported by the German Federal Ministry of Education and Research (BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).","doi":"10.1007/978-3-031-47754-6_18","date_published":"2023-12-01T00:00:00Z","date_created":"2024-01-08T09:30:22Z","page":"309-325","day":"01","publication":"27th International Conference on Financial Cryptography and Data Security","year":"2023"},{"ec_funded":1,"volume":13276,"publication_status":"published","publication_identifier":{"eisbn":["9783031070853"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031070846"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2022/251","open_access":"1"}],"scopus_import":"1","alternative_title":["LNCS"],"intvolume":" 13276","place":"Cham","month":"05","abstract":[{"lang":"eng","text":"Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can efficiently scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security.\r\n\r\nIn current proposals – most notably in TreeKEM (which is part of the IETF’s Messaging Layer Security (MLS) protocol draft) – for users in a group of size n to rotate their keys, they must each craft a message of size log(n) to be broadcast to the group using an (untrusted) delivery server.\r\n\r\nIn larger groups, having users sequentially rotate their keys requires too much bandwidth (or takes too long), so variants allowing any T≤n users to simultaneously rotate their keys in just 2 communication rounds have been suggested (e.g. “Propose and Commit” by MLS). Unfortunately, 2-round concurrent updates are either damaging or expensive (or both); i.e. they either result in future operations being more costly (e.g. via “blanking” or “tainting”) or are costly themselves requiring Ω(T) communication for each user [Bienstock et al., TCC’20].\r\n\r\nIn this paper we propose CoCoA; a new scheme that allows for T concurrent updates that are neither damaging nor costly. That is, they add no cost to future operations yet they only require Ω(log2(n)) communication per user. To circumvent the [Bienstock et al.] lower bound, CoCoA increases the number of rounds needed to complete all updates from 2 up to (at most) log(n); though typically fewer rounds are needed.\r\n\r\nThe key insight of our protocol is the following: in the (non-concurrent version of) TreeKEM, a delivery server which gets T concurrent update requests will approve one and reject the remaining T−1. In contrast, our server attempts to apply all of them. If more than one user requests to rotate the same key during a round, the server arbitrarily picks a winner. Surprisingly, we prove that regardless of how the server chooses the winners, all previously compromised users will recover after at most log(n) such update rounds.\r\n\r\nTo keep the communication complexity low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly forwards packets, but instead actively computes individualized packets tailored to each user. As the server is untrusted, this change requires us to develop new mechanisms ensuring robustness of the protocol."}],"oa_version":"Preprint","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"date_updated":"2023-08-03T07:25:02Z","conference":{"name":"EUROCRYPT: Annual International Conference on the Theory and Applications of Cryptology and Information Security","location":"Trondheim, Norway","end_date":"2022-06-03","start_date":"2022-05-30"},"type":"conference","status":"public","_id":"11476","page":"815–844","date_created":"2022-06-30T16:48:00Z","doi":"10.1007/978-3-031-07085-3_28","date_published":"2022-05-25T00:00:00Z","year":"2022","isi":1,"publication":"Advances in Cryptology – EUROCRYPT 2022","day":"25","oa":1,"publisher":"Springer Nature","quality_controlled":"1","acknowledgement":"We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful feedback on an earlier draft of this paper.","article_processing_charge":"No","external_id":{"isi":["000832305300028"]},"author":[{"last_name":"Alwen","full_name":"Alwen, Joël","first_name":"Joël"},{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","last_name":"Auerbach","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt"},{"full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen"},{"first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"last_name":"Walter","full_name":"Walter, Michael","first_name":"Michael"}],"title":"CoCoA: Concurrent continuous group key agreement","citation":{"short":"J. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2022, Springer Nature, Cham, 2022, pp. 815–844.","ieee":"J. Alwen et al., “CoCoA: Concurrent continuous group key agreement,” in Advances in Cryptology – EUROCRYPT 2022, Trondheim, Norway, 2022, vol. 13276, pp. 815–844.","ama":"Alwen J, Auerbach B, Cueto Noval M, et al. CoCoA: Concurrent continuous group key agreement. In: Advances in Cryptology – EUROCRYPT 2022. Vol 13276. Cham: Springer Nature; 2022:815–844. doi:10.1007/978-3-031-07085-3_28","apa":"Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak, K. Z., & Walter, M. (2022). CoCoA: Concurrent continuous group key agreement. In Advances in Cryptology – EUROCRYPT 2022 (Vol. 13276, pp. 815–844). Cham: Springer Nature. https://doi.org/10.1007/978-3-031-07085-3_28","mla":"Alwen, Joël, et al. “CoCoA: Concurrent Continuous Group Key Agreement.” Advances in Cryptology – EUROCRYPT 2022, vol. 13276, Springer Nature, 2022, pp. 815–844, doi:10.1007/978-3-031-07085-3_28.","ista":"Alwen J, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2022. CoCoA: Concurrent continuous group key agreement. Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT: Annual International Conference on the Theory and Applications of Cryptology and Information Security, LNCS, vol. 13276, 815–844.","chicago":"Alwen, Joël, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “CoCoA: Concurrent Continuous Group Key Agreement.” In Advances in Cryptology – EUROCRYPT 2022, 13276:815–844. Cham: Springer Nature, 2022. https://doi.org/10.1007/978-3-031-07085-3_28."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"},{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}]},{"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2022/093"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 13748","month":"12","abstract":[{"text":"The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known.\r\nWe present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.","lang":"eng"}],"oa_version":"Preprint","volume":13748,"publication_status":"published","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031223648"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"conference":{"location":"Chicago, IL, United States","end_date":"2022-11-10","start_date":"2022-11-07","name":"TCC: Theory of Cryptography"},"type":"conference","status":"public","_id":"12516","department":[{"_id":"KrPi"}],"date_updated":"2023-08-04T10:39:30Z","oa":1,"quality_controlled":"1","publisher":"Springer Nature","acknowledgement":"We are grateful to Devika Sharma and Luca Trevisan for their insight and advice and to an anonymous reviewer for helpful comments.\r\n\r\nThis work was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019547). The first author was additionally supported by RGC GRF CUHK14209920 and the fourth author was additionally supported by ISF grant No. 1399/17, project PROMETHEUS (Grant 780701), and Cariplo CRYPTONOMEX grant.","page":"565-592","date_created":"2023-02-05T23:01:00Z","doi":"10.1007/978-3-031-22365-5_20","date_published":"2022-12-21T00:00:00Z","year":"2022","isi":1,"publication":"Theory of Cryptography","day":"21","article_processing_charge":"No","external_id":{"isi":["000921318200020"]},"author":[{"first_name":"Andrej","full_name":"Bogdanov, Andrej","last_name":"Bogdanov"},{"full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel"},{"id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","first_name":"Charlotte","last_name":"Hoffmann","full_name":"Hoffmann, Charlotte"},{"last_name":"Rosen","full_name":"Rosen, Alon","first_name":"Alon"}],"title":"Public-Key Encryption from Homogeneous CLWE","citation":{"ama":"Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. Public-Key Encryption from Homogeneous CLWE. In: Theory of Cryptography. Vol 13748. Springer Nature; 2022:565-592. doi:10.1007/978-3-031-22365-5_20","apa":"Bogdanov, A., Cueto Noval, M., Hoffmann, C., & Rosen, A. (2022). Public-Key Encryption from Homogeneous CLWE. In Theory of Cryptography (Vol. 13748, pp. 565–592). Chicago, IL, United States: Springer Nature. https://doi.org/10.1007/978-3-031-22365-5_20","short":"A. Bogdanov, M. Cueto Noval, C. Hoffmann, A. Rosen, in:, Theory of Cryptography, Springer Nature, 2022, pp. 565–592.","ieee":"A. Bogdanov, M. Cueto Noval, C. Hoffmann, and A. Rosen, “Public-Key Encryption from Homogeneous CLWE,” in Theory of Cryptography, Chicago, IL, United States, 2022, vol. 13748, pp. 565–592.","mla":"Bogdanov, Andrej, et al. “Public-Key Encryption from Homogeneous CLWE.” Theory of Cryptography, vol. 13748, Springer Nature, 2022, pp. 565–92, doi:10.1007/978-3-031-22365-5_20.","ista":"Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. 2022. Public-Key Encryption from Homogeneous CLWE. Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 13748, 565–592.","chicago":"Bogdanov, Andrej, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. “Public-Key Encryption from Homogeneous CLWE.” In Theory of Cryptography, 13748:565–92. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-22365-5_20."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"intvolume":" 13411","month":"10","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2110.08848","open_access":"1"}],"scopus_import":"1","alternative_title":["LNCS"],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Payment channels effectively move the transaction load off-chain thereby successfully addressing the inherent scalability problem most cryptocurrencies face. A major drawback of payment channels is the need to “top up” funds on-chain when a channel is depleted. Rebalancing was proposed to alleviate this issue, where parties with depleting channels move their funds along a cycle to replenish their channels off-chain. Protocols for rebalancing so far either introduce local solutions or compromise privacy.\r\nIn this work, we present an opt-in rebalancing protocol that is both private and globally optimal, meaning our protocol maximizes the total amount of rebalanced funds. We study rebalancing from the framework of linear programming. To obtain full privacy guarantees, we leverage multi-party computation in solving the linear program, which is executed by selected participants to maintain efficiency. Finally, we efficiently decompose the rebalancing solution into incentive-compatible cycles which conserve user balances when executed atomically."}],"volume":13411,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9783031182822"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783031182839"]},"status":"public","conference":{"start_date":"2022-05-02","location":"Grenada","end_date":"2022-05-06","name":"FC: Financial Cryptography and Data Security"},"type":"conference","_id":"12167","department":[{"_id":"KrPi"}],"date_updated":"2023-09-05T15:10:57Z","oa":1,"quality_controlled":"1","publisher":"Springer Nature","date_created":"2023-01-12T12:10:38Z","date_published":"2022-10-22T00:00:00Z","doi":"10.1007/978-3-031-18283-9_17","page":"358-373","publication":"Financial Cryptography and Data Security","day":"22","year":"2022","title":"Hide & Seek: Privacy-preserving rebalancing on payment channel networks","article_processing_charge":"No","external_id":{"arxiv":["2110.08848"]},"author":[{"id":"c20482a0-3b89-11eb-9862-88cf6404b88c","first_name":"Georgia","last_name":"Avarikioti","full_name":"Avarikioti, Georgia"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"first_name":"Iosif","last_name":"Salem","full_name":"Salem, Iosif"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"first_name":"Samarth","full_name":"Tiwari, Samarth","last_name":"Tiwari"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. 2022. Hide & Seek: Privacy-preserving rebalancing on payment channel networks. Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13411, 358–373.","chicago":"Avarikioti, Georgia, Krzysztof Z Pietrzak, Iosif Salem, Stefan Schmid, Samarth Tiwari, and Michelle X Yeo. “Hide & Seek: Privacy-Preserving Rebalancing on Payment Channel Networks.” In Financial Cryptography and Data Security, 13411:358–73. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_17.","ieee":"G. Avarikioti, K. Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. X. Yeo, “Hide & Seek: Privacy-preserving rebalancing on payment channel networks,” in Financial Cryptography and Data Security, Grenada, 2022, vol. 13411, pp. 358–373.","short":"G. Avarikioti, K.Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, M.X. Yeo, in:, Financial Cryptography and Data Security, Springer Nature, 2022, pp. 358–373.","ama":"Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. Hide & Seek: Privacy-preserving rebalancing on payment channel networks. In: Financial Cryptography and Data Security. Vol 13411. Springer Nature; 2022:358-373. doi:10.1007/978-3-031-18283-9_17","apa":"Avarikioti, G., Pietrzak, K. Z., Salem, I., Schmid, S., Tiwari, S., & Yeo, M. X. (2022). Hide & Seek: Privacy-preserving rebalancing on payment channel networks. In Financial Cryptography and Data Security (Vol. 13411, pp. 358–373). Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_17","mla":"Avarikioti, Georgia, et al. “Hide & Seek: Privacy-Preserving Rebalancing on Payment Channel Networks.” Financial Cryptography and Data Security, vol. 13411, Springer Nature, 2022, pp. 358–73, doi:10.1007/978-3-031-18283-9_17."}},{"date_updated":"2023-09-05T15:12:27Z","department":[{"_id":"KrPi"}],"_id":"12176","conference":{"name":"CRYYPTO: International Cryptology Conference","end_date":"2022-08-18","location":"Santa Barbara, CA, United States","start_date":"2022-08-15"},"type":"conference","status":"public","publication_status":"published","publication_identifier":{"eisbn":["9783031159794"],"isbn":["9783031159787"],"eissn":["1611-3349"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"volume":13508,"abstract":[{"text":"A proof of exponentiation (PoE) in a group G of unknown order allows a prover to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive has recently found exciting applications in the constructions of verifiable delay functions and succinct arguments of knowledge. The most practical PoEs only achieve soundness either under computational assumptions, i.e., they are arguments (Wesolowski, Journal of Cryptology 2020), or in groups that come with the promise of not having any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in general groups of unknown order is due to Block et al. (CRYPTO 2021), and can be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits of security, say λ=80, the number of repetitions required (and thus the blow-up in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound PoE for the case where the exponent q is the product of all primes up to some bound B. We show that, in this case, it suffices to run only λ/log(B) parallel instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to Block et al. by an order of magnitude. Furthermore, we show that in the known applications where PoEs are used as a building block such structured exponents are viable. Finally, we also discuss batching of our PoE, showing that many proofs (for the same G and q but different x and T) can be batched by adding only a single element to the proof per additional statement.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"https://eprint.iacr.org/2022/1021","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 13508","month":"10","citation":{"short":"C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.","ieee":"C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical statistically-sound proofs of exponentiation in any group,” in Advances in Cryptology – CRYPTO 2022, Santa Barbara, CA, United States, 2022, vol. 13508, pp. 370–399.","ama":"Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound proofs of exponentiation in any group. In: Advances in Cryptology – CRYPTO 2022. Vol 13508. Springer Nature; 2022:370-399. doi:10.1007/978-3-031-15979-4_13","apa":"Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., & Pietrzak, K. Z. (2022). Practical statistically-sound proofs of exponentiation in any group. In Advances in Cryptology – CRYPTO 2022 (Vol. 13508, pp. 370–399). Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-031-15979-4_13","mla":"Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.” Advances in Cryptology – CRYPTO 2022, vol. 13508, Springer Nature, 2022, pp. 370–99, doi:10.1007/978-3-031-15979-4_13.","ista":"Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYYPTO: International Cryptology Conference, LNCS, vol. 13508, 370–399.","chicago":"Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.” In Advances in Cryptology – CRYPTO 2022, 13508:370–99. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-15979-4_13."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000886792700013"]},"article_processing_charge":"No","author":[{"orcid":"0000-0003-2027-5549","full_name":"Hoffmann, Charlotte","last_name":"Hoffmann","first_name":"Charlotte","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7"},{"last_name":"Hubáček","full_name":"Hubáček, Pavel","first_name":"Pavel"},{"first_name":"Chethan","last_name":"Kamath","full_name":"Kamath, Chethan"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"title":"Practical statistically-sound proofs of exponentiation in any group","year":"2022","isi":1,"publication":"Advances in Cryptology – CRYPTO 2022","day":"13","page":"370-399","date_created":"2023-01-12T12:12:07Z","doi":"10.1007/978-3-031-15979-4_13","date_published":"2022-10-13T00:00:00Z","acknowledgement":"We would like to thank the authors of [BHR+21] for clarifying several questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19. Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part of this work at Institute of Science and Technology Austria.","oa":1,"publisher":"Springer Nature","quality_controlled":"1"},{"publication_status":"published","publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783030752446"]},"language":[{"iso":"eng"}],"file":[{"success":1,"checksum":"413e564d645ed93d7318672361d9d470","file_id":"11416","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2021_PKC_Walter.pdf","date_created":"2022-05-27T09:48:31Z","creator":"dernst","file_size":489017,"date_updated":"2022-05-27T09:48:31Z"}],"ec_funded":1,"volume":12710,"abstract":[{"text":"In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.","lang":"eng"}],"oa_version":"Published Version","alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 12710","month":"05","date_updated":"2023-02-23T13:58:47Z","ddc":["000"],"department":[{"_id":"KrPi"}],"file_date_updated":"2022-05-27T09:48:31Z","_id":"9466","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"end_date":"2021-05-13","location":"Virtual","start_date":"2021-05-10","name":"PKC: IACR International Conference on Practice and Theory of Public Key Cryptography"},"type":"conference","status":"public","year":"2021","has_accepted_license":"1","publication":"Public-Key Cryptography – PKC 2021","day":"01","page":"45-67","date_created":"2021-06-06T22:01:29Z","doi":"10.1007/978-3-030-75245-3_3","date_published":"2021-05-01T00:00:00Z","acknowledgement":"This work was initiated in discussions with Léo Ducas, when the author was visiting the Simons Institute for the Theory of Computation during the program “Lattices: Algorithms, Complexity, and Cryptography”. We thank Thomas Espitau for pointing out a bug in a proof in an earlier version of this manuscript.","oa":1,"publisher":"Springer Nature","quality_controlled":"1","citation":{"ieee":"M. Walter, “The convergence of slide-type reductions,” in Public-Key Cryptography – PKC 2021, Virtual, 2021, vol. 12710, pp. 45–67.","short":"M. Walter, in:, Public-Key Cryptography – PKC 2021, Springer Nature, 2021, pp. 45–67.","ama":"Walter M. The convergence of slide-type reductions. In: Public-Key Cryptography – PKC 2021. Vol 12710. Springer Nature; 2021:45-67. doi:10.1007/978-3-030-75245-3_3","apa":"Walter, M. (2021). The convergence of slide-type reductions. In Public-Key Cryptography – PKC 2021 (Vol. 12710, pp. 45–67). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-75245-3_3","mla":"Walter, Michael. “The Convergence of Slide-Type Reductions.” Public-Key Cryptography – PKC 2021, vol. 12710, Springer Nature, 2021, pp. 45–67, doi:10.1007/978-3-030-75245-3_3.","ista":"Walter M. 2021. The convergence of slide-type reductions. Public-Key Cryptography – PKC 2021. PKC: IACR International Conference on Practice and Theory of Public Key Cryptography, LNCS, vol. 12710, 45–67.","chicago":"Walter, Michael. “The Convergence of Slide-Type Reductions.” In Public-Key Cryptography – PKC 2021, 12710:45–67. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75245-3_3."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","author":[{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"}],"title":"The convergence of slide-type reductions","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}]},{"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"date_updated":"2023-02-23T14:09:56Z","type":"conference","conference":{"name":"CT-RSA: Cryptographers’ Track at the RSA Conference","start_date":"2021-05-17","location":"Virtual Event","end_date":"2021-05-20"},"status":"public","_id":"9826","volume":12704,"ec_funded":1,"publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783030755386"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/670"}],"month":"05","intvolume":" 12704","abstract":[{"lang":"eng","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."}],"oa_version":"Submitted Version","author":[{"last_name":"Auerbach","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","title":"Inverse-Sybil attacks in automated contact tracing","citation":{"chicago":"Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021, 12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17.","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.","mla":"Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:10.1007/978-3-030-75539-3_17.","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.","ieee":"B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,” in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704, pp. 399–421.","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"International IST Doctoral Program","grant_number":"665385","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"page":"399-421","date_published":"2021-05-11T00:00:00Z","doi":"10.1007/978-3-030-75539-3_17","date_created":"2021-08-08T22:01:30Z","year":"2021","day":"11","publication":"Topics in Cryptology – CT-RSA 2021","publisher":"Springer Nature","quality_controlled":"1","oa":1,"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)."},{"day":"11","publication":"Topics in Cryptology – CT-RSA 2021","year":"2021","doi":"10.1007/978-3-030-75539-3_20","date_published":"2021-05-11T00:00:00Z","date_created":"2021-08-08T22:01:30Z","page":"478-502","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.","publisher":"Springer Nature","quality_controlled":"1","oa":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","citation":{"mla":"Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector Problems (with Preprocessing).” Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021, pp. 478–502, doi:10.1007/978-3-030-75539-3_20.","ieee":"T. Laarhoven and M. Walter, “Dual lattice attacks for closest vector problems (with preprocessing),” in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704, pp. 478–502.","short":"T. Laarhoven, M. Walter, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 478–502.","ama":"Laarhoven T, Walter M. Dual lattice attacks for closest vector problems (with preprocessing). In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer Nature; 2021:478-502. doi:10.1007/978-3-030-75539-3_20","apa":"Laarhoven, T., & Walter, M. (2021). Dual lattice attacks for closest vector problems (with preprocessing). In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 478–502). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_20","chicago":"Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector Problems (with Preprocessing).” In Topics in Cryptology – CT-RSA 2021, 12704:478–502. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_20.","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."},"title":"Dual lattice attacks for closest vector problems (with preprocessing)","author":[{"first_name":"Thijs","full_name":"Laarhoven, Thijs","last_name":"Laarhoven"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783030755386"]},"publication_status":"published","volume":12704,"oa_version":"Preprint","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"}],"month":"05","intvolume":" 12704","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/557"}],"date_updated":"2023-02-23T14:09:54Z","department":[{"_id":"KrPi"}],"_id":"9825","status":"public","type":"conference","conference":{"name":"CT-RSA: Cryptographers’ Track at the RSA Conference","end_date":"2021-05-20","location":"Virtual Event","start_date":"2021-05-17"}},{"_id":"10407","conference":{"name":"TCC: Theory of Cryptography Conference","end_date":"2021-11-11","location":"Raleigh, NC, United States","start_date":"2021-11-08"},"type":"conference","status":"public","date_updated":"2023-08-14T13:07:46Z","department":[{"_id":"KrPi"}],"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"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1224"}],"scopus_import":"1","alternative_title":["LNCS"],"intvolume":" 13043","month":"11","publication_status":"published","publication_identifier":{"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":13043,"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"citation":{"ieee":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 397–428.","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","ama":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:10.1007/978-3-030-90453-1_14","apa":"Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z., & 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. https://doi.org/10.1007/978-3-030-90453-1_14","mla":"Chakraborty, Suvradip, et al. Trojan-Resilience without Cryptography. Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:10.1007/978-3-030-90453-1_14.","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.","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. https://doi.org/10.1007/978-3-030-90453-1_14."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000728364000014"]},"article_processing_charge":"No","author":[{"last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip"},{"first_name":"Stefan","last_name":"Dziembowski","full_name":"Dziembowski, Stefan"},{"last_name":"Gałązka","full_name":"Gałązka, Małgorzata","first_name":"Małgorzata"},{"first_name":"Tomasz","full_name":"Lizurej, Tomasz","last_name":"Lizurej"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo"}],"title":"Trojan-resilience without cryptography","oa":1,"quality_controlled":"1","publisher":"Springer Nature","year":"2021","isi":1,"day":"04","page":"397-428","date_created":"2021-12-05T23:01:42Z","date_published":"2021-11-04T00:00:00Z","doi":"10.1007/978-3-030-90453-1_14"},{"ec_funded":1,"volume":13044,"publication_status":"published","publication_identifier":{"eisbn":["978-3-030-90456-2"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0455-5"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 13044","month":"11","abstract":[{"lang":"eng","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."}],"oa_version":"Preprint","department":[{"_id":"KrPi"}],"date_updated":"2023-08-14T13:19:39Z","conference":{"name":"TCC: Theory of Cryptography","end_date":"2021-11-11","location":"Raleigh, NC, United States","start_date":"2021-11-08"},"type":"conference","status":"public","_id":"10408","page":"222-253","date_created":"2021-12-05T23:01:42Z","doi":"10.1007/978-3-030-90456-2_8","date_published":"2021-11-04T00:00:00Z","year":"2021","isi":1,"publication":"19th International Conference","day":"04","oa":1,"quality_controlled":"1","publisher":"Springer Nature","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).","article_processing_charge":"No","external_id":{"isi":["000728363700008"]},"author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"last_name":"Auerbach","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","last_name":"Baig","full_name":"Baig, Mirza Ahad"},{"first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel"},{"first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"title":"Grafting key trees: Efficient key management for overlapping groups","citation":{"mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:10.1007/978-3-030-90456-2_8.","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.","ieee":"J. F. Alwen et al., “Grafting key trees: Efficient key management for overlapping groups,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: 19th International Conference. Vol 13044. Springer Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8","apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8","chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.","ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","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","grant_number":"665385","name":"International IST Doctoral Program"}]},{"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"10044"}]},"volume":"13043 ","ec_funded":1,"publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"]},"publication_status":"published","language":[{"iso":"eng"}],"alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"month":"11","abstract":[{"lang":"eng","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."}],"oa_version":"Preprint","department":[{"_id":"KrPi"}],"date_updated":"2023-08-17T06:21:38Z","type":"conference","conference":{"end_date":"2021-11-11","location":"Raleigh, NC, United States","start_date":"2021-11-08","name":"TCC: Theory of Cryptography"},"status":"public","_id":"10409","page":"486-517","doi":"10.1007/978-3-030-90453-1_17","date_published":"2021-11-04T00:00:00Z","date_created":"2021-12-05T23:01:43Z","isi":1,"year":"2021","day":"04","publication":"19th International Conference","publisher":"Springer Nature","quality_controlled":"1","oa":1,"acknowledgement":"We are grateful to Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021 and TCC 2021 reviewers for their detailed review and suggestions, which helped improve presentation considerably.","author":[{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","external_id":{"isi":["000728364000017"]},"title":"On treewidth, separators and Yao’s garbling","citation":{"mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517, doi:10.1007/978-3-030-90453-1_17.","apa":"Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In 19th International Conference (Vol. 13043, pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: 19th International Conference. Vol 13043. Springer Nature; 2021:486-517. doi:10.1007/978-3-030-90453-1_17","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517.","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 486–517.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In 19th International Conference, 13043:486–517. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17.","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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}]},{"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"external_id":{"isi":["000927876200012"]},"article_processing_charge":"No","author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip","full_name":"Chakraborty, Suvradip","last_name":"Chakraborty"},{"first_name":"Chaya","full_name":"Ganesh, Chaya","last_name":"Ganesh"},{"first_name":"Mahak","full_name":"Pancholi, Mahak","last_name":"Pancholi"},{"first_name":"Pratik","full_name":"Sarkar, Pratik","last_name":"Sarkar"}],"title":"Reverse firewalls for adaptively secure MPC without setup","citation":{"chicago":"Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar. “Reverse Firewalls for Adaptively Secure MPC without Setup.” In 27th International Conference on the Theory and Application of Cryptology and Information Security, 13091:335–64. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-92075-3_12.","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.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC without Setup.” 27th International Conference on the Theory and Application of Cryptology and Information Security, vol. 13091, Springer Nature, 2021, pp. 335–64, doi:10.1007/978-3-030-92075-3_12.","apa":"Chakraborty, S., Ganesh, C., Pancholi, M., & Sarkar, P. (2021). Reverse firewalls for adaptively secure MPC without setup. In 27th International Conference on the Theory and Application of Cryptology and Information Security (Vol. 13091, pp. 335–364). Virtual, Singapore: Springer Nature. https://doi.org/10.1007/978-3-030-92075-3_12","ama":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively secure MPC without setup. In: 27th International Conference on the Theory and Application of Cryptology and Information Security. Vol 13091. Springer Nature; 2021:335-364. doi:10.1007/978-3-030-92075-3_12","ieee":"S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls for adaptively secure MPC without setup,” in 27th International Conference on the Theory and Application of Cryptology and Information Security, Virtual, Singapore, 2021, vol. 13091, pp. 335–364.","short":"S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2021, pp. 335–364."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"publisher":"Springer Nature","quality_controlled":"1","page":"335-364","date_created":"2022-01-09T23:01:27Z","doi":"10.1007/978-3-030-92075-3_12","date_published":"2021-12-01T00:00:00Z","year":"2021","isi":1,"publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","day":"01","conference":{"location":"Virtual, Singapore","end_date":"2021-12-10","start_date":"2021-12-06","name":"ASIACRYPT: International Conference on Cryptology in Asia"},"type":"conference","status":"public","_id":"10609","department":[{"_id":"KrPi"}],"date_updated":"2023-08-17T06:34:41Z","main_file_link":[{"url":"https://eprint.iacr.org/2021/1262","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 13091","month":"12","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"}],"oa_version":"Preprint","ec_funded":1,"volume":13091,"publication_status":"published","publication_identifier":{"eisbn":["978-3-030-92075-3"],"issn":["0302-9743"],"isbn":["978-3-030-92074-6"],"eissn":["1611-3349"]},"language":[{"iso":"eng"}]},{"department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T13:32:11Z","status":"public","type":"conference","conference":{"name":"CRYPTO: Annual International Cryptology Conference","end_date":"2021-08-20","location":"Virtual","start_date":"2021-08-16"},"_id":"10041","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10035"}]},"volume":12826,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["978-3-030-84245-1"],"issn":["0302-9743"],"isbn":["978-3-030-84244-4"],"eissn":["1611-3349"]},"publication_status":"published","month":"08","place":"Cham","intvolume":" 12826","alternative_title":["LCNS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/945"}],"oa_version":"Preprint","abstract":[{"text":"Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth δ , the loss in security is at most exponential in δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.","lang":"eng"}],"title":"Limits on the Adaptive Security of Yao’s Garbling","author":[{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"full_name":"Wichs, Daniel","last_name":"Wichs","first_name":"Daniel"}],"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In 41st Annual International Cryptology Conference, Part II , 12826:486–515. Cham: Springer Nature, 2021. https://doi.org/10.1007/978-3-030-84245-1_17.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Wichs, D. (2021). Limits on the Adaptive Security of Yao’s Garbling. In 41st Annual International Cryptology Conference, Part II (Vol. 12826, pp. 486–515). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-84245-1_17","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security of Yao’s Garbling. In: 41st Annual International Cryptology Conference, Part II . Vol 12826. Cham: Springer Nature; 2021:486-515. doi:10.1007/978-3-030-84245-1_17","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the Adaptive Security of Yao’s Garbling,” in 41st Annual International Cryptology Conference, Part II , Virtual, 2021, vol. 12826, pp. 486–515.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.","mla":"Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.” 41st Annual International Cryptology Conference, Part II , vol. 12826, Springer Nature, 2021, pp. 486–515, doi:10.1007/978-3-030-84245-1_17."},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"date_published":"2021-08-11T00:00:00Z","doi":"10.1007/978-3-030-84245-1_17","date_created":"2021-09-23T14:06:15Z","page":"486-515","day":"11","publication":"41st Annual International Cryptology Conference, Part II ","year":"2021","publisher":"Springer Nature","quality_controlled":"1","oa":1,"acknowledgement":"We would like to thank the anonymous reviewers of Crypto’21 whose detailed comments helped us considerably improve the presentation of the paper."},{"date_updated":"2023-09-07T13:32:11Z","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"_id":"10049","conference":{"location":"San Francisco, CA, United States","end_date":"2021-05-27","start_date":"2021-05-24","name":"SP: Symposium on Security and Privacy"},"type":"conference","status":"public","publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"related_material":{"record":[{"id":"10035","status":"public","relation":"dissertation_contains"}]},"abstract":[{"text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"month":"08","citation":{"chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: 2021 IEEE Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In 2021 IEEE Symposium on Security and Privacy (pp. 268–284). San Francisco, CA, United States: IEEE. https://doi.org/10.1109/sp40001.2021.00035","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","ieee":"K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in 2021 IEEE Symposium on Security and Privacy , San Francisco, CA, United States, 2021, pp. 268–284."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_processing_charge":"No","author":[{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen"},{"first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"first_name":"Margarita","last_name":"Capretto","full_name":"Capretto, Margarita"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"last_name":"Markov","full_name":"Markov, Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"},{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","project":[{"grant_number":"665385","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"year":"2021","publication":"2021 IEEE Symposium on Security and Privacy ","day":"26","page":"268-284","date_created":"2021-09-27T13:46:27Z","date_published":"2021-08-26T00:00:00Z","doi":"10.1109/sp40001.2021.00035","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.","oa":1,"publisher":"IEEE","quality_controlled":"1"},{"status":"public","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"type":"conference","conference":{"start_date":"2021-11-08","location":"Raleigh, NC, United States","end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference"},"article_number":"2021/926","_id":"10044","title":"On treewidth, separators and Yao's garbling","department":[{"_id":"KrPi"}],"author":[{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"article_processing_charge":"No","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_updated":"2023-09-07T13:32:11Z","citation":{"ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference, 2021/926.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research, 2021.","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in 19th Theory of Cryptography Conference 2021, Raleigh, NC, United States, 2021.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research; 2021.","apa":"Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In 19th Theory of Cryptography Conference 2021. Raleigh, NC, United States: International Association for Cryptologic Research.","mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” 19th Theory of Cryptography Conference 2021, 2021/926, International Association for Cryptologic Research, 2021."},"month":"07","quality_controlled":"1","publisher":"International Association for Cryptologic Research","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"oa":1,"oa_version":"Preprint","acknowledgement":"We would like to thank Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling. ","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 S^O(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(d w log(S)), d 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"}],"date_published":"2021-07-08T00:00:00Z","related_material":{"record":[{"relation":"later_version","id":"10409","status":"public"},{"status":"public","id":"10035","relation":"dissertation_contains"}]},"date_created":"2021-09-24T12:01:34Z","ec_funded":1,"day":"08","language":[{"iso":"eng"}],"publication":"19th Theory of Cryptography Conference 2021","publication_status":"published","year":"2021"},{"supervisor":[{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2023-10-17T09:24:07Z","ddc":["519"],"department":[{"_id":"GradSch"},{"_id":"KrPi"}],"file_date_updated":"2022-03-10T12:15:18Z","_id":"10035","type":"dissertation","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","publication_identifier":{"issn":["2663-337X"]},"publication_status":"published","degree_awarded":"PhD","file":[{"success":1,"checksum":"73a44345c683e81f3e765efbf86fdcc5","file_id":"10082","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"thesis_pdfa.pdf","date_created":"2021-10-04T12:22:33Z","creator":"cchlebak","file_size":2104726,"date_updated":"2021-10-04T12:22:33Z"},{"file_size":9538359,"date_updated":"2022-03-10T12:15:18Z","creator":"cchlebak","file_name":"thesis_final (1).zip","date_created":"2021-10-05T07:04:37Z","content_type":"application/x-zip-compressed","relation":"source_file","access_level":"closed","file_id":"10085","checksum":"7b80df30a0e686c3ef6a56d4e1c59e29"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"10044"},{"relation":"part_of_dissertation","status":"public","id":"10049"},{"status":"public","id":"637","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"10041"},{"relation":"part_of_dissertation","status":"public","id":"6430"},{"relation":"part_of_dissertation","id":"10048","status":"public"}]},"ec_funded":1,"abstract":[{"lang":"eng","text":"Many security definitions come in two flavors: a stronger “adaptive” flavor, where the adversary can arbitrarily make various choices during the course of the attack, and a weaker “selective” flavor where the adversary must commit to some or all of their choices a-priori. For example, in the context of identity-based encryption, selective security requires the adversary to decide on the identity of the attacked party at the very beginning of the game whereas adaptive security allows the attacker to first see the master public key and some secret keys before making this choice. Often, it appears to be much easier to achieve selective security than it is to achieve adaptive security. A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework (published at Crypto ’17 [JKK+17a]) that connects all of these works and allows us to present them in a unified and simplified fashion. Having the framework in place, we show how to achieve adaptive security for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the first adaptive security proofs for continuous group key agreement protocols (published at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that currently used proof techniques cannot lead to significantly better security guarantees for \"graph-building\" games (published at TCC ’21 [KKPW21a]). These games cover generalized selective decryption, as well as the security of prominent constructions for constrained PRFs, continuous group key agreement, and proxy re-encryption. Finally, we revisit the adaptive security of Yao’s garbled circuits and extend the analysis of Jafargholi and Wichs in two directions: While they prove adaptive security only for a modified construction with increased online complexity, we provide the first positive results for the original construction by Yao (published at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi and Wichs are essentially optimal by showing that no black-box reduction can provide a significantly better security bound (published at Crypto ’21 [KKPW21c])."}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"month":"09","citation":{"ieee":"K. Klein, “On the adaptive security of graph-based games,” Institute of Science and Technology Austria, 2021.","short":"K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science and Technology Austria, 2021.","apa":"Klein, K. (2021). On the adaptive security of graph-based games. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:10035","ama":"Klein K. On the adaptive security of graph-based games. 2021. doi:10.15479/at:ista:10035","mla":"Klein, Karen. On the Adaptive Security of Graph-Based Games. Institute of Science and Technology Austria, 2021, doi:10.15479/at:ista:10035.","ista":"Klein K. 2021. On the adaptive security of graph-based games. Institute of Science and Technology Austria.","chicago":"Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10035."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen"}],"article_processing_charge":"No","title":"On the adaptive security of graph-based games","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"has_accepted_license":"1","year":"2021","day":"23","page":"276","date_published":"2021-09-23T00:00:00Z","doi":"10.15479/at:ista:10035","date_created":"2021-09-23T07:31:44Z","acknowledgement":"I want to acknowledge the funding by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).\r\n","publisher":"Institute of Science and Technology Austria","oa":1},{"citation":{"chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th International Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:10.1007/978-3-030-90453-1_19.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The cost of adaptivity in security games on graphs. In 19th International Conference (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th International Conference. Vol 13043. Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 550–581.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"}],"external_id":{"isi":["000728364000019"]},"article_processing_charge":"No","title":"The cost of adaptivity in security games on graphs","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"isi":1,"year":"2021","day":"04","publication":"19th International Conference","page":"550-581","date_published":"2021-11-04T00:00:00Z","doi":"10.1007/978-3-030-90453-1_19","date_created":"2021-12-05T23:01:43Z","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).","publisher":"Springer Nature","quality_controlled":"1","oa":1,"date_updated":"2023-10-17T09:24:07Z","department":[{"_id":"KrPi"}],"_id":"10410","type":"conference","conference":{"end_date":"2021-11-11","location":"Raleigh, NC, United States","start_date":"2021-11-08","name":"TCC: Theory of Cryptography"},"status":"public","publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"]},"publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"10048","status":"public"}]},"volume":13043,"ec_funded":1,"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"}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"https://ia.cr/2021/059","open_access":"1"}],"month":"11","intvolume":" 13043"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-10-17T09:24:08Z","citation":{"chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research, 2021.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in 19th Theory of Cryptography Conference 2021, Raleigh, NC, United States, 2021.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research; 2021.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The cost of adaptivity in security games on graphs. In 19th Theory of Cryptography Conference 2021. Raleigh, NC, United States: International Association for Cryptologic Research."},"department":[{"_id":"KrPi"}],"title":"The cost of adaptivity in security games on graphs","article_processing_charge":"No","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"_id":"10048","status":"public","conference":{"name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08","location":"Raleigh, NC, United States","end_date":"2021-11-11"},"type":"conference","publication":"19th Theory of Cryptography Conference 2021","language":[{"iso":"eng"}],"day":"08","publication_status":"published","year":"2021","date_created":"2021-09-27T12:52:05Z","date_published":"2021-07-08T00:00:00Z","related_material":{"record":[{"id":"10410","status":"public","relation":"later_version"},{"id":"10035","status":"public","relation":"dissertation_contains"}]},"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower\r\nbounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and\r\nbroadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.\r\n"}],"month":"07","oa":1,"main_file_link":[{"url":"https://ia.cr/2021/059","open_access":"1"}],"quality_controlled":"1","publisher":"International Association for Cryptologic Research"},{"type":"conference","conference":{"name":"2021 IFIP Networking Conference (IFIP Networking)","start_date":"2021-06-21","end_date":"2021-06-24","location":"Espoo and Helsinki, Finland"},"status":"public","_id":"9969","department":[{"_id":"KrPi"}],"date_updated":"2023-11-30T10:54:50Z","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2104.04293"}],"month":"06","abstract":[{"lang":"eng","text":"Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths."}],"oa_version":"Submitted Version","related_material":{"record":[{"status":"public","id":"14506","relation":"dissertation_contains"}]},"ec_funded":1,"publication_identifier":{"isbn":["978-1-6654-4501-6"],"eissn":["1861-2288"],"eisbn":["978-3-9031-7639-3"]},"publication_status":"published","language":[{"iso":"eng"}],"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"author":[{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Iosif","full_name":"Salem, Iosif","last_name":"Salem"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"}],"article_processing_charge":"No","external_id":{"arxiv":["2104.04293"],"isi":["000853016800008"]},"title":"LightPIR: Privacy-preserving route discovery for payment channel networks","citation":{"mla":"Pietrzak, Krzysztof Z., et al. LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks. IEEE, 2021, doi:10.23919/IFIPNetworking52078.2021.9472205.","apa":"Pietrzak, K. Z., Salem, I., Schmid, S., & 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. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205","ama":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route discovery for payment channel networks. In: IEEE; 2021. doi:10.23919/IFIPNetworking52078.2021.9472205","short":"K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.","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. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205.","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)."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","quality_controlled":"1","publisher":"IEEE","oa":1,"doi":"10.23919/IFIPNetworking52078.2021.9472205","date_published":"2021-06-21T00:00:00Z","date_created":"2021-08-29T22:01:16Z","isi":1,"year":"2021","day":"21"},{"ec_funded":1,"volume":12171,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9783030568795"],"eissn":["16113349"],"issn":["03029743"]},"intvolume":" 12171","month":"08","main_file_link":[{"url":"https://eprint.iacr.org/2019/1317","open_access":"1"}],"scopus_import":"1","alternative_title":["LNCS"],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to “sanitize” the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a “functionality-preserving way” (i.e. informally speaking, the functionality of the protocol remains unchanged under this attacks). In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question.\r\nIn this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary number n of the parties, and not just for 2). Secondly, it is secure in much stronger corruption settings, namely in the active corruption model. More precisely: we consider an adversary that can fully corrupt up to 𝑛−1 parties, while the remaining parties are corrupt in a functionality-preserving way.\r\nOur core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001)."}],"department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:18:08Z","status":"public","conference":{"name":"CRYPTO: Annual International Cryptology Conference","start_date":"2020-08-17","location":"Santa Barbara, CA, United States","end_date":"2020-08-21"},"type":"conference","_id":"8322","date_created":"2020-08-30T22:01:12Z","doi":"10.1007/978-3-030-56880-1_26","date_published":"2020-08-10T00:00:00Z","page":"732-762","publication":"Advances in Cryptology – CRYPTO 2020","day":"10","year":"2020","oa":1,"publisher":"Springer Nature","quality_controlled":"1","acknowledgement":"We would like to thank the anonymous reviewers for their helpful comments and suggestions. The work was initiated while the first author was in IIT Madras, India. Part of this work was done while the author was visiting the University of Warsaw. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT) and from the Foundation for Polish Science under grant TEAM/2016-1/4 founded within the UE 2014–2020 Smart Growth Operational Program. The last author was supported by the Independent Research Fund Denmark project BETHE and the Concordium Blockchain Research Center, Aarhus University, Denmark.","title":"Reverse firewalls for actively secure MPCs","article_processing_charge":"No","author":[{"first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","full_name":"Chakraborty, Suvradip","last_name":"Chakraborty"},{"first_name":"Stefan","full_name":"Dziembowski, Stefan","last_name":"Dziembowski"},{"full_name":"Nielsen, Jesper Buus","last_name":"Nielsen","first_name":"Jesper Buus"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.” In Advances in Cryptology – CRYPTO 2020, 12171:732–62. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-56880-1_26.","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.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.” Advances in Cryptology – CRYPTO 2020, vol. 12171, Springer Nature, 2020, pp. 732–62, doi:10.1007/978-3-030-56880-1_26.","ama":"Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs. In: Advances in Cryptology – CRYPTO 2020. Vol 12171. Springer Nature; 2020:732-762. doi:10.1007/978-3-030-56880-1_26","apa":"Chakraborty, S., Dziembowski, S., & Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs. In Advances in Cryptology – CRYPTO 2020 (Vol. 12171, pp. 732–762). Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-56880-1_26","ieee":"S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,” in Advances in Cryptology – CRYPTO 2020, Santa Barbara, CA, United States, 2020, vol. 12171, pp. 732–762.","short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 732–762."},"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}]},{"_id":"8339","status":"public","conference":{"name":"PKC: Public-Key Cryptography","start_date":"2020-05-04","location":"Edinburgh, United Kingdom","end_date":"2020-05-07"},"type":"conference","date_updated":"2023-02-23T13:31:06Z","department":[{"_id":"KrPi"}],"oa_version":"Preprint","abstract":[{"text":"Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.\r\nIn this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems.","lang":"eng"}],"intvolume":" 12110","month":"05","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/337"}],"alternative_title":["LNCS"],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783030453732"]},"ec_funded":1,"volume":12110,"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian and subgaussian analysis for lattice cryptography,” in 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Edinburgh, United Kingdom, 2020, vol. 12110, pp. 623–651.","short":"N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature, 2020, pp. 623–651.","ama":"Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In: 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. Vol 12110. Springer Nature; 2020:623-651. doi:10.1007/978-3-030-45374-9_21","apa":"Genise, N., Micciancio, D., Peikert, C., & Walter, M. (2020). Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography (Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_21","mla":"Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, vol. 12110, Springer Nature, 2020, pp. 623–51, doi:10.1007/978-3-030-45374-9_21.","ista":"Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 12110, 623–651.","chicago":"Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” In 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, 12110:623–51. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_21."},"title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","article_processing_charge":"No","author":[{"full_name":"Genise, Nicholas","last_name":"Genise","first_name":"Nicholas"},{"last_name":"Micciancio","full_name":"Micciancio, Daniele","first_name":"Daniele"},{"full_name":"Peikert, Chris","last_name":"Peikert","first_name":"Chris"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"}],"oa":1,"quality_controlled":"1","publisher":"Springer Nature","publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","day":"15","year":"2020","date_created":"2020-09-06T22:01:13Z","date_published":"2020-05-15T00:00:00Z","doi":"10.1007/978-3-030-45374-9_21","page":"623-651"},{"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"citation":{"chicago":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” In Progress in Cryptology, 12578:3–15. LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-65277-7_1.","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.","mla":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” Progress in Cryptology, vol. 12578, Springer Nature, 2020, pp. 3–15, doi:10.1007/978-3-030-65277-7_1.","short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","ieee":"K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks in private contact tracing,” in Progress in Cryptology, Bangalore, India, 2020, vol. 12578, pp. 3–15.","ama":"Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in private contact tracing. In: Progress in Cryptology. Vol 12578. LNCS. Springer Nature; 2020:3-15. doi:10.1007/978-3-030-65277-7_1","apa":"Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay attacks in private contact tracing. In Progress in Cryptology (Vol. 12578, pp. 3–15). Bangalore, India: Springer Nature. https://doi.org/10.1007/978-3-030-65277-7_1"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"isi":["000927592800001"]},"author":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing","oa":1,"quality_controlled":"1","publisher":"Springer Nature","year":"2020","isi":1,"publication":"Progress in Cryptology","day":"08","page":"3-15","date_created":"2021-01-03T23:01:23Z","doi":"10.1007/978-3-030-65277-7_1","date_published":"2020-12-08T00:00:00Z","_id":"8987","series_title":"LNCS","conference":{"location":"Bangalore, India","end_date":"2020-12-16","start_date":"2020-12-13","name":"INDOCRYPT: International Conference on Cryptology in India"},"type":"conference","status":"public","date_updated":"2023-08-24T11:08:58Z","department":[{"_id":"KrPi"}],"abstract":[{"lang":"eng","text":"Currently several projects aim at designing and implementing protocols for privacy preserving automated contact tracing to help fight the current pandemic. Those proposal are quite similar, and in their most basic form basically propose an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, they upload either the beacons they did broadcast (which is the case in decentralized proposals as DP-3T, east and west coast PACT or Covid watch) or received (as in Popp-PT or ROBERT) during the last two weeks or so.\r\n\r\nVaudenay [eprint 2020/399] observes that this basic scheme (he considers the DP-3T proposal) succumbs to relay and even replay attacks, and proposes more complex interactive schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons. The countermeasures that have been suggested so far are either not practical or give up on key privacy aspects. We propose a simple non-interactive variant of the basic protocol that\r\n(security) Provably prevents replay and (if location data is available) relay attacks.\r\n(privacy) The data of all parties (even jointly) reveals no information on the location or time where encounters happened.\r\n(efficiency) The broadcasted message can fit into 128 bits and uses only basic crypto (commitments and secret key authentication).\r\n\r\nTowards this end we introduce the concept of “delayed authentication”, which basically is a message authentication code where verification can be done in two steps, where the first doesn’t require the key, and the second doesn’t require the message."}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/418"}],"scopus_import":"1","intvolume":" 12578","month":"12","publication_status":"published","publication_identifier":{"issn":["03029743"],"isbn":["9783030652760"],"eissn":["16113349"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":12578},{"department":[{"_id":"KrPi"}],"date_updated":"2023-09-05T15:06:40Z","conference":{"end_date":"2020-05-15","start_date":"2020-05-11","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"type":"conference","status":"public","_id":"7966","ec_funded":1,"volume":12107,"publication_status":"published","publication_identifier":{"isbn":["9783030457266","9783030457273"],"eissn":["1611-3349"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/364"}],"alternative_title":["LNCS"],"intvolume":" 12107","month":"05","abstract":[{"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.","lang":"eng"}],"oa_version":"Submitted Version","external_id":{"isi":["000828688000016"]},"article_processing_charge":"No","author":[{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"first_name":"Federico","full_name":"Giacon, Federico","last_name":"Giacon"},{"last_name":"Kiltz","full_name":"Kiltz, Eike","first_name":"Eike"}],"title":"Everybody’s a target: Scalability in public-key encryption","citation":{"mla":"Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key Encryption.” Advances in Cryptology – EUROCRYPT 2020, vol. 12107, Springer Nature, 2020, pp. 475–506, doi:10.1007/978-3-030-45727-3_16.","short":"B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT 2020, Springer Nature, 2020, pp. 475–506.","ieee":"B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability in public-key encryption,” in Advances in Cryptology – EUROCRYPT 2020, 2020, vol. 12107, pp. 475–506.","apa":"Auerbach, B., Giacon, F., & Kiltz, E. (2020). Everybody’s a target: Scalability in public-key encryption. In Advances in Cryptology – EUROCRYPT 2020 (Vol. 12107, pp. 475–506). Springer Nature. https://doi.org/10.1007/978-3-030-45727-3_16","ama":"Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key encryption. In: Advances in Cryptology – EUROCRYPT 2020. Vol 12107. Springer Nature; 2020:475-506. doi:10.1007/978-3-030-45727-3_16","chicago":"Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target: Scalability in Public-Key Encryption.” In Advances in Cryptology – EUROCRYPT 2020, 12107:475–506. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45727-3_16.","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."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"page":"475-506","date_created":"2020-06-15T07:13:37Z","doi":"10.1007/978-3-030-45727-3_16","date_published":"2020-05-01T00:00:00Z","year":"2020","isi":1,"publication":"Advances in Cryptology – EUROCRYPT 2020","day":"01","oa":1,"quality_controlled":"1","publisher":"Springer Nature"},{"oa":1,"publisher":"Institute of Science and Technology Austria","page":"126","date_created":"2020-05-26T14:08:55Z","doi":"10.15479/AT:ISTA:7896","date_published":"2020-05-25T00:00:00Z","year":"2020","has_accepted_license":"1","day":"25","project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","author":[{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"}],"title":"On the average-case hardness of total search problems","citation":{"chicago":"Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","mla":"Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","apa":"Kamath Hosdurg, C. (2020). On the average-case hardness of total search problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896","ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:10.15479/AT:ISTA:7896"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","alternative_title":["ISTA Thesis"],"month":"05","abstract":[{"lang":"eng","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. "}],"oa_version":"Published Version","ec_funded":1,"related_material":{"record":[{"status":"public","id":"6677","relation":"part_of_dissertation"}]},"publication_status":"published","degree_awarded":"PhD","publication_identifier":{"issn":["2663-337X"]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"b39e2e1c376f5819b823fb7077491c64","file_id":"7897","date_updated":"2020-07-14T12:48:04Z","file_size":1622742,"creator":"dernst","date_created":"2020-05-26T14:08:13Z","file_name":"2020_Thesis_Kamath.pdf"},{"file_id":"7898","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","content_type":"application/x-zip-compressed","access_level":"closed","relation":"source_file","date_created":"2020-05-26T14:08:23Z","file_name":"Thesis_Kamath.zip","date_updated":"2020-07-14T12:48:04Z","file_size":15301529,"creator":"dernst"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"dissertation","status":"public","_id":"7896","file_date_updated":"2020-07-14T12:48:04Z","department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T13:15:55Z","supervisor":[{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"ddc":["000"]},{"page":"75-111","date_created":"2019-01-27T22:59:10Z","doi":"10.3233/JCS-181131","date_published":"2019-01-01T00:00:00Z","year":"2019","publication":"Journal of Computer Security","day":"1","oa":1,"publisher":"IOS Press","quality_controlled":"1","article_processing_charge":"No","author":[{"first_name":"Gregory","full_name":"Demay, Gregory","last_name":"Demay"},{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Gazi","full_name":"Gazi, Peter"},{"first_name":"Ueli","last_name":"Maurer","full_name":"Maurer, Ueli"},{"first_name":"Bjorn","full_name":"Tackmann, Bjorn","last_name":"Tackmann"}],"title":"Per-session security: Password-based cryptography revisited","citation":{"mla":"Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography Revisited.” Journal of Computer Security, vol. 27, no. 1, IOS Press, 2019, pp. 75–111, doi:10.3233/JCS-181131.","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27 (2019) 75–111.","ieee":"G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based cryptography revisited,” Journal of Computer Security, vol. 27, no. 1. IOS Press, pp. 75–111, 2019.","ama":"Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based cryptography revisited. Journal of Computer Security. 2019;27(1):75-111. doi:10.3233/JCS-181131","apa":"Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2019). Per-session security: Password-based cryptography revisited. Journal of Computer Security. IOS Press. https://doi.org/10.3233/JCS-181131","chicago":"Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session Security: Password-Based Cryptography Revisited.” Journal of Computer Security. IOS Press, 2019. https://doi.org/10.3233/JCS-181131.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"ec_funded":1,"volume":27,"issue":"1","publication_status":"published","publication_identifier":{"issn":["0926227X"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2016/166","open_access":"1"}],"scopus_import":"1","intvolume":" 27","month":"01","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"}],"oa_version":"Preprint","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:05:08Z","type":"journal_article","article_type":"original","status":"public","_id":"5887"},{"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"start_date":"2019-01-10","location":"San Diego, CA, United States","end_date":"2019-01-12","name":"ITCS 2019: Innovations in Theoretical Computer Science"},"type":"conference","status":"public","_id":"6528","file_date_updated":"2020-07-14T12:47:33Z","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:07:53Z","ddc":["000"],"main_file_link":[{"url":"https://eprint.iacr.org/2018/627","open_access":"1"}],"scopus_import":1,"alternative_title":["LIPIcs"],"intvolume":" 124","month":"01","abstract":[{"lang":"eng","text":"We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism."}],"oa_version":"Published Version","ec_funded":1,"volume":124,"publication_status":"published","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-095-8"]},"language":[{"iso":"eng"}],"file":[{"date_created":"2019-06-06T14:22:04Z","file_name":"2019_LIPIcs_Pietrzak.pdf","creator":"dernst","date_updated":"2020-07-14T12:47:33Z","file_size":558770,"file_id":"6529","checksum":"f0ae1bb161431d9db3dea5ace082bfb5","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_number":"60","article_processing_charge":"No","author":[{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"title":"Simple verifiable delay functions","citation":{"ista":"Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.","chicago":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60.","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ieee":"K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124.","ama":"Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60","apa":"Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60","mla":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","date_created":"2019-06-06T14:12:36Z","date_published":"2019-01-10T00:00:00Z","doi":"10.4230/LIPICS.ITCS.2019.60","year":"2019","has_accepted_license":"1","publication":"10th Innovations in Theoretical Computer Science Conference","day":"10"},{"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019 (Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9","ieee":"M. Walter, “Sampling the integers with low relative error,” in Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180."},"editor":[{"full_name":"Buchmann, J","last_name":"Buchmann","first_name":"J"},{"last_name":"Nitaj","full_name":"Nitaj, A","first_name":"A"},{"full_name":"Rachidi, T","last_name":"Rachidi","first_name":"T"}],"title":"Sampling the integers with low relative error","author":[{"last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael"}],"article_processing_charge":"No","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"day":"29","publication":"Progress in Cryptology – AFRICACRYPT 2019","year":"2019","doi":"10.1007/978-3-030-23696-0_9","date_published":"2019-06-29T00:00:00Z","date_created":"2019-07-29T12:25:31Z","page":"157-180","quality_controlled":"1","publisher":"Springer Nature","oa":1,"date_updated":"2023-02-23T12:50:15Z","department":[{"_id":"KrPi"}],"_id":"6726","series_title":"LNCS","status":"public","type":"book_chapter","conference":{"name":"AFRICACRYPT: International Conference on Cryptology in Africa","end_date":"2019-07-11","location":"Rabat, Morocco","start_date":"2019-07-09"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-0302-3695-3"],"issn":["0302-9743","1611-3349"],"eisbn":["978-3-0302-3696-0"]},"publication_status":"published","volume":11627,"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so."}],"place":"Cham","month":"06","intvolume":" 11627","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/068"}]},{"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9781538692912"]},"oa_version":"Preprint","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|X2019 IEEE International Symposium on Information Theory. IEEE, 2019. https://doi.org/10.1109/isit.2019.8849240.","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.” 2019 IEEE International Symposium on Information Theory, 8849240, IEEE, 2019, doi:10.1109/isit.2019.8849240.","apa":"Skórski, M. (2019). Strong chain rules for min-entropy under few bits spoiled. In 2019 IEEE International Symposium on Information Theory. Paris, France: IEEE. https://doi.org/10.1109/isit.2019.8849240","ama":"Skórski M. Strong chain rules for min-entropy under few bits spoiled. In: 2019 IEEE International Symposium on Information Theory. IEEE; 2019. doi:10.1109/isit.2019.8849240","short":"M. Skórski, in:, 2019 IEEE International Symposium on Information Theory, IEEE, 2019.","ieee":"M. Skórski, “Strong chain rules for min-entropy under few bits spoiled,” in 2019 IEEE International Symposium on Information Theory, Paris, France, 2019."},"title":"Strong chain rules for min-entropy under few bits spoiled","external_id":{"isi":["000489100301043"],"arxiv":["1702.08476"]},"article_processing_charge":"No","author":[{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej","last_name":"Skórski","full_name":"Skórski, Maciej"}],"article_number":"8849240"},{"date_created":"2020-01-30T09:26:14Z","doi":"10.1007/978-3-030-17656-3_10","date_published":"2019-04-24T00:00:00Z","page":"277-291","publication":"Advances in Cryptology – EUROCRYPT 2019","day":"24","year":"2019","isi":1,"oa":1,"publisher":"Springer International Publishing","quality_controlled":"1","title":"Reversible proofs of sequential work","article_processing_charge":"No","external_id":{"isi":["000483516200010"]},"author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","first_name":"Hamza M","last_name":"Abusalah","full_name":"Abusalah, Hamza M"},{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” Advances in Cryptology – EUROCRYPT 2019, vol. 11477, Springer International Publishing, 2019, pp. 277–91, doi:10.1007/978-3-030-17656-3_10.","ieee":"H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “Reversible proofs of sequential work,” in Advances in Cryptology – EUROCRYPT 2019, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.","short":"H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019, pp. 277–291.","apa":"Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2019). Reversible proofs of sequential work. In Advances in Cryptology – EUROCRYPT 2019 (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International Publishing. https://doi.org/10.1007/978-3-030-17656-3_10","ama":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible proofs of sequential work. In: Advances in Cryptology – EUROCRYPT 2019. Vol 11477. Springer International Publishing; 2019:277-291. doi:10.1007/978-3-030-17656-3_10","chicago":"Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “Reversible Proofs of Sequential Work.” In Advances in Cryptology – EUROCRYPT 2019, 11477:277–91. Springer International Publishing, 2019. https://doi.org/10.1007/978-3-030-17656-3_10.","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."},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"ec_funded":1,"volume":11477,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030176556","9783030176563"],"eissn":["1611-3349"]},"intvolume":" 11477","month":"04","main_file_link":[{"url":"https://eprint.iacr.org/2019/252","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","oa_version":"Submitted Version","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"}],"department":[{"_id":"KrPi"}],"date_updated":"2023-09-06T15:26:06Z","status":"public","conference":{"start_date":"2019-05-19","location":"Darmstadt, Germany","end_date":"2019-05-23","name":"International Conference on the Theory and Applications of Cryptographic Techniques"},"type":"conference","_id":"7411"},{"_id":"6677","conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","location":"Phoenix, AZ, United States","start_date":"2019-06-23"},"type":"conference","status":"public","date_updated":"2023-09-07T13:15:55Z","department":[{"_id":"KrPi"}],"abstract":[{"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).","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"https://eprint.iacr.org/2019/549","open_access":"1"}],"scopus_import":"1","month":"06","publication_status":"published","publication_identifier":{"isbn":["9781450367059"]},"language":[{"iso":"eng"}],"ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"7896","status":"public"}]},"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"citation":{"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 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.","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: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400","apa":"Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316400","mla":"Choudhuri, Arka Rai, et al. “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, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.","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.","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 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"isi":["000523199100100"]},"author":[{"first_name":"Arka Rai","full_name":"Choudhuri, Arka Rai","last_name":"Choudhuri"},{"last_name":"Hubáček","full_name":"Hubáček, Pavel","first_name":"Pavel"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Alon","last_name":"Rosen","full_name":"Rosen, Alon"},{"full_name":"Rothblum, Guy N.","last_name":"Rothblum","first_name":"Guy N."}],"title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","oa":1,"quality_controlled":"1","publisher":"ACM Press","year":"2019","isi":1,"publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019","day":"01","page":"1103-1114","date_created":"2019-07-24T09:20:53Z","doi":"10.1145/3313276.3316400","date_published":"2019-06-01T00:00:00Z"},{"alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/426"}],"month":"04","intvolume":" 11443","abstract":[{"text":"A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).","lang":"eng"}],"oa_version":"Preprint","related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"}]},"volume":11443,"ec_funded":1,"publication_identifier":{"eissn":["16113349"],"isbn":["9783030172589"],"issn":["03029743"]},"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","conference":{"location":"Beijing, China","end_date":"2019-04-17","start_date":"2019-04-14","name":"PKC: Public-Key Cryptograhy"},"status":"public","_id":"6430","department":[{"_id":"KrPi"}],"date_updated":"2023-09-08T11:33:20Z","quality_controlled":"1","publisher":"Springer Nature","oa":1,"page":"317-346","date_published":"2019-04-06T00:00:00Z","doi":"10.1007/978-3-030-17259-6_11","date_created":"2019-05-13T08:13:46Z","year":"2019","day":"06","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"author":[{"last_name":"Fuchsbauer","full_name":"Fuchsbauer, Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","title":"Adaptively secure proxy re-encryption","citation":{"ista":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.","chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-17259-6_11.","ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11","apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019). Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11","ieee":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing, China, 2019, vol. 11443, pp. 317–346.","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346.","mla":"Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"issue":"3","volume":2018,"publication_identifier":{"eissn":["2569-2925"]},"publication_status":"published","file":[{"creator":"cchlebak","file_size":955755,"date_updated":"2021-11-15T10:27:29Z","file_name":"2018_IACR_Allini.pdf","date_created":"2021-11-15T10:27:29Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"file_id":"10289","checksum":"b816b848f046c48a8357700d9305dce5"}],"language":[{"iso":"eng"}],"scopus_import":"1","month":"01","intvolume":" 2018","abstract":[{"lang":"eng","text":"In this paper, we evaluate clock signals generated in ring oscillators and self-timed rings and the way their jitter can be transformed into random numbers. We show that counting the periods of the jittery clock signal produces random numbers of significantly better quality than the methods in which the jittery signal is simply sampled (the case in almost all current methods). Moreover, we use the counter values to characterize and continuously monitor the source of randomness. However, instead of using the widely used statistical variance, we propose to use Allan variance to do so. There are two main advantages: Allan variance is insensitive to low frequency noises such as flicker noise that are known to be autocorrelated and significantly less circuitry is required for its computation than that used to compute commonly used variance. We also show that it is essential to use a differential principle of randomness extraction from the jitter based on the use of two identical oscillators to avoid autocorrelations originating from external and internal global jitter sources and that this fact is valid for both kinds of rings. Last but not least, we propose a method of statistical testing based on high order Markov model to show the reduced dependencies when the proposed randomness extraction is applied."}],"oa_version":"Published Version","department":[{"_id":"KrPi"}],"file_date_updated":"2021-11-15T10:27:29Z","date_updated":"2021-11-15T10:48:49Z","ddc":["000"],"article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","_id":"10286","page":"214-242","doi":"10.13154/tches.v2018.i3.214-242","date_published":"2018-01-01T00:00:00Z","date_created":"2021-11-14T23:01:25Z","has_accepted_license":"1","year":"2018","day":"01","publication":"IACR Transactions on Cryptographic Hardware and Embedded Systems","quality_controlled":"1","publisher":"International Association for Cryptologic Research","oa":1,"author":[{"last_name":"Allini","full_name":"Allini, Elie Noumon","first_name":"Elie Noumon"},{"full_name":"Skórski, Maciej","last_name":"Skórski","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej"},{"last_name":"Petura","full_name":"Petura, Oto","first_name":"Oto"},{"full_name":"Bernard, Florent","last_name":"Bernard","first_name":"Florent"},{"first_name":"Marek","last_name":"Laban","full_name":"Laban, Marek"},{"full_name":"Fischer, Viktor","last_name":"Fischer","first_name":"Viktor"}],"article_processing_charge":"No","title":"Evaluation and monitoring of free running oscillators serving as source of randomness","citation":{"chicago":"Allini, Elie Noumon, Maciej Skórski, Oto Petura, Florent Bernard, Marek Laban, and Viktor Fischer. “Evaluation and Monitoring of Free Running Oscillators Serving as Source of Randomness.” IACR Transactions on Cryptographic Hardware and Embedded Systems. International Association for Cryptologic Research, 2018. https://doi.org/10.13154/tches.v2018.i3.214-242.","ista":"Allini EN, Skórski M, Petura O, Bernard F, Laban M, Fischer V. 2018. Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018(3), 214–242.","mla":"Allini, Elie Noumon, et al. “Evaluation and Monitoring of Free Running Oscillators Serving as Source of Randomness.” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 3, International Association for Cryptologic Research, 2018, pp. 214–42, doi:10.13154/tches.v2018.i3.214-242.","short":"E.N. Allini, M. Skórski, O. Petura, F. Bernard, M. Laban, V. Fischer, IACR Transactions on Cryptographic Hardware and Embedded Systems 2018 (2018) 214–242.","ieee":"E. N. Allini, M. Skórski, O. Petura, F. Bernard, M. Laban, and V. Fischer, “Evaluation and monitoring of free running oscillators serving as source of randomness,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 3. International Association for Cryptologic Research, pp. 214–242, 2018.","ama":"Allini EN, Skórski M, Petura O, Bernard F, Laban M, Fischer V. Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018;2018(3):214-242. doi:10.13154/tches.v2018.i3.214-242","apa":"Allini, E. N., Skórski, M., Petura, O., Bernard, F., Laban, M., & Fischer, V. (2018). Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. International Association for Cryptologic Research. https://doi.org/10.13154/tches.v2018.i3.214-242"},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9"},{"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","page":"59:1-59:25","date_created":"2020-01-30T09:16:05Z","date_published":"2018-12-31T00:00:00Z","doi":"10.4230/LIPICS.ITCS.2019.59","year":"2018","has_accepted_license":"1","publication":"10th Innovations in Theoretical Computer Science Conference (ITCS 2019)","day":"31","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"title":"Proofs of catalytic space","citation":{"ieee":"K. Z. Pietrzak, “Proofs of catalytic space,” in 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), San Diego, CA, United States, 2018, vol. 124, p. 59:1-59:25.","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25.","apa":"Pietrzak, K. Z. (2018). Proofs of catalytic space. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (Vol. 124, p. 59:1-59:25). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.59","ama":"Pietrzak KZ. Proofs of catalytic space. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:59:1-59:25. doi:10.4230/LIPICS.ITCS.2019.59","mla":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), vol. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:10.4230/LIPICS.ITCS.2019.59.","ista":"Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). ITCS: Innovations in theoretical Computer Science Conference, LIPIcs, vol. 124, 59:1-59:25.","chicago":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 124:59:1-59:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ITCS.2019.59."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/194"}],"scopus_import":1,"alternative_title":["LIPIcs"],"intvolume":" 124","month":"12","abstract":[{"text":"Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he \"wastes\" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper. ","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"volume":124,"publication_status":"published","publication_identifier":{"isbn":["978-3-95977-095-8"],"issn":["1868-8969"]},"language":[{"iso":"eng"}],"file":[{"file_id":"7443","checksum":"5cebb7f7849a3beda898f697d755dd96","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2018_LIPIcs_Pietrzak.pdf","date_created":"2020-02-04T08:17:52Z","creator":"dernst","file_size":822884,"date_updated":"2020-07-14T12:47:57Z"}],"conference":{"start_date":"2019-01-10","end_date":"2019-01-12","location":"San Diego, CA, United States","name":"ITCS: Innovations in theoretical Computer Science Conference"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","status":"public","_id":"7407","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:47:57Z","date_updated":"2021-01-12T08:13:26Z","ddc":["000"]},{"oa_version":"Published Version","abstract":[{"text":"A proof system is a protocol between a prover and a verifier over a common input in which an honest prover convinces the verifier of the validity of true statements. Motivated by the success of decentralized cryptocurrencies, exemplified by Bitcoin, the focus of this thesis will be on proof systems which found applications in some sustainable alternatives to Bitcoin, such as the Spacemint and Chia cryptocurrencies. In particular, we focus on proofs of space and proofs of sequential work.\r\nProofs of space (PoSpace) were suggested as more ecological, economical, and egalitarian alternative to the energy-wasteful proof-of-work mining of Bitcoin. However, the state-of-the-art constructions of PoSpace are based on sophisticated graph pebbling lower bounds, and are therefore complex. Moreover, when these PoSpace are used in cryptocurrencies like Spacemint, miners can only start mining after ensuring that a commitment to their space is already added in a special transaction to the blockchain. Proofs of sequential work (PoSW) are proof systems in which a prover, upon receiving a statement x and a time parameter T, computes a proof which convinces the verifier that T time units had passed since x was received. Whereas Spacemint assumes synchrony to retain some interesting Bitcoin dynamics, Chia requires PoSW with unique proofs, i.e., PoSW in which it is hard to come up with more than one accepting proof for any true statement. In this thesis we construct simple and practically-efficient PoSpace and PoSW. When using our PoSpace in cryptocurrencies, miners can start mining on the fly, like in Bitcoin, and unlike current constructions of PoSW, which either achieve efficient verification of sequential work, or faster-than-recomputing verification of correctness of proofs, but not both at the same time, ours achieve the best of these two worlds.","lang":"eng"}],"month":"09","alternative_title":["ISTA Thesis"],"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:48:11Z","file_size":876241,"creator":"dernst","date_created":"2019-04-09T06:43:41Z","file_name":"2018_Thesis_Abusalah.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"6245","checksum":"c4b5f7d111755d1396787f41886fc674"},{"content_type":"application/x-gzip","access_level":"closed","relation":"source_file","file_id":"6246","checksum":"0f382ac56b471c48fd907d63eb87dafe","date_updated":"2020-07-14T12:48:11Z","file_size":2029190,"creator":"dernst","date_created":"2019-04-09T06:43:41Z","file_name":"2018_Thesis_Abusalah_source.tar.gz"}],"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"issn":["2663-337X"]},"ec_funded":1,"related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"1229"},{"relation":"part_of_dissertation","id":"1235","status":"public"},{"relation":"part_of_dissertation","id":"1236","status":"public"},{"relation":"part_of_dissertation","id":"559","status":"public"}]},"_id":"83","pubrep_id":"1046","status":"public","type":"dissertation","ddc":["004"],"date_updated":"2023-09-07T12:30:23Z","supervisor":[{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"file_date_updated":"2020-07-14T12:48:11Z","department":[{"_id":"KrPi"}],"oa":1,"publisher":"Institute of Science and Technology Austria","day":"05","year":"2018","has_accepted_license":"1","date_created":"2018-12-11T11:44:32Z","date_published":"2018-09-05T00:00:00Z","doi":"10.15479/AT:ISTA:TH_1046","page":"59","project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ama":"Abusalah HM. Proof systems for sustainable decentralized cryptocurrencies. 2018. doi:10.15479/AT:ISTA:TH_1046","apa":"Abusalah, H. M. (2018). Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:TH_1046","short":"H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies, Institute of Science and Technology Austria, 2018.","ieee":"H. M. Abusalah, “Proof systems for sustainable decentralized cryptocurrencies,” Institute of Science and Technology Austria, 2018.","mla":"Abusalah, Hamza M. Proof Systems for Sustainable Decentralized Cryptocurrencies. Institute of Science and Technology Austria, 2018, doi:10.15479/AT:ISTA:TH_1046.","ista":"Abusalah HM. 2018. Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria.","chicago":"Abusalah, Hamza M. “Proof Systems for Sustainable Decentralized Cryptocurrencies.” Institute of Science and Technology Austria, 2018. https://doi.org/10.15479/AT:ISTA:TH_1046."},"title":"Proof systems for sustainable decentralized cryptocurrencies","article_processing_charge":"No","author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","first_name":"Hamza M","full_name":"Abusalah, Hamza M","last_name":"Abusalah"}],"publist_id":"7971"},{"day":"16","isi":1,"year":"2018","date_published":"2018-08-16T00:00:00Z","doi":"10.1109/ISIT.2018.8437654","date_created":"2018-12-11T11:44:40Z","quality_controlled":"1","publisher":"IEEE","oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Obremski, Marciej, and Maciej Skórski. “Inverted Leftover Hash Lemma,” Vol. 2018. IEEE, 2018. https://doi.org/10.1109/ISIT.2018.8437654.","ista":"Obremski M, Skórski M. 2018. Inverted leftover hash lemma. ISIT: International Symposium on Information Theory, ISIT Proceedings, vol. 2018.","mla":"Obremski, Marciej, and Maciej Skórski. Inverted Leftover Hash Lemma. Vol. 2018, IEEE, 2018, doi:10.1109/ISIT.2018.8437654.","ieee":"M. Obremski and M. Skórski, “Inverted leftover hash lemma,” presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA, 2018, vol. 2018.","short":"M. Obremski, M. Skórski, in:, IEEE, 2018.","ama":"Obremski M, Skórski M. Inverted leftover hash lemma. In: Vol 2018. IEEE; 2018. doi:10.1109/ISIT.2018.8437654","apa":"Obremski, M., & Skórski, M. (2018). Inverted leftover hash lemma (Vol. 2018). Presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA: IEEE. https://doi.org/10.1109/ISIT.2018.8437654"},"title":"Inverted leftover hash lemma","publist_id":"7946","author":[{"first_name":"Marciej","last_name":"Obremski","full_name":"Obremski, Marciej"},{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej","last_name":"Skorski","full_name":"Skorski, Maciej"}],"external_id":{"isi":["000448139300368"]},"article_processing_charge":"No","language":[{"iso":"eng"}],"publication_status":"published","volume":2018,"oa_version":"Submitted Version","abstract":[{"text":"Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \\'collision graph\\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes.","lang":"eng"}],"month":"08","intvolume":" 2018","scopus_import":"1","alternative_title":["ISIT Proceedings"],"main_file_link":[{"url":"https://eprint.iacr.org/2017/507","open_access":"1"}],"date_updated":"2023-09-13T08:23:18Z","department":[{"_id":"KrPi"}],"_id":"108","status":"public","type":"conference","conference":{"name":"ISIT: International Symposium on Information Theory","end_date":"2018-06-22","location":"Vail, CO, USA","start_date":"2018-06-17 "}},{"department":[{"_id":"KrPi"}],"date_updated":"2023-09-13T09:05:17Z","status":"public","type":"journal_article","article_type":"original","_id":"107","volume":65,"issue":"4","ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"08","intvolume":" 65","scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2009/608","open_access":"1"}],"oa_version":"Preprint","abstract":[{"text":"We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a non-malleable code while it is stored in memory.","lang":"eng"}],"title":"Non-malleable codes","publist_id":"7947","author":[{"full_name":"Dziembowski, Stefan","last_name":"Dziembowski","first_name":"Stefan"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"last_name":"Wichs","full_name":"Wichs, Daniel","first_name":"Daniel"}],"external_id":{"isi":["000442938200004"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Dziembowski S, Pietrzak KZ, Wichs D. 2018. Non-malleable codes. Journal of the ACM. 65(4), 20.","chicago":"Dziembowski, Stefan, Krzysztof Z Pietrzak, and Daniel Wichs. “Non-Malleable Codes.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3178432.","ama":"Dziembowski S, Pietrzak KZ, Wichs D. Non-malleable codes. Journal of the ACM. 2018;65(4). doi:10.1145/3178432","apa":"Dziembowski, S., Pietrzak, K. Z., & Wichs, D. (2018). Non-malleable codes. Journal of the ACM. ACM. https://doi.org/10.1145/3178432","short":"S. Dziembowski, K.Z. Pietrzak, D. Wichs, Journal of the ACM 65 (2018).","ieee":"S. Dziembowski, K. Z. Pietrzak, and D. Wichs, “Non-malleable codes,” Journal of the ACM, vol. 65, no. 4. ACM, 2018.","mla":"Dziembowski, Stefan, et al. “Non-Malleable Codes.” Journal of the ACM, vol. 65, no. 4, 20, ACM, 2018, doi:10.1145/3178432."},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"},{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography"}],"article_number":"20","date_published":"2018-08-01T00:00:00Z","doi":"10.1145/3178432","date_created":"2018-12-11T11:44:40Z","day":"01","publication":"Journal of the ACM","isi":1,"year":"2018","publisher":"ACM","quality_controlled":"1","oa":1},{"date_created":"2018-12-11T11:45:07Z","doi":"10.1145/3196494.3196534","date_published":"2018-06-01T00:00:00Z","page":"51 - 65","publication":"Proceedings of the 2018 on Asia Conference on Computer and Communication Security","day":"01","year":"2018","isi":1,"oa":1,"publisher":"ACM","quality_controlled":"1","acknowledgement":"Leonid Reyzin was supported in part by IST Austria and by US NSF grants 1012910, 1012798, and 1422965; this research was performed while he was visiting IST Austria.","title":"On the memory hardness of data independent password hashing functions","external_id":{"isi":["000516620100005"]},"article_processing_charge":"No","author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Peter","full_name":"Gazi, Peter","last_name":"Gazi"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen"},{"last_name":"Osang","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","first_name":"Georg F"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Lenoid","last_name":"Reyzin","full_name":"Reyzin, Lenoid"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"},{"full_name":"Rybar, Michal","last_name":"Rybar","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}],"publist_id":"7723","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ASIACCS: Asia Conference on Computer and Communications Security , 51–65.","chicago":"Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar. “On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings of the 2018 on Asia Conference on Computer and Communication Security, 51–65. ACM, 2018. https://doi.org/10.1145/3196494.3196534.","apa":"Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak, K. Z., … Rybar, M. (2018). On the memory hardness of data independent password hashing functions. In Proceedings of the 2018 on Asia Conference on Computer and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534","ama":"Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534","ieee":"J. F. Alwen et al., “On the memory hardness of data independent password hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.","short":"J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65.","mla":"Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534."},"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"06","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/783"}],"scopus_import":"1","oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF."}],"department":[{"_id":"KrPi"},{"_id":"HeEd"},{"_id":"VlKo"}],"date_updated":"2023-09-13T09:13:12Z","status":"public","conference":{"end_date":"2018-06-08","location":"Incheon, Republic of Korea","start_date":"2018-06-04","name":"ASIACCS: Asia Conference on Computer and Communications Security "},"type":"conference","_id":"193"},{"department":[{"_id":"KrPi"}],"date_updated":"2023-09-13T09:12:04Z","type":"conference","conference":{"name":"Eurocrypt: Advances in Cryptology","location":"Tel Aviv, Israel","end_date":"2018-05-03","start_date":"2018-04-29"},"status":"public","_id":"300","volume":10820,"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2018/077","open_access":"1"}],"month":"03","intvolume":" 10820","abstract":[{"text":"We introduce a formal quantitative notion of “bit security” for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with k-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a k-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems.","lang":"eng"}],"oa_version":"Submitted Version","publist_id":"7581","author":[{"first_name":"Daniele","full_name":"Micciancio, Daniele","last_name":"Micciancio"},{"full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael"}],"external_id":{"isi":["000517097500001"]},"article_processing_charge":"No","title":"On the bit security of cryptographic primitives","citation":{"short":"D. Micciancio, M. Walter, in:, Springer, 2018, pp. 3–28.","ieee":"D. Micciancio and M. Walter, “On the bit security of cryptographic primitives,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10820, pp. 3–28.","apa":"Micciancio, D., & Walter, M. (2018). On the bit security of cryptographic primitives (Vol. 10820, pp. 3–28). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78381-9_1","ama":"Micciancio D, Walter M. On the bit security of cryptographic primitives. In: Vol 10820. Springer; 2018:3-28. doi:10.1007/978-3-319-78381-9_1","mla":"Micciancio, Daniele, and Michael Walter. On the Bit Security of Cryptographic Primitives. Vol. 10820, Springer, 2018, pp. 3–28, doi:10.1007/978-3-319-78381-9_1.","ista":"Micciancio D, Walter M. 2018. On the bit security of cryptographic primitives. Eurocrypt: Advances in Cryptology, LNCS, vol. 10820, 3–28.","chicago":"Micciancio, Daniele, and Michael Walter. “On the Bit Security of Cryptographic Primitives,” 10820:3–28. Springer, 2018. https://doi.org/10.1007/978-3-319-78381-9_1."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"page":"3 - 28","date_published":"2018-03-31T00:00:00Z","doi":"10.1007/978-3-319-78381-9_1","date_created":"2018-12-11T11:45:42Z","isi":1,"year":"2018","day":"31","publisher":"Springer","quality_controlled":"1","oa":1,"acknowledgement":"Research supported in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under the SafeWare program. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views, position or policy of the Government. The second author was also supported by the European Research Council, ERC consolidator grant (682815 - TOCNeT)."},{"date_updated":"2023-09-18T09:29:33Z","department":[{"_id":"KrPi"}],"_id":"302","conference":{"name":"Eurocrypt: Advances in Cryptology","start_date":"2018-04-29","end_date":"2018-05-03","location":"Tel Aviv, Israel"},"type":"conference","status":"public","publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"volume":10821,"abstract":[{"text":"At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement. The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used – in combination with proofs of space – as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies. The construction proposed by [MMV13] is based on a hash function and can be proven secure in the random oracle model, or assuming inherently sequential hash-functions, which is a new standard model assumption introduced in their work. In a proof of sequential work, a prover gets a “statement” χ, a time parameter N and access to a hash-function H, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only N queries to H, while soundness requires that any prover who makes the verifier accept must have made (almost) N sequential queries to H. Thus a solution constitutes a proof that N time passed since χ was received. Solutions must be publicly verifiable in time at most polylogarithmic in N. The construction of [MMV13] is based on “depth-robust” graphs, and as a consequence has rather poor concrete parameters. But the major drawback is that the prover needs not just N time, but also N space to compute a proof. In this work we propose a proof of sequential work which is much simpler, more efficient and achieves much better concrete bounds. Most importantly, the space required can be as small as log (N) (but we get better soundness using slightly more memory than that). An open problem stated by [MMV13] that our construction does not solve either is achieving a “unique” proof, where even a cheating prover can only generate a single accepting proof. This property would be extremely useful for applications to blockchains.","lang":"eng"}],"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/183.pdf"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 10821","month":"05","citation":{"ama":"Cohen B, Pietrzak KZ. Simple proofs of sequential work. In: Vol 10821. Springer; 2018:451-467. doi:10.1007/978-3-319-78375-8_15","apa":"Cohen, B., & Pietrzak, K. Z. (2018). Simple proofs of sequential work (Vol. 10821, pp. 451–467). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_15","short":"B. Cohen, K.Z. Pietrzak, in:, Springer, 2018, pp. 451–467.","ieee":"B. Cohen and K. Z. Pietrzak, “Simple proofs of sequential work,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 451–467.","mla":"Cohen, Bram, and Krzysztof Z. Pietrzak. Simple Proofs of Sequential Work. Vol. 10821, Springer, 2018, pp. 451–67, doi:10.1007/978-3-319-78375-8_15.","ista":"Cohen B, Pietrzak KZ. 2018. Simple proofs of sequential work. Eurocrypt: Advances in Cryptology, LNCS, vol. 10821, 451–467.","chicago":"Cohen, Bram, and Krzysztof Z Pietrzak. “Simple Proofs of Sequential Work,” 10821:451–67. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_15."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000517098700015"]},"article_processing_charge":"No","publist_id":"7579","author":[{"last_name":"Cohen","full_name":"Cohen, Bram","first_name":"Bram"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"title":"Simple proofs of sequential work","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"year":"2018","isi":1,"day":"29","page":"451 - 467","date_created":"2018-12-11T11:45:42Z","date_published":"2018-05-29T00:00:00Z","doi":"10.1007/978-3-319-78375-8_15","oa":1,"quality_controlled":"1","publisher":"Springer"},{"type":"conference","conference":{"name":"Eurocrypt 2018: Advances in Cryptology","start_date":"2018-04-29","location":"Tel Aviv, Israel","end_date":"2018-05-03"},"status":"public","_id":"298","department":[{"_id":"KrPi"}],"date_updated":"2023-09-19T09:59:30Z","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1705.05313","open_access":"1"}],"month":"03","intvolume":" 10821","abstract":[{"lang":"eng","text":"Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains.\r\n\r\nAlwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost.\r\n\r\nIn this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps.\r\n\r\nAs has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps.\r\n\r\nAlong the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅"}],"oa_version":"Preprint","volume":10821,"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"publist_id":"7583","author":[{"last_name":"Alwen","full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jeremiah","full_name":"Blocki, Jeremiah","last_name":"Blocki"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"external_id":{"isi":["000517098700004"],"arxiv":["1705.05313"]},"article_processing_charge":"No","title":"Sustained space complexity","citation":{"apa":"Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2018). Sustained space complexity (Vol. 10821, pp. 99–130). Presented at the Eurocrypt 2018: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_4","ama":"Alwen JF, Blocki J, Pietrzak KZ. Sustained space complexity. In: Vol 10821. Springer; 2018:99-130. doi:10.1007/978-3-319-78375-8_4","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, Springer, 2018, pp. 99–130.","ieee":"J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Sustained space complexity,” presented at the Eurocrypt 2018: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 99–130.","mla":"Alwen, Joel F., et al. Sustained Space Complexity. Vol. 10821, Springer, 2018, pp. 99–130, doi:10.1007/978-3-319-78375-8_4.","ista":"Alwen JF, Blocki J, Pietrzak KZ. 2018. Sustained space complexity. Eurocrypt 2018: Advances in Cryptology, LNCS, vol. 10821, 99–130.","chicago":"Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Sustained Space Complexity,” 10821:99–130. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_4."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer","quality_controlled":"1","oa":1,"page":"99 - 130","doi":"10.1007/978-3-319-78375-8_4","date_published":"2018-03-31T00:00:00Z","date_created":"2018-12-11T11:45:41Z","isi":1,"year":"2018","day":"31"},{"year":"2018","publication_status":"published","isi":1,"language":[{"iso":"eng"}],"publication":"American Institute of Mathematical Sciences","day":"01","page":"17-47","date_created":"2019-02-13T13:49:41Z","issue":"1","doi":"10.3934/amc.2018002","date_published":"2018-02-01T00:00:00Z","volume":12,"abstract":[{"lang":"eng","text":"The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols."}],"oa_version":"None","quality_controlled":"1","scopus_import":"1","publisher":"AIMS","intvolume":" 12","month":"02","date_updated":"2023-09-19T14:27:59Z","citation":{"ieee":"S. Chatterjee, C. Kamath Hosdurg, and V. Kumar, “Private set-intersection with common set-up,” American Institute of Mathematical Sciences, vol. 12, no. 1. AIMS, pp. 17–47, 2018.","short":"S. Chatterjee, C. Kamath Hosdurg, V. Kumar, American Institute of Mathematical Sciences 12 (2018) 17–47.","apa":"Chatterjee, S., Kamath Hosdurg, C., & Kumar, V. (2018). Private set-intersection with common set-up. American Institute of Mathematical Sciences. AIMS. https://doi.org/10.3934/amc.2018002","ama":"Chatterjee S, Kamath Hosdurg C, Kumar V. Private set-intersection with common set-up. American Institute of Mathematical Sciences. 2018;12(1):17-47. doi:10.3934/amc.2018002","mla":"Chatterjee, Sanjit, et al. “Private Set-Intersection with Common Set-Up.” American Institute of Mathematical Sciences, vol. 12, no. 1, AIMS, 2018, pp. 17–47, doi:10.3934/amc.2018002.","ista":"Chatterjee S, Kamath Hosdurg C, Kumar V. 2018. Private set-intersection with common set-up. American Institute of Mathematical Sciences. 12(1), 17–47.","chicago":"Chatterjee, Sanjit, Chethan Kamath Hosdurg, and Vikas Kumar. “Private Set-Intersection with Common Set-Up.” American Institute of Mathematical Sciences. AIMS, 2018. https://doi.org/10.3934/amc.2018002."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000430950400002"]},"article_processing_charge":"No","author":[{"first_name":"Sanjit","last_name":"Chatterjee","full_name":"Chatterjee, Sanjit"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kumar, Vikas","last_name":"Kumar","first_name":"Vikas"}],"title":"Private set-intersection with common set-up","department":[{"_id":"KrPi"}],"_id":"5980","type":"journal_article","status":"public"},{"oa":1,"publisher":"Springer Nature","quality_controlled":"1","year":"2018","isi":1,"publication":"22nd International Conference on Financial Cryptography and Data Security","day":"07","page":"480-499","date_created":"2019-10-14T06:35:38Z","doi":"10.1007/978-3-662-58387-6_26","date_published":"2018-12-07T00:00:00Z","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"citation":{"chicago":"Park, Sunoo, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joel F Alwen, and Krzysztof Z Pietrzak. “SpaceMint: A Cryptocurrency Based on Proofs of Space.” In 22nd International Conference on Financial Cryptography and Data Security, 10957:480–99. Springer Nature, 2018. https://doi.org/10.1007/978-3-662-58387-6_26.","ista":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. 2018. SpaceMint: A cryptocurrency based on proofs of space. 22nd International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 10957, 480–499.","mla":"Park, Sunoo, et al. “SpaceMint: A Cryptocurrency Based on Proofs of Space.” 22nd International Conference on Financial Cryptography and Data Security, vol. 10957, Springer Nature, 2018, pp. 480–99, doi:10.1007/978-3-662-58387-6_26.","ama":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. SpaceMint: A cryptocurrency based on proofs of space. In: 22nd International Conference on Financial Cryptography and Data Security. Vol 10957. Springer Nature; 2018:480-499. doi:10.1007/978-3-662-58387-6_26","apa":"Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J. F., & Pietrzak, K. Z. (2018). SpaceMint: A cryptocurrency based on proofs of space. In 22nd International Conference on Financial Cryptography and Data Security (Vol. 10957, pp. 480–499). Nieuwpoort, Curacao: Springer Nature. https://doi.org/10.1007/978-3-662-58387-6_26","short":"S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J.F. Alwen, K.Z. Pietrzak, in:, 22nd International Conference on Financial Cryptography and Data Security, Springer Nature, 2018, pp. 480–499.","ieee":"S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J. F. Alwen, and K. Z. Pietrzak, “SpaceMint: A cryptocurrency based on proofs of space,” in 22nd International Conference on Financial Cryptography and Data Security, Nieuwpoort, Curacao, 2018, vol. 10957, pp. 480–499."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","external_id":{"isi":["000540656400026"]},"author":[{"last_name":"Park","full_name":"Park, Sunoo","first_name":"Sunoo"},{"first_name":"Albert","full_name":"Kwon, Albert","last_name":"Kwon"},{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","last_name":"Fuchsbauer","full_name":"Fuchsbauer, Georg"},{"full_name":"Gazi, Peter","last_name":"Gazi","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter"},{"full_name":"Alwen, Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"title":"SpaceMint: A cryptocurrency based on proofs of space","abstract":[{"lang":"eng","text":"Bitcoin has become the most successful cryptocurrency ever deployed, and its most distinctive feature is that it is decentralized. Its underlying protocol (Nakamoto consensus) achieves this by using proof of work, which has the drawback that it causes the consumption of vast amounts of energy to maintain the ledger. Moreover, Bitcoin mining dynamics have become less distributed over time.\r\n\r\nTowards addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather than computation. We argue that SpaceMint’s design solves or alleviates several of Bitcoin’s issues: most notably, its large energy consumption. SpaceMint also rewards smaller miners fairly according to their contribution to the network, thus incentivizing more distributed participation.\r\n\r\nThis paper adapts proof of space to enable its use in cryptocurrency, studies the attacks that can arise against a Bitcoin-like blockchain that uses proof of space, and proposes a new blockchain format and transaction types to address these attacks. Our prototype shows that initializing 1 TB for mining takes about a day (a one-off setup cost), and miners spend on average just a fraction of a second per block mined. Finally, we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the canonical game-theoretic notion for games that take place over time) and show that this stylized game satisfies a strong equilibrium notion, thereby arguing for SpaceMint ’s stability and consensus."}],"oa_version":"Submitted Version","main_file_link":[{"url":"https://eprint.iacr.org/2015/528","open_access":"1"}],"scopus_import":"1","alternative_title":["LNCS"],"intvolume":" 10957","month":"12","publication_status":"published","publication_identifier":{"isbn":["9783662583869","9783662583876"],"eissn":["1611-3349"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":10957,"_id":"6941","conference":{"name":"FC: Financial Cryptography and Data Security","start_date":"2018-02-26","location":"Nieuwpoort, Curacao","end_date":"2018-03-02"},"type":"conference","status":"public","date_updated":"2023-09-19T15:02:13Z","department":[{"_id":"KrPi"}]},{"title":"Cumulative space in black-white pebbling and resolution","editor":[{"full_name":"Papadimitriou, Christos","last_name":"Papadimitriou","first_name":"Christos"}],"publist_id":"6179","author":[{"last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"first_name":"Susanna","last_name":"De Rezende","full_name":"De Rezende, Susanna"},{"first_name":"Jakob","full_name":"Nordstrom, Jakob","last_name":"Nordstrom"},{"first_name":"Marc","full_name":"Vinyals, Marc","last_name":"Vinyals"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou (Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.","ieee":"J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space in black-white pebbling and resolution,” presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.","apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., & Vinyals, M. (2017). Cumulative space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol. 67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2017.38","ama":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:38:1-38-21. doi:10.4230/LIPIcs.ITCS.2017.38","mla":"Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38.","ista":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 67, 38:1-38-21.","chicago":"Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou, 67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.38."},"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"date_published":"2017-01-01T00:00:00Z","doi":"10.4230/LIPIcs.ITCS.2017.38","date_created":"2018-12-11T11:50:33Z","page":"38:1-38-21","day":"01","has_accepted_license":"1","year":"2017","status":"public","pubrep_id":"927","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","end_date":"2017-01-11","start_date":"2017-01-09"},"_id":"1175","file_date_updated":"2020-07-14T12:44:37Z","department":[{"_id":"KrPi"}],"ddc":["005","600"],"date_updated":"2021-01-12T06:48:51Z","month":"01","intvolume":" 67","scopus_import":1,"alternative_title":["LIPIcs"],"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure."}],"volume":67,"file":[{"date_created":"2018-12-12T10:17:11Z","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","date_updated":"2020-07-14T12:44:37Z","file_size":557769,"creator":"system","file_id":"5263","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["18688969"]},"publication_status":"published"},{"oa_version":"Submitted Version","abstract":[{"text":"Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem. We show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model. On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to “bypass” our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes.","lang":"eng"}],"month":"11","intvolume":" 10677","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2016/536","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-331970499-9"]},"publication_status":"published","volume":10677,"ec_funded":1,"_id":"605","status":"public","type":"conference","conference":{"start_date":"2017-11-12","location":"Baltimore, MD, United States","end_date":"2017-11-15","name":"TCC: Theory of Cryptography Conference"},"date_updated":"2021-01-12T08:05:53Z","department":[{"_id":"KrPi"}],"publisher":"Springer","quality_controlled":"1","oa":1,"day":"05","year":"2017","doi":"10.1007/978-3-319-70500-2_3","date_published":"2017-11-05T00:00:00Z","date_created":"2018-12-11T11:47:27Z","page":"56 - 81","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. Position based cryptography and multiparty communication complexity. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:56-81. doi:10.1007/978-3-319-70500-2_3","apa":"Brody, J., Dziembowski, S., Faust, S., & Pietrzak, K. Z. (2017). Position based cryptography and multiparty communication complexity. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677, pp. 56–81). Presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States: Springer. https://doi.org/10.1007/978-3-319-70500-2_3","short":"J. Brody, S. Dziembowski, S. Faust, K.Z. Pietrzak, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 56–81.","ieee":"J. Brody, S. Dziembowski, S. Faust, and K. Z. Pietrzak, “Position based cryptography and multiparty communication complexity,” presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States, 2017, vol. 10677, pp. 56–81.","mla":"Brody, Joshua, et al. Position Based Cryptography and Multiparty Communication Complexity. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 56–81, doi:10.1007/978-3-319-70500-2_3.","ista":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. 2017. Position based cryptography and multiparty communication complexity. TCC: Theory of Cryptography Conference, LNCS, vol. 10677, 56–81.","chicago":"Brody, Joshua, Stefan Dziembowski, Sebastian Faust, and Krzysztof Z Pietrzak. “Position Based Cryptography and Multiparty Communication Complexity.” edited by Yael Kalai and Leonid Reyzin, 10677:56–81. Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_3."},"title":"Position based cryptography and multiparty communication complexity","editor":[{"first_name":"Yael","last_name":"Kalai","full_name":"Kalai, Yael"},{"first_name":"Leonid","last_name":"Reyzin","full_name":"Reyzin, Leonid"}],"author":[{"first_name":"Joshua","last_name":"Brody","full_name":"Brody, Joshua"},{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"first_name":"Sebastian","last_name":"Faust","full_name":"Faust, Sebastian"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"publist_id":"7200"},{"oa":1,"publisher":"Springer","quality_controlled":"1","date_created":"2018-12-11T11:47:28Z","date_published":"2017-11-05T00:00:00Z","doi":"10.1007/978-3-319-70500-2_17","page":"493 - 526","day":"05","year":"2017","editor":[{"last_name":"Kalai","full_name":"Kalai, Yael","first_name":"Yael"},{"full_name":"Reyzin, Leonid","last_name":"Reyzin","first_name":"Leonid"}],"title":"Moderately hard functions: Definition, instantiations, and applications","author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"full_name":"Tackmann, Björn","last_name":"Tackmann","first_name":"Björn"}],"publist_id":"7196","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Alwen, Joel F, and Björn Tackmann. “Moderately Hard Functions: Definition, Instantiations, and Applications.” edited by Yael Kalai and Leonid Reyzin, 10677:493–526. Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_17.","ista":"Alwen JF, Tackmann B. 2017. Moderately hard functions: Definition, instantiations, and applications. TCC: Theory of Cryptography, LNCS, vol. 10677, 493–526.","mla":"Alwen, Joel F., and Björn Tackmann. Moderately Hard Functions: Definition, Instantiations, and Applications. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 493–526, doi:10.1007/978-3-319-70500-2_17.","short":"J.F. Alwen, B. Tackmann, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 493–526.","ieee":"J. F. Alwen and B. Tackmann, “Moderately hard functions: Definition, instantiations, and applications,” presented at the TCC: Theory of Cryptography, Baltimore, MD, United States, 2017, vol. 10677, pp. 493–526.","apa":"Alwen, J. F., & Tackmann, B. (2017). Moderately hard functions: Definition, instantiations, and applications. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677, pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United States: Springer. https://doi.org/10.1007/978-3-319-70500-2_17","ama":"Alwen JF, Tackmann B. Moderately hard functions: Definition, instantiations, and applications. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:493-526. doi:10.1007/978-3-319-70500-2_17"},"intvolume":" 10677","month":"11","main_file_link":[{"url":"https://eprint.iacr.org/2017/945","open_access":"1"}],"scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"text":"Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. On a technical level, beyond the mentioned definitions, we instantiate the model for four different notions of hardness. We extend the work of Alwen and Serbinenko (STOC 2015) by providing a general tool for proving security for the first notion of memory-hard functions that allows for provably secure applications. The tool allows us to recover all of the graph-theoretic techniques developed for proving security under the older, non-composable, notion of security used by Alwen and Serbinenko. As an application of our definition of moderately hard functions, we prove the security of two different schemes for proofs of effort (PoE). We also formalize and instantiate the concept of a non-interactive proof of effort (niPoE), in which the proof is not bound to a particular communication context but rather any bit-string chosen by the prover.","lang":"eng"}],"volume":10677,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["978-331970499-9"]},"status":"public","conference":{"end_date":"2017-11-15","location":"Baltimore, MD, United States","start_date":"2017-11-12","name":"TCC: Theory of Cryptography"},"type":"conference","_id":"609","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:06:04Z"},{"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"publist_id":"7154","author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"first_name":"Binchi","full_name":"Chen, Binchi","last_name":"Chen"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonid","full_name":"Reyzin, Leonid","last_name":"Reyzin"},{"first_name":"Stefano","last_name":"Tessaro","full_name":"Tessaro, Stefano"}],"title":"Scrypt is maximally memory hard","editor":[{"last_name":"Coron","full_name":"Coron, Jean-Sébastien","first_name":"Jean-Sébastien"},{"first_name":"Jesper","last_name":"Buus Nielsen","full_name":"Buus Nielsen, Jesper"}],"citation":{"mla":"Alwen, Joel F., et al. Scrypt Is Maximally Memory Hard. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:10.1007/978-3-319-56617-7_2.","short":"J.F. Alwen, B. Chen, K.Z. Pietrzak, L. Reyzin, S. Tessaro, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 33–62.","ieee":"J. F. Alwen, B. Chen, K. Z. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt is maximally memory hard,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 33–62.","ama":"Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. Scrypt is maximally memory hard. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:33-62. doi:10.1007/978-3-319-56617-7_2","apa":"Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., & Tessaro, S. (2017). Scrypt is maximally memory hard. In J.-S. Coron & J. Buus Nielsen (Eds.) (Vol. 10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_2","chicago":"Alwen, Joel F, Binchi Chen, Krzysztof Z Pietrzak, Leonid Reyzin, and Stefano Tessaro. “Scrypt Is Maximally Memory Hard.” edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10212:33–62. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_2.","ista":"Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. 2017. Scrypt is maximally memory hard. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 10212, 33–62."},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","quality_controlled":"1","oa":1,"page":"33 - 62","doi":"10.1007/978-3-319-56617-7_2","date_published":"2017-01-01T00:00:00Z","date_created":"2018-12-11T11:47:37Z","year":"2017","day":"01","type":"conference","conference":{"end_date":"2017-05-04","location":"Paris, France","start_date":"2017-04-30","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"status":"public","_id":"635","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:07:10Z","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2016/989","open_access":"1"}],"month":"01","intvolume":" 10212","abstract":[{"text":"Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt, a simple candidate MHF designed by Percival, and described in RFC 7914. It has been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and has been an inspiration for Argon2d, one of the winners of the recent password-hashing competition. Despite its popularity, no rigorous lower bounds on its memory complexity are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w and n are the output length and number of invocations of the underlying hash function, respectively. High cmc is a strong security target for MHFs introduced by Alwen and Serbinenko (STOC’15) which implies high memory cost even for adversaries who can amortize the cost over many evaluations and evaluate the underlying hash functions many times in parallel. Our proof is the first showing optimal memory-hardness for any MHF. Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of Ω(n2w/ log2 n) for a restricted class of adversaries.","lang":"eng"}],"oa_version":"Submitted Version","volume":10212,"ec_funded":1,"publication_identifier":{"isbn":["978-331956616-0"]},"publication_status":"published","language":[{"iso":"eng"}]},{"publication_identifier":{"isbn":["978-331956616-0"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":10212,"ec_funded":1,"abstract":[{"lang":"eng","text":"Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: – The parallel cumulative pebbling complexity Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). – The sequential space-time pebbling complexity Πst(Gn) should be as close as possible to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn) = Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new upper and lower bounds on the Π∥cc of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions."}],"oa_version":"Submitted Version","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2016/875","open_access":"1"}],"month":"04","intvolume":" 10212","date_updated":"2021-01-12T08:07:22Z","department":[{"_id":"KrPi"}],"_id":"640","type":"conference","conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2017-04-30","location":"Paris, France","end_date":"2017-05-04"},"status":"public","year":"2017","day":"01","page":"3 - 32","date_published":"2017-04-01T00:00:00Z","doi":"10.1007/978-3-319-56617-7_1","date_created":"2018-12-11T11:47:39Z","publisher":"Springer","quality_controlled":"1","oa":1,"citation":{"ieee":"J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Depth-robust graphs and their cumulative memory complexity,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 3–32.","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 3–32.","apa":"Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2017). Depth-robust graphs and their cumulative memory complexity. In J.-S. Coron & J. Buus Nielsen (Eds.) (Vol. 10212, pp. 3–32). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_1","ama":"Alwen JF, Blocki J, Pietrzak KZ. Depth-robust graphs and their cumulative memory complexity. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:3-32. doi:10.1007/978-3-319-56617-7_1","mla":"Alwen, Joel F., et al. Depth-Robust Graphs and Their Cumulative Memory Complexity. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 3–32, doi:10.1007/978-3-319-56617-7_1.","ista":"Alwen JF, Blocki J, Pietrzak KZ. 2017. Depth-robust graphs and their cumulative memory complexity. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 10212, 3–32.","chicago":"Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Depth-Robust Graphs and Their Cumulative Memory Complexity.” edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10212:3–32. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_1."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"7148","author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"first_name":"Jeremiah","last_name":"Blocki","full_name":"Blocki, Jeremiah"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"title":"Depth-robust graphs and their cumulative memory complexity","editor":[{"first_name":"Jean-Sébastien","full_name":"Coron, Jean-Sébastien","last_name":"Coron"},{"full_name":"Buus Nielsen, Jesper","last_name":"Buus Nielsen","first_name":"Jesper"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}]},{"citation":{"ista":"Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 600–613.","chicago":"Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_43.","ieee":"M. Skórski, “On the complexity of breaking pseudoentropy,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 600–613.","short":"M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 600–613.","apa":"Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_43","ama":"Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:600-613. doi:10.1007/978-3-319-55911-7_43","mla":"Skórski, Maciej. On the Complexity of Breaking Pseudoentropy. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:10.1007/978-3-319-55911-7_43."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"7125","author":[{"first_name":"Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","last_name":"Skórski"}],"editor":[{"first_name":"Gerhard","last_name":"Jäger","full_name":"Jäger, Gerhard"},{"first_name":"Silvia","last_name":"Steila","full_name":"Steila, Silvia"}],"title":"On the complexity of breaking pseudoentropy","oa":1,"quality_controlled":"1","publisher":"Springer","year":"2017","day":"01","page":"600 - 613","date_created":"2018-12-11T11:47:42Z","date_published":"2017-04-01T00:00:00Z","doi":"10.1007/978-3-319-55911-7_43","_id":"648","conference":{"name":"TAMC: Theory and Applications of Models of Computation","start_date":"2017-04-20","location":"Bern, Switzerland","end_date":"2017-04-22"},"type":"conference","status":"public","date_updated":"2021-01-12T08:07:39Z","department":[{"_id":"KrPi"}],"abstract":[{"text":"Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.","lang":"eng"}],"oa_version":"Submitted Version","main_file_link":[{"url":"https://eprint.iacr.org/2016/1186.pdf","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 10185","month":"04","publication_status":"published","publication_identifier":{"isbn":["978-331955910-0"]},"language":[{"iso":"eng"}],"volume":10185}]