Hyper の 个人博客

交流技术，分享生活

0%

论文阅读：面向车载自组网中安全和隐私保护车对车通信的支持批量认证的无证书签名方案

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

Info

文章出处：Certificateless Signature Scheme with Batch Verification for Secure and Privacy-Preserving V2V Communications in VANETs

1 方案介绍

1.1 无证书签名方案 CLSS

  • Setup(k)Setup(k)：系统初始化

  • PPKE(UIDi,s)PPKE(UID_i, s)：部分密钥生成

  • SPRK(UIDi,di)SPRK(UID_i, d_i)：设置用户完整私钥

  • SPK(UIDi,svi)SPK(UID_i, sv_i)：设置用户公钥

  • Sign(Mi,ski,UIDi,pki)Sign(M_i, sk_i, UID_i, pk_i)：签名

  • Verify(Mi,σi,UIDi,pki)Verify(M_i, σ_i, UID_i, pk_i)：单次验证

  • BatchVerify({Mi,σi,UIDi,pki}i=1n)BatchVerify(\{M_i, σ_i, UID_i, pk_i\}^n_{i=1})：批量验证

1.1.1 系统初始化

Setup(k)Setup(k)：由 KGCKGC 执行，根据安全参数生成主密钥和参数列表

  • 给定安全参数 kk，生成参数集合 ⟨G1,G2,ψ,GT,e,q,P,P′⟩\langle G_1, G_2, \psi, G_T, e, q, P, P' \rangle

  • 随机选取 s∈Zq∗s \in \mathbb{Z}_{q}^* 作为主私钥，计算主公钥 P0=sP,P0′=sP′P_0 = sP, P'_0 = sP'

  • 选择三个密码学哈希函数 H0:{0,1}∗→G1∗H_0 : \{0, 1\}^* \rightarrow G_1^*, H1:{0,1}∗→Zq∗H_1 : \{0, 1\}^* \rightarrow \mathbb{Z}_{q}^*, H2:{0,1}∗→G2∗H_2 : \{0, 1\}^* \rightarrow G_2^*

  • 公开参数列表 paramList={G1,G2,ψ,GT,e,q,P,P′,P0,P0′,H0,H1,H2}\text{paramList} = \{G_1, G_2, \psi, G_T, e, q, P, P', P_0, P'_0, H_0, H_1, H_2\}

1.1.2 部分密钥生成

PPKE(UIDi,s)PPKE(UID_i, s)：由 KGCKGC 执行，接受用户身份 UIDi∈{0,1}∗UID_i \in \{0, 1\}^* 和主私钥 ss 作为输入，生成用户部分私钥 did_i

  • 计算 di=sQid_i = sQ_i，其中 Qi=H0(UIDi)Q_i = H_0(U ID_i)

1.1.3 设置完整私钥

SPRK(UIDi,di)SPRK(UID_i, d_i)：由具有 UIDiUID_i 身份的用户执行，输入身份 UIDiUID_i 和部分私钥 did_i，生成其完整私钥 skisk_{i}

  • 选择随机数 svi∈Zq∗sv_{i} \in \mathbb{Z}_{q}^*​ 作为其秘密值

  • 设置完整私钥 ski=(svi,di)sk_{i} = (sv_{i}, d_i)

1.1.4 设置公钥

SPK(UIDi,svi)SPK(UID_i, sv_i)：由具有 UIDiUID_i 身份的用户执行，输入用户身份 UIDiUID_i 和秘密值 svisv_i，生成用户公钥 pkipk_i

  • 计算 pki=sviPpk_i=sv_iP

1.1.5 签名

Sign(Mi,ski,UIDi,pki)Sign(M_i, sk_i, UID_i, pk_i)：由具有 UIDiUID_i 身份、完整私钥 skisk_i 和公钥 pkipk_i 的签名者执行，输入消息 MiM_i​、skisk_{i}、UIDiUID_i​ 和 pkipk_i，生成对消息 MiM_i 的签名 σiσ_i

  • 随机选取 ri∈Zq∗r_i \in \mathbb{Z}_{q}^*​，设置 Ri=riPR_i = r_iP

  • 计算 ui=H1(UIDi∣∣Mi∣∣pki∣∣Ri∣∣Δ)u_i = H_1(UID_i || M_i || pk_i || R_i || \Delta) 和 W=H2(Δ)W = H_2(\Delta)，其中 Δ\Delta 是基于时间戳生成的一次性消息

  • 计算 Vi=uisviψ(W)+uidi+ri(ψ(W)+P0)V_i = u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)

  • 设置签名 σi=(Ri,Vi)\sigma_i = (R_i, V_i)

1.1.6 验证

Verify(Mi,σi,UIDi,pki)Verify(M_i, σ_i, UID_i, pk_i)：输入消息 MiM_i、签名 σiσ_i、用户身份 UIDiUID_i 和用户公钥 pkipk_i，验证者验证签名 σiσ_i 的有效性

  • 计算 Qi=H0(UIDi)Q_i = H_0(U ID_i)，ui=H1(UIDi∣∣Mi∣∣pki∣∣Ri∣∣Δ)u_i = H_1(UID_i || M_i || pk_i || R_i || \Delta)，W=H2(Δ)W = H_2(\Delta)

  • 如果 e(Vi,P′)=e(uipki+Ri,W)e(uiQi+Ri,P0′)e(V_i, P') = e(u_ipk_i + R_i, W)e(u_iQ_i + R_i, P'_0) 成立，则输出 11；否则输出 00

正确性证明：代入 Vi=uisviψ(W)+uidi+ri(ψ(W)+P0)V_i = u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)，di=sQid_i = sQ_i​，P0=sPP_0 = sP，P0′=sP′P'_0 = sP'，pki=sviPpk_i=sv_iP，Ri=riPR_i = r_iP，有
e(Vi,P′)=e(uisviψ(W)+uidi+ri(ψ(W)+P0),P′)e(V_i, P') = e(u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0), P')
=e(uisviψ(W),P′)⋅e(uidi,P′)⋅e(riψ(W),P′)⋅e(riP0,P′)=e(u_isv_{i}\psi(W), P') \cdot e(u_id_i , P') \cdot e(r_i\psi(W),P') \cdot e(r_iP_0,P')
=e(uisviP,W)⋅e(uisQi,P′)⋅e(riP,W)⋅e(riP,P0′)=e(u_isv_{i}P,W) \cdot e(u_isQ_i,P') \cdot e(r_iP,W)\cdot e(r_iP,P_0')
=e(uipki,W)⋅e(uiQi,sP′)⋅e(Ri,W)⋅e(Ri,P0′)=e(u_ipk_i,W)\cdot e(u_iQ_i,sP')\cdot e(R_i,W)\cdot e(R_i,P_0')
=e(uipki+Ri,W)e(uiQi+Ri,P0′)=e(u_ipk_i + R_i, W)e(u_iQ_i + R_i, P'_0)

1.1.7 批量验证

BatchVerify({Mi,σi,UIDi,pki}i=1n)BatchVerify(\{M_i, σ_i, UID_i, pk_i\}^n_{i=1})：验证者批量验证消息 - 签名对 (Mi,σi)(M_i, σ_i)

  • 随机选取 θ=(θ1,θ2,...,θn)\theta = (\theta_1, \theta_2, ..., \theta_n)，其中 θi∈{0,1}l\theta_i \in \{0, 1\}^l，ll 为小整数

  • 计算 Qi=H0(UIDi)Q_i = H_0(U ID_i)，ui=H1(UIDi∣∣Mi∣∣pki∣∣Ri∣∣Δ)u_i = H_1(UID_i || M_i || pk_i || R_i || \Delta)，W=H2(Δ)W = H_2(\Delta)

  • 如果 e(∑i=1nθiVi,P′)e(\sum_{i=1}^{n} \theta_i V_i, P') = e(∑i=1nθi(uipki+Ri),W)e(\sum_{i=1}^{n} \theta_i(u_i pk_i + R_i), W)e(∑i=1nθi(uiQi+Ri),P0′)e(\sum_{i=1}^{n} \theta_i(u_i Q_i + R_i), P'_0) 成立，则输出 11；否则输出 00

正确性证明：代入 Vi=uisviψ(W)+uidi+ri(ψ(W)+P0)V_i = u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)，di=sQid_i = sQ_i​，P0=sPP_0 = sP，P0′=sP′P'_0 = sP'，pki=sviPpk_i=sv_iP，Ri=riPR_i = r_iP，有
e(∑i=1nθiVi,P′)=e(∑i=1nθi(uisviψ(W)+uidi+ri(ψ(W)+P0)),P′)e(\sum_{i=1}^{n} \theta_i V_i, P') =e(\sum_{i=1}^{n} \theta_i (u_isv_{i}\psi(W) + u_id_i + r_i(\psi(W) + P_0)), P')
=e((∑i=1nθiuisvi)⋅ψ(W),P′)⋅e(∑i=1nθiuidi,P′)=e((\sum_{i=1}^{n} \theta_iu_isv_{i}) \cdot\psi(W), P') \cdot e(\sum_{i=1}^{n} \theta_iu_id_i , P') ⋅e((∑i=1nθiri)⋅ψ(W),P′)⋅e((∑i=1nθiri)⋅P0,P′)\cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot \psi(W),P') \cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot P_0,P')
=e((∑i=1nθiuisvi)⋅P,W)⋅e(∑i=1nθiuisQi,P′)=e((\sum_{i=1}^{n} \theta_iu_isv_{i}) \cdot P,W) \cdot e(\sum_{i=1}^{n} \theta_iu_isQ_i,P')⋅e((∑i=1nθiri)⋅P,W)⋅e((∑i=1nθiri)⋅P,P0′)\cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot P,W)\cdot e((\sum_{i=1}^{n} \theta_ir_i) \cdot P,P_0')
=e(∑i=1nθiuipki,W)⋅e((∑i=1nθiuiQi,sP′)=e(\sum_{i=1}^{n} \theta_iu_ipk_i,W)\cdot e((\sum_{i=1}^{n} \theta_iu_iQ_i,sP')⋅e(∑i=1nθiRi,W)⋅e(∑i=1nθiRi,P0′)\cdot e(\sum_{i=1}^{n} \theta_iR_i,W)\cdot e(\sum_{i=1}^{n} \theta_iR_i,P_0')
=e(∑i=1nθi(uipki+Ri),W)=e(\sum_{i=1}^{n} \theta_i(u_i pk_i + R_i), W)e(∑i=1nθi(uiQi+Ri),P0′)e(\sum_{i=1}^{n} \theta_i(u_i Q_i + R_i), P'_0)

1.2 车对车通信方案 ES&PPS

1.2.1 系统初始化阶段

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

  • 给定安全参数 kk，运行 Setup(k)Setup(k) 算法，生成主密钥 ss 和参数列表 paramList={G1,G2,ψ,GT,e,q,P,P′,P0,P0′,H0,H1,H2}\text{paramList} = \{G_1, G_2, \psi, G_T, e, q, P, P', P_0, P'_0, H_0, H_1, H_2\}

  • 选择一个安全的对称加密方案 Ekey(⋅)/Dkey(⋅)E_{\text{key}}(\cdot) / D_{\text{key}}(\cdot) 及其密钥 key\text{key}

  • 设置系统主密钥为 (key,s)(\text{key}, s)

  • 公开参数列表 paramList′={paramList,Ekey(⋅)/Dkey(⋅)}\text{paramList}' = \{\text{paramList}, E_{\text{key}}(\cdot) / D_{\text{key}}(\cdot)\}

1.2.2 车辆注册阶段

车辆需要向 KGCKGC 注册，KGCKGC 会为每辆车生成部分私钥和假名，并通过安全信道发送给每辆车；车辆收到后，生成完整私钥及对应公钥

  • 车辆 ViV_i 首先通过安全信道向 KGCKGC 提交注册请求 (UIDi,m~)(UID_i, \tilde{m})，其中 UIDiUID_i 是车辆的真实身份，m~\tilde{m} 是请求的新假名数目

  • 收到来自 ViV_i​ 的注册请求后，KGCKGC 执行以下步骤：

    • 计算 PIDi,j=Ekey(UIDi∣∣j)∣∣tiPID_{i,j} = E_{\text{key}}(U ID_i || j) || t_i 生成一组假名，其中 tit_i 是假名有效期，j∈{1,…,m~}j \in \{1, \ldots, \tilde{m}\}
    • 运行 PPKE(PIDi,j,s)PPKE(P ID_{i,j}, s) 算法，获得与 PIDi,jP ID_{i,j}​ 对应的部分私钥 di,jd_{i,j}
    • 通过安全信道向 ViV_i​ 发送 {(PIDi,j,di,j)}j=1m~\{(P ID_{i,j}, d_{i,j})\}_{j=1}^{\tilde{m}}

  • 车辆 ViV_i​ 分别运行 SPRK(PIDi,j,di,j)SPRK(PID_{i,j}, d_{i,j}) 和 SPK(PIDi,j,svi,j)SPK(P ID_{i,j}, sv_{i,j}) 算法，生成相应的完整私钥 ski,j=(svi,j,di,j)sk_{i,j} = (sv_{i,j}, d_{i,j}) 和公钥 pki,jpk_{i,j}

1.2.3 签名生成阶段

在车载自组网中，车辆需要定期广播交通相关信息 TRM。每辆车首先使用自己的完整私钥对 TRM 签名，再将签名后的 TRM 广播给附近车辆

  • 运行 Sign(Mi,ski,j,PIDi,j,pki,j)\text{Sign}(M_i, sk_{i,j}, P ID_{i,j}, pk_{i,j}) 算法生成对 MiM_i 的签名 σi,j\sigma_{i,j}​

  • ViV_i 广播 {PIDi,j,pki,j,Mi,σi,j}\{P ID_{i,j}, pk_{i,j}, M_i, \sigma_{i,j}\} 为签名后的 TRM

1.2.4 验证阶段

车辆可能在短时间内收到许多 TRM，可批量验证一组 TRM 的有效性。假设 ViV_i 需要广播的 TRM 为 MiM_i，其中包含时间戳 TsiTs_{i}，则

  • 车辆运行 BatchVerify({Mi,σi,j,PIDi,j,pki,j}i=1n)\text{BatchVerify}(\{M_i, \sigma_{i,j}, P ID_{i,j}, pk_{i,j}\}_{i=1}^{n}) 算法验证这些已签名 TRM 的有效性。如果输出 11，则接受这些 TRM

1.2.5 追踪阶段

如果车辆发现了使用伪造签名的 TRM，可以请求 KGCKGC 披露签名者的真实身份

  • KGC 计算 Dkey(PIDi,j)=Dkey(Ekey(UIDi∣∣j))D_{\text{key}}(P ID_{i,j}) = D_{\text{key}}(E_{\text{key}}(U ID_{i}||j)) 得到 UIDi∣∣jUID_{i}||j，从而获知其真实身份 UIDiUID_{i}

2 安全性分析

2.1 安全规约回顾

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

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

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

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

2.2 无证书签名的安全模型

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

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

2.3 本文 CLSS 的模拟方案

底层困难问题 co-CDHP：已知 {P,aP,P′,bP′∣a,b∈Zq∗}\{P, aP, P', bP' | a,b \in Z_q^∗ \}，求解 abPabP 是困难的。模拟方案包含以下步骤：

  • SetupSetup

  • PPK(UIDi)PPK(UID_i) queryquery

  • SVE(UIDi)SVE(UID_i) queryquery

  • PK(UIDi)PK(UID_i) queryquery

  • PKR(UIDi,pki′)PKR(UID_i, pk'_i) queryquery

  • S(Mi,UIDi,pki′)S(M_i,UID_i, pk'_i) queryquery

  • ForgeryForgery

注：本文在规约时全程使用了 Challenger 同敌手进行交互，这是不严谨的。由于挑战者只会如实地回答敌手的询问，这就导致无法将方案规约到困难问题上

2.4 求解困难问题

e(Vi∗,P′)=e(ui∗pki∗+Ri∗,Wi∗)e(ui∗Qi∗+Ri∗,P0′)e(V^{*}_i, P') = e(u^{*}_i pk^*_i + R^*_i, W^*_i) e(u^{*}_i Q^*_i + R^*_i, P'_0) ①

e(Vi∗′,P)=e(ui∗′pki∗+Ri∗,Wi∗)e(ui∗′Qi∗+Ri∗,P0′)e(V^{*'}_i, P) = e(u^{*'}_i pk^*_i + R^*_i, W^*_i) e(u^{*'}_i Q^*_i + R^*_i, P'_0) ②

Type I：由 P0′=aP′P'_0 = aP'，Qi∗=αi∗bPQ^*_i = \alpha^*_i bP，①-②得

abP=αi∗−1[(ui∗−ui∗′)−1(Vi∗−Vi∗′)−γi∗pki∗]abP = {α^∗_i }^{−1} [{(u^∗_i − u^{∗'}_i)}^{−1}(V ^∗_i − V^{∗'}_i ) − γ ^∗_i pk ^∗_i ] 为困难问题的解

Type II：由 Wi∗=βi∗aP′W_i^*=\beta_i^* aP^{'}，pk∗=svi∗bPpk^*={sv}_i^* bP，①-②得

abP=svi∗−1βi∗−1[(ui∗−ui∗′)−1(Vi∗−Vi∗′)−sQi∗]abP={sv^*_i}^{-1}{\beta^*_i}^{-1}[(u^*_i-u^{*'}_i)^{-1}(V^*_i-V^{*'}_i)-sQ^*_i] 为困难问题的解

2.5 非形式化安全性证明

消息认证：车辆 ViV_i 在广播包含时间戳 TsiTs_{i} 的交通相关消息（TRM）MiM_i 前，首先运行 Sign(Mi,ski,j,PIDi,j,pki,j)\text{Sign}(M_i, sk_{i,j}, P ID_{i,j}, pk_{i,j}) 算法生成 {PIDi,j,pki,j,Mi,σi,j}\{PID_{i,j}, pk_{i,j}, M_i, \sigma_{i,j}\} 为签名后的 TRM。当车辆 VjV_j 接收到 n 个消息 - 签名对时，使用算法 BatchVerify({Mi,σi,j,PIDi,j,pki,j}i=1n)\text{BatchVerify}(\{M_i, \sigma_{i,j}, P ID_{i,j}, pk_{i,j}\}_{i=1}^n) 验证其有效性。根据定理 1 和 2，已签名的 TRM 是不可伪造的。

条件隐私：车辆 ViV_i 使用假名 PIDi,jP ID_{i,j}​ 保护其真实身份，假名基于安全对称加密方案 Ekey(⋅)/Dkey(⋅)E_{\text{key}}(·)/D_{\text{key}}(·) 生成，在不知道对称密钥的情况下，任何实体都无法恢复 ViV_i 的真实身份 UIDiUID_i。仅 KGCKGC 拥有密钥，具备恢复 ViV_i 的真实身份 UIDiUID_i 的能力。

3 实验评估

3.1 计算开销

  • TbT_b：执行双线性映射操作的时间

  • Tm1T_{m1}：执行 G1\mathbb{G}_1 上标量乘法操作的时间

  • TmT_m：执行椭圆曲线上标量乘法操作的时间

  • THT_H：执行映射到点的哈希时间

  • Ts1T_{s1}：执行 G1\mathbb{G}_1 上小指数测试的时间

本文此处援引了 Yang et al. 一文，意在说明：I 型双线性映射操作要比 II 型更为昂贵，使用 I 型双线性映射的 TbT_b、Tm1T_{m1}、THT_H 和 Ts1T_{s1} 值显著高于使用 II 型双线性映射设计的方案（译）


按照逻辑，为呼应本文 “方案计算开销低于其他支持批量验证、安全的无证书签名方案” 的主要贡献，此处应当着重比较文献 [35][35] 等，但原文图例标注有误导致无法一一对应。ES&PPS 的批量验证效率仍低于无配对的四种方案（[32],[33],[36],[37][32],[33],[36],[37]），但这些方案是不安全的，或缺少安全性证明。

3.2 通信开销

  • lZp∗l_{Z^*_{p}}：32 字节，Zp∗Z^*_{p}​ 中的元素长度

  • lG1sspl_{G^{\text{ssp}}_{1}}：192 字节，SSP 曲线上 G1\mathbb{G}_1 中的元素长度

  • lG1bnl_{G^{\text{bn}}_{1}}：32 字节，BN 曲线上 G1\mathbb{G}_1 中的元素长度

  • lGeccl_{G_{\text{ecc}}}​​：32 字节，BN 曲线上任意群的元素长度

对 II 型双线性配对，已知采用的曲线为 BN256，则为达到 128bit 安全长度，需要 ∣g1∣≥256(bits)|g_1 |≥ 256(bits)，故群元素的大小为 256÷8=32256\div 8=32 字节。对比表明，本文方案在签名和公钥长度方面具有相同或更低的传输开销。

相关文章：