Topics in Code-based Cryptography

Abstract

Given the rapid advancements in the field of quantum computing, the need for a robust post-quantum cryptosystem has become increasingly urgent. The McEliece cryptosystem, or equivalently the Niederreiter cryptosystem, is a promising quantum-resistant alternative that facilitates faster encryption and decryption processes. Both of these cryptosystems rely on a type of code called the Goppa code. However, a significant challenge with these cryptosystems is the large size of the keys - both private and public. These keys are typically represented using large matrices, which complicates the implementation and deployment of these cryptosystems. To address this issue, numerous efforts have been made to replace Goppa codes with codes that reduce the key size while maintaining security. One such modification involves substituting the Goppa codes in the McEliece and Niederreiter cryptosystems with quasi-cyclic codes. This adaptation results in a variant of the cryptosystem that is not only quantum secure but also offers enhanced performance in terms of transmission and encryption rates, along with significantly smaller key sizes. In this work, we develop one such cryptosystem based on quasi-twisted codes. To successfully develop a secure and efficient code-based cryptosystem, it is essential to have an effective decoding algorithm for the underlying code. In the context of quasi-twisted (QT) codes, one of the primary challenges is ensuring the existence of such a decoding algorithm. To achieve this, we propose a syndrome-based decoding approach, which efficiently corrects errors up to the Hartmann-Tzeng (HT)-like bound, which defines the maximum number of errors that can be reliably corrected without compromising the structure of the code. Quantum Fourier Sampling (QFS) plays a central role in many quantum algorithms, including Shor's algorithm, and proving that a cryptosystem can withstand QFS is considered a critical measure of its quantum security. Therefore, a cryptosystem that resists QFS is considered to be secure against quantum attacks. The quasi-cyclic code-based cryptosystem has been demonstrated to be resistant to QFS-based attacks. Furthermore, there are no known attacks on the cryptosystem. The security of a code-based cryptosystem is fundamentally tied to the indistinguishability of the underlying code from a random linear code. We explore the development of a Niederreiter-like cryptosystem based on quasi-twisted codes and thoroughly analyze its security. Quasi-twisted codes are a generalization of cyclic codes, constacyclic codes, and quasi-cyclic codes. By utilizing the general structure of quasi-twisted codes, as opposed to quasi-cyclic codes, we present a broader alternative to cryptosystems based on quasi-cyclic codes. We show that our cryptosystem can withstand QFS.