Page 65 - ISCI’2017

cryptosystem persistence that was built on the algebraic codes, will determine by the value ρ ∙ t, and

provides noise immunity of transmitted cryptograms will determine the value (1 - ρ) ∙ t.
The third, obviously, one from the most important positive property of the McEliece

cryptosystem is high resistance to the quantum cryptanalysis. The complexity of the quantum

cryptanalysis for the code cryptosystem with the increase its parameters increases very fast in
comparison to other asymmetric cryptosystems, such as RSA. Actually, the complexity of the

cryptanalysis by the quantum algorithms is comparable with the decision of the brute force tasks of
an equivalent keys searching of the symmetric ciphers. Data in Table 1 clearly confirms this tendency.

The main disadvantages of the considered code cryptosystems are huge amounts of key data
(tens of megabits), reduction in the relative data transmission rate (the highest resistance of

cryptosystem is achieved at a relative speed coding R = k / n ≈ 2/3). Will be shown below, that the

relative data transmission rate can be substantially increased. Code cryptosystem proposed in this
paper is removed this design disadvantage of the McEliece scheme.

Niederreiter cryptosystem. An alternative cryptosystem example on the codes is the

Niederreiter scheme, which was proposed firstly in the work [16]. Open key in this cryptosystem is a
matrix

H = XHPD, (22)
X
where H is validation matrix of the algebraic (n, k, d)-code over GF(q) (in the original manuscript
[16] was been proposed to use the generalized Reed-Solomon codes), X is non-degenerate (n – k) ×

(n – k)-matrix with the elements from GF(q), P and D are permutation and a diagonal (n × n)-matrices

(matrix P is only using to binary codes).
Matrices X, P and D (as and for the McEliece cryptosystem) are a secret key, which masks used

algebraic block code under the random code (general position code), i.e. public key (22) represents

to an attacker as a randomly formed parity- validation matrix of a linear code, for which the fast
decoding algorithm is unknown. Conversely, authorized user, who knows the secret key (matrices X,

P and D), can remove the masking effect of the matrices and take advantage a fast algorithm for
decoding of the algebraic code with a validation matrix H.

Cryptogram Sx is a vector of (n – k)-length and it calculates by the rule

T
S = e⋅ H , (23)
X
X
where a vector e is a vector of n-length and the (wh(e) ≤ t)-weight, which carries the confidential
information (information message to be encrypted).

k
Authorized user (who has the secret key) will find one from q solutions of the expression
S = с ⋅ H . The obtained solution is a code word with errors с = I ⋅ G + e . Further, as and fir the
*
T
*
X
X
X
X
X
1 −
McEliece scheme, authorized user builds a vector с * = с * X ⋅ D 1 − ⋅ P and decodes the obtained word.
65