Paper 2026/2940

Short-Input Random Oracles (and PRFs) over Abelian Groups: New Generalisations and Better Bounds

Ritam Bhaumik, Technology Innovation Institute
Abstract

At Eurocrypt '26, Bhaumik et al. initiated a systematic study of short-input random oracles built from public random permutations over $\mathbb{Z}_2^n$. While their main focus was on length-preserving random oracles, they also proved that XORP, the expanding construction at the core of CENC (Iwata, FSE '06), is indifferentiable from a random function up to about $N^{2/3}$ queries for a permutation with domain size $N$ ($= 2^n$). We extend this study in several directions. For classifying short-input expanding random oracles, we introduce GXP, a family of constructions that use independent random permutations over an arbitrary abelian group of order $N$ to build a function with several output blocks, each the difference of two masked permutation outputs. GXP covers XORP with one or several permutations, LXoP (Dinur, Eurocrypt '25), and the widely-studied sum of two permutations. We study the security of GXP in both keyless and keyed settings. In the keyless setting, a recent preprint from Kim has shown that the sum of two permutations over $\mathbb{Z}_2^n$ with a class of simulators called uniform simulators achieves a tight indifferentiability from a random oracle up to about $N^{3/4}$ queries. We build on this analysis, and prove that every member of GXP, over every finite abelian group, with arbitrary automorphism masks (under an extra width condition for some singular masks) and with unused permutation inputs, is indifferentiable up to about $N^{3/4}$ queries, for a uniform simulator with three trials and an acceptance coin. For admissible masks we give a sharper bound with explicit constants; other masks only add lower-order terms. The coin is necessary: without it, the simulator is distinguishable at about $N^{2/3}$ queries. Extending Kim's attack, with coset progressions in place of subgroups, we show that the exponent $3/4$ is tight for this simulator, for every family whose construction domain has density bounded below. In the keyed setting, we extend the Fourier-analytic method put forward by Bhaumik et al. in another recent preprint, and establish the pseudorandomness with advantage $O_w(q/N^{3/2})$ for every rigid-free member of GXP, with explicit constants and over every finite abelian group. Pseudorandomness is thus governed by rigid-freeness, a strengthening of admissibility: rigid pairs and non-admissible masks can both limit it to about $q/N$, while neither affects the indifferentiability exponent. The fork constructions ForkEDMD and ForkCENC of Dutta et al., and EDMD, in which the output of one permutation call becomes the input of all the other calls, are not members of GXP. A change of variables on the permutations turns each of them into a member with exactly the same security, so all our results apply to them as well.

Note: [19/11/26] First version of preprint uploaded.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
indifferentiabilityrandom oracleXORPGXPmodes of operationprovable security
Contact author(s)
bhaumik ritam @ gmail com
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2940
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2940,
      author = {Ritam Bhaumik},
      title = {Short-Input Random Oracles (and {PRFs}) over Abelian Groups: New Generalisations and Better Bounds},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2940},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2940}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.