Semilinear transformations in coding theory and their application to cryptography
share
This paper presents a brand-new idea of masking the algebraic structure of linear codes used in code-based cryptography. Specially, we introduce the so-called semilinear transformations in coding theory, make a thorough study on their algebraic properties and then creatively apply them to the construction of code-based cryptosystems. Note that 𝔽_q^m can be viewed as an 𝔽_q-linear space of dimension m, a semilinear transformation φ is therefore defined to be an 𝔽_q-linear automorphism of 𝔽_q^m. After that, we impose this transformation to a linear code 𝒞 over 𝔽_q^m. Apparently φ(𝒞) forms an 𝔽_q-linear space, but generally does not preserve the 𝔽_q^m-linearity according to our analysis. Inspired by this observation, a new technique for masking the structure of linear codes is developed in this paper. Meanwhile, we endow the secret code with the so-called partial cyclic structure to make a reduction in public-key size. Compared to some other code-based cryptosystems, our proposal admits a much more compact representation of public keys. For instance, 1058 bytes are enough to reach the security of 256 bits, almost 1000 times smaller than that of the Classic McEliece entering the third round of the NIST PQC project.
READ FULL TEXT