SM9

论文大合集

前情提要
困难问题假设

双线性群

标识签名的定义和安全模型
标识签名 (identity-based signature) 由以下 4 个多项式时间算法组成.
• (mpk, msk) ← Setup(λ). 已知系统安全参数 λ, 系统建立算法 Setup 以 λ 为输入, 输出系统主公钥 mpk 和主私钥 msk, 其中 mpk 是公开的, msk 由 KGC 秘密保存. 此算法由 KGC 执行.
• skID ← KeyGen(mpk, msk,ID). 已知标识 ID, 用户私钥生成算法 KeyGen 以系统主公私钥对 (mpk, msk) 和 ID 为输入, 输出用户 ID 的私钥 skID. 此算法由 KGC 执行.
• σ ← Sign(mpk, M,skID). 已知消息 M, 签名算法 Sign 以系统主公钥 mpk、M 和签名者的私钥 skID 为输入, 输出 M 的签名 σ. 此算法由签名者执行.
• 1/0 ← Verify(mpk, M, σ,ID). 验证算法 Verify 以系统主公钥 mpk、签名消息 M 及其签名 σ和签名者的标识 ID 为输入, 输出 “1” 或者 “0”. “1” 表示签名有效, “0” 表示签名无效. 此算法由验证者执行.
标识签名算法的正确性要求对任意的 (mpk, msk) ← Setup(λ), skID ← KeyGen(mpk, msk,ID)和 σ ← Sign(mpk, M,skID), 有 Verify(mpk, M, σ,ID) = 1.

安全模型
适应性选择消息和标识攻击下的存在性不可伪造 (existentially unforgeable against adaptive chosen messageand identity attacks, EUF-CMIA) 安全模型. 该安全模型通过挑战者 (challenger) 和攻击者 (adversary)完成的游戏定义.
EUF-CMIA 安全模型的定义如下:
• 系统建立阶段. 已知安全参数 λ, 挑战者运行算法 Setup(λ), 生成系统主公私钥对 (mpk, msk),并将 mpk 发送给攻击者.
• 私钥询问. 已知标识 ID, 挑战者运行用户私钥生成算法 KeyGen 生成私钥 skID, 并发送给攻击者.
• 签名询问. 已知标识 ID 和消息 M, 挑战者首先运行用户私钥生成算法 KeyGen 生成用户 ID的私钥 skID, 然后以 skID 和 M 为输入, 运行算法 Sign 生成签名 σ, 并将 σ 发送给攻击者.
• 伪造阶段. 最后, 攻击者输出标识 ID∗ 对消息 M∗ 的伪造签名 σ∗. 模型要求攻击者没有询问过标识 ID∗ 的私钥. 若攻击者没有询问过标识 ID∗ 对消息 M∗ 签名且 σ∗ 是消息 M∗ 的有效签名, 则攻击者获胜.
定义模型中攻击者 A 的优势 Adv_A^{EUF-CMIA} (λ) 为赢得以上 EUF-CMIA 游戏的概率.

标识密钥封装的定义和安全模型
标识密钥封装 (identity-based key encapsulation) 由以下 4 个多项式时间算法描述.
• (mpk, msk) ← Setup(λ). 已知系统安全参数 λ, 系统建立算法 Setup(λ) 为输入, 输出系统主公钥 mpk 和主私钥 msk, 其中 mpk 是公开的, msk 由 KGC 秘密保存. 此算法由 KGC 执行.
• skID ← KeyGen(mpk, msk,ID). 已知标识 ID, 用户私钥生成算法 KeyGen 以 (mpk, msk) 和 ID为输入, 输出用户 ID 对应的私钥 skID. 此算法由 KGC 执行.
• (C, K) ← Encap(mpk,ID). 密钥封装算法 Encap 以系统主公钥 mpk 和接收者标识 ID 为输入,输出密文 C 和封装的会话密钥 (简称封装密钥) K. 此算法由密钥封装者执行.
• K/⊥← Decap(mpk, C,skID). 解封装算法 (解密算法) Decap 以系统主公钥 mpk, 密钥封装密文 C 和接收者私钥 skID 为输入, 输出封装密钥 (会话密钥) K 或者解密失败符号 “⊥”. 此算法由解密者执行.
标识密钥封装算法的正确性要求对任意的 (mpk, msk) ← Setup(λ), skID ← KeyGen(mpk, msk,ID) 和 (C, K) ← Encap(mpk,ID), 有 Decap(mpk, C,skID) = K.

安全模型
标识密钥封装机制在适应性选择密文攻击下的不可区分 (indistinguisha-bility against adaptive chosen-ciphertext attacks, IND-CCA) 安全模型确保只有拥有正确私钥的用户才能获得封装的会话密钥. 模型通过挑战者和攻击者参与的游戏定义. IND-CCA 安全模型的定义如下:
• 系统建立阶段. 已知安全参数 λ, 挑战者运行算法 Setup(λ), 生成系统主公私钥对 (mpk, msk),并将 mpk 发送给攻击者.
• 询问阶段 1. 攻击者允许适应性发起解密私钥询问和密文解密询问.
(1) 解密私钥询问. 已知标识 ID, 挑战者运行算法 KeyGen 生成私钥 skID, 并发送给攻击者.
(2) 密文解密询问. 已知封装密文 (C,ID), 挑战者首先运行算法 KeyGen 产生私钥 skID, 然后以 skID 和 C 为输入运行算法 Decap, 并将输出结果发送给攻击者.

进入正题

SM9签名算法

算法：

安全性分析

定理1 设 SM9 签名算法中的密码杂凑函数 H1, H2 是随机谕言器. 如果 q-SDH 假设成立, 则 SM9签名算法是 EUF-CMIA 安全的
感觉文章给的q-SDH有点详略，补充一下

系统建立阶段
B 首先隐式 (implicitly) 设系统主私钥 msk 为 α = a, 其中 a 是未知的, 并执行以下步骤生成系统主公钥.

哈希询问阶段

询问阶段

伪造阶段

Twin-SM9密钥封装算法

正确性分析

安全性分析

定理 4.1. 设算法中的密码杂凑函数 $H_1, H_2$ 为随机谕言器。如果 $q$-BDHI 假设成立，则本文提出的新密钥封装算法 Twin-SM9 是 IND-CCA 安全的。

q-BDHI（q-Bilinear Diffie-Hellman Inversion，q-双线性Diffie-Hellman求逆）
一句话：知道公钥”序列” $(Q, aQ, a^2Q, \dots, a^qQ)$，但你无法反推出 $a$，也就无法算出 $e(P,Q)^{1/a}$。

证明. 假设存在多项式时间概率攻击算法 $\mathcal{A}$ 以不可忽略的优势 $\epsilon$ 攻破 Twin-SM9 密钥封装算法。我们可构造一个多项式时间概率模拟算法 $\mathcal{B}$ 以 $\frac{\epsilon}{q_{H_1}}$ 的概率成功求解 $q$-BDHI 问题。已知 $\mathcal{B}$ 以一个 $q$-BDHI 问题实例

$$
(P, Q, aQ, a^2 Q, \dots, a^q Q)
$$

为输入，其目标是求 $e(P, Q)^{\frac{1}{a}}$，其中 $a$ 未知，$q = q_{H_1}$ 为询问随机谕言器 $H_1$ 的次数。

本小节从通信代价和计算开销两个方面分析新密钥封装算法 Twin-SM9 的性能，并与文献 [10]（SM9）进行比较。符号说明：|𝔾𝑖| 表示群 𝔾𝑖 (𝑖 =1,2,𝑇) 中元素大小，𝑝 表示双线性对运算，𝑆𝑀𝑖 表示群 𝔾𝑖 (𝑖 =1,2) 中的标量乘（scalar multiplication）运算，𝐸𝑡 表示群 𝔾𝑇 中的指数（exponentiation）运算，𝐻𝑁 表示映射到 ℤ∗𝑁 的密码杂凑函数，𝐻𝐵 表示映射到 0,1𝑘𝑙𝑒𝑛 的密码杂凑函数。比较结果见表 1 和表 2。

表 1 通信代价与假设对比

Scheme	Public Key	Private Key	Ciphertext	Assumption
SM9 key encapsulation [10]	$2	G_1	+ 1	G_2
Twin-SM9	$2	G_1	+ 1	G_2

表 2 计算开销与安全性对比

Scheme	Key Generation	Encryption	Decryption	Security
SM9 key encapsulation [10]	1 𝑆𝑀2 +1 𝐻𝑁	2 𝑆𝑀1 +1 𝐸𝑡 +1 𝐻𝑁 +1 𝐻𝐵	1 𝑝 +1 𝐻𝐵	IND-CCA
Twin-SM9	2 𝑆𝑀2 +1 𝐻𝑁	2 𝑆𝑀1 +2 𝐸𝑡 +1 𝐻𝑁 +1 𝐻𝐵	2 𝑝 +1 𝐻𝐵	IND-CCA

表 1 和表 2 显示，与 SM9 密钥封装算法相比较，本文提出的 Twin-SM9 密钥封装算法的系统公钥和用户私钥分别增加一个群元素，密文长度不变，安全性没有降低。虽然在私钥生成、密文生成和解密过程计算开销有小幅度增长，但本算法的安全性基于更弱的 𝑞-BDHI 假设，消除了 Gap 类困难假设，具有一定的理论意义。

Gap 类困难假设：指代像 Gap−q−BCAA1 这样虽然能用于证明 SM9 安全性、但由于其假设较强而逐渐被研究者试图避开的困难假设,。研究 Twin-SM9 的核心目的之一就是“消除 Gap 类困难假设”的影响。