Page 58 - ISCI’2017

2 Asymmetric cryptosystems based on the algebraic block codes (theoretical and code

schemes)

Let us consider the schemes of asymmetric cryptographic transformation, the construction of which
is based on the use of the algebraic codes disguised as general position code (random code, full code)

[15-22]. Let us consider current state of the existing contradictions and prospects of their practical
usage including in the postquantum period.

McEliece cryptosystem. The first and the most studied asymmetric encryption scheme, based

on the use of algebraic block codes is proposed in 1978 the McEliece cryptosystem [15]. It has
undeniable advantages: a high-speed cryptographic transformation, as well as the ability to combine

error checking with protection against unauthorized familiarization [15-22]. In addition, similar
(crypto code) transformations remain steadfast, even in the case of using of quantum computing [28].

Open key in the McEliece scheme is a matrix

G = XGPD , (18)
X
where G is generating matrix of algebraic (n, k, d)-code over GF(q) (in original manuscript [15]
proposed to use considered above the binary Goppa code), X is non-degenerate (k × k)-matrix with

the elements from GF(q), P and D are permutation and diagonal (n × n)-matrices (matrix P is used

only for binary codes).
Matrices X, P and D are a secret key, which masks used algebraic block code under the random

code (general position code), i.e. the open key GX will represent to an attacker as a randomly formed
generating matrix of a linear code for which an algorithm of fast decoding is not known. On the

contrary, the authorized user who knows the secret key (matrices X, P and D), can remove the masking
effect of matrices and take advantage a fast algorithm for decoding of the algebraic code with a

generating matrix G.

The cryptogram is a vector of length n , which is calculated according to the rule

*
с = IG + e , (19)
X
X
where a vector
с = IG
X
X
is a code word of masked code, i.e. cx belongs to (n, k, d)-code with the generating matrix GX, I is k-
ary information vector over GF(q), vector e is a secret vector of an error weight

d
 −1 
w h (e ) ≤ t =   2   .

Vector e should be considered as a one-time session secret key, its weight determines the
*
complexity of decoding of the distorted code word (cryptogram) c x. An attacker would need to
58