基于SM9的属性基在线离线签名方案论文阅读总结

本文用于记录本篇论文的阅读和知识总结与学习

前置内容

关键词

SM9;在线/离线签名;属性基签名;随机谕言机模型;q-SDH 问题

SM9算法

基于双线性对，可以实现属性基加密签名

相对而言，SM2基于椭圆曲线，无属性基相关属性

在线/离线签名

在线签名在服务器（可信的）等设备上进行，离线签名在轻量级设备上；离线签名在在线签名的基础上进行签名，可以减少轻量级设备的运算开销

随机谕言机模型

可以视为一个安全的哈希函数

q-SDH 问题

多个参与者的DH密钥交换，而且更强，而且抗量子

预备知识

双线性映射

给定安全系数 $\kappa$，生成一个双线性元组 $BP=(G_1,G_2,G_T,e,p)$

令 $P$ 是 $G_1$ 的一个生成元，令 $Q$ 是 $G_2$ 的一个生成元，一个双线性映射 $e:G_1\times G_2\rightarrow G_T$ 有：双线性非退化性可计算性三个性质

此外，在 $G_1$ 和 $G_2$ 之间存在一个能有效且能公开计算的同构映射 $\psi:G_2\rightarrow G_1$ ，即 $\psi(Q)=P$

q-SDH(q-strong Diffie-Hellman) 困难问题和困难问题假设

q-SDH困难问题，令 $P,Q$ 分别为 $G_1,G_2$ 的生成元，在 $(G_1,G_2)$ 群上的 q-SDH 问题可以表述为：给定 $q+2$ 个元素的元组 $(P,Q,aQ,a^2Q,…,a^qQ)$ ，找到一堆元素 $(c,\frac{1}{c+a}P)$ ，其中 $c\in \mathbb{Z}_p^*$

$(t,\varepsilon)-$q-SDH 困难问题假设：若不存在概率多项式时间 $t$ 的算法至少以不可忽略的概率 $\varepsilon$ 解决 $(G_1,G_2)$ 上的 q-SDH 问题，则称 q-SDH 问题在 $(G_1,G_2)$ 是 $(t,\varepsilon)$ 困难的

q-strong 指的是 $q$ 个用户，而不是量子quantum的意思

分叉引理

看不懂一点，暂时跳过

形式化定义和安全模型

ABOOS方案的形式化定义

安全模型

方案构造

附录

$\kappa$

安全系数 $\kappa$，LaTex写作 kappa，通常用来量化密码系统抵抗攻击的强度

它表示安全性级别，通常与密钥长度、加密算法的复杂性等因素相关。较大的 $\kappa$ 值意味着更强的安全性，抵御暴力破解和其他攻击的能力更强。

一个经典的例子是基于双线性映射的身份基加密（IBE）。在IBE中，用户的公钥可以是其身份信息（如电子邮件地址），而私钥由一个私钥生成中心生成。假设安全系数 $\kappa$ 为 128 位，这意味着攻击者需要消耗大约 $2^{128}$ 次操作才能成功破解密钥。通过双线性映射，公钥和私钥的生成、加密和解密操作可以高效完成，同时保持与 $\kappa$ 相关的安全性。

生成元

一个元素 $g$ 称为群 $G$ 的生成元，如果对于群 $G$ 中的任意元素 $x$，存在一个整数 $k$ 使得 $x = g^k$。换句话说，生成元是通过其幂（或反复运算）可以生成群中所有元素的元素。

双线性非退化性可计算性

双线性 $e(aP,bQ)=e(P,Q)^{ab}$

具体的，如果 $a=2,b=3$，那么 $e(2P, 3Q) = e(P, Q)^{2 \times 3} = e(P, Q)^6$。

非退化性任意 $P\in G_1,Q\in G_2$，有 \neq 1$

只要 $P$ 和 $Q$ 同时是有效的点，则 $e(P,Q)$ 必然不等于 $1$

可计算性任意 $P\in G_1,Q\in G_2$，有 $e(P,Q)$ 可以被有效计算

映射 $e(P, Q)$ 应能在多项式时间内计算。如果你有 $P$ 和 $Q$ 的坐标，可以通过预先定义的双线性映射算法快速计算出 $e(P, Q)$。

同构映射

对于两个群，一个映射 $\psi:G_2\rightarrow G_1$，需要满足：

一一对应 $a,b\in G_2$，如果 $\psi(a)=\psi(b)$，则 $a=b$
运算保持 $a,b\in G_2$，都有 $\psi(a\cdot b)=\psi(a)\cdot\psi(b)$

同构映射是可逆的

分叉引理

若攻击者能够成功生成有效的签名，即使在有限的查询次数后，我们可以利用这一点来构造另一个有效签名，这通常通过一种“分叉”的方式实现。

输入与图灵机：
- 令 $A$ 为一个输入仅包含公共信息的概率多项式时间的图灵机。这意味着 $A$ 是一个能在多项式时间内运行的算法，且其输入不包含秘密信息（例如签名密钥）。
签名查询与随机谕言机：
- $A$ 进行 $n$ 次签名查询和 $m$ 次随机谕言机查询。签名查询是指 $A$ 请求生成某个消息的签名，而随机谕言机查询则是指 $A$ 请求随机数或其它公用信息。
生成有效签名元组：
- 敌手 $A$ 可以在概率多项式时间内，以 $\epsilon$ 的概率产生一个有效的消息签名元组 $(m, \sigma)$，其中 $m$ 是消息，$\sigma$ 是该消息的签名，且 $H(m)$ 表示与消息 $m$ 相关的哈希值。
不可区分的分布：
- 如果这个签名元组可以在不知道签名密钥的情况下以不可区分的分布概率进行模拟，意味着攻击者 $A$ 的行为与一个理想模型中没有秘密信息的情况没有显著差异。
构造另一台图灵机：
- 根据分叉引理，如果存在这样一个模拟，那么就存在另一台概率多项式时间的图灵机 $B$，它可以在理想情况下，通过控制攻击者 $A$ 的模拟与签名者的交互，生成两个有效的消息签名元组 $(m_1, \sigma_1)$ 和 $(m_2, \sigma_2)$，使得这两个签名都是有效的，并且 $H(m_1) = H(m_2)$。