Linear code based cryptosystem on new metric

Private key

is a set of matrices:

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

Public key

is the matrix:

H_pub = P(F + U G_k)S

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

Plaintext

All plaintexts are chosen as N₁-dimensional vectors:

m=(m₁ m₂ ... m_N₁)

such that rank(m)= min(t_k , t_p), where t_k is the error capacity in RC-metric of a code with the generator matrix G_k, t_p is the error capacity in rank metric of a code with the parity check matrix F^T.

Encryption

A ciphertext is calculated as a syndrome:

c = mH_pub = m(PF + UG_k)S =m_j (F + UG_k)S,

c =  m₁(F₁ + G_k1) + m₂(F₂ + G_k2) + ... + m_N₁(F_N₁ + G_{k_N₁})S = (g + e)S

where m_j= mP, F_i and G_i 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 m_j. Finally, m_jP^(-1) gives the required initial plaintext m.