Hyper の 个人博客

交流技术，分享生活

0%

论文阅读：一种采用匿名生物特征的基于模糊无证书签名的车载自组网高效认证方案

发表于 分类于 ， ， 阅读次数：
本文字数： 11k 阅读时长 ≈ 10 分钟

Info

文章出处：An efficient fuzzy certificateless signature-based authentication scheme using anonymous biometric identities for VANETs

1 预备知识

1.1 困难问题

ECDL 问题
椭圆曲线上的循环加法群 GG 由无穷远点 OO 和曲线 EE 上的其他点组成，PP、qq 为生成元和阶。给定群 GG 中已知两个点 PP 和 QQ，且 Q=xPQ = xP，其中 x∈Zq∗x \in \mathbb{Z}_q^*。敌手 AA 在 PPT 时间内计算 xx 是困难的，即解决 ECDL 问题的概率 ϵ\epsilon 是可忽略的。
* 注：然而，本文方案实际并未使用到椭圆曲线，故基于的困难问题应为离散对数问题
RSA 问题
一个 PPT 敌手 AA 尝试计算一个整数 uu，使得 ue≡c(modn)u^e \equiv c \pmod{n}，其中 (n,e,c)(n,e,c) 是已知的，且 nn 是两个不同奇素数 pp 和 qq 的乘积，满足最大公约数 gcd⁡(e,(p−1)(q−1))=1\gcd(e, (p - 1)(q - 1)) = 1。AA 解决 RSA 问题的概率 ϵRSAA=Pr⁡[A(n,e,c)→u]\epsilon_{\text{RSA}}^A = \Pr[A(n, e, c) \to u] 是可忽略的。
变种 RSA 问题
一个 PPT 敌手 AA 尝试计算两个整数 (w,u)(w,u)，使得 ue≡awz(modn)u^e \equiv a w^z \pmod{n}。其中 (n,e,a,z)(n, e, a, z) 是已知的，且 nn 是两个不同奇素数 pp 和 qq 的乘积，满足 gcd⁡(e,(p−1)(q−1))=1\gcd(e, (p - 1)(q - 1)) = 1。AA 解决 VRSA 问题的概率 ϵVRSAA=Pr⁡[A(n,e,a,z)→(w,u)]\epsilon_{\text{VRSA}}^A = \Pr[A(n, e, a, z) \to (w, u)] 是可忽略的。

1.2 Shamir 秘密共享

Shamir 秘密共享方案通过将一个秘密值 ss 拆分为 nn 个片段 s1,...,sns_1, ..., s_n​，每位参与者 P1,...,PnP_1, ..., P_n 分别持有一个片段。核心原理是：当群体中至少有 tt 个成员时，能够恢复秘密值 ss；否则无法恢复。

  • 秘密分发

    • 随机选择 s∈Zq∗s \in Z_q^* 作为共享的秘密值，随机选取一个满足 f(0)=sf(0) = s 的 t−1t-1 次多项式 f(x)=s+∑j=1t−1ajxj mod qf(x)= s + \sum_{j=1}^{t-1} a_jx^j \ mod \ q
    • 随机选择 αi∈Zq∗\alpha_i \in Z_q^*​，计算 f(αi)=sif(\alpha_i) = s_i，其中 i∈{1,...,n}i \in \{1, ..., n\}
    • 将第 ii 个片段 {αi,f(αi)}\{\alpha_i, f(\alpha_i) \} 分发给对应的参与者 PiP_i

  • 秘密恢复：对包含至少 tt 个参与者的群体 SS，这些参与者通过以下等式恢复秘密值 s=f(αi)s=f(\alpha_i)，其中 Δαi,S(x)\Delta_{\alpha_i,S}(x) 为拉格朗日基本多项式：

    f(x)=∑Pi∈SΔαi,S(x)f(αi)f(x) = \sum_{P_i \in S} \Delta_{\alpha_i,S}(x) f(\alpha_i)

    Δαi,S(x)=∏Pk∈S,k≠ix−αkαi−αkmod  q\Delta_{\alpha_i,S}(x) = \prod_{P_k \in S, k \neq i} \frac{x - \alpha_k}{\alpha_i - \alpha_k} \mod q

1.3 汉明距离

汉明距离（Hamming Distance）最早用于数据传输纠错码，是两个字符串或向量中对应位置位不同的数目。给定两个等长的字符串或向量 x=(x1,x2,…,xn)x = (x_1, x_2, \dots, x_n) 和 y=(y1,y2,…,yn)y = (y_1, y_2, \dots, y_n)，其汉明距离 dH(x,y)d_H(x, y) 定义为：

dH(x,y)=∑i=1nδ(xi,yi), 其中 δ(xi,yi)={1 当 xi≠yi0 当 xi=yid_H (x, y) = \sum_{i=1}^{n} \delta (x_i, y_i), \ \text {其中} \ \delta (x_i, y_i) = \begin {cases} 1 & \text {当 } x_i \neq y_i \\ 0 & \text {当 } x_i = y_i \end {cases}

2 认证方案流程

  • SetupSetup：系统初始化，由 TA 执行，输入安全参数 λλ，TA 与 KGC 共同输出系统主私钥 ss，并发布系统参数 ParaPara​

  • Registration and PseudoRegistration \ and \ Pseudo-identity Generationidentity \ Generation：注册与假名生成，每辆车辆 VjV_j 向 TA 申请注册，TA 运行本算法输入车辆的生物特征 biojbio_j​，输出生物身份 BIDjBID_j。随后车辆为 VjV_j 创建假名 PIDjPID_j​，并通过安全信道发送给车辆

  • Partial Private Key ExtractPartial \ Private \ Key \ Extract：部分密钥生成，由 KGC 执行，输入 VjV_j 的假名 PIDjPID_j​、系统主密钥 ss 和系统参数 ParaPara​，输出 VjV_j​ 的部分私钥 PSPIDPS_{PID}

  • Set Secret ValueSet \ Secret \ Value：设置秘密值，由 VjV_j 执行，输入其假名 PIDjPID_j 和系统参数 ParaPara​，生成其秘密值 xPIDx_{PID}

  • Set Private KeySet \ Private \ Key：设置私钥，由 VjV_j 执行，输入假名 PIDjPID_j​、部分私钥 PSPIDPS_{PID}、系统参数 ParaPara​ 和秘密值 xPIDx_{PID}，生成其完整私钥 SKPIDSK_{PID}

  • Set Public KeySet \ Public \ Key：设置公钥，由 VjV_j 执行，给定车辆 VjV_j​ 的秘密值 xPIDjx_{PID_j}​，生成 VjV_j 的公钥 PKPIDjPK_{PID_j}

  • SignSign：签名，由 VjV_j 执行，输入 VjV_j 的假名 PIDjPID_j、系统参数 ParaPara、消息 mm 和完整私钥 SKPIDSK_{PID}，输出与 PIDjPID_j 和消息 mm 关联的签名 σ\sigma

  • VerifyVerify：验证，给定车辆 VjV_j 的假名 PIDjPID_j​、系统参数 ParaPara、公钥 PKPIDjPK_{PID_j}​、消息 mm 和签名 σ\sigma，返回 11 或 00

2.1 系统初始化


在此阶段，TA 生成系统主密钥并公布参数列表：

  • 给定安全参数 λ\lambda，随机选取大素数 pp 和 qq，计算 ϕ(N)=(p−1)(q−1)ϕ(N)=(p−1)(q−1) 和 N=pqN=pq，并将 pp、qq 和 ϕ(N)ϕ(N) 保密

  • 另选一组大素数 p′p' 和 q′q'，使得 p′≠p、q′≠qp' \neq p、q' \neq q、且 q′∣(p′−1)q' \mid (p'-1)。同时，选取 g∈Zp′∗g \in \mathbb{Z}^*_{p'} 且 g≠1g \neq 1，满足 gq′≡1(modp′)g^{q'} \equiv 1 \pmod{p'}

  • TA 随机选取一个整数 ee，满足 1<e<ϕ(N)1 < e < \phi(N) 且 gcd(e,ϕ(N))=1\text{gcd}(e, \phi(N)) = 1。TA 根据方程 e⋅s≡1(modϕ(N))e \cdot s \equiv 1 \pmod{\phi(N)} 计算出主私钥 ss

  • 定义一个安全的对称密钥加密方案 Encκ(⋅)/Decκ(⋅)\text{Enc}_\kappa(\cdot)/\text{Dec}_\kappa(\cdot)，κ\kappa 为对称密钥

  • TA 与 KGC 选择三个密码学哈希函数：

    • H1:{0,1}∗→ZN∗H_1:\{0, 1\}^* \to\mathbb{Z}^*_{N}
    • H2:{0,1}∗→{0,1}∣N∣/4H_2 : \{0, 1\}^* \to \{0, 1\}^{|N|/4}
    • H3:{0,1}∗×{0,1}∗×Zp′∗×{0,1}π→Zq′∗H_3 : \{0, 1\}^* \times \{0, 1\}^* \times \mathbb{Z}^*_{p'} \times \{0, 1\}^\pi \to \mathbb{Z}^*_{q'}

  • 公开参数列表 Para=(p′,q′,N,e,g,H1,H2,H3)Para=(p',q',N,e,g,H_1,H_2,H_3)

2.2 注册和假名生成


车辆在进入车联网前需要向 TA 注册：

  • VjV_j 通过安全信道向 TA 提供其真实的生物特征 biobio

  • TA 生成生物特征标识 BIDj=IdGen(bio)BID_j = \text{IdGen}(bio)，IdGen(⋅)\text{IdGen}(\cdot) 是一种身份提取函数

  • TA 为 VjV_j 创建假名 PIDj=Encκ(BIDj∥nPID)∥TjPID_j = \text{Enc}_\kappa(BID_j \| n_{PID}) \| T_j，其中 nPIDn_{PID} 是请求的假名数量，TjT_j 为假名有效期

  • TA 通过安全信道向 VjV_j 发送 {BIDj,PIDj}\{BID_j, PID_j\}


这一步还考虑了恶意车辆冒充 RSU 的情况，作者声称的解决方案是：

  • 定义另一个安全签名方案，由 TA 将方案交给 RSU

  • RSU 定期广播自己的公钥、私钥签名后的真实身份、验签方法 Verpk(.)Ver_{pk}(.)

  • 车辆用 RSU 公钥验签；若验证失败，表明为假冒 RSU，向 TA 上报

  • TA 追溯此假冒 RSU 的真实身份

但这样做实际上是把系统的安全性建立在这个签名方案的保密性上，这并不能解决实际问题；而如果方案公开，对于一个正确的签名方案，伪装成 RSU 的恶意车辆总能自行选取一个 RID′RID'，对 RID′RID' 生成一个合法签名并通过其他车辆的验证。

2.3 完整密钥生成

KGC 获取车辆 VjV_j 假名 PIDjPID_j，生物特征相关属性集 ω=(ωi)i=1n\omega = (\omega_i)_{i=1}^n，主私钥 ss，为 VjV_j 生成部分私钥：

  • 随机选取阶数为 d−1d-1 的多项式 p(x)p(x)，满足 p(0)=sp(0) = s

  • 计算 VjV_j​ 的部分私钥 PSPIDj=(PSi,j)i=1nPS_{PID_j}=(PS_{i,j})_{i=1}^n，其中 PSi,j=H1(PIDj)p(ωi) mod NPS_{i,j} = H_1(PID_j)^{p(\omega_i)} \ mod \ N

  • 将部分私钥 PSPIDjPS_{PID_j} 经安全信道交给 VjV_j
    车辆 VjV_j 计算完整的公私钥对：

    • 随机选取 xPIDj∈Zq′∗x_{PID_j} \in \mathbb{Z}^*_{q'} 和阶数为 d−1d-1 的多项式 f(x)f(x)，满足 f(0)=xPIDj={xi,PIDj}i=1nf(0) = x_{PID_j}=\{x_{i, PID_j}\}_{i=1}^n，其中 xi,PIDj=f(ωi)x_{i, PID_j} = f(\omega_i)
    • 私钥 SKPIDj=(PSPIDj,xPIDj)SK_{PID_j} = (PS_{PID_j}, x_{PID_j})，公钥 PKPIDj=gxPIDj mod p′PK_{PID_j} = g^{x_{PID_j}} \ mod \ p'

2.4 签名


车辆 VjV_j 对消息 mjm_j 签名：

  • 随机选取 lj∈ZN∗l_j \in \mathbb{Z}^*_N​ 和阶数为 d−1d−1 的多项式 g(x)g(x)，满足 g(0)=ljg(0) = l_j。对于 i∈{1,…,n}i \in \{1, \dots, n\}，计算：

    • yi,j=li,je mod Ny_{i,j} = l_{i,j}^e \ mod \ N，其中 li,j=g(ωi)l_{i,j} = g(\omega_i)
    • ui,j=PSi,j⋅ljH2(mj) mod Nu_{i,j} = P\text{S}_{i,j} \cdot l_{j}^{H_2(m_j)} \ mod \ N

  • 随机选取 kj∈ZN∗k_j \in \mathbb{Z}^*_N​ 和阶数为 d−1d−1 的多项式 q(x)q(x)，满足 q(0)=kjq(0) = k_j。对于 i∈{1,…,n}i \in \{1, \dots, n\}，计算：

    • rj=gkj mod p′r_j = g^{k_j} \ mod \ p'
    • vi,j=ki,j−xPIDj⋅hj mod q′v_{i,j} = k_{i,j} - x_{PID_j} \cdot h_j \ mod \ q'，其中 ki,j=q(ωi)k_{i,j} = q(\omega_i)，hj=H3(mj,PIDj,rj,Tj)h_j = H_3(m_j, PID_j, r_j, T_j)，TjT_j 为时间戳

  • 得到签名 σj=(uj,vj,yj,rj,hj)\sigma_j = (u_j, v_j, y_j, r_j, h_j)，其中 yj=(yi,j)i=1ny_j = (y_{i,j})_{i=1}^n, uj=(ui,j)i=1nu_j = (u_{i,j})_{i=1}^n, vj=(vi,j)i=1nv_j = (v_{i,j})_{i=1}^n

2.5 验证

验证者接收消息 - 签名对 (mj,σj)(m_j, \sigma_j) 和车辆 VjV_j 公钥 PKPIDjPK_{PID_j}，生物特征相关属性集 ω=(ωi)i=1n\omega = (\omega_i)_{i=1}^n，ω′=(ωi′)i=1n\omega' = (\omega'_i)_{i=1}^n，其满足 ∣ω∩ω′∣≥d|\omega \cap \omega'| \geq d，验证签名：

  • 从 ω∩ω′\omega \cap \omega' 中随机选取一个包含 dd 个元素的子集 SS，验证等式

    (∏ωi∈Sui,jΔωi,S(0))e=H1(PIDj)⋅(∑ωi∈Syi,jΔωi,S(0)H2(mj)edΔωi,S(0))mod  N\left( \prod_{\omega_i \in S} u_{i,j}^{\Delta_{\omega_i, S(0)}} \right)^e = H_1(PID_j) \cdot \left( \sum_{\omega_i \in S} y_{i,j}{\Delta_{\omega_i, S(0)}} ^{H_2(m_j)ed \Delta_{\omega_i, S(0)}} \right) \mod N

    其中 Δωi,S(0)\Delta_{\omega_i, S(0)} 为拉格朗日基本多项式。若上述等式成立，进入下一步验证

  • 计算 hj′=H3(mj,PIDj,rj′,Tj)h_j' = H_3(m_j, PID_j, r_j', T_j)，验证等式

rj′=(∏ωi∈Sgjvi,j′)⋅(PKPIDj)hj′d mod p′r'_j=\left(\prod_{\omega_i \in S} g_j^{v'_{i,j}} \right) \cdot \left(PK_{PID_j} \right)^{h'_j d} \ mod \ p'

3 安全性分析

3.1 安全规约回顾

安全规约中涉及的三类实体：

  • 敌手（Adversary）：意图攻破密码学方案的实体；

  • 挑战者（Challenger）：当敌手与真实方案（Real Scheme）交互时，敌手实际上是在与挑战者交互，由挑战者生成真实方案并应答敌手的询问请求。挑战者仅出现在安全模型和安全描述中；

  • 模拟器（Simulator）：当敌手与模拟方案（Simulated Scheme）进行交互时，敌手实际上是在与模拟器进行交互，由模拟器生成模拟方案并应答来自敌手的询问请求。模拟器仅出现在安全归约中，作为运行归约算法的一方。

3.2 无证书签名的安全模型

  • I 型敌手：外部攻击者，可随意替换任意实体的公钥，但无法获知主密钥

  • II 型敌手：恶意的 KGC，可获知系统主密钥，但无法替换用户公钥

3.3 本文模拟方案

底层困难问题

  • DL 问题：已知 {x,y ∣ y=gx, x∈Zq∗}\{x, y \ | \ y=g^x, \ x \in Z_q^∗ \}，求解 xx 是困难的。

  • VRSA 问题：已知 {n,e,a,z ∣  n=pq, gcd⁡(e,(p−1)(q−1))=1,ue≡awz(modn), u,w∈Zq∗}\{n, e, a, z \ | \ \ n = pq, \ \gcd(e, (p-1)(q-1)) = 1, u^e \equiv a w^z \pmod{n}, \ u, w \in Z_q^∗ \}，求解 uu 和 ww 是困难的。

3.4 求解困难问题

Type I 型敌手

I 型敌手伪造对于 (PID^,m^)(\hat{PID} , \hat{m} ) 的签名 (u^,v^,y^,r^,h^)(\hat{u} ,\hat{v} ,\hat{y} ,\hat{r} ,\hat{h} )，满足

得 (∑ωi∈Sy^iΔωi,S(0),∏ωi∈Su^iΔωi,S(0))\left(\sum_{\omega_i \in S} \hat{y}_i{\Delta_{\omega_i, S(0)}}, \prod_{\omega_i \in S} \hat{u}_i^{\Delta_{\omega_i, S(0)}}\right) 为困难问题的解

然而，这与 VRSA 问题的难度相矛盾，故方案是安全的。

Type II 型敌手

在询问 Public Key QueryPublic \ Key \ Query 时，若 ∣PID∩PIDπ∣≥d|PID \cap PID_{\pi}| \geq d，则令 PKPID=βP K_{PID} = \beta
在求解推导中，通过控制 H3H_3 的不同，得到对同一条消息的两条签名，满足
(∏ωi∈Sgv^)PKPIDπh^d=r^ mod p′\left( \prod_{\omega_i \in S} g^{\hat{v}} \right) PK_{P ID_\pi}^{\hat{h}d} = \hat{r} \ mod \ p' ①
(∏ωi∈Sgv′^)PKPIDπh′^d=r^ mod p′\left( \prod_{\omega_i \in S} g^{\hat{v'}} \right) PK_{P ID_\pi}^{\hat{h'}d} = \hat{r} \ mod \ p' ②
①−②①-②得 log⁡gβ=v^−v^′(h^′−h^)d\log_g \beta = \frac{\hat{v} - \hat{v}'}{(\hat{h}' - \hat{h})d} 为困难问题的解

然而，这与 DL 问题的难度相矛盾，故方案是安全的。

3.5 非形式化安全性证明

  • 消息认证：根据证明，本方案在 ECDLP 和变种 RSA 问题难以解决的假设下是抗自适应选择消息攻击的，所提方案可以保证消息的完整性、认证性和不可否认性。

  • 条件隐私保护：车辆 ViV_i 使用假名 PIDjP ID_j​ 保护其真实身份，假名基于安全对称加密方案 Encκ(⋅)/Decκ(⋅)\text{Enc}_\kappa(\cdot)/\text{Dec}_\kappa(\cdot) 生成，在不知道对称密钥 κ\kappa 的情况下，任何实体都无法恢复 ViV_i 的真实身份。仅 TA 拥有密钥，具备恢复 ViV_i 的真实身份 BIDjBID_j 的能力。

  • 容错性：方案基于秘密共享将系统主私钥 ss 和车辆 VjV_j 的秘密值 xPIDjx_{PID_j} 分别分成 nn 份，使得车辆 VjV_j 的部分私钥、完整私钥及签名均可以被构造为 nn 份的形式。任何包含至少 dd 个属性的属性集均可验证 VjV_j 的签名，因此方案具有容错性。

  • 可追溯性：当恶意车辆发送错误信息时，TA 可通过下述公式提取车辆 VjV_j​ 的生物特征身份 BIDjBID_j​ 并追踪恶意车辆：

  • 不可链接性：假名生成时用到的随机数 ljl_j​ 和 kjk_j​ 是不重复的，每个 PIDPID 是随机且唯一的。因此，攻击者无法关联由同一签名者生成的多个签名。

4 实验评估

4.1 计算开销

本文采用 MIRACL 密码学库计算了不同基本操作的执行时间。选取的参考方案 [19~25] 均为基于双线性配对的方案，因此与作者选取的这些方案相比，本文无配对的方案具有更低的计算开销。

  • TbpT_{bp}：执行双线性映射操作的时间

  • Tbp.mT_{bp.m}：执行基于双线性映射的标量乘法操作的时间

  • Tbp.smT_{bp.sm}：执行基于双线性映射的小指数测试的时间

  • Tbp.aT_{bp.a}：执行基于双线性映射的点加操作的时间

  • Te.mT_{e.m}：执行椭圆曲线上标量乘法操作的时间

  • Te.smT_{e.sm}：执行椭圆曲线上小指数测试的时间

  • Te.aT_{e.a}：执行椭圆曲线上点加操作的时间

  • Te.exT_{e.ex}：执行模幂运算所需的时间

  • TmtpT_{mtp}：执行映射到点的哈希时间

4.2 通信开销

对 I 型双线性配对，为达到 80bit 安全长度，需要 ∣g1∣≥1024(bits)|g_1 |≥ 1024(bits)，故 G1\mathbb{G}_1 的群元素大小为 1024÷8=1281024\div 8=128 字节。对比表明，本文方案在签名长度方面具有更低的通信开销。

  • lZq∗l_{Z^*_{q}}：20 字节，Zq∗Z^*_{q}​ 中的元素长度

  • lG1l_{G_1}：128 字节， G1\mathbb{G}_1 中的元素长度

  • lGl_{G}：40 字节，G\mathbb{G} 中的元素长度

  • 时间戳和哈希函数的输出分别设置为 4 字节和 20 字节

相关文章：