【密码学】基于编码的密码学学习笔记(五) 线性码

之前，我们已经讲解过编码的一些相关的定义，以及编解码的策略和能力，从本文开始，我们主要是来聊一下线性码的相关知识，因为后续基于编码的密码学，也主要用到的是线性码，其他的编码目前就不做过多的介绍了。

定义

首先，我们来看一下线性码的定义，这里先来看一个正经的定义吧。

设为有限域(q为素数幂)，n为正整数。一个线性码是有限域上的一个长度为n的向量空间的一个线性子空间(非空)，即满足:

1. 加法的封闭性: 对于任意的两个码字，有
2. 标量乘法的封闭性: 对于任意的和，有

此时，我们称是一个线性码，其中是子空间的维度。如果的最小汉明距离是d, 则进一步称其为线性码。

看到这个定义，如果对于线性空间熟悉的话，应该不难理解，线性码的本质是向量空间当中的子空间。这里，用一个不一定非常恰当的例子来解释一下，读者可能或多或少的听过皇室战争这个游戏。

在游戏开始之前，可以选择一个卡组，选择完成之后，上场的卡组就只能限定在选择的卡组之中了，这里，上场无论是相同的卡组，还是不同的组合，都是在限定的卡组里面。

这里，对于线性空间，有个非常重要的例子，也就是基。

基

对于一个线性码，令是上的一组基，对于线性码，我们可以表示为

其中，因此，这里对于码字的数量，根据乘法原理，显然有

对于基，还是可以用上面提到的卡牌游戏来理解，就相当于是选择的卡组，而对于码字，其实就相当于阵容的变化。

性质

有了上面的表述，接下来，我们来看一些有关于线性码的性质，首先，我们来看一下线性码的信息率。

信息率

对于一个线性码，他的信息率可以表示为

除了信息率，对于编码来说，还有一个非常重要的量，那便是距离，接下来我们来看一下，对于一个线性码他的距离如何来计算。

距离

我们先来回顾一下，向量的「L0范数」，它用来表示向量中非0元素的个数，对于向量

我们有

其中是指示函数(当时为1，否则为0)。

类似的，我们可以定义一个码的L0范数，对于一个线性码，我们有

那么，这个定义看起来，和码的汉明距离非常相似啊，对，实际上他俩是相等的。接下来，我们来简单的证明一下吧。

这里，注意到，并且是线性码，因此，我们有。

编码&解码

有了前面的铺垫，我们就可以来聊一聊具体的编码和解码方式了。这里，对于编码的方式，也非常的简单，我们知道，可以编码的消息实际上是一个k维的数组，也就是

我们只需要做一个映射

就可以完成编码了，这里需要注意的是，对于不同的基，会有不同的编码的结果。

生成矩阵

为了更方便的描述这个编码，看到上面的结果，我们不难想到可以用一个矩阵来描述编码的过程，对于一个线性码，利用它的一组基，可以构造一个的矩阵，矩阵元素是基的行向量表示，即

这里，编码过程可以简化为

我们称这个矩阵为生成矩阵。

案例

接下来，我们来看一个例子，我们考虑一个的线性码，也就是编码元素我们取二进制。给定一个生成矩阵

这里，我们来搞一个编码的样例。

从这里，可以看到，信息率，，因此，对于这个编码，我们可以写成线性码。

接下来，我们来看一下，码相等的条件，就是在什么情况下，我们说这两个码是相等的。

码相等

线性系统码

再看之前，我们先来了解一下什么是线性系统码，对于一个线性码，如果其生成矩阵满足

其中:

• 是一个的单位矩阵
• 是的校验位生成矩阵

生成的码字的结构为:

我们称这个编码为线性系统码。

码相等

两个线性码相等当且仅当它们的码字集合完全相同。具体来说，若两个码的生成矩阵可以通过行初等变换（如行交换、行倍乘、行相加）相互转化，则它们的行空间相同，生成的码相等。

我们，还是来看一个例子，比如如下的生成矩阵。

我们同样，可以得到对应的编码。

这就和上面，我们给出的例子是的编码是相等的。这里，我们再次来看一下，码相等的条件，我们可以总结为三个等价的命题。

• 集合相等: 和对应的集合包含完全相同的码字
• 生成矩阵的空间相同: 存在初等行变换，使得和的生成矩阵和满足

总结

从本文开始，我们算是正式进入基于编码的密码学的讲解，后续，我们只讨论线性码，对于其他的编码，如果感兴趣的读者，可以自行研究，好了，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://www.taptap.cn/moment/48083832930305206
2. https://courses.smp.uq.edu.au/MATH3302/2010/files/codingnotes.pdf
3. https://link.springer.com/chapter/10.1007/978-3-540-88702-7_4
4. https://www.itsoc.org/sites/default/files/2021-11/Code-Based%20Cryptography.pdf