Code-based Cryptography: Attacking and Constructing Cryptographic Systems

This thesis discusses novel results in the area of code-based cryptography, ranging from cryptanalyses on several code-based cryptographic constructions to proposing a code-based authentication scheme based on a novel Syndrome Decoding variant.

To address the looming threat of large-scale quantum computers that would
break many widely-used public-key cryptosystems, the National Institute of Stan-
dards and Technology (NIST), in 2016, promptly called for new quantum-resistant
cryptographic standards. After several comprehensive evaluation stages, several algorithms were chosen as the way forward. Recently, in 2022, “NIST expressed
particular interest in additional general-purpose signature schemes based on a security assumption that did not use structured lattices as well as signature schemes with short signatures and fast verification...” [NIS22]. This process reignited the competition, introducing many interesting and novel proposals.

Code-based cryptography has been pivotal in both processes, being the secu-
rity keystone for many proposals, particularly in the selected HQC algorithm. Its strong track record of research offers strong confidence in code-based cryptosys-
tems. From a complexity theory point of view, code-based assumptions are often
N P-hard computational problems, which have been the staples for provably-secured systems. On the other hand, cryptanalysis algorithms have witnessed
significant advancements, employing increasingly more sophisticated techniques. Yet, the fundamental Syndrome Decoding Problem remains resistant, suggesting that code-based cryptography is an exceptionally well-founded and dependable tool.
Many variants/alternatives of the Syndrome Decoding Problem have been
put forward to offer better performance without compromising security. Specifi-
cally, in this thesis, one encounters the Learning Parity with Noise (LPN) and Re-
stricted Syndrome Decoding Problem (RSDP). LPN has been a notable candidate in lightweight cryptography, and RSDP has gained traction due to its appearance in CROSS- a remaining candidate in the Round-2 of NIST Additional Digital Signa-
ture Schemes. Code-based cryptography, as a research field, shows immense versatility and richness far beyond its origin as a PKE proposed by McEliece [McE78].
We analyze several lightweight code-based cryptosystems in the first three
works, ranging from stream ciphers to wPRFs and authentication protocols. We
investigate the design weaknesses that allow us to launch attacks using various techniques. In particular, we analyze a novel LPN-based stream cipher called Firekite, a wPRFs construction, and an HB-like authentication protocol named LCMQ. Using diverse techniques in conjunction with information-set decoding algorithms (ISD), our studies improve previous results (if any) and impose stronger security parameters for said constructions.
Then, we draw connections between lattice-solving algorithms and traditional
syndrome decoding algorithms with our new proposal: a sieving-style ISD algorithm. Our algorithm offers a novel time-memory trade-off in solving relevant code-based parameters. In the low error-weight regime, the sieving-style ISD can use memory more efficiently without losing its competitiveness in computational performance. Thus, we introduce a valuable and practical alternative to cryptanalysis.
The last two papers look at the novel RSDP problem from a new perspective
- the Oracle model, analogous to the LWE or LPN problems. We construct an
HB-like authentication protocol, replacing the LPN problem with the (Oracle)
RSDP problem, showing its remarkable adaptiveness to the most secure designs.
In practice, RSDP structures allow incredibly efficient operations, rivaling those
of LPN. Moreover, RSDP also achieves high-security guarantees with modest pa-
rameters, yielding significant superiority regarding communication cost. Finally,
we expand the cryptanalysis of the RSDP problem, especially when many RSDP
samples are allowed with a BKW-style solver. We analyze the concrete complexity of RSDP in new regimes outside of CROSS parameters. Hence, our work is a useful calibrating tool for similar RSDP-based cryptosystems in the future.