CHAPTER 3 Families of Post-quantum Schemes 27 However, decoding arbitrary (random) codes is computationally hard and can be infeasible depending on the code parameters. Nevertheless, there are specific codes for which efficient decoding algorithms are known. Therefore, in practice only such codes are used that have efficient decoding algorithms. The main security assumption of code-based cryptography is the hardness of decoding a random linear code 49. Even when taking quantum computers into account, only exponential-time algorithms are known. The first code-based public-key cryptosystem was proposed by McEliece in 1978 43. This scheme has not been fundamentally broken since, although the original parameters from 1978 are not considered secure anymore. Instead of correcting errors of an unreliable channel, for the McEliece scheme we now assume to have a reliable channel and we deliberately add an error in order to protect the contents of a message against an eavesdropper. The public key of the receiver is a generator matrix pub �� of his code. The sender encrypts the message ⃗ �� by converting it into a code word and by adding a secret error vector ⃗�� weight t: ⃗�� = ⃗ ���� pub ⊕ ⃗�� The receiver decodes the »corrupted« code word ⃗�� and obtains ⃗ ��. Now, to make this cryptosystem secure, the attacker must not be able to distinguish the code from a random code. The public generator matrix pub must be »scrambled« in order to hide the secret structure of the �� code such that it does not give the attacker any information that allows him to use an efficient decoding algorithm in order to decode . The ��⃗McEliece public-key cryptosystem describes how to compute pub in �� such a way while still allowing the owner of the private key to decode messages efficiently 43. The main problem of the McEliece cryptosystem is the size of the keys. McEliece is using binary Goppa codes and requires key sizes of about 4MB in order to achieve post-quantum security. An alternative to McEliece is a variant due to Niederreiter 47. Niederreiter gives some improvements to encryption and decryption cost and requires smaller public-key sizes. Furthermore, Niederreiter introduced a trick that can be used to further reduce the size of public keys in code-based schemes, e.g., to about 1MB for both McEliece and Niederreiter cryptosystems using Goppa codes 10. Niederreiter uses a slightly different approach than McEliece in order to construct a public-key system. The basic idea is not to add a random error to the codeword before transmission but to encode the plain
PQC_for_Dummies
To see the actual publication please follow the link above