Pavol Zajac

Multiple Right-Hand Sides (MRHS) equations represent a mathematical formalism with applications in algebraic cryptanalysis. Solving MRHS equation systems is in general a difficult problem. In this article, we investigate the efficient use of genetic algorithms for solving random sparse MRHS systems. Our experiments suggest that the steady-state selection method with low elitism and mutation rate gives the best results. If the systems are sparse, the system size does not have a significant impact on the success of the algorithm. On the other hand, the method is very sensitive to the system density, with the success rate rapidly declining with increased system density.

The syndrome decoding problem (SDP) is an NPcomplete problem that has important applications in the development of post-quantum cryptography. Currently, the most efficient algorithms for SDP are based on the Information Set Decoding (ISD) approach that leverages efficiently time-memory and probability trade-offs. In our contribution, we explore a different approach based on transforming an instance of the SDP problem into a so-called Multiple Right-Hand-Sides (MRHS) Equation system. The MRHS system is then solved with a specialized MRHS solver. We explore how difficult is to solve (small) instances of SDP in MRHS form, and which trade-offs and parametric selections lead to the best results. Although our practical results are worse than those obtained by ISD, we believe that they show a better understanding of the connection between SDP and its MRHS representation, and can be a basis for future improvements.

The regular decoding problem asks for (the existence of) regular solutions to a syndrome decoding problem (SDP). This problem has increased applications in post-quantum cryptography and cryptanalysis. Recently, Esser and Santini explored in depth the connection between the regular (RSD) and classical syndrome decoding problems. They have observed that while RSD to SDP reductions are known (in any parametric regime), a similar generic reduction from SDP to RSD is not known. In our contribution, we examine two different generic polynomial reductions from a syndrome decoding problem to a regular decoding problem instance. The first reduction is based on constructing a special parity check matrix that encodes weight counter progression inside the parity check matrix, which is then the input of the regular decoding oracle. The target regular decoding problem has a significantly longer code length, that depends linearly on the weight parameter of the original SDP. The second reduction is based on translating the SDP to a non-linear system of equations in the Multiple Right-Hand Sides form, and then applying RSD oracle to solve this system. The second reduction has better code length. The ratio between RSD and SDP code length of the second reduction can be bounded by a constant (less than 8).

One of the tasks of security analysts is to detect security vulnerabilities and ongoing attacks. There is already a large number of software tools that can help to collect security-relevant data, such as event logs, security settings, application manifests, and even the (decompiled) source code of potentially malicious applications. The analyst must study these data, evaluate them, and properly identify and classify suspicious activities and applications. Fast advances in the area of Artificial Intelligence have produced large language models that can perform a variety of tasks, including generating text summaries and reports. In this article, we study the potential black-box use of LLM chatbots as a support tool for security analysts. We provide two case studies: the first is concerned with the identification of vulnerabilities in Android applications, and the second one is concerned with the analysis of security logs. We show how LLM chatbots can help security analysts in their work, but point out specific limitations and security concerns related to this approach.

Ascon is a family of lightweight authenticated encryption and hashing algorithms, which is a finalist in the NIST Lightweight Cryptography competition. We study the Ascon algorithm from the perspective of algebraic cryptanalysis based on the MRHS representation of the cipher. We call such an approach an MRHS cryptanalysis. We represent the system on the gate level (focusing on individual AND-gates) and the S-box level (basing MRHS equations on 5-bit S-boxes). We compare the results from the application of two custom MRHS solvers. The RZ solver is based on linear algebra and exhaustive search. The HC solver is based on adaptive bit-flipping with restarts. We show that both the choice of the solver and the choice of the system representation influence the total complexity of the attack. On the other hand, these choices do not change the fundamental properties of the attack, such as scaling with the amount of information the attacker possesses. A similar assessment holds for using a scaled-down version of Ascon for the experiments. Our method can be used for the experimental evaluation of cipher designs against algebraic attacks.

PQC migration represents multiple challenges in education. We will need to educate our future cryptography researchers and engineers on new topics, introduce new challenges, and explain new cryptographic primitives. In the paper, we present our view on education challenges associated with the transition to post-quantum cryptography.

In this work, we survey the existing research in the area of algebraic cryptanalysis based on Multiple Right-Hand Sides (MRHS) equations (MRHS cryptanalysis). MRHS equation is a formal inclusion that contains linear combinations of variables on the left-hand side, and a potential set of values for these combinations on the right-hand side. We describe MRHS equation systems in detail, including the evolution of this representation. Then we provide an overview of the methods that can be used to solve MRHS equation systems. Finally, we explore the use of MRHS equation systems in algebraic cryptanalysis and survey existing experimental results.

Cryptographic S-boxes are vectorial Boolean functions that must fulfill strict criteria to provide security for cryptographic algorithms. There are several existing methods for generating strong cryptographic S-boxes, including stochastic search algorithms. These search algorithms typically generate random candidate Boolean functions (or permutations) that are improved during the search by examining the search space in a specific way. Here, we introduce a new type of stochastic algorithm for generating cryptographic S-boxes. We do not generate and then improve the Boolean function; instead, we build the vector of values incrementally. New values are obtained by randomized search driven by restrictions on the differential spectrum of the generated S-box. In this article, we formulate two new algorithms based on this new approach and study the better one in greater detail. We prove the correctness of the proposed algorithm and evaluate its complexity. The final part contains an experimental evaluation of the method. We show that the algorithm generates S-boxes with better properties than a random search. We believe that our approach can be extended in the future by adopting more advanced stochastic search methods.

The topic of this contribution is the practical use of secret sharing schemes in securing private data. In the first part, we focus on the security model and the overview of the available solutions. In the second part, we describe our solution for storing sensitive data in commercial cloud storage systems, an application called Datachest. The application uploads the data in encrypted form. Cryptographic keys are divided into shares. Each cloud receives one share. This solution improves the security of users’ sensitive data in the cloud. In the final part, we explore the ramifications of secret sharing on the security and management of IoT devices, especially home appliances.

The Štolba cipher machine was the first Czechoslovak cipher machine used in the army after the mid-1930s, and later in Slovakia during WW2. It had a unique design based on pneumatic transmission and complex stepping rules. We present basic facts about the Štolba machine from documents found in Czech and Slovak archives. Although the machine description was incomplete (and in some cases not accurate), we have been able to reconstruct (a highly probable) encryption algorithm, and develop a method to reconstruct (message) key from a known PC pair. Part of the machine configuration, however, still remains unknown due to the large space of possible settings and the complexity of the algorithm.