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

##### 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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1221

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.