Paper 2022/1221
MultiUser Security of the Sum of Truncated Random Permutations (Full Version)
Abstract
For several decades, constructing pseudorandom functions from pseudorandom permutations, socalled LubyRackoff backward construction, has been a popular cryptographic problem. Two methods are wellknown 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 LubyRackoff 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 permutationbased variant using domain separation. The distinguishing advantage against SaT1 and SaT2 is upper bounded by O(\sqrt{\mu q_max}/2^{n0.5m}) and O({\sqrt{\mu}q_max^1.5}/2^{2n0.5m}), respectively, in the multiuser 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 SoP32, is upper bounded by O(\sqrt{\mu} q_max^2}/2^{2.5n})$. In the multiuser setting with \mu = O(2^{nm}), 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)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2022
 Keywords
 pseudorandom function LubyRackoff backward sum of permutations truncated random permutation multiuser security
 Contact author(s)

wonseok @ kias re kr
buddha93 @ kaist ac kr
hicalf @ kaist ac kr
dudals4780 @ kaist ac kr  History
 20220915: approved
 20220915: received
 See all versions
 Short URL
 https://ia.cr/2022/1221
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1221, author = {Wonseok Choi and Hwigyeom Kim and Jooyoung Lee and Yeongmin Lee}, title = {MultiUser 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} }