COMPUTATIONALLY EFFICIENT METHOD FOR DETERMINING THE AVERAGE LINEAR PROPERTIES OF PSEUDO-DYNAMIC SUBSTITUTIONS
Keywords:
Pseudo-random functions, linear cryptanalysis, pseudo-dynamic substitutions
Abstract
Pseudo-dynamic substitutions PD-sbox can become an effective replacement for fixed substitutions
in pseudo-random functions, since they have the positive properties of both fixed substitutions
(low consumption of computational resources) and dynamic substitutions (which can radically complicate
the application of statistical cryptanalysis methods). The problem of active implementation of
pseudo-dynamic substitutions is, inter alia, the absence of a computationally efficient method for
determining the averaged linear properties for the entire set of equivalent substitutions generated
using PD-sbox, while in most cases, only the determination of the maximum values of the prevalence
(bias) bias (α, β) from the ideal value 1/2. To solve this problem, an original method is proposed,
which consists in the fact that the maximum dominance values are calculated only for relatively small
fixed substitutions included in the PD-sbox, and the resulting maximum dominance values are obtained
by iterative calculation using a logical-probabilistic expression for the Exclusive OR operation
-NO (XNOR). The effect of using the proposed method is a dramatic reduction in computational
operations and, accordingly, the possibility of determining on a typical personal computer the maximum
values of the prevalence bias (α, β) for 16-element PD-sboxes consisting of 8-bit fixed substitutions
(which is unattainable when using a trivial method).
References
1. Preneel B. Final report of European project number IST-1999-12324, named New European
Schemes for Signatures, Integrity, and Encryption. Berlin Heidelberg NewYork London Paris
Tokyo Hong Kong Barcelona Budapest: Springer-Verlag, 2004.
2. Matsui M. The first experimental cryptanalysis of the data encryption standard, Y. Desmedt
(ed.), CRYPTO, Lecture Notes in Computer Science, Vol. 839. Springer, 1994, pp. 1-11.
3. Harpes C., Kramer G.G., Massey J.L. A generalization of linear cryptanalysis and the applicability
of Matsui’s piling-up lemma, L.C. Guillou, J.-J. Quisquater (eds.), EUROCRYPT, Lecture
Notes in Computer Science, Vol. 921. Springer, 1995, pp. 24-38.
4. Selçuk A.A. On probability of success in linear and differential cryptanalysis, J. Cryptology,
2008, Vol. 21 (1), pp. 131-147.
5. Bogdanov A., Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block
Ciphers. Designs, Codes and Cryptography. Springer, US, 2012, pp. 1-15.
6. Long Wen, Meiqin Wang, Andrey Bogdanov, Huaifeng Chen. Multidimensional zerocorrelation
attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO
standard, Information Processing Letters, 2014, Vol. 114, Issue 6, pp. 322-330. Available at:
https://doi.org/10.1016/j.ipl.2014.01.007.
7. Andrey Bogdanov, Elif Bilge Kavun, Elmar Tischhauser, Tolga Yalçın. Large-scale highresolution
computational validation of novel complexity models in linear cryptanalysis, Journal
of Computational and Applied Mathematics, 2014, Vol. 259, Part B, pp. 592-598.
Available at: https://doi.org/10.1016/j.cam.2013.10.020.
8. Eichlseder M., Leander G., & Rasoolzadeh S. (Accepted/In press). Computing Expected Differential
Probability of (Truncated) Differentials and Expected Linear Potential of (Multidimensional)
Linear Hulls in SPN Block Ciphers. In Progress in Cryptology - IndoCrypt 2020.
9. Logachev O.A., Sal'nikov A.A., Yashchenko V.V. Bulevy funktsii v teorii kodirovaniya i
kriptologii [Boolean functions in coding theory and cryptology]. Moscow: Moskovskiy tsentr
nepreryvnogo matematicheskogo obrazovaniya, 2004, 470 p.
10. Security Advisory 2868725: Recommendation to disable RC4. Security Research and Defense
Blog. Available at: http://blogs.technet.com/b/srd/archive/2013/11/12/security-advisory-
2868725-recommendation-to-disable-rc4.aspx.
11. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki:
osnova sovremennykh simmetrichnykh kriptoalgoritmov [Pseudo-dynamic substitutions: the basis
of modern symmetric cryptoalgorithms], Nauchnoe obozrenie [Scientific Review], 2014, No. 12,
pp. 162-166. Available at: http://www.sced.ru/ru/files/7_12_1_2014/7_12_1_2014.pdf.
12. 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.
13. Polikarpov S.V., Kozhevnikov A.A. Psevdo-dinamicheskie podstanovoki: issledovanie lineynykh
svoystv [Pseudo-dynamic substitutions: investigation of linear propertie], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 8 (169), pp. 19-31.
14. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy
podstanovki: issledovanie differentsial'nykh kharakteristik [Pseudo-dynamic substitutions: research
of differential characteristics], Fiziko-matematicheskie metody i informatsionnye
tekhnologii v estestvoznanii, tekhnike i gumanitarnykh naukakh: sbornik materialov
mezhdunarodnogo nauchnogo e-simpoziuma [Physical and mathematical methods and information
technologies in natural science, engineering and humanities: collection of materials of
the international scientific e-symposium]. Electron. text data. Russia. Moscow, 2014. Kirov:
MTSNIP, 2015, pp. 77-89.
15. Sergey Polikarpov, Konstantin Rumyantsev and Dmitry Petrov. Computationally efficient
method for determining averaged distribution of differentials for pseudo-dynamic substitutions,
AIP Conference Proceedings 1952, 020091. 2018.
16. Polikarpov S., Petrov D., Kozhevnikov A. On A Class Pseudo-Dynamic Substitutions
PD-Sbox, With A Perfect Averaged Distribution of Differentials in Static Mode of Work, Proceedings
of the 2017 International Conference on Cryptography, Security and Privacy. Wuhan,
China: ACM, 2017, pp. 17-21. (ICCSP 17). ISBN 978-1-4503-4867-6. DOI:
10.1145/3058060.3058087. Available at: http://doi.acm.org/10.1145/3058060.3058087.
17. 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 questions of Cryptography], 2016, Vol. 7:2, pp. 91-102. Available
at: https://doi.org/10.4213/mvk186.
18. Polikarpov S.V., Kozhevnikov A.A., Rumyantsev K.E., Prudnikov V.A. Psevdosluchaynaya
funktsiya PCOLLAPSER, obespechivayushchaya ekstremal'nyy parallelizm obrabotki
informatsii [Pseudo-random function PCOLLAPSER providing extreme parallelism of information
processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2019, No. 5 (207), pp. 88-100.
19. 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. Available at:
http://dx.doi.org/10.1007/3-540-48285-7_33.
20. Ryabinin I.A. Logiko-veroyatnostnyy analiz problem i nadezhnosti, zhivuchesti i bezopasnosti:
ocherki raznykh let [Logical-probabilistic analysis of problems and reliability, survivability
and safety: essays from different years]. YURGTU, 2009. 599 p. Available at:
https://books.google.ru/books?id=7ACRkgAACAAJ.
Schemes for Signatures, Integrity, and Encryption. Berlin Heidelberg NewYork London Paris
Tokyo Hong Kong Barcelona Budapest: Springer-Verlag, 2004.
2. Matsui M. The first experimental cryptanalysis of the data encryption standard, Y. Desmedt
(ed.), CRYPTO, Lecture Notes in Computer Science, Vol. 839. Springer, 1994, pp. 1-11.
3. Harpes C., Kramer G.G., Massey J.L. A generalization of linear cryptanalysis and the applicability
of Matsui’s piling-up lemma, L.C. Guillou, J.-J. Quisquater (eds.), EUROCRYPT, Lecture
Notes in Computer Science, Vol. 921. Springer, 1995, pp. 24-38.
4. Selçuk A.A. On probability of success in linear and differential cryptanalysis, J. Cryptology,
2008, Vol. 21 (1), pp. 131-147.
5. Bogdanov A., Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block
Ciphers. Designs, Codes and Cryptography. Springer, US, 2012, pp. 1-15.
6. Long Wen, Meiqin Wang, Andrey Bogdanov, Huaifeng Chen. Multidimensional zerocorrelation
attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO
standard, Information Processing Letters, 2014, Vol. 114, Issue 6, pp. 322-330. Available at:
https://doi.org/10.1016/j.ipl.2014.01.007.
7. Andrey Bogdanov, Elif Bilge Kavun, Elmar Tischhauser, Tolga Yalçın. Large-scale highresolution
computational validation of novel complexity models in linear cryptanalysis, Journal
of Computational and Applied Mathematics, 2014, Vol. 259, Part B, pp. 592-598.
Available at: https://doi.org/10.1016/j.cam.2013.10.020.
8. Eichlseder M., Leander G., & Rasoolzadeh S. (Accepted/In press). Computing Expected Differential
Probability of (Truncated) Differentials and Expected Linear Potential of (Multidimensional)
Linear Hulls in SPN Block Ciphers. In Progress in Cryptology - IndoCrypt 2020.
9. Logachev O.A., Sal'nikov A.A., Yashchenko V.V. Bulevy funktsii v teorii kodirovaniya i
kriptologii [Boolean functions in coding theory and cryptology]. Moscow: Moskovskiy tsentr
nepreryvnogo matematicheskogo obrazovaniya, 2004, 470 p.
10. Security Advisory 2868725: Recommendation to disable RC4. Security Research and Defense
Blog. Available at: http://blogs.technet.com/b/srd/archive/2013/11/12/security-advisory-
2868725-recommendation-to-disable-rc4.aspx.
11. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki:
osnova sovremennykh simmetrichnykh kriptoalgoritmov [Pseudo-dynamic substitutions: the basis
of modern symmetric cryptoalgorithms], Nauchnoe obozrenie [Scientific Review], 2014, No. 12,
pp. 162-166. Available at: http://www.sced.ru/ru/files/7_12_1_2014/7_12_1_2014.pdf.
12. 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.
13. Polikarpov S.V., Kozhevnikov A.A. Psevdo-dinamicheskie podstanovoki: issledovanie lineynykh
svoystv [Pseudo-dynamic substitutions: investigation of linear propertie], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 8 (169), pp. 19-31.
14. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy
podstanovki: issledovanie differentsial'nykh kharakteristik [Pseudo-dynamic substitutions: research
of differential characteristics], Fiziko-matematicheskie metody i informatsionnye
tekhnologii v estestvoznanii, tekhnike i gumanitarnykh naukakh: sbornik materialov
mezhdunarodnogo nauchnogo e-simpoziuma [Physical and mathematical methods and information
technologies in natural science, engineering and humanities: collection of materials of
the international scientific e-symposium]. Electron. text data. Russia. Moscow, 2014. Kirov:
MTSNIP, 2015, pp. 77-89.
15. Sergey Polikarpov, Konstantin Rumyantsev and Dmitry Petrov. Computationally efficient
method for determining averaged distribution of differentials for pseudo-dynamic substitutions,
AIP Conference Proceedings 1952, 020091. 2018.
16. Polikarpov S., Petrov D., Kozhevnikov A. On A Class Pseudo-Dynamic Substitutions
PD-Sbox, With A Perfect Averaged Distribution of Differentials in Static Mode of Work, Proceedings
of the 2017 International Conference on Cryptography, Security and Privacy. Wuhan,
China: ACM, 2017, pp. 17-21. (ICCSP 17). ISBN 978-1-4503-4867-6. DOI:
10.1145/3058060.3058087. Available at: http://doi.acm.org/10.1145/3058060.3058087.
17. 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 questions of Cryptography], 2016, Vol. 7:2, pp. 91-102. Available
at: https://doi.org/10.4213/mvk186.
18. Polikarpov S.V., Kozhevnikov A.A., Rumyantsev K.E., Prudnikov V.A. Psevdosluchaynaya
funktsiya PCOLLAPSER, obespechivayushchaya ekstremal'nyy parallelizm obrabotki
informatsii [Pseudo-random function PCOLLAPSER providing extreme parallelism of information
processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2019, No. 5 (207), pp. 88-100.
19. 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. Available at:
http://dx.doi.org/10.1007/3-540-48285-7_33.
20. Ryabinin I.A. Logiko-veroyatnostnyy analiz problem i nadezhnosti, zhivuchesti i bezopasnosti:
ocherki raznykh let [Logical-probabilistic analysis of problems and reliability, survivability
and safety: essays from different years]. YURGTU, 2009. 599 p. Available at:
https://books.google.ru/books?id=7ACRkgAACAAJ.
Published
2021-01-19
Issue
Section
SECTION I. INFORMATION PROCESSING ALGORITHMS
