On TRP-RF Switch in the Quantum Query Model
Authors
Ashwin Jha
Ashwin Jha
Ruhr University of Bochum, Bochum, Germany
ashwin dot jha at outlook dot de
ashwin dot jha at outlook dot de
Abstract
The tweakable random permutation (TRP) to random function (RF) switch in the quantum query model (Hosoyamada and Iwata, IACR ASIACRYPT 2019) is tightened. This immediately improves the security bounds for TNT and LRWQ against quantum chosen-plaintext attacks. We further demonstrate the utility of this tightened switch by establishing birthday-bound security for two additional TRP-based modes, including the cascade function.
References
[ABB+17]
Elena Andreeva, Guy Barwell, Ritam Bhaumik, Mridul Nandi, Dan Page, and Martijn Stam. Turning Online Ciphers Off. IACR Trans. Symmetric Cryptol., 2017(2):105–142, 2017. DOI: 10.13154/TOSC.V2017.I2.105-142
[ARR00]
P. Bhimasankaram A. Ramachandra Rao. Linear Algebra. Hindustan Book Agency 2000. DOI: 10.1007/978-93-86279-01-9
[BBKN01]
Mihir Bellare, Alexandra Boldyreva, Lars R. Knudsen, and Chanathip Namprempre. Online Ciphers and the Hash-CBC Construction. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pages 292–309. 2001. Springer. DOI: 10.1007/3-540-44647-8_18
[BCEJ23a]
Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, and Ashwin Jha. On Quantum Secure Compressing Pseudorandom Functions. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023, Proceedings, Part III, volume 14440 of Lecture Notes in Computer Science, pages 34–66. 2023. Springer. DOI: 10.1007/978-981-99-8727-6_2
[BCEJ23b]
Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, and Ashwin Jha. On Quantum Secure Compressing Pseudorandom Functions. IACR Cryptol. ePrint Arch. 2023/207. 2023.
[BCEJ24]
Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, and Ashwin Jha. Mind the Bad Norms - Revisiting Compressed Oracle-Based Quantum Indistinguishability Proofs. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology - ASIACRYPT 2024, Proceedings, Part IX, volume 15492 of Lecture Notes in Computer Science, pages 215–247. 2024. Springer. DOI: 10.1007/978-981-96-0947-5_8
[BGGS20]
Zhenzhen Bao, Chun Guo, Jian Guo, and Ling Song. TNT: How to Tweak a Block Cipher. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 641–673. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_22
[BH22]
Mihir Bellare and Viet Tung Hoang. Efficient Schemes for Committing Authenticated Encryption. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022, Proceedings, Part II, volume 13276 of Lecture Notes in Computer Science, pages 845–875. 2022. Springer. DOI: 10.1007/978-3-031-07085-3_29
[BKR94]
Mihir Bellare, Joe Kilian, and Phillip Rogaway. The Security of Cipher Block Chaining. In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 341–358. 1994. Springer. DOI: 10.1007/3-540-48658-5_32
[BR06]
Mihir Bellare and Phillip Rogaway. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 409–426. 2006. Springer. DOI: 10.1007/11761679_25
[CFHL21]
Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer Science, pages 598–629. 2021. Springer. DOI: 10.1007/978-3-030-77886-6_21
[CN08]
Donghoon Chang and Mridul Nandi. A Short Proof of the PRP/PRF Switching Lemma. IACR Cryptol. ePrint Arch. 2008/078. 2008.
[Dam89]
Ivan Damgård. A Design Principle for Hash Functions. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 416–427. 1989. Springer. DOI: 10.1007/0-387-34805-0_39
[FLLW18]
Christian Forler, Eik List, Stefan Lucks, and Jakob Wenzel. POEx: A Beyond-Birthday-Bound-Secure On-line Cipher. Cryptogr. Commun., 10(1):177–193, 2018. DOI: 10.1007/S12095-017-0250-9
[GGM84]
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to Construct Random Functions (Extended Abstract). In 25th Annual Symposium on Foundations of Computer Science - FOCS 1984, Proceedings, pages 464–479. 1984. IEEE Computer Society. DOI: 10.1109/SFCS.1984.715949
[HI19a]
Akinori Hosoyamada and Tetsu Iwata. 4-Round Luby-Rackoff Construction is a qPRP. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019, Proceedings, Part I, volume 11921 of Lecture Notes in Computer Science, pages 145–174. 2019. Springer. DOI: 10.1007/978-3-030-34578-5_6
[HI19b]
Akinori Hosoyamada and Tetsu Iwata. Tight Quantum Security Bound of the 4-Round Luby-Rackoff Construction. IACR Cryptol. ePrint Arch. 2019/243 v20190913:015401. 2019.
[HI21a]
Akinori Hosoyamada and Tetsu Iwata. On Tight Quantum Security of HMAC and NMAC in the Quantum Random Oracle Model. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, Proceedings, Part I, volume 12825 of Lecture Notes in Computer Science, pages 585–615. 2021. Springer. DOI: 10.1007/978-3-030-84242-0_21
[HI21b]
Akinori Hosoyamada and Tetsu Iwata. Provably Quantum-Secure Tweakable Block Ciphers. IACR Trans. Symmetric Cryptol., 2021(1):337–377, 2021. DOI: 10.46586/TOSC.V2021.I1.337-377
[HWKS98]
Chris Hall, David A. Wagner, John Kelsey, and Bruce Schneier. Building PRFs from PRPs. In Hugo Krawczyk, editor, Advances in Cryptology - CRYPTO 1998, Proceedings, volume 1462 of Lecture Notes in Computer Science, pages 370–389. 1998. Springer. DOI: 10.1007/BFB0055742
[IKMP20]
Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin. Duel of the Titans: The Romulus and Remus Families of Lightweight AEAD Algorithms. IACR Trans. Symmetric Cryptol., 2020(1):43–120, 2020. DOI: 10.13154/TOSC.V2020.I1.43-120
[IR88]
Russell Impagliazzo and Steven Rudich. Limits on the Provable Consequences of One-way Permutations. In Shafi Goldwasser, editor, Advances in Cryptology - CRYPTO 1988, Proceedings, volume 403 of Lecture Notes in Computer Science, pages 8–26. 1988. Springer. DOI: 10.1007/0-387-34799-2_2
[LRW02]
Moses D. Liskov, Ronald L. Rivest, and David A. Wagner. Tweakable Block Ciphers. In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 31–46. 2002. Springer. DOI: 10.1007/3-540-45708-9_3
[Mer89]
Ralph C. Merkle. A Certified Digital Signature. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 218–238. 1989. Springer. DOI: 10.1007/0-387-34805-0_21
[Nan24]
Mridul Nandi. Improving Tightness Gap of GGM Construction and Its Applications. In Sourav Mukhopadhyay and Pantelimon Stanica, editors, Progress in Cryptology - INDOCRYPT 2024, Proceedings, Part I, volume 15495 of Lecture Notes in Computer Science, pages 28–50. 2024. Springer. DOI: 10.1007/978-3-031-80308-6_2
[NC10]
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press 2010. DOI: 10.1017/CBO9780511976667
[RZ11]
Phillip Rogaway and Haibin Zhang. Online Ciphers from Tweakable Blockciphers. In Aggelos Kiayias, editor, Topics in Cryptology - CT-RSA 2011, Proceedings, volume 6558 of Lecture Notes in Computer Science, pages 237–249. 2011. Springer. DOI: 10.1007/978-3-642-19074-2_16
[SY17]
Fang Song and Aaram Yun. Quantum Security of NMAC and Related Constructions - PRF Domain Extension Against Quantum attacks. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017, Proceedings, Part II, volume 10402 of Lecture Notes in Computer Science, pages 283–309. 2017. Springer. DOI: 10.1007/978-3-319-63715-0_10
[Unr23]
Dominique Unruh. Towards Compressed Permutation Oracles. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023, Proceedings, Part IV, volume 14441 of Lecture Notes in Computer Science, pages 369–400. 2023. Springer. DOI: 10.1007/978-981-99-8730-6_12
[Yue14]
Henry Yuen. A Quantum Lower Bound for Distinguishing Random Functions from Random Permutations. Quantum Inf. Comput., 14(13-14):1089–1097, 2014. DOI: 10.26421/QIC14.13-14-2
[Zha12]
Mark Zhandry. How to Construct Quantum Random Functions. In 53rd Annual IEEE Symposium on Foundations of Computer Science - FOCS 2012, Proceedings, pages 679–687. 2012. IEEE Computer Society. DOI: 10.1109/FOCS.2012.37
[Zha15]
Mark Zhandry. A Note on the Quantum Collision and Set Equality Problems. Quantum Inf. Comput., 15(7&8):557–567, 2015. DOI: 10.26421/QIC15.7-8-2
[Zha19]
Mark Zhandry. How to Record Quantum Queries, and Applications to Quantum Indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019, Proceedings, Part II, volume 11693 of Lecture Notes in Computer Science, pages 239–268. 2019. Springer. DOI: 10.1007/978-3-030-26951-7_9
PDF
History
Submitted: 2025-04-05
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Ashwin Jha, On TRP-RF Switch in the Quantum Query Model. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/a3waksuc2.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.