**Semilinear transformations in coding theory and their application to cryptography**

*Wenshuo Guo and Fang-Wei Fu*

**Abstract: **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 $\mathbb{F}_{q^m}$ can be viewed as an $\mathbb{F}_q$-linear space of dimension $m$, a semilinear transformation $\varphi$ is therefore defined to be an $\mathbb{F}_q$-linear automorphism of $\mathbb{F}_{q^m}$. After that, we impose this transformation to a linear code $\mathcal{C}$ over $\mathbb{F}_{q^m}$. Apparently $\varphi(\mathcal{C})$ forms an $\mathbb{F}_q$-linear space, but generally does not preserve the $\mathbb{F}_{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.

**Category / Keywords: **public-key cryptography / post-quantum cryptography,code-based cryptography

**Original Publication**** (with minor differences): **https://arxiv.org/

**Date: **received 7 Jul 2021, last revised 9 Jul 2021

**Contact author: **ws_guo at mail nankai edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20210709:175340 (All versions of this report)

**Short URL: **ia.cr/2021/921

[ Cryptology ePrint archive ]