Geodesic
Random number generators based on permutations can pass the collision test
Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 1, pp. 97-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate pseudorandom number generators (PRNGs) based on random permutations which may be considered as models of block ciphers with randomly chosen keys. A simple method for calculating upper and lower bounds on the collision probability in a finite length output sequence based on the conditional probability bounds of the next symbol to appear after a known prefix was developed. We found that the difference between these upper and lower bounds may be made extremely small for any practical output length. Moreover the collision probability for a true RNG always lies within these bounds. This implies that the investigated generators will pass the collision test, i. e. they are indistinguishable by this test from a true RNG. 
@article{MVK_2021_12_1_a4,
     author = {A. V. Urivskiy},
     title = {Random number generators based on permutations can pass the collision test},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {97--108},
     year = {2021},
     volume = {12},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a4/}
}
TY  - JOUR
AU  - A. V. Urivskiy
TI  - Random number generators based on permutations can pass the collision test
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 97
EP  - 108
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a4/
LA  - en
ID  - MVK_2021_12_1_a4
ER  - 
%0 Journal Article
%A A. V. Urivskiy
%T Random number generators based on permutations can pass the collision test
%J Matematičeskie voprosy kriptografii
%D 2021
%P 97-108
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a4/
%G en
%F MVK_2021_12_1_a4
A. V. Urivskiy. Random number generators based on permutations can pass the collision test. Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 1, pp. 97-108. http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a4/

[1] ISO/IEC 18031:2011. Information technology – Security techniques – Random bit generation, International standard

[2] Urivskiy A., Rybkin A., Borodin M., “On some properties of PRNGs based on block ciphers in counter mode”, Electr. Notes Discr. Math., 57 (2017), 211–218 | DOI | Zbl

[3] Urivskiy A., “On unpredictability of PRNGs based on multiple block ciphers”, Proc. XV Int. Symp. Probl. of Redundancy in Inform. and Control Syst., 2016, 162–165

[4] Lucks S., “The sum of PRPs is a secure PRF”, EUROCRYPT 2000, Lect. Notes Comput. Sci., 1807, 2000, 470–484 | DOI | MR | Zbl

[5] Patarin J., “A proof of security in $O(2n)$ for the XOR of two random permutations”, Proc. Inform. Theor. Security — ICITS 2008, Lect. Notes Comput. Sci., 5155, 2008, 232–248 | DOI | MR | Zbl

[6] Urivskiy A., Borodin M., Rybkin A., “Finding distinguishers for pseudorandom number generators based on permutations”, J. Computer Virol. Hack. Techn., 16 (2020), 295–303 | DOI