Informatics and Applications

2026, Volume 20, Issue 3, pp 2-22

SOME PROPERTIES OF THE CODE OF QUADRATIC RELATIONSHIPS AND ITS APPLICATION TO THE DECODING PROBLEM FOR LINEAR CODES

  • I. V. Chizhov

Abstract

In 2023, an approach to attacking the McEliece cryptosystem was proposed that is based on the study of so-called quadratic relationship codes, which are closely connected with the Schur-Hadamard product. These codes are constructed from quadratic forms that vanish on the columns of a generator matrix of a linear code. The effectiveness of this approach was recently demonstrated by an attack on the McEliece cryptosystem built upon binary Goppa codes of small degree. This attack exploits the fact that the quadratic relationship code contains a quadratic form of a relatively small rank. In the present paper, a systematic study is carried out of linear codes whose quadratic relationship code contains forms of rank 2 and lower. A special case is considered where the quadratic relationship code contains a reducible quadratic form, i. e., a form that decomposes into a product of two nonzero linear forms. Finally, the decoding problem is addressed for codes whose quadratic relationship codes contain no reducible quadratic forms or contain relatively few of them.

[+] References (33)

[+] About this article