Paper 2022/1221

Multi-User Security of the Sum of Truncated Random Permutations (Full Version)

Wonseok Choi, Korea Institute for Advanced Study
Hwigyeom Kim, Korea Advanced Institute of Science and Technology
Jooyoung Lee, Korea Advanced Institute of Science and Technology
Yeongmin Lee, Korea Advanced Institute of Science and Technology
Abstract

For several decades, constructing pseudorandom functions from pseudorandom permutations, so-called Luby-Rackoff backward construction, has been a popular cryptographic problem. Two methods are well-known and comprehensively studied for this problem: summing two random permutations and truncating partial bits of the output from a random permutation. In this paper, by combining both summation and truncation, we propose new Luby-Rackoff backward constructions, dubbed SaT1 and SaT2, respectively. SaT2 is obtained by partially truncating output bits from the sum of two independent random permutations, and SaT1 is its single permutation-based variant using domain separation. The distinguishing advantage against SaT1 and SaT2 is upper bounded by O(\sqrt{\mu q_max}/2^{n-0.5m}) and O({\sqrt{\mu}q_max^1.5}/2^{2n-0.5m}), respectively, in the multi-user setting, where n is the size of the underlying permutation, m is the output size of the construction, \mu is the number of users, and q_max is the maximum number of queries per user. We also prove the distinguishing advantage against a variant of XORP[3]~(studied by Bhattacharya and Nandi at Asiacrypt 2021) using independent permutations, dubbed SoP3-2, is upper bounded by O(\sqrt{\mu} q_max^2}/2^{2.5n})$. In the multi-user setting with \mu = O(2^{n-m}), a truncated random permutation provides only the birthday bound security, while SaT1 and SaT2 are fully secure, i.e., allowing O(2^n) queries for each user. It is the same security level as XORP[3] using three permutation calls, while SaT1 and SaT2 need only two permutation calls.

Note: A minor revision of an IACR publication in ASIACRYPT 2022

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
pseudorandom function Luby-Rackoff backward sum of permutations truncated random permutation multi-user security
Contact author(s)
wonseok @ kias re kr
buddha93 @ kaist ac kr
hicalf @ kaist ac kr
dudals4780 @ kaist ac kr
History
2022-09-15: approved
2022-09-15: received
See all versions
Short URL
https://ia.cr/2022/1221
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1221,
      author = {Wonseok Choi and Hwigyeom Kim and Jooyoung Lee and Yeongmin Lee},
      title = {Multi-User Security of the Sum of Truncated Random Permutations (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1221},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1221}},
      url = {https://eprint.iacr.org/2022/1221}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.