International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Luby-Rackoff Backwards with More Users and More Security

Srimanta Bhattacharya , SIAS, Krea University
Mridul Nandi , Indian Statistical Institute, Kolkata
DOI: 10.1007/978-3-030-92078-4_12
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: It is known, from the work of Dai \textit{et al.} (in CRYPTO'17), that the PRF advantage of $\xorp$ (bitwise-xor of two outputs of $n$-bit random permutations with domain separated inputs), against an adversary making $q$ queries, is about $q/2^n$ for $q \leq 2^{n- 5}$. The same bound can be easily shown to hold for $\xorp[k]$ (bitwise-xor of $k$ outputs $n$-bit pseudorandom random permutations with domain separated inputs), for $k \geq 3$. In this work, we first consider multi-user security of $\xorp[3]$. We show that the multi-user PRF advantage of $\xorp[3]$ is about $\sqrt{uq_{\max}}/2^n$ for all {$q_{\max} \leq 2^{n}/12$}, where $u$ is the number of users and $q_{\max}$ is the maximum number of queries the adversary can make to each user. In the multi-user setup, this implies that $\xorp[3]$ gives security for $O(2^n)$ users even allowing almost $O(2^n)$ queries to each user. This also indicates significant improvement in the single-user setup ({\em i.e.,} when $u =1$), where the distinguishing advantage of the adversary even after making $O(2^n)$ queries is $O({1 \over \sqrt{2^n}})$, {\em i.e.,} negligible. Subsequently, we consider a simple efficient variant of $\xorp[3]$ in which we use five calls to produce $2n$ bit output (instead of six calls in the case of $\xorp[3]$). This variant also achieves similar level of security. As an immediate application, we can construct a variant of block cipher based counter mode which provides much higher security (both in the single-user and the multi-user setup) compared to the security of the encryption part of GCM at the cost of efficiency.
Video from ASIACRYPT 2021
  title={Luby-Rackoff Backwards with More Users and More Security},
  author={Srimanta Bhattacharya and Mridul Nandi},