Page 59 - ISCI’2017

*
encode a codogramm c x using the known generating matrix GX. However, random code decoding
(with appropriate parameters n, k, q and wh(e)) is computationally unattainable. Without the matrices
X, P and D an attacker cannot restore a matrix G and will use a decoding algorithm of polynomial

complexity. Based on this, volume wh(e) should maximize, for example, at wh(e) = t decoding
complexity will be maximal, this ensures the highest level of resistance for code cryptosystem at the

specified parameters n, k, q.
For an authorized user (who knows a secret key) decoding is polynomial solvable problem.

*
1
*
1
*
−
−
Really, an authorized user, when he/she obtains a vector c x, will build a vector с = с ⋅ D ⋅ P .
X
Matrix Λ = PD saves a weight and the Hamming distance, i.e. for any code words c and c' the
following equalities are performed:
w h (c ) = w h ( Λc ), w h (c ) ' ,c = w h ( Λ cc ' , Λ ).
*
This means that the vector с is distorted in no more than in t-ary by the code word of the
algebraic code with the generating matrix G and it can be decoded by the fast algorithm of polynomial

complexity [19].
An authorized, using the algorithm of polynomial complexity, is decoded the vector

*
−
1
с = I ⋅ ' G + ' e , i.e. will find 'I . After this, this user calculate k-ary information vector = II ' X .
Thus, the primary means of masking for the linear block (n, k, d)-code over linear random code
(general position code) in the McEliece cryptosystem are the matrices X, P and D. Additional secret

parameter, which can be used in a case of the Goppa codes, is the Goppa polynomial G(x), or, more
broadly, the vector Y = (Y0, Y1, …, Yn-1) in a case of alternantive codes (see the expressions (15)-(17)).

Template change is not decrease structural code characteristics, i.e. from a point of view of
cryptographic transformations, not lead to a reduction in security. However, knowledge about vector-

template Y = (Y0, Y1, …, Yn-1) (or the polynomial G(x)) is a necessary for the correct decoding of

information message, i.e. for correct decryption at the receiving side.
A large number of different attacks on crypto code of the information protection scheme [19,

33 - 36] has been published in nowadays, some of which were quite effective about individual variants
of code cryptosystems. However, the basic scheme [15], which has been proposed about 40 years

ago, remains resistant to all known cryptanalysis methods, including in case of using quantum-
computing systems.

The most natural way in a development of cryptanalysis methods for the McEliece code scheme

is using non-algebraic decoding methods. Really, if there exists computationally efficient method for
decoding the code word (19) only by known generating matrix (18), then the information message I

can be effectively restored and without the knowledge of the secret key (matrices X, P and D).

59