Sidelnikov cryptosystem

Sidelnikov's cryptosystem ( Mac-Alice-Sidelnikov ) is a public-key cryptographic system based on the McEliece cryptosystem . It was proposed by the mathematician, academician of the Academy of Cryptography of the Russian Federation Vladimir Mikhailovich Sidelnikov in 1994 ^[1] . Sidelnikov proposed this cryptosystem, since by that time algorithms had already been found for the McEliece system that cracked it in polynomial or sub-exponential time ^[2] .

The algorithm used in the Sidelnikov cryptosystem is based on the complexity of decoding the Reed-Muller code ^[1] . The generating matrix of such a code has dimensions $k\times n,$ ${\ displaystyle k \ times n,}$ $k \ times n,$ Where

k=\sum _{k=0}^{r}C_{m}^{k},n=2^{m}

{\ displaystyle k = \ sum _ {k = 0} ^ {r} C_ {m} ^ {k}, n = 2 ^ {m}}

k = \ sum_ {k = 0} ^ r C_m ^ k, n = 2 ^ m

When using the Reed-Muller code, you can select keys of a smaller size than in the McEliece cryptosystem; and also to achieve high decryption speed, since for this code there are fast decoding algorithms ^[2] . Moreover, the Sidelnikov cryptosystem, like any system based on linear codes , is not vulnerable to attacks that will become possible with the advent of a quantum computer .

This cryptosystem did not find real application, since, despite some improvements compared to the McEliece system, it was hacked in 2007.

Some sources refer to the Mac Alice-Sidelnikov cryptosystem.

Content

1 Key Generation
2 Encryption
3 Decryption
4 Attack on the cryptosystem
- 4.1 Essence of attack
- 4.2 Temporary estimates of the hacking algorithm
  - 4.2.1 Experimental runtime
5 Generalized Sidelnikov system
6 See also
7 notes
8 Literature

Key Generation

Sidelnikov's system, like all asymmetric cryptosystems , uses public and private keys. The public key is used to encrypt messages and is not secret. The private key is used for decryption and should be known only to the party to whom the encrypted messages are intended. The task of the owner of the private key is to mask the generating matrix $G$ ${\ displaystyle G}$ Knowing which, the cryptanalyst will be able to restore the original message. Matrices are used for these purposes. $P$ ${\ displaystyle P}$ and $A$ ${\ displaystyle A}$ described further in the algorithm. Computations everywhere occur in $k$ ${\ displaystyle k}$ -dimensional subspace of space $\mathbb {F} _{2}^{n}$ ${\ displaystyle \ mathbb {F} _ {2} ^ {n}}$ .

The key generation process is as follows ^[1] :

Reed-Muller code is selected with certain parameters $r$ ${\ displaystyle r}$ and $m$ ${\ displaystyle m}$ (Where $r$ ${\ displaystyle r}$ is the code order, and $2^{m}$ ${\ displaystyle 2 ^ {m}}$ - codeword length).
Random generated $n\times n$ ${\ displaystyle n \ times n}$ permutation matrix $P$ ${\ displaystyle P}$ .
Random non-degenerate generated $k\times k$ ${\ displaystyle k \ times k}$ matrix $A$ ${\ displaystyle A}$ .
The matrix is calculated $E=AGP$ ${\ displaystyle E = AGP}$ .
Matrix $E$ ${\ displaystyle E}$ and the number of errors corrected by the code $t$ ${\ displaystyle t}$ form a public key , and matrices $(A,G,P)$ ${\ displaystyle (A, G, P)}$ - private key of the cryptosystem.

Encryption

For coding using linear codes (in particular, using the Reed-Muller code), an informational message must be provided $m$ ${\ displaystyle m}$ as a sequence of $0$ ${\ displaystyle 0}$ and $one$ ${\ displaystyle 1}$ . This bit sequence is encrypted as follows ^[1] :

The auxiliary vector is calculated $\mathbf {a} =mE$ ${\ displaystyle \ mathbf {a} = mE}$ .
An error vector is randomly generated. $\mathbf {e}$ ${\ displaystyle \ mathbf {e}}$ dimensions $n$ ${\ displaystyle n}$ containing units of no more than $t=2^{m-r-1}-1$ ${\ displaystyle t = 2 ^ {mr-1} -1}$ discharges.
The transmitted ciphertext is calculated by adding the previously computed vectors $\mathbf {b} =\mathbf {a} +\mathbf {e}$ ${\ displaystyle \ mathbf {b} = \ mathbf {a} + \ mathbf {e}}$ .

Decryption

The ciphertext received on the public channel is a vector $\mathbf {b} =mE+\mathbf {e}$ ${\ displaystyle \ mathbf {b} = mE + \ mathbf {e}}$ where $m$ ${\ displaystyle m}$ - Announcement. To decrypt a cryptogram ^[2] :

The vector is calculated $\mathbf {b} '=\mathbf {b} P^{-1}$ ${\ displaystyle \ mathbf {b} '= \ mathbf {b} P ^ {- 1}}$ , which is a vector of the Reed-Muller code with a generating matrix $G$ ${\ displaystyle G}$ distorted no more than in $t$ ${\ displaystyle t}$ discharges. Strictly speaking, the error vector $\mathbf {e}$ ${\ displaystyle \ mathbf {e}}$ with this approach, it is also multiplied by the matrix $P^{-1}$ ${\ displaystyle P ^ {- 1}}$ , but for the decoding algorithm this does not matter, since its weight during permutations, obviously, remains the same.
Using any Reed-Muller code decoding algorithm, a vector is found $\mathbf {a} '$ ${\ displaystyle \ mathbf {a} '}$ satisfying the condition $\mathbf {b} '=\mathbf {a} 'G+\mathbf {e}$ ${\ displaystyle \ mathbf {b} '= \ mathbf {a}' G + \ mathbf {e}}$ .
An informational message is calculated . $m=\mathbf {a} 'A^{-1}$ ${\ displaystyle m = \ mathbf {a} 'A ^ {- 1}}$ .

Attack on the cryptosystem

Sidelnikov in one of his articles showed the inconsistency of the McEliece cryptosystem based on Reed-Solomon codes , finding a way to crack such a system in polynomial time ^[3] . In this regard, and also, wishing to eliminate some of the shortcomings of the McEliece system, Sidelnikov proposed and described a cryptosystem based on Reed-Muller codes ^[1] .

Despite the fact that Sidelnikov considered his cryptosystem reliable, in 2007 cryptographers L. Minder and A. Shokrolllahi invented a very original way to crack Sidelnikov’s system. The method was based on the assertion that $RM(0,m)\subset RM(1,m)\subset \ldots \subset RM(m,m)$ ${\ displaystyle RM (0, m) \ subset RM (1, m) \ subset \ ldots \ subset RM (m, m)}$ for anyone $m$ ${\ displaystyle m}$ (here we approach the code as a linear space spanned by a basis of code vectors) ^[2] .

Denote by $RM(r,m)^{\delta }$ ${\ displaystyle RM (r, m) ^ {\ delta}}$ Reed-Muller code after applying the permutation operator to it. Then, finding in some way the permutation matrix that was used to generate the private key, it is possible by computing the matrix $P^{-1}$ ${\ displaystyle P ^ {- 1}}$ (this can be done, since for any permutation matrix there is an inverse), find the matrix $G^{*}=AG$ ${\ displaystyle G ^ {*} = AG}$ ; since the public key in the Sidelnikov system is the matrix $A G P$ ${\ displaystyle AGP}$ multiplying which by $P^{-1}$ ${\ displaystyle P ^ {- 1}}$ can be found $G^{*}$ ${\ displaystyle G ^ {*}}$ ^[2] .

It remains only to calculate the matrix $A$ ${\ displaystyle A}$ . To solve this matrix problem $G^{*}$ ${\ displaystyle G ^ {*}}$ and $E$ ${\ displaystyle E}$ are written side by side, and using linear transformations of the strings, the matrix $G^{*}$ ${\ displaystyle G ^ {*}}$ reduced to matrix $G$ ${\ displaystyle G}$ , which is known in advance for a given Reed-Muller code. As a result, there is a chain of transformations $(G^{*}|E)\rightarrow (G|A^{-1})$ ${\ displaystyle (G ^ {*} | E) \ rightarrow (G | A ^ {- 1})}$ , which follows from basic information about linear algebra. Generally speaking, the matrix $A$ ${\ displaystyle A}$ you don’t have to search, since it’s easy enough to show that $A G$ ${\ displaystyle AG}$ and $G$ ${\ displaystyle G}$ generate the same Reed-Muller code ^[2] .

Attack Essence

Minder and Shokrolllahi in their article proposed the following way to search for a permutation matrix:

Looking for code code vectors $RM(r,m)^{\delta }$ ${\ displaystyle RM (r, m) ^ {\ delta}}$ that are very likely to belong to the code $RM(r-1,m)^{\delta }$ ${\ displaystyle RM (r-1, m) ^ {\ delta}}$ . A sufficient number of such vectors is found to construct the basis of space $RM(r-1,m)^{\delta }$ ${\ displaystyle RM (r-1, m) ^ {\ delta}}$ . The search is based on the statement that the Reed-Muller code is of order $r$ ${\ displaystyle r}$ is a subspace of the same order code $r-1$ ${\ displaystyle r-1}$ , as well as on the properties of code vectors with a minimum weight.
Repeat step 1 until the code is received. $RM(1,m)^{\delta }$ ${\ displaystyle RM (1, m) ^ {\ delta}}$ .
Rearranging columns in a certain way $RM(1,m)^{\delta }$ ${\ displaystyle RM (1, m) ^ {\ delta}}$ , it is possible to find the source code $RM(1,m)$ ${\ displaystyle RM (1, m)}$ with a probability of more $1/2$ ${\ displaystyle 1/2}$ (a maximum of 2 iterations is required to obtain a positive result) ^[2] . In other words, it is possible to find the permutation operator used to generate the private key.

Temporary estimates of the hacking algorithm

In a temporary analysis of the algorithm, the number is taken as the input parameter $n=2^{m}$ ${\ displaystyle n = 2 ^ {m}}$ being the dimension of the codeword. Code order $r$ ${\ displaystyle r}$ relies on small compared to $m$ ${\ displaystyle m}$ , since the Reed-Muller code at large orders is rather useless in terms of practical application (in particular, the number of errors it corrects with increasing $r$ ${\ displaystyle r}$ becomes very small). The most computationally complex part of the entire algorithm is the search for code words with minimal weight, since all other operations are performed in a known polynomial time ^[2] .

Asymptotic estimate of the complexity of the algorithm: $O(poly(n))\cdot e^{O(poly(log(n)))}$ ${\ displaystyle O (poly (n)) \ cdot e ^ {O (poly (log (n)))}}$ . For large orders of code $r$ ${\ displaystyle r}$ the task becomes computationally difficult, since the time taken to search for code words with minimal weight increases significantly ^[2] .

Experimental

Minder and Shokrolllahi conducted a series of experiments on a computer with a clock frequency of 2.4 GHz ^[2] . The results can be seen in the table:

	$r=2$ ${\ displaystyle r = 2}$	$r=3$ ${\ displaystyle r = 3}$	$r=4$ ${\ displaystyle r = 4}$
$m=5~(n=32)$ ${\ displaystyle m = 5 ~ (n = 32)}$	$<0{,}01c$ ${\ displaystyle <0 {,} 01c}$
$m=6~(n=64)$ ${\ displaystyle m = 6 ~ (n = 64)}$	$<0{,}01c$ ${\ displaystyle <0 {,} 01c}$
$m=7~(n=128)$ ${\ displaystyle m = 7 ~ (n = 128)}$	$0{,}02c$ ${\ displaystyle 0 {,} 02c}$	$5{,}261c$ ${\ displaystyle 5 {,} 261c}$
$m=8~(n=256)$ ${\ displaystyle m = 8 ~ (n = 256)}$	$0{,}081c$ ${\ displaystyle 0 {,} 081c}$	$2{,}059c$ ${\ displaystyle 2 {,} 059c}$
$m=9~(n=512)$ ${\ displaystyle m = 9 ~ (n = 512)}$	$0{,}0448c$ ${\ displaystyle 0 {,} 0448c}$	$3{,}462c$ ${\ displaystyle 3 {,} 462c}$	$176{,}914c$ ${\ displaystyle 176 {,} 914c}$
$m=10~(n=1024)$ ${\ displaystyle m = 10 ~ (n = 1024)}$	$2{,}46c$ ${\ displaystyle 2 {,} 46c}$	$26{,}6c$ ${\ displaystyle 26 {,} 6c}$	$82197{,}4c$ ${\ displaystyle 82197 {,} 4c}$
$m=11~(n=2048)$ ${\ displaystyle m = 11 ~ (n = 2048)}$	$18{,}34c$ ${\ displaystyle 18 {,} 34c}$	$1192{,}71c$ ${\ displaystyle 1192 {,} 71c}$	$-$ ${\ displaystyle -}$

Operating time at $r=3,m=7$ ${\ displaystyle r = 3, m = 7}$ is the result of an error in the implementation of the algorithm.

Sidelnikov generalized system

Sidelnikov also proposed an enhanced version of his cryptosystem using $u$ ${\ displaystyle u}$ generating matrices. In other words, a public key in such a system is calculated as $|AG_{1},AG_{2}\ldots ,AG_{u}|P$ ${\ displaystyle | AG_ {1}, AG_ {2} \ ldots, AG_ {u} | P}$ where the first factor is a composite matrix of size $un\times k$ ${\ displaystyle un \ times k}$ .

Minder and Shokrolllahi in their article showed that hacking a cryptosystem thus improved does not differ in complexity from hacking a cryptosystem with a single generating matrix, since breaking the code into blocks is a very simple task ^[2] .

Notes

↑ ¹ ² ³ ⁴ ⁵ Chizhov, Borodin, 2013 .
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ Minder, Shokrollahi, 2007 .
↑ Sidelnikov, Shestakov, 1992 .

Literature

Sidelnikov V. M. , Shestakov S. O. On an encryption system based on generalized Reed – Solomon codes // Diskr. mate. - 1992. - T. 4, no. 3. - S. 57–63. - ISSN 2305-3143
<a href=" https://wikidata.org/wiki/Track:Q21753923 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21753922 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21753925 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21766545 "> </a>
Sidelnikov V. M. Open encryption based on binary Reed – Muller codes // Diskr. mate. - 1994. - T. 4, no. 3. - S. 191–207. - ISSN 2305-3143
<a href=" https://wikidata.org/wiki/Track:Q21753923 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21766801 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21753922 "> </a>
Minder L. , Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem // Advances in Cryptology - EUROCRYPT 2007 : 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007. Proceedings / M. Naor - Springer Berlin Heidelberg , 2007. - P. 347-360. - ( Lecture Notes in Computer Science ; Vol. 4515) - ISBN 978-3-540-72539-8 - ISSN 0302-9743 - doi: 10.1007 / 978-3-540-72540-4_20
<a href=" https://wikidata.org/wiki/Track:Q21777805 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21777804 "</a> <a href = " https://wikidata.org/wiki/Track:Q21777806 "> </a> <a href=" https://wikidata.org/wiki/Track:Q924044 "> </a> <a href = " https://wikidata.org/wiki/Track:Q6899861 "> </a> <a href=" https://wikidata.org/wiki/Track:Q4746324 "> </a> <a href = " https : //wikidata.org/wiki/Track: Q21587985 "> </a>
Chizhov I. V. , Borodin M. A. The failure of McEliece PKC based on Reed-Muller codes // Prikl. Diskr. Mat. Suppl. - Tomsk State University , 2013 .-- Iss. 6. - P. 48–49. - ISSN 2226-308X
<a href=" https://wikidata.org/wiki/Track:Q21777337 "> </a> <a href=" https://wikidata.org/wiki/Track:Q742494 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21777332 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21777333 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21777341 "> </a>

[_51464d5b21273037-1] ¹ ² ³ ⁴ ⁵ Chizhov, Borodin, 2013 .

[_7a358e378edd199d-2] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ Minder, Shokrollahi, 2007 .

[_5e51e3c54261368b-3] Sidelnikov, Shestakov, 1992 .