The Fifth International Students' Olympiad in Cryptography - NSUCRYPTO: problems and their solutions

Anastasiya Gorodilova, Sergey Agievich, Claude Carlet, Xiang-dong Hou, Valeriya Idrisova, Nikolay Kolomeec, Alexandr Kutsenko, Luca Mariot, Alexey Oblaukhov, Stjepan Picek, Bart Preneel, Razvan Rosie, Natalia N. TokarevaCryptologia 2019 · DOI · OpenReview

Abstract

This paper presents the problems and solutions from the Fifth International Students’ Olympiad in Cryptography (NSUCRYPTO 2018). We explore a diverse range of cryptographic challenges, including attacks on ciphers and hash functions, properties of Boolean functions, quantum circuit optimization, and specialized matrix theory. A key highlight is the formal resolution of an open problem regarding Sylvester matrices by participant teams.

Introduction: Bridging the Gap in Cryptography Education

The NSUCRYPTO Olympiad is a global initiative designed to bridge the gap between undergraduate mathematics and professional cryptographic research. While standard academic curricula often focus on established protocols like AES or RSA, they rarely expose students to the "messy," unsolved problems found in modern research. NSUCRYPTO addresses this "knowledge gap" by presenting a tiered set of challenges, ranging from school-level puzzles to open problems that have stumped the academic community. By documenting these solutions, this paper provides a pedagogical roadmap for analyzing and breaking complex cryptographic primitives.

Methodology: A Multi-Domain Approach

The analysis covers 16 distinct problems, employing a variety of mathematical and algorithmic methods:

  • Mathematical Proofs: Applied to problems involving Boolean functions and Reed-Muller codes, often utilizing modular arithmetic and linear algebra.
  • Algorithmic Analysis: Solutions for sequence-based ciphers and hash collisions (such as FNV-1a) leverage the LLL (Lenstra–Lenstra–Lovász) lattice reduction algorithm.
  • Quantum Logic: Problems involving quantum circuits are addressed by simplifying Dirac notation representations into classical Boolean functions.
  • Cryptanalysis: Challenges like "Stickers" and "Enigma" (which utilized the text of Herman Melville’s Moby Dick as plaintext) require "outside-the-box" thinking, combining visual pattern recognition with classical frequency analysis and known-plaintext attacks.

Key Insights and Ideas

One of the most significant breakthroughs during the 2018 Olympiad was the formal proof regarding Sylvester matrices. Participants successfully proved that for polynomials of degree $m$ and $n$, an invertible Sylvester matrix has an inverse that is also a Sylvester matrix if and only if $m \le n$ (under specific conditions). This moved a previously "unsolved" problem into the "solved" category.

Another critical insight involves Quantum Circuit Reduction. The Olympiad demonstrated that complex-looking quantum gate sequences can often be reduced to simple "swap" operations. This reduction allows researchers to analyze quantum ciphers using classical Boolean logic, significantly simplifying the cryptanalytic process.

A complex quantum circuit analyzed during the Olympiad, featuring multiple gates and measurement operations.
A simplified quantum gate sequence representing a 'swap' operation, used to reduce complex circuits to classical logic.

Additionally, the "A Sequence" problem highlighted how the superincreasing property of a sequence allows for efficient decryption, turning a seemingly hard problem into a simple linear-time comparison, reminiscent of the Merkle-Hellman knapsack cryptosystem.

Key Results and Global Impact

The 2018 Olympiad attracted over 1,600 participants from 52 countries, reflecting a high global interest in competitive cryptography. Out of 16 problems, 13 were fully solved. Key technical results include:

  • Hash Collisions: The paper provides concrete hexadecimal strings representing collisions for the FNV-1a hash function, demonstrating the practical application of the LLL algorithm in finding small-coordinate solutions in a lattice.
  • Mathematical Bounds: For the "Key Matrices" problem, tight theoretical bounds were established for the number of 1s in a binary matrix where every diagonal must have an odd number of 1s ($2n+1$ for minimum and $n^2-n+1$ for maximum).

Limitations and Future Work

Despite these successes, three problems remain officially unsolved or only partially addressed:

  1. Orthogonal Arrays: Finding a 4-(2, 11, $\lambda$) orthogonal array with a minimal value of $\lambda$ remains an open challenge. While $\lambda=8$ is known, it is unproven if a smaller $\lambda$ exists.
  2. Disjunct Matrices: The original formulation of the "5-disjunct matrix" problem was found to be trivialized by a missing constraint, leaving room for more rigorous future bounds.
  3. Metrical Cryptosystems: While "Metrical Cryptosystem – 2" was solved, "strongly metrically regular sets" remain a deep area of study with many open questions in higher dimensions.

The community is invited to submit solutions to these remaining open problems via the NSUCRYPTO web portal, maintaining the Olympiad as a living research project.

Summary updated

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.
BibTeX
@inproceedings{gorodilova2019fifth,
  author = {Anastasiya Gorodilova and Sergey Agievich and Claude Carlet and Xiang-dong Hou and Valeriya Idrisova and Nikolay Kolomeec and Alexandr Kutsenko and Luca Mariot and Alexey Oblaukhov and Stjepan Picek and Bart Preneel and Razvan Rosie and Natalia N. Tokareva},
  title = {{The Fifth International Students' Olympiad in Cryptography - NSUCRYPTO: problems and their solutions}},
  booktitle = {Cryptologia},
  year = {2019},
  doi = {10.1080/01611194.2019.1670282},
}
Figure