Dilithium Signature
Table of Contents
1. 简介
Dilithium Signature 是一种后量子（Post-Quantum）数字签名算法，本文简单介绍它。
1.1. 基本思路
Dilithium 签名的基本思路如图 1 所示。
Figure 1: Template of Dilithium Signature
在生成签名时， \(\mathbf{y}\) 是随机生成的 masking 多项式，其多项式系数小于等于 \(\gamma_1 - 1\) 。其中 \(\gamma_1\) 是一个足够大的参数。因为在 \(\mathbf{z} := \mathbf{y} + c \mathbf{s_1}\) 中， \(\mathbf{z}\) 是公开的，要想保护私钥 \(\mathbf{s_1}\) 的隐私，随机的 masking \(\mathbf{y}\) 必须足够大，否则 \(\mathbf{z}\) 可能泄露 \(\mathbf{s_1}\) 的部分信息。
在生成签名时， \(c\) 是一种特殊 Hash 生成的，这种 Hash 的结果是其中的 60 个比特位为 \(1\) 或者 \(-1\) ，其它 196 个比特位均为 \(0\) 。
在签名校验时，为什么 \(w_1'\) 会和计算签名时的 \(w_1\) 相等呢？即为什么 \(\mathbf{A}\mathbf{z}-c\mathbf{t}\) 的高比特位会和 \(\mathbf{A}y\) 的高比特位相等。式子 \(\mathbf{A}\mathbf{z}-c\mathbf{t}\) 在代入 \(\mathbf{z}\) 和 \(\mathbf{t}\) 的计算式后，有 \(\mathbf{A}\mathbf{z}-c\mathbf{t}=\mathbf{A}\mathbf{y}-c\mathbf{s_2}\) ，也就是说如果下式成立： \[\text{HighBits}(\mathbf{A}\mathbf{y}-c\mathbf{s_2}) = \text{HighBits}(\mathbf{A}\mathbf{y})\] 那么 \(w_1'\) 和 \(w_1\) 就会相等。 由于 \(c\mathbf{s_2}\) 比较小，在 \(\mathbf{A}\mathbf{y}\) 基础上减去 \(c\mathbf{s_2}\) 也不足以影响到 \(\mathbf{A}\mathbf{y}\) 的高比特位。 所以 \(\text{HighBits}(\mathbf{A}\mathbf{y}-c\mathbf{s_2}) = \text{HighBits}(\mathbf{A}\mathbf{y})\) 会成立，从而 \(w_1'\) 和 \(w_1\) 会相等。
2. Dilithium 签名
节 1.1 中介绍的签名方案中，有个缺点：公钥 \((\mathbf{A},\mathbf{t})\) 数据量太大了，比如 \(\mathbf{A}\) 是个 \(k\cdot l\) 的多项式矩阵。
Dilithium 签名中采用了下面措施来减少公钥的大小：
- 随机产生一个种子 \(\rho\) 作为公钥，通过这个种子来生成所需的 \(\mathbf{A}\) 。显然保存 \(\rho\) 比直接保存 \(\mathbf{A}\) 要省空间，当需要 \(\mathbf{A}\) 时，由 \(\rho\) 推导即可。
- 由于签名校验中，不太会用到 \(\mathbf{t}\) 的低比特位。在保存公钥 \(\mathbf{t}\) 时，优化为只保存它的高比特位，放弃公钥 \(\mathbf{t}\) 的低比特位。这个优化措施可以减少 \(\mathbf{t}\) 的数据量。不过，当 \(c\mathbf{t}\) 出现进位时，进位信息需要以其它形式保存（即图 2 中的 \(\mathbf{h}\) ），否则无法签名校验。总结： 省掉公钥 \(\mathbf{t}\) 的低比特位后，需要在签名数据增加 \(\mathbf{h}\) ，这会导致签名数据稍微增大，不过总体来说还是划算的。
Dilithium 签名如图 2 所示。
Figure 2: Dilithium Signature