[{"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session Security: Password-Based Cryptography Revisited.” Journal of Computer Security. IOS Press, 2019. https://doi.org/10.3233/JCS-181131.","ista":"Demay G, Gazi P, Maurer U, Tackmann B. 2019. Per-session security: Password-based cryptography revisited. Journal of Computer Security. 27(1), 75–111.","mla":"Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography Revisited.” Journal of Computer Security, vol. 27, no. 1, IOS Press, 2019, pp. 75–111, doi:10.3233/JCS-181131.","ama":"Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based cryptography revisited. Journal of Computer Security. 2019;27(1):75-111. doi:10.3233/JCS-181131","apa":"Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2019). Per-session security: Password-based cryptography revisited. Journal of Computer Security. IOS Press. https://doi.org/10.3233/JCS-181131","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27 (2019) 75–111.","ieee":"G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based cryptography revisited,” Journal of Computer Security, vol. 27, no. 1. IOS Press, pp. 75–111, 2019."},"title":"Per-session security: Password-based cryptography revisited","author":[{"full_name":"Demay, Gregory","last_name":"Demay","first_name":"Gregory"},{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Gazi, Peter","last_name":"Gazi"},{"first_name":"Ueli","last_name":"Maurer","full_name":"Maurer, Ueli"},{"full_name":"Tackmann, Bjorn","last_name":"Tackmann","first_name":"Bjorn"}],"article_processing_charge":"No","publisher":"IOS Press","quality_controlled":"1","oa":1,"day":"1","publication":"Journal of Computer Security","year":"2019","date_published":"2019-01-01T00:00:00Z","doi":"10.3233/JCS-181131","date_created":"2019-01-27T22:59:10Z","page":"75-111","_id":"5887","status":"public","article_type":"original","type":"journal_article","date_updated":"2021-01-12T08:05:08Z","department":[{"_id":"KrPi"}],"oa_version":"Preprint","abstract":[{"text":"Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved.","lang":"eng"}],"month":"01","intvolume":" 27","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/166"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0926227X"]},"publication_status":"published","volume":27,"issue":"1","ec_funded":1},{"title":"SpaceMint: A cryptocurrency based on proofs of space","author":[{"last_name":"Park","full_name":"Park, Sunoo","first_name":"Sunoo"},{"full_name":"Kwon, Albert","last_name":"Kwon","first_name":"Albert"},{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer"},{"first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","last_name":"Gazi","full_name":"Gazi, Peter"},{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"external_id":{"isi":["000540656400026"]},"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Park, Sunoo, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joel F Alwen, and Krzysztof Z Pietrzak. “SpaceMint: A Cryptocurrency Based on Proofs of Space.” In 22nd International Conference on Financial Cryptography and Data Security, 10957:480–99. Springer Nature, 2018. https://doi.org/10.1007/978-3-662-58387-6_26.","ista":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. 2018. SpaceMint: A cryptocurrency based on proofs of space. 22nd International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 10957, 480–499.","mla":"Park, Sunoo, et al. “SpaceMint: A Cryptocurrency Based on Proofs of Space.” 22nd International Conference on Financial Cryptography and Data Security, vol. 10957, Springer Nature, 2018, pp. 480–99, doi:10.1007/978-3-662-58387-6_26.","apa":"Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J. F., & Pietrzak, K. Z. (2018). SpaceMint: A cryptocurrency based on proofs of space. In 22nd International Conference on Financial Cryptography and Data Security (Vol. 10957, pp. 480–499). Nieuwpoort, Curacao: Springer Nature. https://doi.org/10.1007/978-3-662-58387-6_26","ama":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. SpaceMint: A cryptocurrency based on proofs of space. In: 22nd International Conference on Financial Cryptography and Data Security. Vol 10957. Springer Nature; 2018:480-499. doi:10.1007/978-3-662-58387-6_26","short":"S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J.F. Alwen, K.Z. Pietrzak, in:, 22nd International Conference on Financial Cryptography and Data Security, Springer Nature, 2018, pp. 480–499.","ieee":"S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J. F. Alwen, and K. Z. Pietrzak, “SpaceMint: A cryptocurrency based on proofs of space,” in 22nd International Conference on Financial Cryptography and Data Security, Nieuwpoort, Curacao, 2018, vol. 10957, pp. 480–499."},"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"date_published":"2018-12-07T00:00:00Z","doi":"10.1007/978-3-662-58387-6_26","date_created":"2019-10-14T06:35:38Z","page":"480-499","day":"07","publication":"22nd International Conference on Financial Cryptography and Data Security","isi":1,"year":"2018","publisher":"Springer Nature","quality_controlled":"1","oa":1,"department":[{"_id":"KrPi"}],"date_updated":"2023-09-19T15:02:13Z","status":"public","type":"conference","conference":{"name":"FC: Financial Cryptography and Data Security","start_date":"2018-02-26","location":"Nieuwpoort, Curacao","end_date":"2018-03-02"},"_id":"6941","volume":10957,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783662583869","9783662583876"],"issn":["0302-9743"]},"publication_status":"published","month":"12","intvolume":" 10957","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2015/528","open_access":"1"}],"oa_version":"Submitted Version","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."}]},{"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"author":[{"first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","full_name":"Gazi, Peter","last_name":"Gazi"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"last_name":"Rybar","full_name":"Rybar, Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}],"title":"The exact security of PMAC","citation":{"ista":"Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161.","chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology. Ruhr University Bochum, 2017. https://doi.org/10.13154/TOSC.V2016.I2.145-161.","ama":"Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2017;2016(2):145-161. doi:10.13154/TOSC.V2016.I2.145-161","apa":"Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC. IACR Transactions on Symmetric Cryptology. Ruhr University Bochum. https://doi.org/10.13154/TOSC.V2016.I2.145-161","ieee":"P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2. Ruhr University Bochum, pp. 145–161, 2017.","short":"P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161.","mla":"Gazi, Peter, et al. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:10.13154/TOSC.V2016.I2.145-161."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"publisher":"Ruhr University Bochum","quality_controlled":"1","page":"145-161","date_created":"2019-04-04T13:48:23Z","doi":"10.13154/TOSC.V2016.I2.145-161","date_published":"2017-02-03T00:00:00Z","year":"2017","has_accepted_license":"1","publication":"IACR Transactions on Symmetric Cryptology","day":"03","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","status":"public","_id":"6196","file_date_updated":"2020-07-14T12:47:24Z","department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T12:02:27Z","ddc":["000"],"intvolume":" 2016","month":"02","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."}],"oa_version":"Published Version","ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"838"}]},"volume":2016,"issue":"2","publication_status":"published","publication_identifier":{"eissn":["2519-173X"]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"f23161d685dd957ae8d7274132999684","file_id":"6197","creator":"dernst","date_updated":"2020-07-14T12:47:24Z","file_size":597335,"date_created":"2019-04-04T13:53:58Z","file_name":"2017_IACR_Gazi.pdf"}]},{"author":[{"first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","full_name":"Gazi, Peter","last_name":"Gazi"},{"full_name":"Tessaro, Stefano","last_name":"Tessaro","first_name":"Stefano"}],"publist_id":"5872","title":"Provably robust sponge-based PRNGs and KDFs","citation":{"chicago":"Gazi, Peter, and Stefano Tessaro. “Provably Robust Sponge-Based PRNGs and KDFs,” 9665:87–116. Springer, 2016. https://doi.org/10.1007/978-3-662-49890-3_4.","ista":"Gazi P, Tessaro S. 2016. Provably robust sponge-based PRNGs and KDFs. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9665, 87–116.","mla":"Gazi, Peter, and Stefano Tessaro. Provably Robust Sponge-Based PRNGs and KDFs. Vol. 9665, Springer, 2016, pp. 87–116, doi:10.1007/978-3-662-49890-3_4.","ama":"Gazi P, Tessaro S. Provably robust sponge-based PRNGs and KDFs. In: Vol 9665. Springer; 2016:87-116. doi:10.1007/978-3-662-49890-3_4","apa":"Gazi, P., & Tessaro, S. (2016). Provably robust sponge-based PRNGs and KDFs (Vol. 9665, pp. 87–116). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-662-49890-3_4","ieee":"P. Gazi and S. Tessaro, “Provably robust sponge-based PRNGs and KDFs,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9665, pp. 87–116.","short":"P. Gazi, S. Tessaro, in:, Springer, 2016, pp. 87–116."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"page":"87 - 116","date_created":"2018-12-11T11:51:36Z","date_published":"2016-05-01T00:00:00Z","doi":"10.1007/978-3-662-49890-3_4","year":"2016","day":"01","oa":1,"quality_controlled":"1","publisher":"Springer","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T06:50:11Z","conference":{"start_date":"2016-05-08","end_date":"2016-05-12","location":"Vienna, Austria","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"type":"conference","status":"public","_id":"1366","ec_funded":1,"volume":9665,"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/169/20160219:201940"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9665","month":"05","abstract":[{"text":"We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed. We propose a seeded variant of Bertoni et al.’s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation. As a further application of our techniques, we also present an efficient sponge-based key-derivation function (which can be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.","lang":"eng"}],"oa_version":"Preprint"},{"oa":1,"quality_controlled":"1","publisher":"Springer","year":"2015","day":"01","page":"159 - 180","date_created":"2018-12-11T11:53:13Z","date_published":"2015-01-01T00:00:00Z","doi":"10.1007/978-3-319-17470-9_10","project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"citation":{"ista":"Demay G, Gazi P, Maurer U, Tackmann B. 2015. Query-complexity amplification for random oracles. ICITS: International Conference on Information Theoretic Security, LNCS, vol. 9063, 159–180.","chicago":"Demay, Grégory, Peter Gazi, Ueli Maurer, and Björn Tackmann. “Query-Complexity Amplification for Random Oracles,” 9063:159–80. Springer, 2015. https://doi.org/10.1007/978-3-319-17470-9_10.","apa":"Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2015). Query-complexity amplification for random oracles (Vol. 9063, pp. 159–180). Presented at the ICITS: International Conference on Information Theoretic Security, Lugano, Switzerland: Springer. https://doi.org/10.1007/978-3-319-17470-9_10","ama":"Demay G, Gazi P, Maurer U, Tackmann B. Query-complexity amplification for random oracles. In: Vol 9063. Springer; 2015:159-180. doi:10.1007/978-3-319-17470-9_10","ieee":"G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Query-complexity amplification for random oracles,” presented at the ICITS: International Conference on Information Theoretic Security, Lugano, Switzerland, 2015, vol. 9063, pp. 159–180.","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, Springer, 2015, pp. 159–180.","mla":"Demay, Grégory, et al. Query-Complexity Amplification for Random Oracles. Vol. 9063, Springer, 2015, pp. 159–80, doi:10.1007/978-3-319-17470-9_10."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Demay","full_name":"Demay, Grégory","first_name":"Grégory"},{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Gazi","full_name":"Gazi, Peter"},{"last_name":"Maurer","full_name":"Maurer, Ueli","first_name":"Ueli"},{"last_name":"Tackmann","full_name":"Tackmann, Björn","first_name":"Björn"}],"publist_id":"5507","title":"Query-complexity amplification for random oracles","abstract":[{"text":"Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem. This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r < R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter c.","lang":"eng"}],"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2015/315"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9063","month":"01","publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"volume":9063,"_id":"1644","conference":{"name":"ICITS: International Conference on Information Theoretic Security","start_date":"2015-05-02","location":"Lugano, Switzerland","end_date":"2015-05-05"},"type":"conference","status":"public","date_updated":"2021-01-12T06:52:13Z","department":[{"_id":"KrPi"}]},{"_id":"1645","article_number":"7133163","type":"conference","conference":{"name":"ITW 2015: IEEE Information Theory Workshop","start_date":"2015-04-26","end_date":"2015-05-01","location":"Jerusalem, Israel"},"project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"status":"public","date_updated":"2021-01-12T06:52:13Z","citation":{"apa":"Gazi, P., & Tessaro, S. (2015). Secret-key cryptography from ideal primitives: A systematic verview. In 2015 IEEE Information Theory Workshop. Jerusalem, Israel: IEEE. https://doi.org/10.1109/ITW.2015.7133163","ama":"Gazi P, Tessaro S. Secret-key cryptography from ideal primitives: A systematic verview. In: 2015 IEEE Information Theory Workshop. IEEE; 2015. doi:10.1109/ITW.2015.7133163","ieee":"P. Gazi and S. Tessaro, “Secret-key cryptography from ideal primitives: A systematic verview,” in 2015 IEEE Information Theory Workshop, Jerusalem, Israel, 2015.","short":"P. Gazi, S. Tessaro, in:, 2015 IEEE Information Theory Workshop, IEEE, 2015.","mla":"Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal Primitives: A Systematic Verview.” 2015 IEEE Information Theory Workshop, 7133163, IEEE, 2015, doi:10.1109/ITW.2015.7133163.","ista":"Gazi P, Tessaro S. 2015. Secret-key cryptography from ideal primitives: A systematic verview. 2015 IEEE Information Theory Workshop. ITW 2015: IEEE Information Theory Workshop, 7133163.","chicago":"Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal Primitives: A Systematic Verview.” In 2015 IEEE Information Theory Workshop. IEEE, 2015. https://doi.org/10.1109/ITW.2015.7133163."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","full_name":"Gazi, Peter","last_name":"Gazi"},{"first_name":"Stefano","last_name":"Tessaro","full_name":"Tessaro, Stefano"}],"publist_id":"5506","department":[{"_id":"KrPi"}],"title":"Secret-key cryptography from ideal primitives: A systematic verview","abstract":[{"lang":"eng","text":"Secret-key constructions are often proved secure in a model where one or more underlying components are replaced by an idealized oracle accessible to the attacker. This model gives rise to information-theoretic security analyses, and several advances have been made in this area over the last few years. This paper provides a systematic overview of what is achievable in this model, and how existing works fit into this view."}],"oa_version":"None","publisher":"IEEE","quality_controlled":"1","scopus_import":1,"month":"06","year":"2015","publication_status":"published","day":"24","publication":"2015 IEEE Information Theory Workshop","language":[{"iso":"eng"}],"doi":"10.1109/ITW.2015.7133163","date_published":"2015-06-24T00:00:00Z","ec_funded":1,"date_created":"2018-12-11T11:53:13Z"},{"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9453","month":"12","abstract":[{"text":"HMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box.\r\n\r\nGeneric security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question.\r\n\r\nIn this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing.\r\n\r\nWhile our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions. ","lang":"eng"}],"oa_version":"Submitted Version","ec_funded":1,"volume":9453,"publication_status":"published","language":[{"iso":"eng"}],"file":[{"file_name":"IST-2016-676-v1+1_881.pdf","date_created":"2018-12-12T10:09:09Z","file_size":512071,"date_updated":"2020-07-14T12:45:08Z","creator":"system","file_id":"4732","checksum":"d1e53203db2d8573a560995ccdffac62","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"conference":{"start_date":"2015-11-29","location":"Auckland, New Zealand","end_date":"2015-12-03","name":"ASIACRYPT: Theory and Application of Cryptology and Information Security"},"type":"conference","pubrep_id":"676","status":"public","_id":"1654","series_title":"Lecture Notes in Computer Science","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:45:08Z","date_updated":"2021-01-12T06:52:16Z","ddc":["004","005"],"oa":1,"publisher":"Springer","quality_controlled":"1","page":"85 - 109","date_created":"2018-12-11T11:53:17Z","date_published":"2015-12-30T00:00:00Z","doi":"10.1007/978-3-662-48800-3_4","year":"2015","has_accepted_license":"1","day":"30","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography"}],"publist_id":"5496","author":[{"full_name":"Gazi, Peter","last_name":"Gazi","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"full_name":"Tessaro, Stefano","last_name":"Tessaro","first_name":"Stefano"}],"title":"Generic security of NMAC and HMAC with input whitening","citation":{"short":"P. Gazi, K.Z. Pietrzak, S. Tessaro, 9453 (2015) 85–109.","ieee":"P. Gazi, K. Z. Pietrzak, and S. Tessaro, “Generic security of NMAC and HMAC with input whitening,” vol. 9453. Springer, pp. 85–109, 2015.","apa":"Gazi, P., Pietrzak, K. Z., & Tessaro, S. (2015). Generic security of NMAC and HMAC with input whitening. Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Auckland, New Zealand: Springer. https://doi.org/10.1007/978-3-662-48800-3_4","ama":"Gazi P, Pietrzak KZ, Tessaro S. Generic security of NMAC and HMAC with input whitening. 2015;9453:85-109. doi:10.1007/978-3-662-48800-3_4","mla":"Gazi, Peter, et al. Generic Security of NMAC and HMAC with Input Whitening. Vol. 9453, Springer, 2015, pp. 85–109, doi:10.1007/978-3-662-48800-3_4.","ista":"Gazi P, Pietrzak KZ, Tessaro S. 2015. Generic security of NMAC and HMAC with input whitening. 9453, 85–109.","chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “Generic Security of NMAC and HMAC with Input Whitening.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-48800-3_4."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"title":"The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC","author":[{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Gazi, Peter","last_name":"Gazi"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Tessaro, Stefano","last_name":"Tessaro","first_name":"Stefano"}],"publist_id":"5478","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Gazi P, Pietrzak KZ, Tessaro S. 2015. The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC. CRYPTO: International Cryptology Conference, LNCS, vol. 9215, 368–387.","chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC,” 9215:368–87. Springer, 2015. https://doi.org/10.1007/978-3-662-47989-6_18.","ama":"Gazi P, Pietrzak KZ, Tessaro S. The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC. In: Vol 9215. Springer; 2015:368-387. doi:10.1007/978-3-662-47989-6_18","apa":"Gazi, P., Pietrzak, K. Z., & Tessaro, S. (2015). The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC (Vol. 9215, pp. 368–387). Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-47989-6_18","short":"P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.","ieee":"P. Gazi, K. Z. Pietrzak, and S. Tessaro, “The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9215, pp. 368–387.","mla":"Gazi, Peter, et al. The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC. Vol. 9215, Springer, 2015, pp. 368–87, doi:10.1007/978-3-662-47989-6_18."},"project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"date_created":"2018-12-11T11:53:23Z","doi":"10.1007/978-3-662-47989-6_18","date_published":"2015-08-01T00:00:00Z","page":"368 - 387","day":"01","year":"2015","has_accepted_license":"1","oa":1,"publisher":"Springer","quality_controlled":"1","file_date_updated":"2020-07-14T12:45:11Z","department":[{"_id":"KrPi"}],"ddc":["004","005"],"date_updated":"2021-01-12T06:52:25Z","pubrep_id":"673","status":"public","conference":{"name":"CRYPTO: International Cryptology Conference","location":"Santa Barbara, CA, United States","end_date":"2015-08-20","start_date":"2015-08-16"},"type":"conference","_id":"1671","ec_funded":1,"volume":9215,"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"17d854227b3b753fd34f5d29e5b5a32e","file_id":"4827","creator":"system","file_size":592296,"date_updated":"2020-07-14T12:45:11Z","file_name":"IST-2016-673-v1+1_053.pdf","date_created":"2018-12-12T10:10:38Z"}],"publication_status":"published","intvolume":" 9215","month":"08","scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"This paper studies the concrete security of PRFs and MACs obtained by keying hash functions based on the sponge paradigm. One such hash function is KECCAK, selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC, the exact security of keyed sponges is not well understood. Indeed, recent security analyses delivered concrete security bounds which are far from existing attacks. This paper aims to close this gap. We prove (nearly) exact bounds on the concrete PRF security of keyed sponges using a random permutation. These bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output length; and for l ≤ q queries (to the construction or the underlying permutation). Moreover, we also improve standard-model bounds. As an intermediate step of independent interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction, which operates as plain CBC-MAC, but only returns a prefix of the output."}]},{"series_title":"Lecture Notes in Computer Science","_id":"1668","type":"conference","conference":{"name":"FSE: Fast Software Encryption","location":"Istanbul, Turkey","end_date":"2015-03-11","start_date":"2015-03-08"},"status":"public","date_updated":"2020-08-11T10:09:26Z","department":[{"_id":"KrPi"}],"abstract":[{"lang":"eng","text":"We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number qe of queries to the underlying ideal block cipher, representing adversary’s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number qc of plaintext/ciphertext pairs that is less than the entire codebook. For any such qc, we aim to determine the highest number of block-cipher queries qe the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.\r\nMore concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and κ-bit keys:\r\nPlain cascades of length ℓ=2r+1 are secure whenever qcqre≪2r(κ+n), qc≪2κ and qe≪22κ. The bound for r=1 also applies to two-key triple encryption (as used within Triple DES).\r\nThe r-round XOR-cascade is secure as long as qcqre≪2r(κ+n), matching an attack by Gaži (CRYPTO 2013).\r\nWe fully characterize the security of Gaži and Tessaro’s two-call "}],"oa_version":"Submitted Version","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2015/397"}],"month":"08","intvolume":" 9054","publication_status":"published","language":[{"iso":"eng"}],"volume":9054,"ec_funded":1,"project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"citation":{"chicago":"Gazi, Peter, Jooyoung Lee, Yannick Seurin, John Steinberger, and Stefano Tessaro. “Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-48116-5_16.","ista":"Gazi P, Lee J, Seurin Y, Steinberger J, Tessaro S. 2015. Relaxing full-codebook security: A refined analysis of key-length extension schemes. 9054, 319–341.","mla":"Gazi, Peter, et al. Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes. Vol. 9054, Springer, 2015, pp. 319–41, doi:10.1007/978-3-662-48116-5_16.","apa":"Gazi, P., Lee, J., Seurin, Y., Steinberger, J., & Tessaro, S. (2015). Relaxing full-codebook security: A refined analysis of key-length extension schemes. Presented at the FSE: Fast Software Encryption, Istanbul, Turkey: Springer. https://doi.org/10.1007/978-3-662-48116-5_16","ama":"Gazi P, Lee J, Seurin Y, Steinberger J, Tessaro S. Relaxing full-codebook security: A refined analysis of key-length extension schemes. 2015;9054:319-341. doi:10.1007/978-3-662-48116-5_16","ieee":"P. Gazi, J. Lee, Y. Seurin, J. Steinberger, and S. Tessaro, “Relaxing full-codebook security: A refined analysis of key-length extension schemes,” vol. 9054. Springer, pp. 319–341, 2015.","short":"P. Gazi, J. Lee, Y. Seurin, J. Steinberger, S. Tessaro, 9054 (2015) 319–341."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Gazi","full_name":"Gazi, Peter"},{"first_name":"Jooyoung","last_name":"Lee","full_name":"Lee, Jooyoung"},{"last_name":"Seurin","full_name":"Seurin, Yannick","first_name":"Yannick"},{"first_name":"John","last_name":"Steinberger","full_name":"Steinberger, John"},{"full_name":"Tessaro, Stefano","last_name":"Tessaro","first_name":"Stefano"}],"publist_id":"5481","title":"Relaxing full-codebook security: A refined analysis of key-length extension schemes","publisher":"Springer","quality_controlled":"1","oa":1,"year":"2015","day":"12","page":"319 - 341","doi":"10.1007/978-3-662-48116-5_16","date_published":"2015-08-12T00:00:00Z","date_created":"2018-12-11T11:53:22Z"},{"month":"01","publisher":"IEEE","quality_controlled":"1","scopus_import":1,"main_file_link":[{"url":"https://eprint.iacr.org/2014/299","open_access":"1"}],"oa":1,"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"Most cryptographic security proofs require showing that two systems are indistinguishable. A central tool in such proofs is that of a game, where winning the game means provoking a certain condition, and it is shown that the two systems considered cannot be distinguished unless this condition is provoked. Upper bounding the probability of winning such a game, i.e., provoking this condition, for an arbitrary strategy is usually hard, except in the special case where the best strategy for winning such a game is known to be non-adaptive. A sufficient criterion for ensuring the optimality of non-adaptive strategies is that of conditional equivalence to a system, a notion introduced in [1]. In this paper, we show that this criterion is not necessary to ensure the optimality of non-adaptive strategies by giving two results of independent interest: 1) the optimality of non-adaptive strategies is not preserved under parallel composition; 2) in contrast, conditional equivalence is preserved under parallel composition."}],"date_published":"2014-01-01T00:00:00Z","doi":"10.1109/ISIT.2014.6875125","date_created":"2018-12-11T11:54:39Z","day":"01","language":[{"iso":"eng"}],"publication":"IEEE International Symposium on Information Theory","year":"2014","publication_status":"published","status":"public","type":"conference","conference":{"name":"IEEE International Symposium on Information Theory Proceedings","start_date":"2014-06-29","location":"Honolulu, USA","end_date":"2014-07-04"},"article_number":"6875125","_id":"1907","title":"Optimality of non-adaptive strategies: The case of parallel games","department":[{"_id":"KrPi"}],"publist_id":"5188","author":[{"first_name":"Grégory","last_name":"Demay","full_name":"Demay, Grégory"},{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Gazi, Peter","last_name":"Gazi"},{"first_name":"Ueli","last_name":"Maurer","full_name":"Maurer, Ueli"},{"first_name":"Björn","last_name":"Tackmann","full_name":"Tackmann, Björn"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:53:59Z","citation":{"apa":"Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2014). Optimality of non-adaptive strategies: The case of parallel games. In IEEE International Symposium on Information Theory. Honolulu, USA: IEEE. https://doi.org/10.1109/ISIT.2014.6875125","ama":"Demay G, Gazi P, Maurer U, Tackmann B. Optimality of non-adaptive strategies: The case of parallel games. In: IEEE International Symposium on Information Theory. IEEE; 2014. doi:10.1109/ISIT.2014.6875125","ieee":"G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Optimality of non-adaptive strategies: The case of parallel games,” in IEEE International Symposium on Information Theory, Honolulu, USA, 2014.","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, IEEE International Symposium on Information Theory, IEEE, 2014.","mla":"Demay, Grégory, et al. “Optimality of Non-Adaptive Strategies: The Case of Parallel Games.” IEEE International Symposium on Information Theory, 6875125, IEEE, 2014, doi:10.1109/ISIT.2014.6875125.","ista":"Demay G, Gazi P, Maurer U, Tackmann B. 2014. Optimality of non-adaptive strategies: The case of parallel games. IEEE International Symposium on Information Theory. IEEE International Symposium on Information Theory Proceedings, 6875125.","chicago":"Demay, Grégory, Peter Gazi, Ueli Maurer, and Björn Tackmann. “Optimality of Non-Adaptive Strategies: The Case of Parallel Games.” In IEEE International Symposium on Information Theory. IEEE, 2014. https://doi.org/10.1109/ISIT.2014.6875125."}},{"publist_id":"4955","author":[{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Gazi, Peter","last_name":"Gazi"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rybar, Michal","last_name":"Rybar","first_name":"Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87"}],"title":"The exact PRF-security of NMAC and HMAC","editor":[{"last_name":"Garay","full_name":"Garay, Juan","first_name":"Juan"},{"last_name":"Gennaro","full_name":"Gennaro, Rosario","first_name":"Rosario"}],"citation":{"chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact PRF-Security of NMAC and HMAC.” edited by Juan Garay and Rosario Gennaro, 8616:113–30. Springer, 2014. https://doi.org/10.1007/978-3-662-44371-2_7.","ista":"Gazi P, Pietrzak KZ, Rybar M. 2014. The exact PRF-security of NMAC and HMAC. CRYPTO: International Cryptology Conference, LNCS, vol. 8616, 113–130.","mla":"Gazi, Peter, et al. The Exact PRF-Security of NMAC and HMAC. Edited by Juan Garay and Rosario Gennaro, vol. 8616, no. 1, Springer, 2014, pp. 113–30, doi:10.1007/978-3-662-44371-2_7.","ama":"Gazi P, Pietrzak KZ, Rybar M. The exact PRF-security of NMAC and HMAC. In: Garay J, Gennaro R, eds. Vol 8616. Springer; 2014:113-130. doi:10.1007/978-3-662-44371-2_7","apa":"Gazi, P., Pietrzak, K. Z., & Rybar, M. (2014). The exact PRF-security of NMAC and HMAC. In J. Garay & R. Gennaro (Eds.) (Vol. 8616, pp. 113–130). Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, USA: Springer. https://doi.org/10.1007/978-3-662-44371-2_7","ieee":"P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact PRF-security of NMAC and HMAC,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara, USA, 2014, vol. 8616, no. 1, pp. 113–130.","short":"P. Gazi, K.Z. Pietrzak, M. Rybar, in:, J. Garay, R. Gennaro (Eds.), Springer, 2014, pp. 113–130."},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"page":"113 - 130","date_created":"2018-12-11T11:55:36Z","doi":"10.1007/978-3-662-44371-2_7","date_published":"2014-01-01T00:00:00Z","year":"2014","has_accepted_license":"1","day":"01","oa":1,"quality_controlled":"1","publisher":"Springer","file_date_updated":"2020-07-14T12:45:28Z","department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T12:02:27Z","ddc":["000","004"],"conference":{"name":"CRYPTO: International Cryptology Conference","end_date":"2014-08-21","location":"Santa Barbara, USA","start_date":"2014-08-17"},"type":"conference","pubrep_id":"682","status":"public","_id":"2082","ec_funded":1,"volume":8616,"issue":"1","related_material":{"record":[{"relation":"dissertation_contains","id":"838","status":"public"}]},"publication_status":"published","language":[{"iso":"eng"}],"file":[{"date_created":"2018-12-12T10:13:17Z","file_name":"IST-2016-682-v1+1_578.pdf","date_updated":"2020-07-14T12:45:28Z","file_size":492310,"creator":"system","file_id":"4999","checksum":"dab6ab36a5f6af94f2b597e6404ed11d","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"alternative_title":["LNCS"],"intvolume":" 8616","month":"01","abstract":[{"text":"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). Security proofs and attacks for NMAC can typically be lifted to HMAC. 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, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable guarantees for NMAC, Bellare [Crypto'06] showed its security based solely on the assumption that f is a PRF, albeit via a non-uniform reduction. - Our first contribution is a simpler and uniform proof for this fact: 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 then show that this ε+ℓqδ bound is basically tight. For the most interesting case where ℓqδ ≥ ε we prove this by constructing an f for which an attack with advantage ℓqδ exists. This also violates the bound O(ℓε) on the PRF-security of NMAC recently claimed by Koblitz and Menezes. - Finally, we analyze the PRF-security of a modification of NMAC called NI [An and Bellare, Crypto'99] that differs mainly by using a compression function with an additional keying input. This avoids the constant rekeying on multi-block messages in NMAC and allows for a security proof starting by the standard switch from a PRF to a random function, followed by an information-theoretic analysis. We carry out such an analysis, obtaining a tight ℓq2/2 c bound for this step, improving over the trivial bound of ℓ2q2/2c. The proof borrows combinatorial techniques originally developed for proving the security of CBC-MAC [Bellare et al., Crypto'05].","lang":"eng"}],"oa_version":"Submitted Version"}]