Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / post-quantum cryptography, code-based cryptography, Reed--Muller subcodes, Reed--Muller codes, Hadamard product, McEliece cryptosystem

Original Publication (with minor differences):

Date: received 30 Apr 2020

Contact author: vysotskaya victory at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200505:010644 (All versions of this report)

Short URL: ia.cr/2020/507


[ Cryptology ePrint archive ]