STUDY OF THE MINIVERSION PROPERTIES IN THE PSEUDO-RANDOM FUNCTION PCOLLAPSER
Abstract
The aim of the work is to evaluate the cryptographic properties of the pCollapser family of pseudo-
random functions (PRF) based on the study of the properties of its mini_pCollapser_12x12 miniversion
using fixed substitutions with extremely low cryptographic properties. As a comparison element,
we used a mini-version of a typical function based on an SP-net, containing a similar number of fixed
substitutions, and having a similar input/output dimension equal to 12 bits. To achieve this goal, the
following tasks were solved: – determination of the structure of the studied functions and the number of
rounds; – definition of a model for the formation of fixed substitutions with extremely low cryptographic
properties; – generation of sets of 6-bit fixed substitutions with extremely low cryptographic properties; – inclusion of the substitutions obtained into the functions under study and determination of the main
cryptographic properties of functions – the maximum dominance value for individual key values and the
maximum dominance value averaged over the entire set of keys, the maximum and averaged over the
entire set of keys value in the difference distribution table, algebraic degree and algebraic immunity;
– analysis of the obtained results. The paper presents two models for the formation of fixed substitutions
with extremely low cryptographic properties – based on the mixing of cell values in a pre-filled table
and based on the simplest ARX function (consisting of modulo addition, cyclic shift and XOR). The use
of fixed substitutions with extremely low non-linearity makes it possible to estimate how complex (nonlinear)
the function under study is and what minimum level of non-linearity is necessary to effectively
destroy the statistical dependencies between input/output data. In addition, it becomes clear that ARX
functions can be used as non-linear elements, which often have controversial and clearly low cryptographic
properties, but allow creating high-speed software and hardware implementations. It has been
determined that the PRF pCollapser mini-version, in contrast to the typical function based on the SP
network, makes it possible to obtain a high-quality non-linear function from the set of ARX-functions
with extremely low cryptographic properties, given that no other non-linear elements are presented in
pCollapser. The obtained results reflect the existence of a fundamental difference between the
pCollapser PRF and a typical SP-network based PRF and confirm the correctness of the concept of
PD-sbox pseudo-dynamic substitutions and the pCollapser function consisting of them as a whole.
References
funktsiya PCOLLAPSER, obespechivayushchaya ekstremal'nyy parallelizm obrabotki
informatsii [A pseudo-random PCOLLAPSER function that provides extreme parallelism of
information processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2019, No. 5 (207), pp. 88-99. DOI: 10.23683/2311-3103-2019-5-8.
2. Raphael Chung-Wei Phan. Mini Advanced Encryption Standard (Mini-AES): A Testbed for
Cryptanalysis Students, Cryptologia, XXVI (4). Swinburne Sarawak Institute of Technology,
2002, pp. 283-306. Available at: https://doi.org/10.1080/0161-110291890948.
3. Bara Hitapuru, Santi Indarjani. Square attack on Mini-AES and Simplified AES using all
variants of active nibble position, AIP Conference Proceedings, 1729, 020007, 2016. Available
at: https://doi.org/10.1063/1.4946910.
4. Bizaki H.K., Mansoori S.D. and Falahati A. Linear Cryptanalysis on Second Round Mini-
AES, 2006 2nd International Conference on Information & Communication Technologies,
2006, pp. 1958-1962. DOI: 10.1109/ICTTA.2006.1684690.
5. Asadini Dwi Ajeng Gemellia, Santi Indarjani. Differential attack on mini-AES, AIP Conference
Proceedings. 1450, 222, 2012. Available at: https://doi.org/10.1063/1.4724144.
6. Sundari Tianingrum, Santi Indarjani. Algebraic attack on Mini-AES algorithm, AIP Conference
Proceedings. 1729, 020003, 2016. Available at: https://doi.org/10.1063/1.4946906.
7. Liu X. When Mini-AES Meets Machine Learning: Practice and Experience, 2020 IEEE International
Symposium on Systems Engineering (ISSE), 2020, pp. 1-5. DOI: 10.1109/ISSE49799.
2020.9272227.
8. Data Encryption Standard (DES). National Institute of Standards and Technology. FIPS Publication,
46-3, 1999.
9. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Issledovanie lineynykh kharakteristik
psevdo-dinamicheskikh podstanovok [Investigation of linear characteristics of pseudodynamic
substitutions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2015, No. 5 (166), pp. 111-123. Available at: http://izv-tn.tti.sfedu.ru/wpcontent/
uploads/2015/5/11.pdf.
10. Polikarpov S., Rumyantsev K., Petrov D. Computationally efficient method for determining
averaged distribution of differentials for pseudo-dynamic substitutions, International Conference
on Electrical, Electronics, Materials and Applied Science, AIP Conf. Proc., 1952, eds.
V. Rao, A. Ben, S. Bhukya, Amer. Inst. Phys., 2018, UNSP 020091. DOI: 10.1063/1.5032053.
11. Kozhevnikov A.A., Polikarpov S.V., Rumyantsev K.E. On differential properties of a symmetric
cryptoalgorithm based on pseudo-dynamic substitutions, Matematicheskie voprosy kriptografii [Mathematical
Issues of Cryptography], 2016, 7:2, pp. 91-102. DOI: https://doi.org/10.4213/mvk186.
12. Biryukov Alex and Léo Perrin. State of the Art in Lightweight Symmetric Cryptography, IACR
Cryptol. ePrint Arch., 2017. (2017): 511.
13. Howard M. Heys. Key Dependency of Differentials: Experiments in the Differential Cryptanalysis
of Block Ciphers Using Small S-boxes, Cryptology ePrint Archive, Paper 2020/1349.
2020. Available at: https://eprint.iacr.org/2020/1349.
14. Nir Y., Langley A. ChaCha20 and Poly1305 for IETF Protocols. RFC 8439. 2018. ISSN: 2070-
1721.
15. Biham Eli, Shamir Adi. Differential Cryptanalysis of DES-like Cryptosystems, J. Cryptology,
1991, Vol. 4, No. 1, pp. 3-72. DOI: http://dx.doi.org/10.1007/BF00630563.
16. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher, Advances in Cryptology -
EUROCRYPT ’93: Workshop on the Theory and Application of of Cryptographic Techniques,
Lofthus, Norway, May 23-27, 1993: Proceedings, 1993, pp. 386-397. DOI:
http://dx.doi.org/10.1007/3-540-48285-7_33.
17. Zhenzhen Bao and Jian Guo and San Ling and Yu Sasaki. SoK: Peigen – a Platform for Evaluation,
Implementation, and Generation of S-boxes, Cryptology ePrint Archive, Paper
2019/209, 2019.
18. Adrián Ranea and Vincent Rijmen. Characteristic Automated Search of Cryptographic Algorithms
for Distinguishing Attacks (CASCADA), Cryptology ePrint Archive, Paper 2022/513,
2022. DOI: 10.1049/ise2.12077. https://eprint.iacr.org/2022/513
19. Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, and Olivier
Ruatta. Efficient computation of algebraic immunity for algebraic and fast algebraic attacks,
In Proceedings of the 24th annual international conference on The Theory and Applications of
Cryptographic Techniques (EUROCRYPT'06). Springer-Verlag, Berlin, Heidelberg, pp. 147-
164. Available at: https://doi.org/10.1007/11761679_10
20. Eichlseder M. et al. An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application
to Full MiMC. In: Moriai, S., Wang, H. (eds), Advances in Cryptology – ASIACRYPT
2020. ASIACRYPT 2020: Lecture Notes in Computer Science, Vol. 12491. Springer, Cham,
2020. Available at: https://doi.org/10.1007/978-3-030-64837-4_16.
