主要记录一下Technicla Foundations和The Proposed Scheme两个部分

Technicla Foundations

knowledge

keypoint:(Bilinear Pairings)

三个性质：

这里提到了两个配对（简要了解一下）：1、Weil-pairing 2、Tate-pairing

Weil-pairing性质

destination:定义在$E[r]$上，$E[r]={P:rP=O}$(r-torsion subgroup)

双线性：$e_W(aP,bQ)=e_W(P,Q)^{ab}$
反对称：$e_W(P,Q)=e_W(Q,P)^{-1}$->$e_W(P,P)=1$
非退化：if$e(P,Q)=1$对于所有$Q$都成立->$P=O$

Tate-pairing

定义：$e_T:G_1× G_2→F_{q^k}^*$(k为嵌入度)

也就是配对结果进入括域

GDH(这个之前也没有特别清楚只知道有这么一个东西Gap具体Gap啥也是不知道)

先讲3个问题

DLP
- 给$a,g^a$求解$a$是困难的（目前没有已知的多项式时间算法）
CDH（Computational Diffie-Hellman)
- 给$g,g^a,g^b$计算$g^{ab}$(直接算)
DDH(Decisional Diffie-Hellman）
- 给四元组$(g,g^a,g^b,T)$判断$T=g^{ab}$或$T=g^c$（结果是0/1）不用计算

在双线性配对后DDH变得很容易，而CDH依然困难，所以出现了Gap

ID-Based Public Key Setting

核心：ID就是公钥

The Proposed Scheme

Syntax of ID-Based Proxy Signature Schemes

定义一个含多个算法和协议的元组：$(\mathcal{G}, \mathcal{K}, \mathcal{S}, \mathcal{V}, (\mathcal{D}, \mathcal{P}), \mathcal{PS}, \mathcal{PV}, \mathcal{ID})$

$\mathcal{G}$:系统参数生成算法

$\mathcal{K}$:密钥提取算法

Warrant:

$\mathcal{S}$:签名算法

输入委托人$d_{ID}$和授权信息$m_\omega$输出授权$\omega$

$ \mathcal{V}$:验证算法

输入委托人身份、授权信息$m_\omega$和授权书$\omega$,输出接受或拒绝

$(\mathcal{D}, \mathcal{P})$:代理授权交互委托人$\mathcal{D}$和代理人$ \mathcal{P}$

INPUT

双方身份信息$ID_i,ID_j$
委托人$\mathcal{D}$:输出私钥$d_i$、授权书消息$m_\omega$和授权书签名$\omega$;
代理方$\mathcal{P}$:输入私钥$d_j$

OUTPUT

代理人$\mathcal{P}$获得代理签名私钥$skp$和授权书$\omega$

代理签名算法$\mathcal{PS}$:

$\mathcal{P}$ input: $skp、m、\omega$ and output 代理签名$psig$

代理验证算法$\mathcal{PV}$

input $ID_j、m、\omega、psig$ and output “accept or reject”

代理身份识别算法$\mathcal{ID}$:

input $\omega、psig$ and output $ID_j$

结合双线性对

$PS=(\mathcal{G}, \mathcal{K}, \mathcal{S}, \mathcal{V}, (\mathcal{D}, \mathcal{P}), \mathcal{PS}, \mathcal{PV}, \mathcal{ID})$

$\mathcal{G}$:

选择一个阶为$q$的GDH群$G$和双线性映射$\hat{e}$,random master key$s\in Z_{q}^*$，公开系统公钥$P_{pub}=sP$还有四个哈希函数$H_1, H_2, H_3 : {0, 1} ^∗ → G$,$ H_4 : {0, 1} ^∗ → \mathbb{Z} ^∗_ q$

$H: {0,1}^* \to \mathbb{Z}_q$	输入任意二进制串，输出模 q的一个整数
$H: {0,1}^* \to G$	输入任意二进制串，输出群 G 中的一个元素（通常是椭圆曲线点）

$\mathcal{K}$:

give a users id $ID$, compute $Q_{ID}=H_1(ID)\in G$ and $d_{ID}=sQ_{ID}\in G$

$\mathcal{S}$:

sign a message $m_\omega$ use $d_i$ of $ID_i$

过程包括选取随机数$r_\omega\in Z_{q}^*$,compute $U_\omega=r_\omega P\in G$,and $H_\omega=H_2(ID_i,m_\omega,U_\omega)\in G$
compute $V_\omega=d_i+r_\omega H_\omega \in G$,Warrant=$\omega=<U_\omega,V_\omega>$

$\mathcal{V}$:

$(\mathcal{D,P})$:

$\mathcal{PS}$:

(代理签名过程)

随机选取 $r_p\in Z_q^*$ ,计算 $U_p=r_pP\in G$ and $H_p=H_3(ID_j,m,U_p)\in G$
$V_p=skp+r_pH_p\in G$
签名：$psig=(m_\omega,ID_j,U_\omega,U_p,V_p)$

$\mathcal{PV}$:

if true accept else reject

推导过程

基础参数与定义

根据来源，我们需要以下已知等式作为推导基础：

系统参数：$P_{pub} = sP$ [1, 2]。
用户私钥：$d_i = sQ_i$，$d_j = sQ_j$（其中 $Q = H_1(ID)$）[1, 2]。
授权书签名：$V_\omega = d_i + r_\omega H_\omega$ [3]。
代理私钥：$skp = H_4 \cdot d_j + V_\omega$（注：此处 $H_4$ 为 $H_4(ID_i, ID_j, m_\omega, U_\omega)$ 的简写）[4]。
代理签名组件：$V_p = skp + r_p H_p$ [4]。
随机值映射：$U_\omega = r_\omega P$，$U_p = r_p P$ [2, 4]。

完整推导步骤

我们从验证等式的左侧 $\hat{e}(P, V_p)$ 开始：

第一步：展开 $V_p$
$$\hat{e}(P, V_p) = \hat{e}(P, skp + r_p H_p)$$
利用双线性映射的性质 $\hat{e}(P, A+B) = \hat{e}(P, A)\hat{e}(P, B)$ [5]：
$$= \hat{e}(P, skp) \cdot \hat{e}(P, r_p H_p)$$

第二步：展开 $skp$
代入 $skp = H_4 \cdot d_j + V_\omega$ [4]：
$$= \hat{e}(P, H_4 \cdot d_j + V_\omega) \cdot \hat{e}(P, r_p H_p)$$
$$= \hat{e}(P, H_4 \cdot d_j) \cdot \hat{e}(P, V_\omega) \cdot \hat{e}(P, r_p H_p)$$

第三步：展开 $V_\omega$ 并应用私钥定义
代入 $V_\omega = d_i + r_\omega H_\omega$ [3]：
$$= \hat{e}(P, H_4 \cdot d_j) \cdot \hat{e}(P, d_i + r_\omega H_omega) \cdot \hat{e}(P, r_p H_p)$$
$$= \hat{e}(P, H_4 \cdot d_j) \cdot \hat{e}(P, d_i) \cdot \hat{e}(P, r_\omega H_\omega) \cdot \hat{e}(P, r_p H_p)$$

第四步：利用双线性性质转化每一项
利用 $\hat{e}(P, aQ) = \hat{e}(aP, Q)$ 以及 $P_{pub} = sP$ 的关系 [1, 5]：

$\hat{e}(P, H_4 \cdot d_j) = \hat{e}(P, H_4 \cdot s Q_j) = \hat{e}(sP, Q_j)^{H_4} = \mathbf{\hat{e}(P_{pub}, Q_j)^{H_4}}$
$\hat{e}(P, d_i) = \hat{e}(P, s Q_i) = \hat{e}(sP, Q_i) = \mathbf{\hat{e}(P_{pub}, Q_i)}$
$\hat{e}(P, r_p H_p) = \hat{e}(r_p P, H_p) = \mathbf{\hat{e}(U_p, H_p)}$
$\hat{e}(P, r_\omega H_\omega) = \hat{e}(r_\omega P, H_\omega) = \mathbf{\hat{e}(U_\omega, H_\omega)}$
最终结论

将上述转化后的项重新组合，得到验证者在 $PV$ 步骤中使用的最终公式 [6]：

$$\hat{e}(P, V_p) = \hat{e}(P_{pub}, Q_j)^{H_4(ID_i, ID_j, m_\omega, U_\omega)} \cdot \hat{e}(P_{pub}, Q_i) \cdot \hat{e}(U_p, H_p) \cdot \hat{e}(U_\omega, H_\omega)$$

推导意义：这个推导过程证明了只要代理签名 $psig$ 是由合法的代理私钥 $skp$（该私钥包含了委托人的授权 $V_\omega$ 和代理人自己的私钥 $d_j$）生成的，那么验证等式就一定会成立 [6]。

$\mathcal{ID}$: