Everyone is welcome to attend the PhD defence of Simona (live or online) that will take place in the Jacques Louis Lions 1 hall (building C of INRIA Paris).
Relevant to attendees online: For those not able to attend in person but still willing to follow the defence online, I will send a Zoom link along with the reminder for the defense.
Please contact Simona Etinsky directly for more information.
Title: Generalized Syndrome Decoding Problem and its Application to Post-Quantum Cryptography
Abstract: In this thesis, we focus on the syndrome decoding problem (SDP), its generalization, cryptanalysis, and its application to digital signature scheme designs. We introduce a new problem, which we refer to as the generalized syndrome decoding problem. In the cryptanalytic part of the thesis, we then focus on the classical and quantum cryptanalysis of the generalized syndrome decoding problem using the information set decoding framework. More precisely, we calculate the running time of three different (classical) information set decoding algorithms, which we refer to as Prange's, Stern's/Dumer's, and Wagner's algorithms. The three algorithms are adapted to solve specific versions of the generalized problem which are given over the Hamming weight, taken as a baseline, and the Lee weight, taken as an alternative to the most commonly used Hamming weight. We then compare the obtained running times with the running time of the hybrid classical-quantum algorithm, obtained by introducing the Grover search and the amplitude amplification in the appropriate step of Wagner's algorithm. In the protocol design part of the paper, we modify Stern's identification protocol, and the corresponding signature scheme, to the newly introduced generalized syndrome decoding problem. To keep the zero-knowledge property of the scheme, we eventually replace the syndrome decoding problem with the permuted kernel one (PKP), for which we show that the average-case SDP reduces to average-case PKP. We then suggest different methods for optimizing the efficiency of the scheme and then provide numerical results that compare the efficiency of the original construction and our newly introduced scheme. The outcome of this work is an analysis of the newly introduced variant of the syndrome decoding problem that estimates the asymptotic complexity of the problem, as well as the concrete security of the scheme based on this problem. The results indicate that the proper choice of a weight function introduces a harder version of the syndrome decoding problem and thus yields more efficient protocols based upon it.
Jury:
Frédéric Magniez, (Advisor)
André Chailloux (Co-Advisor)
Daniel Augot (Reviewer)
Elena Kirshanova (Reviewer)
Nicolas Sendrier (Examiner)
Nicolas Resch (Examiner)
Sophie Laplante (Examiner)
