CryptoDB
Luby-Rackoff Backwards with More Users and More Security
| Authors: |
|
|---|---|
| Download: | |
| 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
BibTeX
@inproceedings{asiacrypt-2021-31395,
title={Luby-Rackoff Backwards with More Users and More Security},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-92078-4_12},
author={Srimanta Bhattacharya and Mridul Nandi},
year=2021
}