Linear code based cryptosystem on new metric

 

Private key

is a set of matrices:

(F Gk S P), where F and Gk concatenation of Frobenius-like matrices with linearly independent rows.

Public key

is the matrix:

Hpub = P(F + U Gk)S 

where U is some nonsingular matrix. Code vectors are rows of the matrix UGk . Matrix U is not needed for decryption but it has to be inaccessible for cryptanalyst.

Plaintext

All plaintexts are chosen as N1-dimensional vectors:

m=(m1 m2 ... mN1)

such that rank(m)= min(tk , tp), where tk is the error capacity in RC-metric of a code with the generator matrix Gk, tp is the error capacity in rank metric of a code with the parity check matrix FT.

Encryption

A ciphertext is calculated as a syndrome:

c = mHpub = m(PF + UGk)S =mj (F + UGk)S,

 

c =  m1(F1 + Gk1) + m2(F2 + Gk2) + ... + mN1(FN1 + GkN1)S = (g + e)S

 

where mj= mP, Fi and Gi are rows of matrices F and UG correspondingly.

Decryption

An authorized user multiplies obtained ciphertext (g + e)S by S(-1). Then user has to use the fast decoding algorithm in RC-metric. As a result, the user will obtain vectors g and e. During the next step legitimate user applies the fast decoding algorithm for the parent rank code and obtains a vector mj. Finally, mjP(-1) gives the required initial plaintext m.