Paper 2020/507

Characteristics of Hadamard square of Reed--Muller subcodes of special type (Extended abstract)

Victoria Vysotskaya

Abstract

The existence of some structure in a code can lead to the decrease of security of the whole system built on it. Often subcodes are used to ``disguise'' the code as a ``general-looking'' one. However, the security of subcodes, whose Hadamard square is equal to the square of the base code, is reduced to the security of this code, i.e. this condition is undesirable. The paper finds the limiting conditions on the number of vectors of degree $ r $ removing of which retains this weakness for Reed--Muller subcodes and, accordingly, conditions for it to vanish. For $ r = 2 $ the exact structure of all resistant subcodes was found. For an arbitrary code $ RM(r, m) $, the desired number was estimated from both sides. Finally, the ratio of subcodes, whose Hadamard square is not equal to the square of the original code, was proven to tend to zero if additional conditions on the codimension of the subcode and the parameter $ r $ are imposed and $ m \rightarrow \infty $. Thus, the implementation of checks proposed in the paper helps to immediately filter out some insecure subcodes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Unknown, but not published by IACR
Keywords
post-quantum cryptographycode-based cryptographyReed--Muller subcodesReed--Muller codesHadamard productMcEliece cryptosystem
Contact author(s)
vysotskaya victory @ gmail com
History
2020-05-05: received
Short URL
https://ia.cr/2020/507
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/507,
      author = {Victoria Vysotskaya},
      title = {Characteristics of Hadamard square of Reed--Muller subcodes of  special type (Extended abstract)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/507},
      year = {2020},
      url = {https://eprint.iacr.org/2020/507}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.