Dilithium Signature

Table of Contents

1. 简介

Dilithium Signature 是一种后量子(Post-Quantum)数字签名算法,本文简单介绍它。

1.1. 基本思路

Dilithium 签名的基本思路如图 1 所示。

dilithium_template.jpg

Figure 1: Template of Dilithium Signature

在生成签名时, y 是随机生成的 masking 多项式,其多项式系数小于等于 γ11 。其中 γ1 是一个足够大的参数。因为在 z:=y+cs1 中, z 是公开的,要想保护私钥 s1 的隐私,随机的 masking y 必须足够大,否则 z 可能泄露 s1 的部分信息。

在生成签名时, c 是一种特殊 Hash 生成的,这种 Hash 的结果是其中的 60 个比特位为 1 或者 1 ,其它 196 个比特位均为 0

在签名校验时,为什么 w1 会和计算签名时的 w1 相等呢?即为什么 Azct 的高比特位会和 Ay 的高比特位相等。式子 Azct 在代入 zt 的计算式后,有 Azct=Aycs2 ,也就是说如果下式成立: HighBits(Aycs2)=HighBits(Ay) 那么 w1w1 就会相等。 由于 cs2 比较小,在 Ay 基础上减去 cs2 也不足以影响到 Ay 的高比特位。 所以 HighBits(Aycs2)=HighBits(Ay) 会成立,从而 w1w1 会相等。

1.2. 属于 Schnorr 签名框架

Dilithium 签名属于 Schnorr 签名框架,两者的对比如表 1 所示。

Table 1: Dilithium 签名和 Schnorr 签名的相似之处
Schnorr 签名 Dilithium 签名
签名第 1 部分 z=k+cs 签名第 1 部分 z=y+cs1
签名第 2 部分 c 签名第 2 部分 c
k 是随机数 y 是随机多项式
c 是 Challenge c 是 Challenge
s 是私钥 s1 是私钥

2. Dilithium 签名

1.1 中介绍的签名方案中,有个缺点:公钥 (A,t) 数据量太大了,比如 A 是个 kl 的多项式矩阵。

Dilithium 签名中采用了下面措施来减少公钥的大小:

  1. 随机产生一个种子 ρ 作为公钥,通过这个种子来生成所需的 A 。显然保存 ρ 比直接保存 A 要省空间,当需要 A 时,由 ρ 推导即可。
  2. 由于签名校验中,不太会用到 t 的低比特位。在保存公钥 t 时,优化为只保存它的高比特位,放弃公钥 t 的低比特位。这个优化措施可以减少 t 的数据量。不过,当 ct 出现进位时,进位信息需要以其它形式保存(即图 2 中的 h ),否则无法签名校验。总结: 省掉公钥 t 的低比特位后,需要在签名数据增加 h ,这会导致签名数据稍微增大,不过总体来说还是划算的。

Dilithium 签名如图 2 所示。

dilithium_signature.gif

Figure 2: Dilithium Signature

3. 参考

Author: cig01

Created: <2023-09-24 Sun>

Last updated: <2023-09-24 Sun>

Creator: Emacs 27.1 (Org mode 9.4)