بررسی کشف نوشته رمزی رمزنگاری مبتنی بر کد: از تئوری تا حملات فیزیکی Survey on cryptanalysis of code-based cryptography: From theoretical to physical attacks

I. INTRODUCTION The evolution of the Internet and its related security problems created a fertile ground for public-key cryptography (PKC). It is probably one of today’s most spread solution to secure communications. Three of the main technologies used for security purposes, namely TLS, PGP, and SSH, all contain elliptic-curve cryptography. A major advantage of PKC compared to secret-key cryptography (SKC) is that today’s requirements are all achievable by PKC, namely integrity, confidentiality, authentication, identification, and nonrepudiation. Current PKC bases its strength on mathematical problems from number theory, such as the integer factorization and discrete logarithm problems. In the past, these two problems were considered hard enough for a cryptographic purpose. Nowadays, the security of cryptosystems based on number theory is rather uncertain. This fact is mainly due to the discovery of polynomial time quantum algorithms for solving the aforementioned problems [1]. Even though a real quantum computer able to factor large numbers does not yet exist, the cryptographic community has already started to get ready for this event. One of the institutes that prepares and elaborates standards for security solutions is the National Institute of Standards and Technology (NIST). It launched a vast program on postquantum cryptography (PQC) standardization. The purpose of this process is to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. For that, they will organize an international conference.collocated with PQCrypto 2018. At this moment, the submission phase is finished and the list of candidates is public. Among the possible solutions, code-based cryptography has an important number of candidates. Roughly speaking, 3/8 proposals are code-based protocols. McEliece introduced in 1978 the first code-based cryptosystem [2]. The scheme is not based on number theory primitives but rather difficult problems coming from coding theory. Its security relies on two problems: the hardness of the Syndrome Decoding Problem [3], and the difficulty to distinguish between a binary Goppa code and a random linear code [4]. When compared to other PKC, McEliece’s scheme disposes of various advantages: the complexity of encryption and decryption algorithms are equivalent to those of symmetric schemes, i.e. are very efficient [5]. Also, the best attacks for solving the syndrome decoding problem are exponential in the code length, i.e. McEliece scheme presents a high potential [6]. Our contribution: In this article, we make a state-of-theart of code-based cryptography, essentially for encryption and signature schemes. We provide the main ideas for theoretical and physical cryptanalysis. Note that in the literature, other surveys exists, such as [7], [8] or the well-known book of Pellikaan at al. [9].