Self-dual monomial codes and their use in cryptography
The purpose of this section is to analyze structural properties of recently proposed monomial self-dual codes. The results we obtained were accepted for publication at IMACC 2021.
The article focuses on the self-dual monomial codes that have an underlying structure of
decreasing/weakly decreasing monomial codes. Having such a property permits an in-depth
analysis of their structure: The permutation group of a subclass is (significantly) bigger than the
affine group. Upon looking at higher powers of the code, we see that its third power is the entire
space, but the dual of the square code gives information helpful for decoding. Using operations
such as shortening, puncturing and taking the discrete derivative, we extract the subcode
generated by the multiples of a certain variable. Recently, self-dual monomial codes have been
proposed for a McEliece public key encryption scheme. They seem to possess strong security
features – they have a large permutation group, they are self-dual, there are exponentially many of
them by counting the possible monomial bases used in their construction. A more detailed analysis
allows us to identify subclasses where the square code and shortening methods yield non-trivial
results; in these cases, the security is dominated by the complexity of the Information Set
Decoding, which is exponential in the square root of the length of the code. This is a solid
argument for the security of the McEliece variant based on self-dual monomial codes.