Cryptanalysis of McEliece Cryptosystem Sample Clauses

Cryptanalysis of McEliece Cryptosystem. ‌ As a last motivation, there has been some recent use of code squares in the cryptanalysis of variants of the McEliece cryptosystem. McEliece cryptosys- tem [52] is a code-based public-key cryptosystem which relies on the hardness of the general decoding problem [8]. Let C be a code, with encoding and decoding algorithm Enc and Dec, and assume that Dec can correct efficiently t errors. For instance, one may think that C admits a t-error correcting pair. Then a secret message m can be 11Under the additional assumption that the field extension is separable. encrypted as c := Enc(m) + e, where e is a random vector of weight t. Due to the error correcting property of the algorithm, it is possible to recover the original message as m = Dec(c) = Dec(Enc(m) + e). An external adversary (who does not know Dec, or in our example a t-error correcting pair for C), in order to recover m, is required to solve the general decoding problem, which is known to be hard. Concretely, the private key consists of C and Dec, while the public key is a generator matrix G of C together with the decoding capability t of Dec. The matrix G is “scrambled” in a way so that the original structure of the code is hidden12, and consequently the efficient decoding algorithm as well,. To build this cryptosystem, Goppa codes [48, Chapter 12] are standardly used. One immediately notices that the public key, being a matrix, is huge: this is the main disadvantage of this cryptosystem. The main advantage is the reliance on the general decoding problem, which makes this cryptosystem resistant even in a post-quantum scenario. On the other hand, recent attacks aim to recover the “hidden” structure of the code from the “scrambled” matrix, hence the efficient decoding algorithm, rather than the original message directly via general decoding algorithms. The idea exploited in [34, 23, 25, 26] is that Goppa codes have a square that has a substantially smaller dimension than typical random linear codes: this allows to build a distinguisher which can be used to attack the cryptosystem. As an example, we quickly sketch how code squares were used in [24] to attack Xxxxxxxxxxxx’s encryption scheme [73]. To give a bit of context, we recall that McEliece cryptosystem based on Xxxx-Xxxxxxx codes, as proposed in [55], was proved to be insecure in [68]: here it was shown that, in the case of a Xxxx-Xxxxxxx code, a generator matrix in standard form can be recovered efficiently from any scrambled one. To fix this, Xx...