Volume 27, No 4, 2020, P. 21-57

UDC 519.7+518.25
A. A. Gorodilova, N. N. Tokareva, S. V. Agievich, C. Carlet, E. V. Gorkunov, V. A. Idrisova, N. A. Kolomeec, A. V. Kutsenko, R. K. Lebedev, S. Nikova, A. K. Oblaukhov, I. A. Pankratova, M. A. Pudovkina, V. Rijmen, and A. N. Udovenko
On the Sixth International Olympiad in Cryptography NSUCRYPTO

Abstract:
We present problems of the Sixth International Olympiad in cryptography NSUCRYPTO’2019 along with their solutions. The problems are 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.
Tab. 11, illustr. 7, bibliogr. 21.

Keywords: cryptography, cipher, hash function, Hamming code, slide attack, threshold implementation, Dickson polynomial, APN function, olympiad, NSUCRYPTO.

DOI: 10.33048/daio.2020.27.689

Anastasiya A. Gorodilova ¹
Natalia N. Tokareva ^1,2
Sergey V. Agievich ³
Claude Carlet ⁴
Evgeny V. Gorkunov ^1,5
Valeria A. Idrisova ¹
Nikolay A. Kolomeec ¹
Aleksandr V. Kutsenko ^1,5
Roman K. Lebedev ⁵
Svetla Nikova ⁶
Aleksey K. Oblaukhov ¹
Irina A. Pankratova ⁷
Marina A. Pudovkina ⁸
Vincent Rijmen ⁶
Aleksey N. Udovenko ⁹
1. Sobolev Institute of Mathematics,
4 Akad. Koptyug Avenue, 630090 Novosibirsk, Russia
2. Laboratory of Cryptography JetBrains Research,
1 Pirogov Street, 630090 Novosibirsk, Russia
3. Belarusian State University,
4 Nezavisimost Avenue, 220030 Minsk, Belarus
4. University of Paris 8,
2 Rue de la Liberte, 93200 Saint-Denis, France
5. Novosibirsk State University,
2 Pirogov Street, 630090 Novosibirsk, Russia
6. ESAT-COSIC, KU Leuven,
10 Kasteelpark Arenberg, B-3001 Leuven, Belgium
7. Tomsk State University,
36 Lenin Avenue, 634050 Tomsk, Russia
8. Bauman Moscow State Technical University,
5/1 Vtoraya Baumanskaya Street, 105005 Moscow, Russia
9. SnT, University of Luxembourg,
2 Avenue de l’Universite, L-4365 Esch-sur-Alzette, Luxembourg
e-mail: nsucrypto@nsu.ru

Received May 20, 2020
Revised August 18, 2020
Accepted August 21, 2020

References

[1] The official website of NSUCRYPTO (Novosibirsk State Univ., Novosibirsk, 2020). Available at nsucrypto.nsu.ru (accessed Sept. 24, 2020).

[2] Unsolved problems of NSUCRYPTO. Available at nsucrypto.nsu.ru/unsolved-problems (accessed Sept. 24, 2020).

[3] K. L. Geut, K. A. Kirienko, P. O. Sadkov, R. I. Taskin, and S. S. Titov, On explicit constructions for solving the problem “A secret sharing”, Prikl. Diskretn. Mat., Prilozh., No. 10, 68–70 (2017) [Russian].

[4] S. V. Agievich, A. A. Gorodilova, V. A. Idrisova, N. A. Kolomeec, G. I. Shushuev, and N. N. Tokareva, Mathematical problems of the Second International Students’ Olympiad in Cryptography, Cryptologia 41 (6), 534–565 (2017).

[5] S. V. Agievich, A. A. Gorodilova, N. A. Kolomeec, S. Nikova, B. Preneel, V. Rijmen, G. I. Shushuev, N. N. Tokareva, and V. A. Vitkup, Problems, solutions and experience of the First International Students’
Olympiad in Cryptography, Prikl. Diskretn. Mat., No 3, 41–62 (2015).

[6] A. A. Gorodilova, S. V. Agievich, C. Carlet, E. V. Gorkunov, V. A. Idrisova, N. A. Kolomeec, A. V. Kutsenko, S. Nikova, A. K. Oblaukhov, S. Picek, B. Preneel, V. Rijmen, and N. N. Tokareva, Problems and solutions from the Fourth International Students’ Olympiad in Cryptography (NSUCRYPTO), Cryptologia. 43 (2), 138–174 (2019).

[7] A. A. Gorodilova, S. V. Agievich, C. Carlet, X. Hou, V. A. Idrisova, N. A. Kolomeec, A. V. Kutsenko, L. Mariot, A. K. Oblaukhov, S. Picek, B. Preneel, R. Rosie, and N. N. Tokareva, The Fifth International Students’ Olympiad in Cryptography – NSUCRYPTO: Problems and their solutions, Cryptologia 44 (3), 223–256 (2020).

[8] N. N. Tokareva, A. A. Gorodilova, S. V. Agievich, V. A. Idrisova, N. A. Kolomeec, A. V. Kutsenko, A. K. Oblaukhov, and G. I. Shushuev, Mathematical methods in solutions of the problems presented at the
Third International Students’ Olympiad in Cryptography, Prikl. Diskretn. Mat., No. 40, 34–58 (2018).

[9] B. Schneier, Applied cryptography: Protocols, algorithms and source code in C (Wiley, Hoboken, NJ, 1996).

[10] R. E. Lewand, Cryptological mathematics (MAA Press, Washington, DC, 2000).

[11] Letter frequency, in Wikipedia (Wikimedia Foundation, San Francisco, 2020). Available at en.wikipedia.org/wiki/Letter_frequency (accessed Sept. 24, 2020).

[12] Find words using pattern matching, in Litscape.com (The Bitmill, Calgary, 2018). Available at www.litscape.com/word_tools/pattern_match.php (accessed Sept. 24, 2020).

[13] M. Brinkmann and G. Leander, On the classification of APN functions up to dimension five, Des. Codes Cryptogr. 49 (1–3), 273–288 (2008).

[14] C. De Cannière, Analysis and design of symmetric encryption algorithms, PhD thesis (Katholieke Univ. Leuven, Heverlee, 2007).

[15] Test server for the problem TwinPeaks3. Available at nsucrypto.nsu.ru/archive/2019/round/2/task/4 (accessed Sept. 24, 2020).

[16] An implementation for the function Curl27 in Java. Available at nsucrypto.nsu.ru/media/Olympiads/2019/Round_2/Tasks/curl27.java (accessed Aug. 24, 2020).

[17] 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 (Rev. Sel. Pap. 5th Int. Conf. Cryptol. Inform. Secur. Latin America, Havana, Cuba, Sept. 20–22, 2017) (Springer, Cham, 2019), pp. 191–206 (Lect. Notes Comput. Sci., Vol. 11368).

[18] D. B. Fomin, New classes of 8-bit permutations based on a butterfly structure, Mat. Vopr. Kriptogr. 10 (2), 169–180 (2019).

[19] C. Carlet, Componentwise APNness, Walsh uniformity of APN functions, and cyclic-additive difference sets, Finite Fields Appl. 53, 226–253 (2018).

[20] C. Carlet, On APN exponents, characterizations of differentially uniform functions by the Walsh transform, and related cyclic-difference-set-like structures, Des. Codes Cryptogr. 87 (2–3), 203–224 (2019).

[21] Total results of NSUCRYPTO’2019. Available at nsucrypto.nsu.ru/archive/ 2019/total_results/#data (accessed Sept. 24, 2020).