Alternative security models for a pseudorandom function

K. D. Tsaregorodtsev

Matematičeskie voprosy kriptografii, Tome 15 (2024), pp. 113-134.

Résumé

In the paper we analyze various security models for pseudorandom functions that arise in the analysis of cryptographic protocols (such as 5G-AKA) and study the reducibility of non-standard pseudorandomness models to the standard $\mathsf{PRF}$ model. We consider several models. (a) $\mathsf{PRF}^+$ model formalizes the following requirement: the outputs of a pseudorandom function on adaptively selected inputs must be indistinguishable from random binary strings of the appropriate length, even if the adversary has the opportunity to receive as “an additional information” the outputs of a “real” pseudorandom function. (b) $\mathsf{UF}$-$\mathsf{PRF}$ model formalizes the requirement that it is impossible to forge the value of a pseudorandom function on a fresh input (similar to the models for the MAC function). (c) $\mathsf{LOR}$-$\mathsf{PRF}$ model formalizes the indistinguishability property of “cryptographic bindings” calculated via pseudorandom function on different keys. We also study the natural generalization of these models to the case of multiple users in the system ($\mathsf{mPRF}^+$ and $\mathsf{mUF}$-$\mathsf{PRF}$ models). We show that these new models can be reduced to the basic $\mathsf{PRF}$ model for a pseudorandom function family. The results can be used in the analysis of various cryptographic protocols.

Bibliographie

[1] Sipser M., Introduction to the Theory of Computation, 3rd Edition, Cengage Learning, 2012, 504 pp.

[2] Mezhgosudarstvennyi standart GOST 34.12-2018. Informatsionnaya tekhnologiya (IT). Kriptograficheskaya zaschita informatsii. Blochnye shifry, 2018

[3] Katz J., Lindell Y., Introduction to modern cryptography, CRC press, Boca Raton, Florida, 2020, 626 pp. | MR

[4] 3GPP, Technical specification (TS). Security architecture and procedures for 5G System (3GPP TS 33.501 version 17.5.0 Release 17), 2022

[5] Belskii B. S., Drynkin A. V., Davydov S. A., “Voprosy obespecheniya bezopasnosti abonentov v setyakh radiodostupa pyatogo pokoleniya”, Int. J. Open Inf. Technol., 9:7 (2021), 32–54, Laboratoriya Otkrytykh Informatsionnykh Tekhnologii fakulteta VMK MGU

[6] Rekomendatsii po standartizatsii “IT.KZI. Kriptograficheskie algoritmy vyrabotki klyuchei shifrovaniya informatsii i autentifikatsionnykh vektorov, prednaznachennye dlya realizatsii v apparatnykh modulyakh doveriya dlya ispolzovaniya v podvizhnoi radiotelefonnoi svyazi”, 2023

[7] Kiryukhin V. A., “Keyed Streebog is a secure PRF and MAC”, Matematicheskie voprosy kriptografii, 14:2 (2023), 77–96 | DOI | MR | Zbl

[8] Kiryukhin V. A., “O «$k$-bitnoi stoikosti» algoritmov imitozaschity, osnovannykh na khesh-funktsii «Stribog»”, Matematicheskie voprosy kriptografii, 15:2 (2024), 47–68 | DOI | MR

[9] Boyd C., Mathuria A., Stebila D., Protocols for authentication and key establishment, Springer, Berlin–Heidelberg, 2003, 321 pp.

[10] Nesterenko A. Yu., Semenov A. M., “Metodika otsenki bezopasnosti kriptograficheskikh protokolov”, Prikladnaya diskretnaya matematika, 2022, no. 56, 33–82 | DOI

[11] Hermans J., Pashalidis A., Vercauteren F., Preneel B., “A new RFID privacy model”, Eur. Symp. Research in Computer Security, Lect. Notes Comput. Sci., 6879, 2011, 568–587 | DOI

[12] Koutsos A., “The 5G-AKA Authentication Protocol Privacy”, IEEE Eur. Symp. Security and Privacy, EuroS, IEEE Computer Society, 2019, 464–479

[13] Bellare M., Goldreich O., Mityagin A., The power of verification queries in message authentication and authenticated encryption, Cryptology ePrint Archive, Report 2004/309, 2004 eprint.iacr.org/2004/309.pdf

[14] Mittelbach A., Fischlin M., The Theory of Hash Functions and Random Oracles, Springer, Cham, 2021, 788 pp.

[15] Chatterjee S., Menezes A., Sarkar P., “Another look at tightness”, SAC 2011, Lect. Notes Comput. Sci., 7118, 2012, 293–319 | DOI | MR | Zbl