The Fifth International Students’ Olympiad in cryptography—NSUCRYPTO: Problems and their solutions

Abstract

Problems and their solutions of the Fifth International Students’ Olympiad in cryptography NSUCRYPTO’2018 are presented. We consider problems related to attacks on ciphers and hash functions, Boolean functions, quantum circuits, Enigma, etc. We discuss several open problems on orthogonal arrays, Sylvester matrices, and disjunct matrices. The problem of existing an invertible Sylvester matrix whose inverse is again a Sylvester matrix was completely solved during the Olympiad.

Keywords:

• hash functions
• Enigma
• quantum circuits
• metrically regular sets
• irreducible polynomials
• orthogonal arrays
• Sylvester matrices
• disjunct matrices
• Olympiad
• NSUCRYPTO

About the authors

Anastasiya Gorodilova is a researcher at the Sobolev Institute of Mathematics; an Assistant Professor at Novosibirsk State University; a researcher at the Mathematical center in Akademgorodok. She is interested in cryptographic Boolean functions, APN functions, bent functions, symmetric cryptography, combinatorics, and algebra.

Sergey Agievich is the head of the IT Security Research Laboratory of the Research Institute for Applied Problems of Mathematics and Informatics (Belarusian State University). His research interests include Boolean functions in cryptography, cryptographic algorithms and protocols, enumerative and asymptotic combinatorics, exponential sums and systems of polynomial equations.

Claude Carlet is a Professor emeritus of mathematics at the University of Paris 8, Laboratory LAGA; a member of the Department of Informatics of the University of Bergen. His research interests include algebra, coding theory and cryptography, cryptographic Boolean functions.

Xiang-dong Hou is a Professor at the faculty of Mathematics and Statistics in the University of South Florida. His research areas are algebra, number theory, coding theory and cryptography, combinatorics, and topology.

Valeria Idrisova is a researcher at the Sobolev Institute of Mathematics and Novosibirsk State University; a researcher at the Mathematical center in Akademgorodok. Her research interests includes vectorial Boolean functions, APN permutations, block ciphers, and side-channel attacks.

Nikolay Kolomeec is a researcher at the Sobolev Institute of Mathematics; an Assistant at Novosibirsk State University; a researcher in Mathematical center in Akademgorodok. Research areas are pseudorandom sequences, cryptographic Boolean functions, bent functions, and discrete mathematics.

Alexandr Kutsenko is a PhD student at the Department of Mathematics and Mechanics in Novosibirsk State University; a researcher at the Mathematical center in Akademgorodok. His research interests include mathematical problems of quantum cryptography and cryptographic Boolean functions.

Luca Mariot is a postdoctoral researcher at the University of Milano-Bicocca, and a member of the BiS Lab (Bicocca Security Lab). His research interests include natural computing models and techniques for cryptography.

Alexey Oblaukhov is a PhD student at the Sobolev Institute of Mathematics; an assistant at Novosibirsk State University; a researcher at the Mathematical center in Akademgorodok. His research interests are blockchain technologies, cryptography, and discrete mathematics.

Stjepan Picek is an assistant professor in the Cyber Security research group of the faculty of Electrical Engineering, Mathematics and Computer Science at Delft University of Technology. His main research interests are at the intersection of cryptography, cybersecurity, evolutionary computation, and machine learning.

Bart Preneel is a full professor in the research group COSIC of the Electrical Engineering Department of KU Leuven; a director of the International Association for cryptologic Research. Main interests are cryptography and information security. His research focuses on cryptographic algorithms and protocols as well as their applications to computer and network security and mobile communications.

Razvan Rosie is a researcher at University of Luxembourg. His research interests are in data security, focusing on constructions and applications of primitives in the area of public-key cryptography.

Natalia Tokareva is a senior researcher in the Sobolev Institute of Mathematics; associate professor at Novosibirsk State University; a head of the Laboratory of Cryptography JetBrains Research; a researcher at the Mathematical center in Akademgorodok. Her research interests include Boolean functions in cryptography, bent functions, block and stream ciphers, cryptanalysis, coding theory, combinatorics, and algebra.

Notes

1. This means that an input letter is processed, in order, by three permutation—right, middle, and left—reflected by the reflector, and processed once again, in order, by the inverse permutations corresponding to left, middle and right rotors before being output. Once the letter passes through a rotor, it is permuted with one position, the rotor’s permutation is applied, and the result goes directly into the following rotor, which acts similarly.

Additional information

Funding

The paper was supported by the Russian Ministry of Science and Education (the 5–100 Excellence Programme and the Project no. 1.13559.2019/13.1), by the Russian Foundation for Basic Research (project nos. 18-07-01394, 18-31-00479, and 18-31-00374), by the program of fundamental scientific researches of the SB RAS no. I.5.1, project no. 0314-2019-0017, by JetBrains Research, Novosibirsk, Russia.