GPT cryptosystem

The GPT cryptosystem ( Gabidulina-Paramonova-Tretyakov ) is a public -key cryptosystem based on rank codes ^[1] , developed in 1991 by E. M. Gabidulin , A. V. Paramonov and O. V. Tretyakov ^[2] based on the cryptosystem McEliece .

This cryptosystem, unlike the McEliece cryptosystem, is more resistant to decoding attacks, and also has a smaller key size ^[3] , which is better suited for practical use.

Most versions of the system were hacked by R. Overbeck ^[4] .

Content

Description

Clear Text

As plain text, any $k$ ${\ displaystyle k}$ -vector $m=(m_{1},m_{2},...,m_{k})$ ${\ displaystyle m = (m_ {1}, m_ {2}, ..., m_ {k})}$ , $m_{s}\in \mathbb {F} _{q^{N}},s=1,2,...,k$ ${\ displaystyle m_ {s} \ in \ mathbb {F} _ {q ^ {N}}, s = 1,2, ..., k}$ .

Public Key

The public key is a size generating matrix $k\times (n+t_{1})$ ${\ displaystyle k \ times (n + t_ {1})}$ :

G_{pub}=S[X

{\ displaystyle G_ {pub} = S [X}

G_{k}]P

{\ displaystyle G_ {k}] P}

,

Where:

$G_{k}$ ${\ displaystyle G_ {k}}$ - generating matrix $(n,k,d)$ ${\ displaystyle (n, k, d)}$ code with maximum rank distance $d$ ${\ displaystyle d}$ for code length $n\leq N$ ${\ displaystyle n \ leq N}$ with number of characters $k$ ${\ displaystyle k}$ defined by a matrix of the following form:

G_{k}={\begin{bmatrix}g_{1}&g_{2}&\cdots &g_{n}\\g_{1}^{[1]}&g_{2}^{[1]}&\cdots &g_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\g_{1}^{[k-1]}&g_{2}^{[k-1]}&\cdots &g_{n}^{[k-1]}\end{bmatrix}}

{\ displaystyle G_ {k} = {\ begin {bmatrix} g_ {1} & g_ {2} & \ cdots & g_ {n} \\ g_ {1} ^ {[1]} & g_ {2} ^ {[1] } & \ cdots & g_ {n} ^ {[1]} \\\ vdots & \ vdots & \ ddots & \ vdots \\ g_ {1} ^ {[k-1]} & g_ {2} ^ {[k- 1]} & \ cdots & g_ {n} ^ {[k-1]} \ end {bmatrix}}}

Where

g_{1},g_{2},...,g_{n}

{\ displaystyle g_ {1}, g_ {2}, ..., g_ {n}}

- any set of elements of the extended field

\mathbb {F} _{q^{N}}

{\ displaystyle \ mathbb {F} _ {q ^ {N}}}

linearly independent over the field

\mathbb {F} _{q}

{\ displaystyle \ mathbb {F} _ {q}}

.

main matrix

G_{k}

{\ displaystyle G_ {k}}

used to correct errors. Errors of a rank no more

{\tfrac {n-k}{2}}

{\ displaystyle {\ tfrac {nk} {2}}}

can be fixed.

String scrambler $S$ ${\ displaystyle S}$ Is a non-degenerate square order matrix $k$ ${\ displaystyle k}$ over the field $\mathbb {F} _{q^{N}}$ ${\ displaystyle \ mathbb {F} _ {q ^ {N}}}$
$X$ ${\ displaystyle X}$ - size distortion matrix $(k\times {t_{1}})$ ${\ displaystyle (k \ times {t_ {1}})}$ over the field $\mathbb {F} _{q^{N}}$ ${\ displaystyle \ mathbb {F} _ {q ^ {N}}}$ with column rank $Rk_{col}(X$ ${\ displaystyle Rk_ {col} (X}$ | $\mathbb {F} _{q})=t_{1}$ ${\ displaystyle \ mathbb {F} _ {q}) = t_ {1}}$ and rank $Rk(X$ ${\ displaystyle Rk (X}$ | $\mathbb {F} _{q^{N}})=t_{X},$ ${\ displaystyle \ mathbb {F} _ {q ^ {N}}) = t_ {X},}$ $t_{X}\leq t_{1}$ ${\ displaystyle t_ {X} \ leq t_ {1}}$ .

Matrix

[X

{\ displaystyle [X}

G_{k}]

{\ displaystyle G_ {k}]}

has a column rank

Rk_{col}([X

{\ displaystyle Rk_ {col} ([X}

G_{k}]

{\ displaystyle G_ {k}]}

|

\mathbb {F} _{q})=n+t_{1}

{\ displaystyle \ mathbb {F} _ {q}) = n + t_ {1}}

.

Column scrambler $P$ ${\ displaystyle P}$ - square order matrix $(t_{1}+n)$ ${\ displaystyle (t_ {1} + n)}$ over the field $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ .
$t_{1}+n$ ${\ displaystyle t_ {1} + n}$ maybe more $N$ ${\ displaystyle N}$ but $n\leq N$ ${\ displaystyle n \ leq N}$ .

Private Key

The private key is a set $(S,G_{k},X,P)$ ${\ displaystyle (S, G_ {k}, X, P)}$ as well as an algorithm for fast decoding of MPP code, which uses a parity check matrix $H^{(n-k)\times n}$ ${\ displaystyle H ^ {(nk) \ times n}}$ such that $G_{k}H^{T}=0:$ ${\ displaystyle G_ {k} H ^ {T} = 0:}$

H={\begin{bmatrix}h_{1}&h_{2}&\cdots &h_{n}\\h_{1}^{[1]}&h_{2}^{[1]}&\cdots &h_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\h_{1}^{[d-2]}&h_{2}^{[d-2]}&\cdots &h_{n}^{[d-2]}\end{bmatrix}}

{\ displaystyle H = {\ begin {bmatrix} h_ {1} & h_ {2} & \ cdots & h_ {n} \\ h_ {1} ^ {[1]} & h_ {2} ^ {[1]} & \ cdots & h_ {n} ^ {[1]} \\\ vdots & \ vdots & \ ddots & \ vdots \\ h_ {1} ^ {[d-2]} & h_ {2} ^ {[d-2]} & \ cdots & h_ {n} ^ {[d-2]} \ end {bmatrix}}}

,

Where

h_{1},h_{2},...,h_{n}

{\ displaystyle h_ {1}, h_ {2}, ..., h_ {n}}

- elements of the extended field

\mathbb {F} _{q^{N}}

{\ displaystyle \ mathbb {F} _ {q ^ {N}}}

linearly independent over the main field

\mathbb {F} _{q}

{\ displaystyle \ mathbb {F} _ {q}}

Matrix

X

{\ displaystyle X}

It is not used to decrypt crypto text and can be deleted after calculating the private key.

Optimal code parameters

Code length $n\leq N$ ${\ displaystyle n \ leq N}$ ,
Dimension $k=n-d+1$ ${\ displaystyle k = n-d + 1}$ ,
Code Rank Distance $d=n-k+1$ ${\ displaystyle d = n-k + 1}$

Encryption

The corresponding plaintext cryptotext is calculated as follows:

c=mG_{pub}+e=mS[X

{\ displaystyle c = mG_ {pub} + e = mS [X}

G_{k}]P+e

{\ displaystyle G_ {k}] P + e}

,

Where $e$ ${\ displaystyle e}$ - artificial error vector of rank not higher $t_{2}$ ${\ displaystyle t_ {2}}$ , and $t_{1}+t_{2}\leq t=\lfloor {\tfrac {n-k}{2}}\rfloor$ {\ displaystyle t_ {1} + t_ {2} \ leq t = \ lfloor {\ tfrac {nk} {2}} \ rfloor} .

Decryption

Legal recipient receiving $c$ ${\ displaystyle c}$ , performs the following actions:

Calculates $c'=(c_{1}',c_{2}',...,c_{t_{1}+n}')=cP^{-1}=mS[X$ ${\ displaystyle c '= (c_ {1}', c_ {2} ', ..., c_ {t_ {1} + n}') = cP ^ {- 1} = mS [X}$ $G_{k}]+eP^{-1}$ ${\ displaystyle G_ {k}] + eP ^ {- 1}}$
Of $c^{'}$ ${\ displaystyle c '}$ selects a subvector $c''=(c_{t_{1}+1}',c_{t_{1}+2}',...,c_{t_{1}+n}')=mSG_{k}+e''$ ${\ displaystyle c '' = (c_ {t_ {1} +1} ', c_ {t_ {1} +2}', ..., c_ {t_ {1} + n} ') = mSG_ {k} + e ''}$ where $e^{″}$ ${\ displaystyle e ''}$ - subvector $eP^{-1}$ ${\ displaystyle eP ^ {- 1}}$
Applies fast decoding algorithm to correct error $e^{″}$ ${\ displaystyle e ''}$
Gets $m S$ ${\ displaystyle mS}$
Restores $m=(mS)S^{-1}$ ${\ displaystyle m = (mS) S ^ {- 1}}$

In this system, the size of the public key is $V=k(t_{1}+n)N$ ${\ displaystyle V = k (t_ {1} + n) N}$ bit, and information transfer rate $R={\tfrac {k}{t_{1}+n}}$ ${\ displaystyle R = {\ tfrac {k} {t_ {1} + n}}}$ .

Hacking

Frobenius automorphism

We introduce the Frobenius automorphism : $\sigma (x)=x^{q},$ ${\ displaystyle \ sigma (x) = x ^ {q},}$ $x\in \mathbb {F} _{q^{N}}$ ${\ displaystyle x \ in \ mathbb {F} _ {q ^ {N}}}$ . It has the following properties:

For matrix $L=(l_{ij})$ ${\ displaystyle L = (l_ {ij})}$ over the same field $\sigma (L)=(\sigma (l_{ij}))=(l_{ij}^{q})$ ${\ displaystyle \ sigma (L) = (\ sigma (l_ {ij})) = (l_ {ij} ^ {q})}$
For any integer s : $\sigma ^{s}(L)=\sigma (\sigma ^{s-1}(L))$ ${\ displaystyle \ sigma ^ {s} (L) = \ sigma (\ sigma ^ {s-1} (L))}$
$\sigma ^{N}=\sigma$ ${\ displaystyle \ sigma ^ {N} = \ sigma}$
$\sigma ^{-1}=\sigma ^{N-1}$ ${\ displaystyle \ sigma ^ {- 1} = \ sigma ^ {N-1}}$
$\sigma (a+b)=\sigma (a)+\sigma (b)$ ${\ displaystyle \ sigma (a + b) = \ sigma (a) + \ sigma (b)}$
$\sigma (ab)=\sigma (a)\sigma (b)$ ${\ displaystyle \ sigma (ab) = \ sigma (a) \ sigma (b)}$
In general $\sigma (L)\neq L$ ${\ displaystyle \ sigma (L) \ neq L}$ . Equality is achieved if $L$ ${\ displaystyle L}$ - matrix above the main field $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Overback attack description ^[4]

The cryptanalyst calculates the extended public key from the public key:

G_{ext,pub}={\begin{Vmatrix}G_{pub}\\\sigma (G_{pub})\\\cdots \\\sigma ^{u}(G_{pub})\end{Vmatrix}}={\begin{Vmatrix}S&[X&G_{k}]&P\\\sigma (S)&[\sigma (X)&\sigma (G_{k})]&P\\\cdots &\cdots &\cdots &\cdots \\\sigma ^{u}(S)&[\sigma ^{u}(X)&\sigma ^{u}(G_{k}]&P\end{Vmatrix}}

{\ displaystyle G_ {ext, pub} = {\ begin {Vmatrix} G_ {pub} \\\ sigma (G_ {pub}) \\\ cdots \\\ sigma ^ {u} (G_ {pub}) \ end {Vmatrix}} = {\ begin {Vmatrix} S & [X & G_ {k}] & P \\\ sigma (S) & [\ sigma (X) & \ sigma (G_ {k})] & P \\\ cdots & \ cdots & \ cdots & \ cdots \\\ sigma ^ {u} (S) & [\ sigma ^ {u} (X) & \ sigma ^ {u} (G_ {k}] & P \ end {Vmatrix}}}

Here property 7 of the Frobenius automorphism is used:

\sigma (P)=P

{\ displaystyle \ sigma (P) = P}

, because

P

{\ displaystyle P}

- matrix above the main field

\mathbb {F} _{q}

{\ displaystyle \ mathbb {F} _ {q}}

.

Rewrites this matrix as $G_{ext,pub}=S_{ext}[X_{ext}$ ${\ displaystyle G_ {ext, pub} = S_ {ext} [X_ {ext}}$ $G_{ext}]$ ${\ displaystyle G_ {ext}]}$ ,

Where

S_{ext}=diag{\begin{bmatrix}S&\sigma (S)&\cdots &\sigma ^{u}(S)\end{bmatrix}}

{\ displaystyle S_ {ext} = diag {\ begin {bmatrix} S & \ sigma (S) & \ cdots & \ sigma ^ {u} (S) \ end {bmatrix}}}

,

X_{ext}={\begin{bmatrix}X\\\sigma (X)\\\vdots \\\sigma ^{u}(X)\end{bmatrix}}

{\ displaystyle X_ {ext} = {\ begin {bmatrix} X \\\ sigma (X) \\\ vdots \\\ sigma ^ {u} (X) \ end {bmatrix}}}

,

G_{ext}={\begin{bmatrix}G_{k}\\\sigma (G_{k})\\\vdots \\\sigma ^{u}(G_{k})\end{bmatrix}}

{\ displaystyle G_ {ext} = {\ begin {bmatrix} G_ {k} \\\ sigma (G_ {k}) \\\ vdots \\\ sigma ^ {u} (G_ {k}) \ end {bmatrix }}}

.

Selects $u=n-k-1$ ${\ displaystyle u = nk-1}$ .
Defines matrices:

X_{1}^{(k-1\times t_{1})}

{\ displaystyle X_ {1} ^ {(k-1 \ times t_ {1})}}

derived from

X^{(k\times t_{1})}

{\ displaystyle X ^ {(k \ times t_ {1})}}

deleting the last line,

X_{2}^{(k-1\times t_{1})}

{\ displaystyle X_ {2} ^ {(k-1 \ times t_ {1})}}

derived from

X^{(k\times t_{1})}

{\ displaystyle X ^ {(k \ times t_ {1})}}

deleting the first line.

Defines a linear display. $T$ ${\ displaystyle T}$ : $\mathbb {F} _{q^{N}}^{k\times t_{1}}\rightarrow \mathbb {F} _{q^{N}}^{(k-1)\times t_{1}}$ ${\ displaystyle \ mathbb {F} _ {q ^ {N}} ^ {k \ times t_ {1}} \ rightarrow \ mathbb {F} _ {q ^ {N}} ^ {(k-1) \ times t_ {1}}}$ according to the following rule:

if a

X\in \mathbb {F} _{q^{N}}^{k\times t_{1}}

{\ displaystyle X \ in \ mathbb {F} _ {q ^ {N}} ^ {k \ times t_ {1}}}

then

T(X)=Y=\sigma (X_{1})-X_{2}

{\ displaystyle T (X) = Y = \ sigma (X_ {1}) - X_ {2}}

Writes down $Y_{ext}={\begin{bmatrix}Y&\sigma (Y)&\sigma ^{2}(Y)&\cdots &\sigma ^{u-1}(Y)\end{bmatrix}}^{\top }$ ${\ displaystyle Y_ {ext} = {\ begin {bmatrix} Y & \ sigma (Y) & \ sigma ^ {2} (Y) & \ cdots & \ sigma ^ {u-1} (Y) \ end {bmatrix} } ^ {\ top}}$

Using matrix transformations, the extended public key is brought to the form:

{\widetilde {G}}_{pub,ext}={\widetilde {S}}_{ext}{\begin{bmatrix}Z&|&G_{n-1}\\Y_{ext}&|&0\end{bmatrix}}P

{\ displaystyle {\ widetilde {G}} _ {pub, ext} = {\ widetilde {S}} _ {ext} {\ begin {bmatrix} Z & | & G_ {n-1} \\ Y_ {ext} & | & 0 \ end {bmatrix}} P}

Where

G_{n-1}

{\ displaystyle G_ {n-1}}

- generating matrix

(n,n-1,2)

{\ displaystyle (n, n-1,2)}

MPP code.

Trying to find a solution to the system.

{\widetilde {S}}_{ext}={\begin{bmatrix}Z&|&G_{n-1}\\Y_{ext}&|&0\end{bmatrix}}Pu^{T}=0

{\ displaystyle {\ widetilde {S}} _ {ext} = {\ begin {bmatrix} Z & | & G_ {n-1} \\ Y_ {ext} & | & 0 \ end {bmatrix}} Pu ^ {T} = 0}

,

Where

u

{\ displaystyle u}

- row vector above the extended field

\mathbb {F} _{q^{N}}

{\ displaystyle \ mathbb {F} _ {q ^ {N}}}

lengths

t_{1}+n

{\ displaystyle t_ {1} + n}

Represents Vector $Pu^{T}$ ${\ displaystyle Pu ^ {T}}$ as:

Pu^{T}={\begin{bmatrix}y&h\end{bmatrix}}^{\top }

{\ displaystyle Pu ^ {T} = {\ begin {bmatrix} y & h \ end {bmatrix}} ^ {\ top}}

Where

y

{\ displaystyle y}

- length sub-vector

t_{1}

{\ displaystyle t_ {1}}

, but

h

{\ displaystyle h}

- lengths

n

{\ displaystyle n}

Now the system of equations is equivalent to the following:

{\begin{cases}Zy^{T}+G_{n-1}h^{T}=0,\\Y_{ext}y^{T}=0\end{cases}}

{\ displaystyle {\ begin {cases} Zy ^ {T} + G_ {n-1} h ^ {T} = 0, \\ Y_ {ext} y ^ {T} = 0 \ end {cases}}}

Assuming the condition is true $Rk(Y_{ext}|\mathbb {F} _{q^{N}})=t_{1}$ ${\ displaystyle Rk (Y_ {ext} | \ mathbb {F} _ {q ^ {N}}) = t_ {1}}$ , we see that the above system has only a trivial solution $y^{T}=0$ ${\ displaystyle y ^ {T} = 0}$ . Therefore, the first equation from the system is converted to the form:

G_{n-1}h^{T}=0

{\ displaystyle G_ {n-1} h ^ {T} = 0}

.

This will allow you to find the first row of the parity check matrix for the code with this generating matrix ${\widetilde {G}}_{pub,ext}$ ${\ displaystyle {\ widetilde {G}} _ {pub, ext}}$ . Therefore, this solution breaks the described cryptosystem in polynomial time. Overbeck attack requires $O((n+t_{1})^{3})$ ${\ displaystyle O ((n + t_ {1}) ^ {3})}$ field operations $\mathbb {F} _{q^{N}}$ ${\ displaystyle \ mathbb {F} _ {q ^ {N}}}$ , since each attack step has a complexity not higher than cubic on $n+t_{1}$ ${\ displaystyle n + t_ {1}}$ .

Notes

↑ Gabidulin E. M. Theory of Codes with Maximum Rank Distance (Unavailable Link) // Probl. transmission inform. - 1985. - T. 21, no. 1 .-- S. 3-16.
↑ Gabidulin EM, Paramonov AV, Tretjakov OV Ideals over a Non-commutative Ring and Their Application in Cryptology // Advances in Cryptology - Eurocrypt '91, LNCS 547, 1991, pp. 482-489.
↑ Khan E., Gabidulin EM, Honary B., Ahmed H. Modified Niederreiter type of GPT Cryptosystem based on Reducible Rank Codes // et al. Des. Codes Cryptogr. (2014) 70: 231. - ISSN 0925-1022
↑ ¹ ² Overbeck R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes // Journal of Cryptology : volume 21, number 2, april 2008 - ISSN 0933-2790

Literature

Gabidulin, E. M., Pilipchuk, N.I., Honari B., and Rashvan H. Information Security in a Network with Random Network Encoding // Probl. transmission inform. , 2013, Volume 49, Issue 2, 92-106
Gadouleau M., Yan Zh. Security of GPT-type cryptosystems // Proc. 2006 IEEE Int. Sympos. on Information Theory (ISIT'2006) . - ISIT.2006.261627
Rashwan H., Gabidulin EM, Honary B. A smart approach for GPT Cryptosystem Based on Rank Codes // Proc. 2010 IEEE Int. Sympos. on Information Theory (ISIT'2010). Austin, Texas, USA. June 13-18, 2010. P. 2463-2467.
Kshevetskiy AS Security of GPT-like cryptosystems based on linear rank codes // Signal Design and Its Applications in Communications, 2007. IWSDA 2007 . On page (s): 143-147.
Ourivski AV, Gabidulin EM Column Scrambler for the GPT Cryptosystem // Discrete Applied Mathematics. 128 (1): 207-221 (2003).
Overbeck R. Extending Gibson's attacks on the GPT cryptosystem // In Proc. of WCC 2005, volume 3969 of LNCS, pp. 178-188, Springer Verlag, 2006.

[1] Gabidulin E. M. Theory of Codes with Maximum Rank Distance (Unavailable Link) // Probl. transmission inform. - 1985. - T. 21, no. 1 .-- S. 3-16.

[2] Gabidulin EM, Paramonov AV, Tretjakov OV Ideals over a Non-commutative Ring and Their Application in Cryptology // Advances in Cryptology - Eurocrypt '91, LNCS 547, 1991, pp. 482-489.

[3] Khan E., Gabidulin EM, Honary B., Ahmed H. Modified Niederreiter type of GPT Cryptosystem based on Reducible Rank Codes // et al. Des. Codes Cryptogr. (2014) 70: 231. - ISSN 0925-1022

[Overbeck-4] ¹ ² Overbeck R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes // Journal of Cryptology : volume 21, number 2, april 2008 - ISSN 0933-2790

GPT cryptosystem

Content

Description

Clear Text

Public Key

Private Key

Optimal code parameters

Encryption

Decryption

Hacking

Frobenius automorphism

Overback attack description [4]

Notes

Literature

More articles:

Overback attack description ^[4]