{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T15:32:13Z","timestamp":1767972733836,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,8,19]],"date-time":"2024-08-19T00:00:00Z","timestamp":1724025600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,19]],"date-time":"2024-08-19T00:00:00Z","timestamp":1724025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A two-input function is a dual PRF if it is a PRF when keyed by either of its inputs. Dual PRFs are assumed in the design and analysis of numerous primitives and protocols including HMAC, AMAC, TLS 1.3 and MLS. But, not only do we not know whether particular functions on which the assumption is made really are dual PRFs; we do not know if dual PRFs even exist. What if the goal is impossible? This paper addresses this with a foundational treatment of dual PRFs, giving constructions based on standard assumptions. This provides what we call a generic validation of the dual PRF assumption. Our approach is to introduce and construct symmetric PRFs, which imply dual PRFs and may be of independent interest. We give a general construction of a symmetric PRF based on a function having a weak form of collision resistance coupled with a leakage hardcore function, a strengthening of the usual notion of hardcore functions we introduce. We instantiate this general construction in two ways to obtain two specific symmetric and dual PRFs, the first assuming any collision-resistant hash function and the second assuming any one-way permutation. A construction based on any one-way function evades us and is left as an intriguing open problem.\n<\/jats:p>","DOI":"10.1007\/s00145-024-09513-6","type":"journal-article","created":{"date-parts":[[2024,8,19]],"date-time":"2024-08-19T22:02:00Z","timestamp":1724104920000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of a Prevailing Assumption"],"prefix":"10.1007","volume":"37","author":[{"given":"Mihir","family":"Bellare","sequence":"first","affiliation":[]},{"given":"Anna","family":"Lysyanskaya","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,19]]},"reference":[{"key":"9513_CR1","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Angel, B.\u00a0Dowling, A.\u00a0H\u00fclsing, P.\u00a0Schwabe, F.\u00a0J. Weber. Post quantum noise. In H.\u00a0Yin, A.\u00a0Stavrou, C.\u00a0Cremers, and E.\u00a0Shi, editors, ACM CCS 2022, pp. 97\u2013109. (ACM Press, 2022)","DOI":"10.1145\/3548606.3560577"},{"key":"9513_CR2","unstructured":"N.\u00a0Aviram, B.\u00a0Dowling, I.\u00a0Komargodski, K.\u00a0G. Paterson, E.\u00a0Ronen, E.\u00a0Yogev. Practical (post-quantum) key combiners from one-wayness and applications to TLS. Cryptology ePrint Archive, Report 2022\/065, 2022. https:\/\/eprint.iacr.org\/2022\/065"},{"key":"9513_CR3","series-title":"Part III, volume 14083 of LNCS","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/978-3-031-38548-3_22","volume-title":"CRYPTO 2023","author":"M Backendal","year":"2023","unstructured":"M.\u00a0Backendal, M.\u00a0Bellare, F.\u00a0G\u00fcnther, and M.\u00a0Scarlata. When messages are keys: Is HMAC a dual-PRF? In H.\u00a0Handschuh and A.\u00a0Lysyanskaya, editors, CRYPTO\u00a02023, Part\u00a0III, volume 14083 of LNCS, pages 661\u2013693. Springer, Heidelberg, Aug. 2023."},{"key":"9513_CR4","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-29011-4_42","volume-title":"EUROCRYPT 2012","author":"A Banerjee","year":"2012","unstructured":"A.\u00a0Banerjee, C.\u00a0Peikert, and A.\u00a0Rosen. Pseudorandom functions and lattices. In D.\u00a0Pointcheval and T.\u00a0Johansson, editors, EUROCRYPT\u00a02012, volume 7237 of LNCS, pages 719\u2013737. Springer, Heidelberg, Apr. 2012."},{"key":"9513_CR5","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44647-8_1","volume-title":"CRYPTO 2001","author":"B Barak","year":"2001","unstructured":"B.\u00a0Barak, O.\u00a0Goldreich, R.\u00a0Impagliazzo, S.\u00a0Rudich, A.\u00a0Sahai, S.\u00a0P. Vadhan, and K.\u00a0Yang. On the (im)possibility of obfuscating programs. In J.\u00a0Kilian, editor, CRYPTO\u00a02001, volume 2139 of LNCS, pages 1\u201318. Springer, Heidelberg, Aug. 2001."},{"key":"9513_CR6","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare. New proofs for NMAC and HMAC: Security without collision resistance. Journal of Cryptology, 28(4):844\u2013878, Oct. 2015. Preliminary version in C.\u00a0Dwork, editor, CRYPTO\u00a02006, volume 4117 of LNCS, pp. 602\u2013619, (Springer, Heidelberg, 2006)","DOI":"10.1007\/s00145-014-9185-x"},{"key":"9513_CR7","series-title":"Part I, volume 9665 of LNCS","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-662-49890-3_22","volume-title":"EUROCRYPT 2016","author":"M Bellare","year":"2016","unstructured":"M.\u00a0Bellare, D.\u00a0J. Bernstein, and S.\u00a0Tessaro. Hash-function based PRFs: AMAC and its multi-user security. In M.\u00a0Fischlin and J.-S. Coron, editors, EUROCRYPT\u00a02016, Part\u00a0I, volume 9665 of LNCS, pages 566\u2013595. Springer, Heidelberg, May 2016."},{"key":"9513_CR8","series-title":"LNCS","first-page":"1","volume-title":"CRYPTO\u201996","author":"M Bellare","year":"1996","unstructured":"M.\u00a0Bellare, R.\u00a0Canetti, and H.\u00a0Krawczyk. Keying hash functions for message authentication. In N.\u00a0Koblitz, editor, CRYPTO\u201996, volume 1109 of LNCS, pages 1\u201315. Springer, Heidelberg, Aug. 1996."},{"key":"9513_CR9","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1007\/978-3-642-14623-7_36","volume-title":"CRYPTO 2010","author":"M Bellare","year":"2010","unstructured":"M.\u00a0Bellare and D.\u00a0Cash. Pseudorandom functions and permutations provably secure against related-key attacks. In T.\u00a0Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS, pages 666\u2013684. Springer, Heidelberg, Aug. 2010."},{"key":"9513_CR10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/978-3-642-29011-4_38","volume-title":"EUROCRYPT 2012","author":"M Bellare","year":"2012","unstructured":"M.\u00a0Bellare, R.\u00a0Dowsley, B.\u00a0Waters, and S.\u00a0Yilek. Standard security does not imply security against selective-opening. In D.\u00a0Pointcheval and T.\u00a0Johansson, editors, EUROCRYPT\u00a02012, volume 7237 of LNCS, pages 645\u2013662. Springer, Heidelberg, Apr. 2012."},{"key":"9513_CR11","unstructured":"M.\u00a0Bellare, A.\u00a0Lysyanskaya. Symmetric and dual PRFs from standard assumptions: A generic validation of a prevailing assumption. Cryptology ePrint Archive, Report 2015\/1198, 2015. https:\/\/eprint.iacr.org\/2015\/1198"},{"key":"9513_CR12","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, P.\u00a0Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In S.\u00a0Vaudenay, editor, EUROCRYPT\u00a02006, vol. 4004 of LNCS, pp. 409\u2013426. (Springer, Heidelberg, 2006)","DOI":"10.1007\/11761679_25"},{"key":"9513_CR13","doi-asserted-by":"crossref","unstructured":"D.\u00a0J. Bernstein, N.\u00a0Duif, T.\u00a0Lange, P.\u00a0Schwabe, B.-Y. Yang. High-speed high-security signatures. In B.\u00a0Preneel and T.\u00a0Takagi, editors, CHES\u00a02011, vol. 6917 of LNCS, pp. 124\u2013142. (Springer, Heidelberg, 2011)","DOI":"10.1007\/978-3-642-23951-9_9"},{"key":"9513_CR14","series-title":"Part II, volume 8270 of LNCS","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-42045-0_17","volume-title":"ASIACRYPT 2013","author":"DJ Bernstein","year":"2013","unstructured":"D.\u00a0J. Bernstein and T.\u00a0Lange. Non-uniform cracks in the concrete: The power of free precomputation. In K.\u00a0Sako and P.\u00a0Sarkar, editors, ASIACRYPT\u00a02013, Part\u00a0II, volume 8270 of LNCS, pages 321\u2013340. Springer, Heidelberg, Dec. 2013."},{"key":"9513_CR15","series-title":"PQCrypto 2019","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-030-25510-7_12","volume-title":"Post-Quantum Cryptography - 10th International Conference","author":"N Bindel","year":"2019","unstructured":"N.\u00a0Bindel, J.\u00a0Brendel, M.\u00a0Fischlin, B.\u00a0Goncalves, and D.\u00a0Stebila. Hybrid key encapsulation mechanisms and authenticated key exchange. In J.\u00a0Ding and R.\u00a0Steinwandt, editors, Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019, pages 206\u2013226. Springer, Heidelberg, 2019."},{"issue":"4","key":"9513_CR16","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M Blum","year":"1984","unstructured":"M.\u00a0Blum and S.\u00a0Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13(4):850\u2013864, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"9513_CR17","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, V.\u00a0Kumar. A new pseudorandom generator from collision-resistant hash functions. In O.\u00a0Dunkelman, editor, CT-RSA\u00a02012, vol. 7178 of LNCS, pp. 187\u2013202. (Springer, Heidelberg, 2012)","DOI":"10.1007\/978-3-642-27954-6_12"},{"key":"9513_CR18","doi-asserted-by":"crossref","unstructured":"C.\u00a0Brzuska, E.\u00a0Cornelissen, and K.\u00a0Kohbrok. Security analysis of the MLS key derivation. In 2022 IEEE Symposium on Security and Privacy, pp. 2535\u20132553. (IEEE Computer Society Press, 2022)","DOI":"10.1109\/SP46214.2022.9833678"},{"key":"9513_CR19","series-title":"Part I, volume 13791 of LNCS","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/978-3-031-22963-3_21","volume-title":"ASIACRYPT 2022","author":"C Brzuska","year":"2022","unstructured":"C.\u00a0Brzuska, A.\u00a0Delignat-Lavaud, C.\u00a0Egger, C.\u00a0Fournet, K.\u00a0Kohbrok, and M.\u00a0Kohlweiss. Key-schedule security for the TLS 1.3 standard. In S.\u00a0Agrawal and D.\u00a0Lin, editors, ASIACRYPT\u00a02022, Part\u00a0I, volume 13791 of LNCS, pages 621\u2013650. Springer, Heidelberg, Dec. 2022."},{"key":"9513_CR20","unstructured":"Y.\u00a0Dodis, R.\u00a0Ostrovsky, L.\u00a0Reyzin, and A.\u00a0Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. Cryptology ePrint Archive, Report 2003\/235, 2003. https:\/\/eprint.iacr.org\/2003\/235"},{"key":"9513_CR21","series-title":"LNCS","first-page":"416","volume-title":"PKC 2005","author":"Y Dodis","year":"2005","unstructured":"Y.\u00a0Dodis and A.\u00a0Yampolskiy. A verifiable random function with short proofs and keys. In S.\u00a0Vaudenay, editor, PKC\u00a02005, volume 3386 of LNCS, pages 416\u2013431. Springer, Heidelberg, Jan. 2005."},{"issue":"4","key":"9513_CR22","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00145-021-09384-1","volume":"34","author":"B Dowling","year":"2021","unstructured":"B.\u00a0Dowling, M.\u00a0Fischlin, F.\u00a0G\u00fcnther, and D.\u00a0Stebila (2021) A cryptographic analysis of the TLS 13 handshake protocol. Journal of Cryptology, 34(4):37","journal-title":"Journal of Cryptology"},{"key":"9513_CR23","series-title":"Part I, volume 8616 of LNCS","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-662-44371-2_7","volume-title":"CRYPTO 2014","author":"P Ga\u017ei","year":"2014","unstructured":"P.\u00a0Ga\u017ei, K.\u00a0Pietrzak, and M.\u00a0Ryb\u00e1r. The exact PRF-security of NMAC and HMAC. In J.\u00a0A. Garay and R.\u00a0Gennaro, editors, CRYPTO\u00a02014, Part\u00a0I, volume 8616 of LNCS, pages 113\u2013130. Springer, Heidelberg, Aug. 2014."},{"issue":"4","key":"9513_CR24","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"O.\u00a0Goldreich, S.\u00a0Goldwasser, and S.\u00a0Micali. How to construct random functions. Journal of the ACM, 33(4):792\u2013807, Oct. 1986.","journal-title":"Journal of the ACM"},{"key":"9513_CR25","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, L.\u00a0A. Levin. A hard-core predicate for all one-way functions. In 21st ACM STOC, pp. 25\u201332. (ACM Press, 1989)","DOI":"10.1145\/73007.73010"},{"key":"9513_CR26","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/3-540-44448-3_34","volume-title":"ASIACRYPT 2000","author":"S Hada","year":"2000","unstructured":"S.\u00a0Hada. Zero-knowledge and code obfuscation. In T.\u00a0Okamoto, editor, ASIACRYPT\u00a02000, volume 1976 of LNCS, pages 443\u2013457. Springer, Heidelberg, Dec. 2000."},{"issue":"4","key":"9513_CR27","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"J.\u00a0H\u00e5stad, R.\u00a0Impagliazzo, L.\u00a0A. Levin, and M.\u00a0Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364\u20131396, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"9513_CR28","doi-asserted-by":"crossref","unstructured":"A.\u00a0H\u00fclsing, K.-C. Ning, P.\u00a0Schwabe, F.\u00a0J. Weber, P.\u00a0R. Zimmermann. Post-quantum WireGuard. In 2021 IEEE Symposium on Security and Privacy, pp. 304\u2013321. (IEEE Computer Society Press, 2021)","DOI":"10.1109\/SP40001.2021.00030"},{"key":"9513_CR29","doi-asserted-by":"crossref","unstructured":"A.\u00a0B. Lewko, B.\u00a0Waters. Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In E.\u00a0Al-Shaer, S.\u00a0Jha, and A.\u00a0D. Keromytis, editors, ACM CCS 2009, pp. 112\u2013120. (ACM Press, 2009)","DOI":"10.1145\/1653662.1653677"},{"issue":"2","key":"9513_CR30","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M Naor","year":"2004","unstructured":"M.\u00a0Naor and O.\u00a0Reingold. Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM, 51(2):231\u2013262, Mar. 2004.","journal-title":"Journal of the ACM"},{"key":"9513_CR31","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11958239_14","volume-title":"Progress in Cryptology - VIETCRYPT 06","author":"P Rogaway","year":"2006","unstructured":"P.\u00a0Rogaway. Formalizing human ignorance. In P.\u00a0Q. Nguyen, editor, Progress in Cryptology - VIETCRYPT 06, volume 4341 of LNCS, pages 211\u2013228. Springer, Heidelberg, Sept. 2006."},{"key":"9513_CR32","unstructured":"D.\u00a0Stebila, S.\u00a0Fluhrer, S.\u00a0Gueron. Hybrid key exchange in TLS\u00a01.3 \u2013 draft-ietf-tls-hybrid-design-05. https:\/\/datatracker.ietf.org\/doc\/html\/draft-ietf-tls-hybrid-design-05, Aug. 2022"},{"key":"9513_CR33","unstructured":"A.\u00a0C.-C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd FOCS, pp. 80\u201391. (IEEE Computer Society Press, 1982)"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09513-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09513-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09513-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T21:01:38Z","timestamp":1729890098000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09513-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,19]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["9513"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09513-6","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,19]]},"assertion":[{"value":"15 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"33"}}