Abstract
NSUCRYPTO is the unique cryptographic Olympiad containing scientific mathematical problems for professionals, school and university students from any country. Its aim is to involve young researchers in solving curious and tough scientific problems of modern cryptography. From the very beginning, the concept of the Olympiad was not to focus on solving olympic tasks but on including unsolved research problems at the intersection of mathematics and cryptography. The Olympiad history starts in 2014. In 2019, it was held for the sixth time. We present the problems and their solutions of the Sixth International Olympiad in cryptography NSUCRYPTO \(^{\prime} \)2019. Under consideration are the problems related to attacks on ciphers and hash functions, protocols, Boolean functions, Dickson polynomials, prime numbers, rotor machines, etc. We discuss several open problems on mathematical countermeasures to side-channel attacks, APN involutions, S-boxes, etc. The problem of finding a collision for the hash function Curl27 was partially solved during the Olympiad.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
https://nsucrypto.nsu.ru/.
https://nsucrypto.nsu.ru/unsolved-problems/.
K. Geut, K. Kirienko, P. Sadkov, R. Taskin, and S. Titov, “On Explicit Constructions for Solving the Problem ‘A Secret Sharing’,” Prikl. Diskret. Mat. Pril. No. 10, 68–70 (2017).
S. Agievich, A. Gorodilova, N. Kolomeec, S. Nikova, B. Preneel, V. Rijmen, G. Shushuev, N. Tokareva, and V. Vitkup, “Problems, Solutions, and Experience of the First International Student’s Olympiad in Cryptography,” Prikl. Diskret. Mat. (Appl. Discret. Math.) No. 3, 41–62 (2015).
S. Agievich, A. Gorodilova, V. Idrisova, N. Kolomeec, G. Shushuev, and N. Tokareva, “Mathematical Problems of the Second International Student’s Olympiad in Cryptography,” Cryptologia 41 (6), 534–565 (2017).
N. Tokareva, A. Gorodilova, S. Agievich, V. Idrisova, N. Kolomeec, A. Kutsenko, A. Oblaukhov, and G. Shushuev, “Mathematical Methods in Solutions of the Problems from the Third International Students’ Olympiad in Cryptography,” Prikl. Diskret. Mat. (Appl. Discret. Math.) No. 40, 34–58 (2018).
A. Gorodilova, S. Agievich, C. Carlet, E. Gorkunov, V. Idrisova, N. Kolomeec, A. Kutsenko, S. Nikova, A. Oblaukhov, S. Picek, B. Preneel, V. Rijmen, and N. Tokareva, “Problems and Solutions of the Fourth International Students Olympiad in Cryptography (NSUCRYPTO),” Cryptologia 43 (2), 138–174 (2019).
A. Gorodilova, S. Agievich, C. Carlet, X. Hou, V. Idrisova, N. Kolomeec, A. Kutsenko, L. Mariot, A. Oblaukhov, S. Picek, B. Preneel, R. Rosie, and N. Tokareva, “The Fifth International Students’ Olympiad in Cryptography—NSUCRYPTO: Problems and Their Solutions,” Cryptologia 44 (3), 223–256 (2020).
B. Schneier, Applied Cryptography: Protocols, Algorithms and Source Code in C, 2nd Ed. (Wiley, Indianapolis, 1996).
R. E. Lewand, Cryptological Mathematics (MAA, Washington, 2000).
“Letter Frequency,” in Wikipedia. Available at https://en.wikipedia.org/wiki/Letter_frequency.
“Find Words Using Pattern Matching,” in Litscape.com. Available at http://www.litscape.com/word_tools/pattern_match.php.
M. Brinkmann and G. Leander, “On the Classification of APN Functions up to Dimension Five,” Designs, codes and cryptography 49, 273–288 (2008).
C. De Canni‘ere, Analysis and Design of Symmetric Encrytption Algorithms, Ph.D. Thesis (Katholieke Universiteit Leuven, Heverlee, 2007).
https://nsucrypto.nsu.ru/archive/2019/round/2/task/4/.
https://nsucrypto.nsu.ru/media/Olympiads/ 2019/Round_2/Tasks/curl27.java.
R. A. de la Cruz Jimènez, “Generation of \(8 \)-Bit S-Boxes Having Almost Optimal Cryptographic Properties Using Smaller \(4\)-Bit S-Boxes and Finite Field Multiplication,” in Progress in Cryptology—LATINCRYPT 2017 : 5th International Conference on Cryptology and Information Security in Latin America (Havana, Cuba, September 20–22, 2017): Revised Selected Papers, Ed. by T. Lange and O. Dunkelman (Springer, Cham, 2019), pp. 191–206 [Lecture Notes in Computer Science, Vol. 11368].
D. B. Fomin, “New Classes of \(8 \)-Bit Permutations Based on a Butterfly Structure,” Mat. Vopr. Kript. 10 (2), 169–180 (2019). https://ctcrypt.ru/files/files/2018/09_Fomin.pdf.
C. Carlet, “Componentwise APNness, Walsh Uniformity of APN Functions, and Cyclic-Additive Difference Sets,” Finite Fields and Their Applications 53, 226–253 (2018).
C. Carlet, “On APN Exponents, Characterizations of Differentially Uniform Functions by the Walsh Transform, and Related Cyclic-Difference-Set-Like Structures,” in Proceedings of WCC 2017 Designs, Codes and Cryptography 87, 203–224 (2018).
https://nsucrypto.nsu.ru/archive/2019/total_results/#data.
Funding
The work of the first two authors and the sixth author was supported by the Mathematical Center in Akademgorodok under Agreement No. 075–15–2019–1613 with the Ministry of Science and Higher Education of the Russian Federation and the Laboratory of Cryptography JetBrains Research. The work of the fifth author was supported by the State Task to the Sobolev Institute of Mathematics (project no. 0314–2019–0016). The work of the seventh, eighth, and eleventh authors was supported by the Russian Foundation for Basic Research (projects nos. 20–31–70043, 18–07–01394, and 19–31–90093).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Translated by A. Gorodilova
Rights and permissions
About this article
Cite this article
Gorodilova, A.A., Tokareva, N.N., Agievich, S.V. et al. On the Sixth International Olympiad in Cryptography NSUCRYPTO. J. Appl. Ind. Math. 14, 623–647 (2020). https://doi.org/10.1134/S1990478920040031
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478920040031