[{"date_updated":"2026-04-08T14:10:22Z","abstract":[{"lang":"eng","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."}],"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"}],"date_created":"2018-12-11T11:44:32Z","author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","full_name":"Abusalah, Hamza M","last_name":"Abusalah","first_name":"Hamza M"}],"title":"Proof systems for sustainable decentralized cryptocurrencies","date_published":"2018-09-05T00:00:00Z","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","file_date_updated":"2020-07-14T12:48:11Z","publist_id":"7971","publisher":"Institute of Science and Technology Austria","supervisor":[{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"citation":{"ama":"Abusalah HM. Proof systems for sustainable decentralized cryptocurrencies. 2018. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:TH_1046\">10.15479/AT:ISTA:TH_1046</a>","apa":"Abusalah, H. M. (2018). <i>Proof systems for sustainable decentralized cryptocurrencies</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:TH_1046\">https://doi.org/10.15479/AT:ISTA:TH_1046</a>","chicago":"Abusalah, Hamza M. “Proof Systems for Sustainable Decentralized Cryptocurrencies.” Institute of Science and Technology Austria, 2018. <a href=\"https://doi.org/10.15479/AT:ISTA:TH_1046\">https://doi.org/10.15479/AT:ISTA:TH_1046</a>.","ista":"Abusalah HM. 2018. Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria.","ieee":"H. M. Abusalah, “Proof systems for sustainable decentralized cryptocurrencies,” Institute of Science and Technology Austria, 2018.","short":"H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies, Institute of Science and Technology Austria, 2018.","mla":"Abusalah, Hamza M. <i>Proof Systems for Sustainable Decentralized Cryptocurrencies</i>. Institute of Science and Technology Austria, 2018, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:TH_1046\">10.15479/AT:ISTA:TH_1046</a>."},"ddc":["004"],"day":"05","_id":"83","article_processing_charge":"No","oa_version":"Published Version","alternative_title":["ISTA Thesis"],"department":[{"_id":"KrPi"}],"month":"09","doi":"10.15479/AT:ISTA:TH_1046","has_accepted_license":"1","page":"59","related_material":{"record":[{"id":"559","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"1236"},{"relation":"part_of_dissertation","id":"1235","status":"public"},{"status":"public","id":"1229","relation":"part_of_dissertation"}]},"year":"2018","oa":1,"language":[{"iso":"eng"}],"file":[{"relation":"main_file","date_created":"2019-04-09T06:43:41Z","date_updated":"2020-07-14T12:48:11Z","file_name":"2018_Thesis_Abusalah.pdf","file_size":876241,"checksum":"c4b5f7d111755d1396787f41886fc674","content_type":"application/pdf","file_id":"6245","creator":"dernst","access_level":"open_access"},{"relation":"source_file","date_created":"2019-04-09T06:43:41Z","content_type":"application/x-gzip","file_size":2029190,"checksum":"0f382ac56b471c48fd907d63eb87dafe","file_name":"2018_Thesis_Abusalah_source.tar.gz","date_updated":"2020-07-14T12:48:11Z","file_id":"6246","creator":"dernst","access_level":"closed"}],"publication_identifier":{"issn":["2663-337X"]},"status":"public","pubrep_id":"1046","ec_funded":1,"OA_place":"publisher","type":"dissertation","degree_awarded":"PhD"},{"month":"12","isi":1,"oa":1,"year":"2018","language":[{"iso":"eng"}],"page":"480-499","conference":{"location":"Nieuwpoort, Curacao","end_date":"2018-03-02","name":"FC: Financial Cryptography and Data Security","start_date":"2018-02-26"},"doi":"10.1007/978-3-662-58387-6_26","volume":10957,"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783662583869"],"eisbn":["9783662583876"]},"ec_funded":1,"status":"public","type":"conference","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"author":[{"full_name":"Park, Sunoo","first_name":"Sunoo","last_name":"Park"},{"last_name":"Kwon","first_name":"Albert","full_name":"Kwon, Albert"},{"full_name":"Fuchsbauer, Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","last_name":"Fuchsbauer"},{"first_name":"Peter","last_name":"Gazi","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","full_name":"Gazi, Peter"},{"last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"}],"title":"SpaceMint: A cryptocurrency based on proofs of space","external_id":{"isi":["000540656400026"]},"date_created":"2019-10-14T06:35:38Z","main_file_link":[{"url":"https://eprint.iacr.org/2015/528","open_access":"1"}],"date_updated":"2026-04-16T10:30:49Z","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."}],"publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication":"22nd International Conference on Financial Cryptography and Data Security","date_published":"2018-12-07T00:00:00Z","citation":{"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.” <i>22nd International Conference on Financial Cryptography and Data Security</i>, vol. 10957, Springer Nature, 2018, pp. 480–99, doi:<a href=\"https://doi.org/10.1007/978-3-662-58387-6_26\">10.1007/978-3-662-58387-6_26</a>.","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 <i>22nd International Conference on Financial Cryptography and Data Security</i>, Nieuwpoort, Curacao, 2018, vol. 10957, pp. 480–499.","ama":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. SpaceMint: A cryptocurrency based on proofs of space. In: <i>22nd International Conference on Financial Cryptography and Data Security</i>. Vol 10957. Springer Nature; 2018:480-499. doi:<a href=\"https://doi.org/10.1007/978-3-662-58387-6_26\">10.1007/978-3-662-58387-6_26</a>","apa":"Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J. F., &#38; Pietrzak, K. Z. (2018). SpaceMint: A cryptocurrency based on proofs of space. In <i>22nd International Conference on Financial Cryptography and Data Security</i> (Vol. 10957, pp. 480–499). Nieuwpoort, Curacao: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-58387-6_26\">https://doi.org/10.1007/978-3-662-58387-6_26</a>","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 <i>22nd International Conference on Financial Cryptography and Data Security</i>, 10957:480–99. Springer Nature, 2018. <a href=\"https://doi.org/10.1007/978-3-662-58387-6_26\">https://doi.org/10.1007/978-3-662-58387-6_26</a>."},"quality_controlled":"1","publisher":"Springer Nature","scopus_import":"1","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"intvolume":"     10957","day":"07","article_processing_charge":"No","oa_version":"Submitted Version","_id":"6941"},{"_id":"1174","article_processing_charge":"No","oa_version":"Submitted Version","day":"01","intvolume":"        66","alternative_title":["LIPIcs"],"department":[{"_id":"KrPi"}],"scopus_import":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publist_id":"6180","quality_controlled":"1","citation":{"chicago":"Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,” Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">https://doi.org/10.4230/LIPIcs.STACS.2017.57</a>.","ama":"Skórski M. Lower bounds on key derivation for square-friendly applications. In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">10.4230/LIPIcs.STACS.2017.57</a>","apa":"Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications (Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">https://doi.org/10.4230/LIPIcs.STACS.2017.57</a>","mla":"Skórski, Maciej. <i>Lower Bounds on Key Derivation for Square-Friendly Applications</i>. Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2017.57\">10.4230/LIPIcs.STACS.2017.57</a>.","short":"M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"M. Skórski, “Lower bounds on key derivation for square-friendly applications,” presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 2017, vol. 66.","ista":"Skórski M. 2017. Lower bounds on key derivation for square-friendly applications. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66, 57."},"article_number":"57","date_published":"2017-03-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the &quot;RT-bound&quot;, extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a &quot;weak&quot; key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for &quot;weak&quot; keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\\'13, CRYPTO\\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.","lang":"eng"}],"date_updated":"2025-07-10T11:50:14Z","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2017/6976"}],"date_created":"2018-12-11T11:50:32Z","external_id":{"isi":["000521077300057"]},"author":[{"last_name":"Skórski","first_name":"Maciej","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"title":"Lower bounds on key derivation for square-friendly applications","project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"type":"conference","status":"public","ec_funded":1,"publication_identifier":{"issn":["1868-8969"]},"volume":66,"doi":"10.4230/LIPIcs.STACS.2017.57","conference":{"start_date":"2017-03-08","location":"Hannover, Germany","end_date":"2017-03-11","name":"STACS: Symposium on Theoretical Aspects of Computer Science"},"language":[{"iso":"eng"}],"year":"2017","oa":1,"isi":1,"month":"03"},{"month":"01","license":"https://creativecommons.org/licenses/by/4.0/","editor":[{"full_name":"Papadimitriou, Christos","first_name":"Christos","last_name":"Papadimitriou"}],"isi":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:44:37Z","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","content_type":"application/pdf","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","file_size":557769,"date_created":"2018-12-12T10:17:11Z","relation":"main_file","access_level":"open_access","creator":"system","file_id":"5263"}],"oa":1,"year":"2017","has_accepted_license":"1","conference":{"start_date":"2017-01-09","name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","end_date":"2017-01-11"},"page":"38:1-38-21","doi":"10.4230/LIPIcs.ITCS.2017.38","volume":67,"status":"public","pubrep_id":"927","publication_identifier":{"issn":["1868-8969"]},"type":"conference","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"full_name":"De Rezende, Susanna","last_name":"De Rezende","first_name":"Susanna"},{"first_name":"Jakob","last_name":"Nordstrom","full_name":"Nordstrom, Jakob"},{"first_name":"Marc","last_name":"Vinyals","full_name":"Vinyals, Marc"}],"title":"Cumulative space in black-white pebbling and resolution","date_created":"2018-12-11T11:50:33Z","external_id":{"isi":["001532708700038"]},"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."}],"date_updated":"2025-09-10T10:49:13Z","file_date_updated":"2020-07-14T12:44:37Z","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","date_published":"2017-01-01T00:00:00Z","ddc":["005","600"],"quality_controlled":"1","citation":{"apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">https://doi.org/10.4230/LIPIcs.ITCS.2017.38</a>","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:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">10.4230/LIPIcs.ITCS.2017.38</a>","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. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">https://doi.org/10.4230/LIPIcs.ITCS.2017.38</a>.","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.","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.","mla":"Alwen, Joel F., et al. <i>Cumulative Space in Black-White Pebbling and Resolution</i>. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2017.38\">10.4230/LIPIcs.ITCS.2017.38</a>.","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."},"publist_id":"6179","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"department":[{"_id":"KrPi"}],"intvolume":"        67","scopus_import":"1","article_processing_charge":"No","oa_version":"Published Version","_id":"1175","day":"01"},{"date_created":"2018-12-11T11:50:33Z","external_id":{"isi":["000424197300011"]},"author":[{"first_name":"Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F"},{"last_name":"Blocki","first_name":"Jeremiah","full_name":"Blocki, Jeremiah"}],"title":"Towards practical attacks on Argon2i and balloon hashing","abstract":[{"lang":"eng","text":"The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the \"paranoid\" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A."}],"date_updated":"2023-09-20T11:22:25Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/759"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","article_number":"7961977","date_published":"2017-07-03T00:00:00Z","quality_controlled":"1","citation":{"ieee":"J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon hashing,” presented at the EuroS&#38;P: European Symposium on Security and Privacy, Paris, France, 2017.","mla":"Alwen, Joel F., and Jeremiah Blocki. <i>Towards Practical Attacks on Argon2i and Balloon Hashing</i>. 7961977, IEEE, 2017, doi:<a href=\"https://doi.org/10.1109/EuroSP.2017.47\">10.1109/EuroSP.2017.47</a>.","short":"J.F. Alwen, J. Blocki, in:, IEEE, 2017.","ista":"Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon hashing. EuroS&#38;P: European Symposium on Security and Privacy, 7961977.","chicago":"Alwen, Joel F, and Jeremiah Blocki. “Towards Practical Attacks on Argon2i and Balloon Hashing.” IEEE, 2017. <a href=\"https://doi.org/10.1109/EuroSP.2017.47\">https://doi.org/10.1109/EuroSP.2017.47</a>.","apa":"Alwen, J. F., &#38; Blocki, J. (2017). Towards practical attacks on Argon2i and balloon hashing. Presented at the EuroS&#38;P: European Symposium on Security and Privacy, Paris, France: IEEE. <a href=\"https://doi.org/10.1109/EuroSP.2017.47\">https://doi.org/10.1109/EuroSP.2017.47</a>","ama":"Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing. In: IEEE; 2017. doi:<a href=\"https://doi.org/10.1109/EuroSP.2017.47\">10.1109/EuroSP.2017.47</a>"},"publist_id":"6178","publisher":"IEEE","department":[{"_id":"KrPi"}],"scopus_import":"1","_id":"1176","oa_version":"Submitted Version","article_processing_charge":"No","day":"03","month":"07","isi":1,"language":[{"iso":"eng"}],"year":"2017","oa":1,"doi":"10.1109/EuroSP.2017.47","conference":{"start_date":"2017-04-26","name":"EuroS&P: European Symposium on Security and Privacy","end_date":"2017-04-28","location":"Paris, France"},"status":"public","publication_identifier":{"isbn":["978-150905761-0"]},"type":"conference"},{"abstract":[{"lang":"eng","text":"We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol."}],"date_updated":"2025-04-14T07:22:06Z","external_id":{"isi":["000410788600007"]},"date_created":"2018-12-11T11:50:37Z","author":[{"last_name":"Kiltz","first_name":"Eike","full_name":"Kiltz, Eike"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"},{"full_name":"Venturi, Daniele","first_name":"Daniele","last_name":"Venturi"},{"full_name":"Cash, David","last_name":"Cash","first_name":"David"},{"last_name":"Jain","first_name":"Abhishek","full_name":"Jain, Abhishek"}],"title":"Efficient authentication from hard learning problems","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"},{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668"}],"date_published":"2017-10-01T00:00:00Z","publication":"Journal of Cryptology","file_date_updated":"2020-07-14T12:44:37Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","publisher":"Springer","publist_id":"6166","ddc":["000"],"citation":{"chicago":"Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek Jain. “Efficient Authentication from Hard Learning Problems.” <i>Journal of Cryptology</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00145-016-9247-3\">https://doi.org/10.1007/s00145-016-9247-3</a>.","apa":"Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., &#38; Jain, A. (2017). Efficient authentication from hard learning problems. <i>Journal of Cryptology</i>. Springer. <a href=\"https://doi.org/10.1007/s00145-016-9247-3\">https://doi.org/10.1007/s00145-016-9247-3</a>","ama":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from hard learning problems. <i>Journal of Cryptology</i>. 2017;30(4):1238-1275. doi:<a href=\"https://doi.org/10.1007/s00145-016-9247-3\">10.1007/s00145-016-9247-3</a>","ieee":"E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication from hard learning problems,” <i>Journal of Cryptology</i>, vol. 30, no. 4. Springer, pp. 1238–1275, 2017.","mla":"Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.” <i>Journal of Cryptology</i>, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:<a href=\"https://doi.org/10.1007/s00145-016-9247-3\">10.1007/s00145-016-9247-3</a>.","short":"E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275.","ista":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication from hard learning problems. Journal of Cryptology. 30(4), 1238–1275."},"quality_controlled":"1","_id":"1187","oa_version":"Submitted Version","article_processing_charge":"No","day":"01","intvolume":"        30","department":[{"_id":"KrPi"}],"article_type":"original","scopus_import":"1","isi":1,"month":"10","doi":"10.1007/s00145-016-9247-3","issue":"4","has_accepted_license":"1","page":"1238 - 1275","related_material":{"record":[{"status":"public","id":"3238","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"file":[{"relation":"main_file","date_created":"2020-05-14T16:30:17Z","file_name":"2017_JournalCrypto_Kiltz.pdf","date_updated":"2020-07-14T12:44:37Z","content_type":"application/pdf","checksum":"c647520d115b772a1682fc06fa273eb1","file_size":516959,"file_id":"7843","creator":"dernst","access_level":"open_access"}],"year":"2017","oa":1,"status":"public","ec_funded":1,"volume":30,"type":"journal_article"},{"type":"conference","publication_identifier":{"isbn":["978-331970499-9"]},"ec_funded":1,"status":"public","volume":10677,"page":"56 - 81","conference":{"name":"TCC: Theory of Cryptography Conference","end_date":"2017-11-15","location":"Baltimore, MD, United States","start_date":"2017-11-12"},"doi":"10.1007/978-3-319-70500-2_3","oa":1,"year":"2017","language":[{"iso":"eng"}],"isi":1,"editor":[{"last_name":"Kalai","first_name":"Yael","full_name":"Kalai, Yael"},{"first_name":"Leonid","last_name":"Reyzin","full_name":"Reyzin, Leonid"}],"month":"11","day":"05","article_processing_charge":"No","oa_version":"Submitted Version","_id":"605","scopus_import":"1","department":[{"_id":"KrPi"}],"alternative_title":["LNCS"],"intvolume":"     10677","publisher":"Springer","publist_id":"7200","citation":{"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.","short":"J. Brody, S. Dziembowski, S. Faust, K.Z. Pietrzak, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 56–81.","mla":"Brody, Joshua, et al. <i>Position Based Cryptography and Multiparty Communication Complexity</i>. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 56–81, doi:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">10.1007/978-3-319-70500-2_3</a>.","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.","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:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">10.1007/978-3-319-70500-2_3</a>","apa":"Brody, J., Dziembowski, S., Faust, S., &#38; Pietrzak, K. Z. (2017). Position based cryptography and multiparty communication complexity. In Y. Kalai &#38; L. Reyzin (Eds.) (Vol. 10677, pp. 56–81). Presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">https://doi.org/10.1007/978-3-319-70500-2_3</a>","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. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">https://doi.org/10.1007/978-3-319-70500-2_3</a>."},"quality_controlled":"1","date_published":"2017-11-05T00:00:00Z","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","main_file_link":[{"url":"https://eprint.iacr.org/2016/536","open_access":"1"}],"date_updated":"2025-09-11T07:36:46Z","abstract":[{"lang":"eng","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."}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"title":"Position based cryptography and multiparty communication complexity","author":[{"full_name":"Brody, Joshua","first_name":"Joshua","last_name":"Brody"},{"last_name":"Dziembowski","first_name":"Stefan","full_name":"Dziembowski, Stefan"},{"full_name":"Faust, Sebastian","last_name":"Faust","first_name":"Sebastian"},{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000739735000003"]},"date_created":"2018-12-11T11:47:27Z"},{"year":"2017","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-70500-2_17","conference":{"name":"TCC: Theory of Cryptography","end_date":"2017-11-15","location":"Baltimore, MD, United States","start_date":"2017-11-12"},"page":"493 - 526","month":"11","editor":[{"last_name":"Kalai","first_name":"Yael","full_name":"Kalai, Yael"},{"full_name":"Reyzin, Leonid","last_name":"Reyzin","first_name":"Leonid"}],"isi":1,"type":"conference","volume":10677,"publication_identifier":{"isbn":["978-331970499-9"]},"status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","date_published":"2017-11-05T00:00:00Z","date_created":"2018-12-11T11:47:28Z","external_id":{"isi":["000739735000017"]},"title":"Moderately hard functions: Definition, instantiations, and applications","author":[{"full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","last_name":"Alwen"},{"full_name":"Tackmann, Björn","first_name":"Björn","last_name":"Tackmann"}],"date_updated":"2025-09-11T07:36:16Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/945"}],"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"}],"scopus_import":"1","intvolume":"     10677","department":[{"_id":"KrPi"}],"alternative_title":["LNCS"],"day":"05","_id":"609","oa_version":"Submitted Version","article_processing_charge":"No","citation":{"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. <i>Moderately Hard Functions: Definition, Instantiations, and Applications</i>. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 493–526, doi:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">10.1007/978-3-319-70500-2_17</a>.","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., &#38; Tackmann, B. (2017). Moderately hard functions: Definition, instantiations, and applications. In Y. Kalai &#38; L. Reyzin (Eds.) (Vol. 10677, pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">https://doi.org/10.1007/978-3-319-70500-2_17</a>","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:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">10.1007/978-3-319-70500-2_17</a>","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. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">https://doi.org/10.1007/978-3-319-70500-2_17</a>."},"quality_controlled":"1","publist_id":"7196","publisher":"Springer"},{"publist_id":"7154","publisher":"Springer","quality_controlled":"1","citation":{"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. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">https://doi.org/10.1007/978-3-319-56617-7_2</a>.","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:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">10.1007/978-3-319-56617-7_2</a>","apa":"Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., &#38; Tessaro, S. (2017). Scrypt is maximally memory hard. In J.-S. Coron &#38; J. Buus Nielsen (Eds.) (Vol. 10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">https://doi.org/10.1007/978-3-319-56617-7_2</a>","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.","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.","mla":"Alwen, Joel F., et al. <i>Scrypt Is Maximally Memory Hard</i>. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">10.1007/978-3-319-56617-7_2</a>.","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."},"oa_version":"Submitted Version","article_processing_charge":"No","_id":"635","day":"01","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"intvolume":"     10212","scopus_import":"1","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"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/989"}],"date_updated":"2025-09-11T07:24:51Z","title":"Scrypt is maximally memory hard","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"last_name":"Chen","first_name":"Binchi","full_name":"Chen, Binchi"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Reyzin, Leonid","last_name":"Reyzin","first_name":"Leonid"},{"full_name":"Tessaro, Stefano","last_name":"Tessaro","first_name":"Stefano"}],"date_created":"2018-12-11T11:47:37Z","external_id":{"isi":["000419175900002"]},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"date_published":"2017-01-01T00:00:00Z","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"status":"public","publication_identifier":{"isbn":["978-331956616-0"]},"volume":10212,"type":"conference","isi":1,"month":"01","editor":[{"last_name":"Coron","first_name":"Jean-Sébastien","full_name":"Coron, Jean-Sébastien"},{"full_name":"Buus Nielsen, Jesper","last_name":"Buus Nielsen","first_name":"Jesper"}],"conference":{"location":"Paris, France","end_date":"2017-05-04","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2017-04-30"},"page":"33 - 62","doi":"10.1007/978-3-319-56617-7_2","language":[{"iso":"eng"}],"oa":1,"year":"2017"},{"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"external_id":{"isi":["000419175900001"]},"date_created":"2018-12-11T11:47:39Z","author":[{"full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","last_name":"Alwen"},{"first_name":"Jeremiah","last_name":"Blocki","full_name":"Blocki, Jeremiah"},{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"}],"title":"Depth-robust graphs and their cumulative memory complexity","date_updated":"2025-09-11T07:21:36Z","main_file_link":[{"url":"https://eprint.iacr.org/2016/875","open_access":"1"}],"abstract":[{"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.","lang":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","date_published":"2017-04-01T00:00:00Z","corr_author":"1","citation":{"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.","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 3–32.","mla":"Alwen, Joel F., et al. <i>Depth-Robust Graphs and Their Cumulative Memory Complexity</i>. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 3–32, doi:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">10.1007/978-3-319-56617-7_1</a>.","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.","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:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">10.1007/978-3-319-56617-7_1</a>","apa":"Alwen, J. F., Blocki, J., &#38; Pietrzak, K. Z. (2017). Depth-robust graphs and their cumulative memory complexity. In J.-S. Coron &#38; J. Buus Nielsen (Eds.) (Vol. 10212, pp. 3–32). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">https://doi.org/10.1007/978-3-319-56617-7_1</a>","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. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">https://doi.org/10.1007/978-3-319-56617-7_1</a>."},"quality_controlled":"1","publisher":"Springer","publist_id":"7148","scopus_import":"1","intvolume":"     10212","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"day":"01","_id":"640","oa_version":"Submitted Version","article_processing_charge":"No","editor":[{"last_name":"Coron","first_name":"Jean-Sébastien","full_name":"Coron, Jean-Sébastien"},{"last_name":"Buus Nielsen","first_name":"Jesper","full_name":"Buus Nielsen, Jesper"}],"month":"04","isi":1,"year":"2017","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-56617-7_1","conference":{"end_date":"2017-05-04","location":"Paris, France","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2017-04-30"},"page":"3 - 32","volume":10212,"publication_identifier":{"isbn":["978-331956616-0"]},"status":"public","ec_funded":1,"type":"conference"},{"date_published":"2017-04-01T00:00:00Z","corr_author":"1","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","main_file_link":[{"url":"https://eprint.iacr.org/2016/1186.pdf","open_access":"1"}],"date_updated":"2025-09-11T07:14:42Z","abstract":[{"lang":"eng","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."}],"title":"On the complexity of breaking pseudoentropy","author":[{"first_name":"Maciej","last_name":"Skórski","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"external_id":{"isi":["000425175500043"]},"date_created":"2018-12-11T11:47:42Z","day":"01","article_processing_charge":"No","oa_version":"Submitted Version","_id":"648","scopus_import":"1","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"intvolume":"     10185","publist_id":"7125","publisher":"Springer","citation":{"chicago":"Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">https://doi.org/10.1007/978-3-319-55911-7_43</a>.","apa":"Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger &#38; S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">https://doi.org/10.1007/978-3-319-55911-7_43</a>","ama":"Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:600-613. doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">10.1007/978-3-319-55911-7_43</a>","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.","mla":"Skórski, Maciej. <i>On the Complexity of Breaking Pseudoentropy</i>. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">10.1007/978-3-319-55911-7_43</a>.","ista":"Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 600–613."},"quality_controlled":"1","page":"600 - 613","conference":{"start_date":"2017-04-20","end_date":"2017-04-22","location":"Bern, Switzerland","name":"TAMC: Theory and Applications of Models of Computation"},"doi":"10.1007/978-3-319-55911-7_43","oa":1,"year":"2017","language":[{"iso":"eng"}],"isi":1,"month":"04","editor":[{"last_name":"Jäger","first_name":"Gerhard","full_name":"Jäger, Gerhard"},{"first_name":"Silvia","last_name":"Steila","full_name":"Steila, Silvia"}],"type":"conference","publication_identifier":{"isbn":["978-331955910-0"]},"status":"public","volume":10185},{"department":[{"_id":"KrPi"}],"scopus_import":1,"oa_version":"Preprint","_id":"6526","day":"09","citation":{"chicago":"Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. IEEE, 2017. <a href=\"https://doi.org/10.1109/isit.2017.8006529\">https://doi.org/10.1109/isit.2017.8006529</a>.","apa":"Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. Aachen, Germany: IEEE. <a href=\"https://doi.org/10.1109/isit.2017.8006529\">https://doi.org/10.1109/isit.2017.8006529</a>","ama":"Skórski M. On the complexity of estimating Rènyi divergences. In: <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. IEEE; 2017. doi:<a href=\"https://doi.org/10.1109/isit.2017.8006529\">10.1109/isit.2017.8006529</a>","short":"M. Skórski, in:, 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, 2017.","mla":"Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>, 8006529, IEEE, 2017, doi:<a href=\"https://doi.org/10.1109/isit.2017.8006529\">10.1109/isit.2017.8006529</a>.","ieee":"M. Skórski, “On the complexity of estimating Rènyi divergences,” in <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>, Aachen, Germany, 2017.","ista":"Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017 IEEE International Symposium on Information Theory (ISIT). ISIT: International Symposium on Information Theory, 8006529."},"quality_controlled":"1","publisher":"IEEE","publication":"2017 IEEE International Symposium on Information Theory (ISIT)","publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","article_number":"8006529","date_published":"2017-08-09T00:00:00Z","author":[{"full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","last_name":"Skórski","first_name":"Maciej"}],"title":"On the complexity of estimating Rènyi divergences","external_id":{"arxiv":["1702.01666"]},"date_created":"2019-06-06T12:53:09Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"abstract":[{"text":"This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.","lang":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1702.01666","open_access":"1"}],"date_updated":"2021-01-12T08:07:53Z","type":"conference","ec_funded":1,"status":"public","publication_identifier":{"isbn":["9781509040964"]},"language":[{"iso":"eng"}],"oa":1,"year":"2017","conference":{"name":"ISIT: International Symposium on Information Theory","location":"Aachen, Germany","end_date":"2017-06-30","start_date":"2017-06-25"},"doi":"10.1109/isit.2017.8006529","month":"08","arxiv":1},{"oa":1,"year":"2017","language":[{"iso":"eng"}],"page":"1001-1017","conference":{"start_date":"2017-10-30","name":"CCS: Conference on Computer and Communications Security","location":"Dallas, TX, USA","end_date":"2017-11-03"},"doi":"10.1145/3133956.3134031","month":"10","isi":1,"type":"conference","publication_identifier":{"isbn":["9781450349468"]},"ec_funded":1,"status":"public","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security","date_published":"2017-10-30T00:00:00Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"}],"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F"},{"full_name":"Blocki, Jeremiah","first_name":"Jeremiah","last_name":"Blocki"},{"full_name":"Harsha, Ben","last_name":"Harsha","first_name":"Ben"}],"title":"Practical graphs for optimal side-channel resistant memory-hard functions","external_id":{"isi":["000440307700063"]},"date_created":"2019-06-06T13:21:29Z","main_file_link":[{"url":"https://eprint.iacr.org/2017/443","open_access":"1"}],"date_updated":"2025-09-18T10:40:38Z","abstract":[{"lang":"eng","text":"A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.\r\n\r\nEssentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called \"depth-robustness\") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.\r\n\r\nIn this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:\r\n*Prove that their depth-robustness is asymptotically maximal.\r\n*Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.\r\n*Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. \r\nWe find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.\r\n\r\nAlong the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).\r\n"}],"scopus_import":"1","department":[{"_id":"KrPi"}],"day":"30","oa_version":"Submitted Version","article_processing_charge":"No","_id":"6527","quality_controlled":"1","citation":{"ista":"Alwen JF, Blocki J, Harsha B. 2017. Practical graphs for optimal side-channel resistant memory-hard functions. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. CCS: Conference on Computer and Communications Security, 1001–1017.","short":"J.F. Alwen, J. Blocki, B. Harsha, in:, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2017, pp. 1001–1017.","mla":"Alwen, Joel F., et al. “Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions.” <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>, ACM, 2017, pp. 1001–17, doi:<a href=\"https://doi.org/10.1145/3133956.3134031\">10.1145/3133956.3134031</a>.","ieee":"J. F. Alwen, J. Blocki, and B. Harsha, “Practical graphs for optimal side-channel resistant memory-hard functions,” in <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>, Dallas, TX, USA, 2017, pp. 1001–1017.","ama":"Alwen JF, Blocki J, Harsha B. Practical graphs for optimal side-channel resistant memory-hard functions. In: <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>. ACM; 2017:1001-1017. doi:<a href=\"https://doi.org/10.1145/3133956.3134031\">10.1145/3133956.3134031</a>","apa":"Alwen, J. F., Blocki, J., &#38; Harsha, B. (2017). Practical graphs for optimal side-channel resistant memory-hard functions. In <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i> (pp. 1001–1017). Dallas, TX, USA: ACM. <a href=\"https://doi.org/10.1145/3133956.3134031\">https://doi.org/10.1145/3133956.3134031</a>","chicago":"Alwen, Joel F, Jeremiah Blocki, and Ben Harsha. “Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions.” In <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>, 1001–17. ACM, 2017. <a href=\"https://doi.org/10.1145/3133956.3134031\">https://doi.org/10.1145/3133956.3134031</a>."},"publisher":"ACM"},{"scopus_import":"1","alternative_title":["LIPIcs"],"department":[{"_id":"KrPi"}],"intvolume":"        80","day":"01","oa_version":"Published Version","article_processing_charge":"No","_id":"697","citation":{"mla":"Pietrzak, Krzysztof Z., and Maciej Skórski. <i>Non Uniform Attacks against Pseudoentropy</i>. Vol. 80, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">10.4230/LIPIcs.ICALP.2017.39</a>.","short":"K.Z. Pietrzak, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"K. Z. Pietrzak and M. Skórski, “Non uniform attacks against pseudoentropy,” presented at the ICALP: Automata, Languages and Programming, Warsaw, Poland, 2017, vol. 80.","ista":"Pietrzak KZ, Skórski M. 2017. Non uniform attacks against pseudoentropy. ICALP: Automata, Languages and Programming, LIPIcs, vol. 80, 39.","chicago":"Pietrzak, Krzysztof Z, and Maciej Skórski. “Non Uniform Attacks against Pseudoentropy,” Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">https://doi.org/10.4230/LIPIcs.ICALP.2017.39</a>.","apa":"Pietrzak, K. Z., &#38; Skórski, M. (2017). Non uniform attacks against pseudoentropy (Vol. 80). Presented at the ICALP: Automata, Languages and Programming, Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">https://doi.org/10.4230/LIPIcs.ICALP.2017.39</a>","ama":"Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2017.39\">10.4230/LIPIcs.ICALP.2017.39</a>"},"quality_controlled":"1","ddc":["005"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publist_id":"7003","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:46Z","date_published":"2017-07-01T00:00:00Z","corr_author":"1","article_number":"39","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"}],"title":"Non uniform attacks against pseudoentropy","author":[{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Maciej","last_name":"Skórski","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej"}],"date_created":"2018-12-11T11:47:59Z","date_updated":"2025-07-10T11:54:07Z","abstract":[{"lang":"eng","text":"De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. "}],"type":"conference","volume":80,"publication_identifier":{"issn":["1868-8969"]},"ec_funded":1,"status":"public","pubrep_id":"893","oa":1,"year":"2017","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"file_name":"IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf","date_updated":"2020-07-14T12:47:46Z","content_type":"application/pdf","checksum":"e95618a001692f1af2d68f5fde43bc1f","file_size":601004,"date_created":"2018-12-12T10:08:40Z","relation":"main_file","access_level":"open_access","creator":"system","file_id":"4701"}],"has_accepted_license":"1","conference":{"start_date":"2017-07-10","location":"Warsaw, Poland","end_date":"2017-07-14","name":"ICALP: Automata, Languages and Programming"},"doi":"10.4230/LIPIcs.ICALP.2017.39","month":"07"},{"date_published":"2017-08-01T00:00:00Z","corr_author":"1","article_number":"20","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:49Z","date_updated":"2025-07-10T11:54:14Z","abstract":[{"lang":"eng","text":"We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha&gt;1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha&gt;1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method. "}],"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"author":[{"last_name":"Obremski","first_name":"Maciej","full_name":"Obremski, Maciej"},{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","last_name":"Skórski","first_name":"Maciej"}],"title":"Renyi entropy estimation revisited","date_created":"2018-12-11T11:48:04Z","day":"01","article_processing_charge":"No","oa_version":"Published Version","_id":"710","scopus_import":"1","department":[{"_id":"KrPi"}],"alternative_title":["LIPIcs"],"intvolume":"        81","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publist_id":"6979","quality_controlled":"1","citation":{"ista":"Obremski M, Skórski M. 2017. Renyi entropy estimation revisited. 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, LIPIcs, vol. 81, 20.","mla":"Obremski, Maciej, and Maciej Skórski. <i>Renyi Entropy Estimation Revisited</i>. Vol. 81, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>.","short":"M. Obremski, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"M. Obremski and M. Skórski, “Renyi entropy estimation revisited,” presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA, 2017, vol. 81.","apa":"Obremski, M., &#38; Skórski, M. (2017). Renyi entropy estimation revisited (Vol. 81). Presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>","ama":"Obremski M, Skórski M. Renyi entropy estimation revisited. In: Vol 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>","chicago":"Obremski, Maciej, and Maciej Skórski. “Renyi Entropy Estimation Revisited,” Vol. 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20\">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20</a>."},"ddc":["005","600"],"has_accepted_license":"1","conference":{"name":"20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX","location":"Berkeley, USA","end_date":"2017-08-18","start_date":"2017-08-18"},"doi":"10.4230/LIPIcs.APPROX-RANDOM.2017.20","oa":1,"year":"2017","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"creator":"system","access_level":"open_access","file_id":"4991","file_size":604813,"content_type":"application/pdf","checksum":"89225c7dcec2c93838458c9102858985","date_updated":"2020-07-14T12:47:49Z","file_name":"IST-2017-888-v1+1_LIPIcs-APPROX-RANDOM-2017-20.pdf","relation":"main_file","date_created":"2018-12-12T10:13:10Z"}],"month":"08","type":"conference","publication_identifier":{"issn":["1868-8969"]},"ec_funded":1,"pubrep_id":"888","status":"public","volume":81},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","date_published":"2017-01-01T00:00:00Z","date_created":"2018-12-11T11:47:38Z","external_id":{"isi":["000438672600005"]},"author":[{"full_name":"Jafargholi, Zahra","last_name":"Jafargholi","first_name":"Zahra"},{"full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","orcid":"0009-0006-6812-7317"},{"first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen"},{"full_name":"Komargodski, Ilan","first_name":"Ilan","last_name":"Komargodski"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wichs, Daniel","first_name":"Daniel","last_name":"Wichs"}],"title":"Be adaptive avoid overcommitting","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"abstract":[{"lang":"eng","text":"For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). 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 that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs."}],"date_updated":"2026-04-08T07:01:44Z","main_file_link":[{"url":"https://eprint.iacr.org/2017/515","open_access":"1"}],"intvolume":"     10401","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"scopus_import":"1","_id":"637","oa_version":"Submitted Version","article_processing_charge":"No","day":"01","quality_controlled":"1","citation":{"ista":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401, 133–163.","ieee":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak, and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.","mla":"Jafargholi, Zahra, et al. <i>Be Adaptive Avoid Overcommitting</i>. Edited by Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:<a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">10.1007/978-3-319-63688-7_5</a>.","short":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak, D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163.","apa":"Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak, K. Z., &#38; Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz &#38; H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">https://doi.org/10.1007/978-3-319-63688-7_5</a>","ama":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer; 2017:133-163. doi:<a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">10.1007/978-3-319-63688-7_5</a>","chicago":"Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski, Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">https://doi.org/10.1007/978-3-319-63688-7_5</a>."},"publisher":"Springer","publist_id":"7151","language":[{"iso":"eng"}],"year":"2017","oa":1,"doi":"10.1007/978-3-319-63688-7_5","page":"133 - 163","related_material":{"record":[{"id":"10035","status":"public","relation":"dissertation_contains"}]},"conference":{"start_date":"2017-07-20","name":"CRYPTO: Cryptology","end_date":"2017-07-24","location":"Santa Barbara, CA, United States"},"editor":[{"first_name":"Jonathan","last_name":"Katz","full_name":"Katz, Jonathan"},{"full_name":"Shacham, Hovav","last_name":"Shacham","first_name":"Hovav"}],"month":"01","isi":1,"type":"conference","volume":10401,"status":"public","ec_funded":1,"publication_identifier":{"isbn":["978-331963687-0"]}},{"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","date_published":"2017-11-18T00:00:00Z","title":"Beyond Hellman’s time-memory trade-offs with applications to proofs of space","author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","full_name":"Abusalah, Hamza M","first_name":"Hamza M","last_name":"Abusalah"},{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"first_name":"Bram","last_name":"Cohen","full_name":"Cohen, Bram"},{"full_name":"Khilko, Danylo","last_name":"Khilko","first_name":"Danylo"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Reyzin","first_name":"Leonid","full_name":"Reyzin, Leonid"}],"date_created":"2018-12-11T11:47:10Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"abstract":[{"lang":"eng","text":"Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2)."}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/893.pdf"}],"date_updated":"2026-04-08T14:10:21Z","department":[{"_id":"KrPi"}],"alternative_title":["LNCS"],"intvolume":"     10625","scopus_import":1,"oa_version":"Submitted Version","_id":"559","day":"18","citation":{"chicago":"Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space,” 10625:357–79. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-70697-9_13\">https://doi.org/10.1007/978-3-319-70697-9_13</a>.","apa":"Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., &#38; Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China: Springer. <a href=\"https://doi.org/10.1007/978-3-319-70697-9_13\">https://doi.org/10.1007/978-3-319-70697-9_13</a>","ama":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer; 2017:357-379. doi:<a href=\"https://doi.org/10.1007/978-3-319-70697-9_13\">10.1007/978-3-319-70697-9_13</a>","short":"H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379.","mla":"Abusalah, Hamza M., et al. <i>Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space</i>. Vol. 10625, Springer, 2017, pp. 357–79, doi:<a href=\"https://doi.org/10.1007/978-3-319-70697-9_13\">10.1007/978-3-319-70697-9_13</a>.","ieee":"H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.","ista":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625, 357–379."},"quality_controlled":"1","publisher":"Springer","publist_id":"7257","language":[{"iso":"eng"}],"oa":1,"year":"2017","page":"357 - 379","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"83"}]},"conference":{"name":"ASIACRYPT: Theory and Applications of Cryptology and Information Security","end_date":"2017-12-07","location":"Hong Kong, China","start_date":"2017-12-03"},"doi":"10.1007/978-3-319-70697-9_13","month":"11","type":"conference","volume":10625,"ec_funded":1,"status":"public","publication_identifier":{"isbn":["978-331970696-2"]}},{"file":[{"file_id":"4799","creator":"system","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:10:13Z","file_size":847400,"content_type":"application/pdf","checksum":"ff8639ec4bded6186f44c7bd3ee26804","file_name":"IST-2017-828-v1+3_2017_Rybar_thesis.pdf","date_updated":"2020-07-14T12:48:12Z"},{"file_id":"6202","creator":"dernst","access_level":"closed","relation":"source_file","date_created":"2019-04-05T08:24:11Z","checksum":"3462101745ce8ad199c2d0f75dae4a7e","file_size":26054879,"content_type":"application/zip","date_updated":"2020-07-14T12:48:12Z","file_name":"2017_Thesis_Rybar_source.zip"}],"language":[{"iso":"eng"}],"year":"2017","oa":1,"doi":"10.15479/AT:ISTA:th_828","page":"86","has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"2082","relation":"part_of_dissertation"},{"id":"6196","status":"public","relation":"part_of_dissertation"}]},"month":"06","type":"dissertation","degree_awarded":"PhD","OA_place":"publisher","status":"public","pubrep_id":"828","publication_identifier":{"issn":["2663-337X"]},"file_date_updated":"2020-07-14T12:48:12Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","corr_author":"1","date_published":"2017-06-26T00:00:00Z","date_created":"2018-12-11T11:48:46Z","title":"(The exact security of) Message authentication codes","author":[{"id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","full_name":"Rybar, Michal","last_name":"Rybar","first_name":"Michal"}],"abstract":[{"text":"In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k &gt; 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. ","lang":"eng"}],"date_updated":"2026-04-08T14:18:39Z","department":[{"_id":"KrPi"}],"alternative_title":["ISTA Thesis"],"_id":"838","oa_version":"Published Version","article_processing_charge":"No","day":"26","ddc":["000"],"citation":{"ieee":"M. Rybar, “(The exact security of) Message authentication codes,” Institute of Science and Technology Austria, 2017.","short":"M. Rybar, (The Exact Security of) Message Authentication Codes, Institute of Science and Technology Austria, 2017.","mla":"Rybar, Michal. <i>(The Exact Security of) Message Authentication Codes</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">10.15479/AT:ISTA:th_828</a>.","ista":"Rybar M. 2017. (The exact security of) Message authentication codes. Institute of Science and Technology Austria.","chicago":"Rybar, Michal. “(The Exact Security of) Message Authentication Codes.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">https://doi.org/10.15479/AT:ISTA:th_828</a>.","apa":"Rybar, M. (2017). <i>(The exact security of) Message authentication codes</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">https://doi.org/10.15479/AT:ISTA:th_828</a>","ama":"Rybar M. (The exact security of) Message authentication codes. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_828\">10.15479/AT:ISTA:th_828</a>"},"publisher":"Institute of Science and Technology Austria","publist_id":"6810"},{"quality_controlled":"1","citation":{"ama":"Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. <i>IACR Transactions on Symmetric Cryptology</i>. 2017;2016(2):145-161. doi:<a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">10.13154/TOSC.V2016.I2.145-161</a>","apa":"Gazi, P., Pietrzak, K. Z., &#38; Rybar, M. (2017). The exact security of PMAC. <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum. <a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>","chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum, 2017. <a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>.","ista":"Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161.","mla":"Gazi, Peter, et al. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:<a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">10.13154/TOSC.V2016.I2.145-161</a>.","short":"P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161.","ieee":"P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” <i>IACR Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2. Ruhr University Bochum, pp. 145–161, 2017."},"ddc":["000"],"publisher":"Ruhr University Bochum","department":[{"_id":"KrPi"}],"intvolume":"      2016","day":"03","oa_version":"Published Version","_id":"6196","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"title":"The exact security of PMAC","author":[{"last_name":"Gazi","first_name":"Peter","full_name":"Gazi, Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"last_name":"Rybar","first_name":"Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","full_name":"Rybar, Michal"}],"date_created":"2019-04-04T13:48:23Z","date_updated":"2026-04-08T14:18:39Z","abstract":[{"lang":"eng","text":"PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of  Ο(σ2/2n), while the currently best bound is  Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith block is computed as τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of γi’s which contains a large coset of a subgroup of GF(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem."}],"publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:24Z","publication":"IACR Transactions on Symmetric Cryptology","date_published":"2017-02-03T00:00:00Z","volume":2016,"publication_identifier":{"eissn":["2519-173X"]},"ec_funded":1,"status":"public","type":"journal_article","month":"02","oa":1,"year":"2017","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"creator":"dernst","access_level":"open_access","file_id":"6197","content_type":"application/pdf","checksum":"f23161d685dd957ae8d7274132999684","file_size":597335,"date_updated":"2020-07-14T12:47:24Z","file_name":"2017_IACR_Gazi.pdf","relation":"main_file","date_created":"2019-04-04T13:53:58Z"}],"related_material":{"record":[{"status":"public","id":"838","relation":"dissertation_contains"}]},"page":"145-161","has_accepted_license":"1","issue":"2","doi":"10.13154/TOSC.V2016.I2.145-161"},{"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","corr_author":"1","date_published":"2017-01-01T00:00:00Z","external_id":{"isi":["000425175500042"]},"date_created":"2018-12-11T11:47:42Z","author":[{"first_name":"Maciej","last_name":"Skórski","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"title":"A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds","abstract":[{"text":"In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy.","lang":"eng"}],"date_updated":"2026-04-16T09:59:38Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/965.pdf"}],"intvolume":"     10185","alternative_title":["LNCS"],"department":[{"_id":"KrPi"}],"scopus_import":"1","_id":"650","article_processing_charge":"No","oa_version":"Submitted Version","day":"01","quality_controlled":"1","citation":{"ama":"Skórski M. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:586-599. doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">10.1007/978-3-319-55911-7_42</a>","apa":"Skórski, M. (2017). A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In G. Jäger &#38; S. Steila (Eds.) (Vol. 10185, pp. 586–599). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">https://doi.org/10.1007/978-3-319-55911-7_42</a>","chicago":"Skórski, Maciej. “A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds.” edited by Gerhard Jäger and Silvia Steila, 10185:586–99. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">https://doi.org/10.1007/978-3-319-55911-7_42</a>.","ista":"Skórski M. 2017. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 586–599.","short":"M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 586–599.","mla":"Skórski, Maciej. <i>A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds</i>. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 586–99, doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">10.1007/978-3-319-55911-7_42</a>.","ieee":"M. Skórski, “A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 586–599."},"publist_id":"7119","publisher":"Springer","language":[{"iso":"eng"}],"year":"2017","oa":1,"doi":"10.1007/978-3-319-55911-7_42","page":"586 - 599","conference":{"end_date":"2017-04-22","location":"Bern, Switzerland","name":"TAMC: Theory and Applications of Models of Computation","start_date":"2017-04-20"},"month":"01","editor":[{"full_name":"Jäger, Gerhard","first_name":"Gerhard","last_name":"Jäger"},{"last_name":"Steila","first_name":"Silvia","full_name":"Steila, Silvia"}],"isi":1,"type":"conference","volume":10185,"status":"public","publication_identifier":{"issn":["0302-9743"]}}]