“A better understanding of SDP and its generalization is thus relevant for developing more efficient cryptographic protocols secure against quantum attacks even if full-scale quantum devices are developed” Simona Etinski, former PhD student at IRIF.
Link to her PhD thesis: Generalized Syndrome Decoding Problem and its Application to Post-Quantum Cryptography

Hi, I am Simona, a freshly graduated PhD in theoretical computer science at Université Paris Cité. During my PhD studies, I was part of two research groups, the Algorithms and Complexity group of IRIF and the COSMIQ team of INRIA Paris. Before I started my PhD studies in Paris, I obtained my bachelor's and master's degree in electrical engineering with a major in signal processing at the University of Novi Sad. After obtaining my master's degree in 2017, I started my PhD studies in signal processing at the same university. Soon enough, I realized I would like to change the research topic, so I applied for the MathInParis scholarship. Obtaining the scholarship enabled me to start my PhD studies in theoretical computer science in 2019. Under the supervision of André Chailloux (INRIA Paris) and Frédéric Magniez (IRIF), I managed to bring my studies to a successful end in June this year.

That is a long story. To make it short, I will summarize it as follows. During high school, I attended seminars at Petnica Science Center - an educational center for high-school students where the students have a chance to do small research projects. There I got my first research-like experience and decided to become a researcher when I grow up. The choice of the topic came a bit later. Namely, after switching my interests from linguistics to electrical engineering, I finally decided to do a PhD in theoretical computer science, and, more precisely, post-quantum cryptography.

My thesis is about the syndrome decoding problem - a computational problem that is believed to be difficult to solve even for the best algorithms known but whose solutions are efficiently verifiable. This problem is taken as the basis of different cryptographic protocols where the solutions to the problem are used to either protect the data or identify a party. The protocols based on this problem are believed to be secure against attacks by current state-of-the-art computational devices, also known as classical devices, as well as against attacks of so-called quantum devices, which are believed to be even more computationally powerful if ever developed on the full scale. However, these protocols lack efficiency. The focus of my thesis is on the generalization of the syndrome decoding problem that potentially increases the difficulty of the problem and eventually leads to the design of more efficient protocols.

The syndrome decoding problem (SDP) is a computational problem derived from the syndrome decoding method, originally introduced in coding theory. The original method aims to recover the encoded message sent through a noisy channel, which we refer to as the decoding task. It is known as the most common decoding method and it is rather efficient for codes commonly in use. Nevertheless, this method can be rather inefficient for arbitrary codes. In this thesis, I was interested in the so-called linear codes, for which we can show that this problem is NP-complete. This suggests that the worst-case instances of SDP for linear codes are difficult for both classical and quantum devices and that these can be used as the basis of post-quantum protocols, i.e. protocols resistant to attacks by quantum devices. A better understanding of SDP and its generalization is thus relevant for developing more efficient cryptographic protocols secure against quantum attacks even if full-scale quantum devices are developed.

What we know about the syndrome decoding problem is that it is in the class NP, which strongly suggests that its hardest instances are difficult to solve by any computational device available now or developed in the close future. Nevertheless, how hard are arbitrary instances of the problem, relevant for cryptographic purposes, is less clear. We thus design algorithms that attack the problem and, for the chosen values of the parameters of the problem, we calculate the resources necessary for attacking the problem, which eventually gives us an estimate of the problem's complexity. The given approach is known as the cryptanalytic approach or cryptanalysis. Cryptanalysis of the problem thus represents the first step of the cryptographic analysis of the newly introduced problem. The cryptanalysis of original SDP is a rather active area of research which indicates that for both classical and quantum devices, solving this problem requires time exponential in the size of the problem's input. In simpler terms, this means that for the large enough instances of the problem and properly chosen parameters' values, we do not expect to design either a classical or quantum algorithm that is efficient enough to solve SDP in a reasonable amount of time. The original SDP is thus taken as a good candidate for the basis of the post-quantum cryptographic protocols. The generalization of the problem, introduced in this thesis, aims to increase the coefficient of the exponent of the running time, i.e. increase the complexity of the original problem. In my thesis, I focus on the cryptanalysis of the generalized version of the problem to obtain the estimate of the exponents of the running time. To do so, I adapt the classical algorithms for attacking the original version of the problem to the generalized setting and design quantum algorithms that do the same task. The design and analysis of these algorithms is an interesting task for me, whose outcome indicates a direction for the development of new post-quantum protocols based on the generalized SDP.

There are many possible cryptographic applications of the generalized syndrome decoding problem. In my thesis, I focused on the design of digital signature protocols, which are used for secure signing of digital documents. In my thesis, I showed that for the right choice of parameter values, the efficiency of Stern's signature scheme is improved by replacing the original syndrome decoding problem with its generalized version.

The goal of my current research is to port some of the tools used for solving the so-called lattice-based problems to the syndrome decoding setting. The lattice-based problems are believed to be post-quantum and, in general, yield rather efficient cryptographic protocols. Despite being similar to the syndrome decoding problem, the lattice-based problems are analyzed using different cryptanalytic tools. I believe that adapting the tools used for cryptanalysis of lattice-based problems to the syndrome decoding setting and vice versa would give us a better insight into both lattice-based problems and SDP and bring the two areas of research closer together. This would hopefully lead to improving the efficiency of the code-based protocols and a better understanding of why lattice-based protocols work so well in practice.