论文阅读：面向 6G 车联网的 CPP 多域认证与假名管理

文章出处：Conditional Privacy-Preserving Multi-Domain Authentication and Pseudonym Management for 6G-Enabled IoV

1 方案介绍

1.1 MACPP 多域认证方案

1.1.1 系统初始化阶段

$SD$ ：

选择椭圆曲线 $E：y_2 = x_3 + ax + b \ (mod\ p)$ 上阶为 $q$ 的加法群 $\mathbb{G}$ ，其中 $a、b ∈ \mathbb{F}_p$ ， $p、q$ 为两个大素数
定义三个安全哈希函数 $h_1：\mathbb{G} → \mathbb{Z}^*_q$ ， $h_2：\{0,1\}^* → \mathbb{Z}^*_q$ ， $h_3：G × \{0,1\}^* × \{0,1\}^* × \{0,1\}^* × \{0,1\}^* → \mathbb{Z}^*_q$
广播公共参数 $Params = \{\mathbb{G},P,p,q,a,b,h_1,h_2,h_3\}$
$TA_i$ ：
选取 $tp_i ∈ \mathbb{Z}^*_q$ 作为系统私钥，计算系统公钥 $TP_{pk_i} = tp_i \cdot P$
通过有线信道将 $TP_{pk_i}$ 传给区域内的每个 RSU，由 RSU 周期性广播

1.1.2 车辆注册和假名生成阶段

车辆 $V ^j _a$ ：

提前向 $TA_i$ 注册真实身份 $VID^j _a$ $KGC_j$ ：
选取 $Tag_j ∈ \mathbb{Z}^*_q$ 作为统一标签，证明具有 $Tag_j$ 的车辆属于 $AD_j$
计算并广播 $T AG_j = T ag_j \cdot P$
预先加载 $\{VID^j _a , AD_j , Tag_j \}$ 至车辆 $V ^j _a$ 的 OBU
车辆 $V ^j _a$ ：
向 OBU 发送假名生成请求
OBU 选取 $κ ^j _a ∈ \mathbb{Z}^*_q$ ，计算 $P ID^j_{a,1} = κ ^j _a \cdot P$ ， $P ID^j_{a,2} = VID^j _a ⊕ h_1 (κ ^j _a \cdot T AG_j ) ⊕ AD_j$
返回 $\{P ID^j_a , sk^j_a , T^j_a \}$ 给 $V ^j _a$ ，其中 $P ID^j_a=\{P ID^j_{a,1},P ID^j_{a,2}\}$ ， $sk^j_a = κ ^j _a + α ^j _a \cdot T ag_j \ mod \ q$ ， $α ^j _a=h_2 (P ID^j _a ∥ T ^j _a )$

1.1.3 消息签名阶段

车辆 $V ^j _a$ ：

选取 $w ^j_ a ∈ \mathbb{Z}^*_q$ ，计算 $W^ j_ a = w ^j_ a \cdot P$ ， $β ^ j_ a = h _3 (W ^ j_ a ∥ M ^ j_ a ∥ AD_ j ∥ P ID ^ j_ a ∥ T^ j_ a)$ ， $σ ^ j_ a= sk^ j_ a+ β ^ j_ a \cdot w^ j_ a \ mod \ q$
向附近车辆和 RSU 广播消息 $\{M ^ j_ a, P ID ^ j_ a, AD _j, W ^ j_ a, σ ^ j_ a, T ^ j_ a\}$

1.1.4 验证阶段

其他车辆 / RSU：

依次检查 $T^j_a$ 和 $P ID^j_a$ 是否有效
使用收到的消息和系统参数 $Params$ 计算 $α^j_a$ 和 $β^j_a$
计算并检查等式 $σ^j_a · P = P ID^j_{a,1} + α^j_a · T AG_j + β^j_a·W^j_a$ 是否成立
正确性证明：
$σ^j_a \cdot P$ $= (sk^j_a + β^j_a \cdot w^j_a) \cdot P$
$= (κ^j_a + α^j_a \cdot T ag_j + β^j_a \cdot w^j_a) \cdot P$
$= κ^j_a \cdot P + α^j_a \cdot T ag_j \cdot P + β^j_a\cdot w^j_a \cdot P$
$= P ID^j_{a,1} + α^j_a \cdot TAG_j + β^j_a \cdot W^j_a$

批量认证：

检查每条信息中时间戳的新鲜度
验证者检查左侧等式是否成立。若成立，则表明所有 $n$ 个签名均有效
复杂度分析
忽略 $\mathbb{Z}^*_q$ 中的加法和哈希运算等简单操作的开销，对 $n$ 个签名的情况，有：
逐一验证：开销为 $3n$ 次点乘运算和 $2n$ 次点加运算
批量验证：开销为 $(n + 2)$ 次点乘运算和 $(2n + 2)$ 次点加运算结论：由于点乘运算的显著减少，扩展的批量验证方案效率更高。

1.2 BAPM 假名管理方案

1.2.1 系统初始化

动态稀疏默克尔树 DSMT

结构：完全二叉树，每个数据块赋予唯一索引，空叶节点值被置为 $H(null)$ ；
动态：树的高度由 TA 在最新块中打包的假名数目决定；
稀疏性：允许大部分树被缓存，因为节点中存在恒定值如 $H(null)$ ， $H(H(null)∥H(null))$ 等。

示例： $TA_i$ 按注册时间顺序在最新块中存储假名，每个假名对应唯一索引。TAi 将每辆车的假名索引记录到Ω中。其中，假名的索引与车辆的真实身份索引不同，以防止攻击者将假名与真实车辆相关联。

Ω：每个 $TA$ 维护的列表，包含所有车辆真实身份，通过 $SD$ 做离线同步，保持所有 $TA$ 间的一致性

1.2.2 假名生成 / 更新

车辆 $V ^j _a$ ：

向 OBU 发送假名生成请求
OBU 选取 $κ ^j _a ∈ \mathbb{Z}^*_q$ ，计算 $P ID^j_{a,1} = κ ^j _a \cdot P$ ， $P ID^j_{a,2} = VID^j _a ⊕ h_1 (κ ^j _a \cdot T AG_j ) ⊕ AD_j$
返回 $\{P ID^j_a , sk^j_a , T^j_a \}$ 给 $V ^j _a$

1.2.3 假名验证与上传

假名在注册过后方可使用。生成新假名后， $V ^j _a$ 必须与 $TA_i$ 同步进行注册。
车辆 $V ^j _a$ ：

加密 $VID^j _a$ ，打包消息 $M_{en} = \{PID^j _a , AEnc(TP_{pki} , VID^j _a ), T_{en} \}$
签名消息，将 $M_{en}$ 和签名单播至最近的 RSU 验证
$RSU$ ：
验签，验证成功后经有线信道将 $M_{en}$ 上传至关联的 $TA_i$
$TA_i$ ：
获得消息中的 $PID^j _a$ ，使用 $tp_i$ 解密得到 $VID^j _a$

1.2.4 假名注册与存储

$TA_i$ ：

检查 $Ω$ 中 $VID^j _a$ 对应车辆是否已撤销
将 $PID^j _a$ 存储到由 $Idx_a$ 索引的当前 DSMT 中的首个空节点
计算 $H(PID^j _a)$ 、更新默克尔根并上链
在 $Ω$ 中记录新的 $Idx_a$

其他车辆和 RSU 可以通过区块链快速检查接收到的消息中假名的有效性。示例：如果一辆车想要验证假名 P ID j a 的合法性，它可以从区块链中的最新块查询 H (P ID j a) 的成员证明。如果车辆能够使用成员证明重建根 RT ′ 以使 RT ′ 等于最新块中包含的 Merkle 根，则假名有效。否则，车辆会直接拒绝该消息。

1.2.5 假名撤销

$TA_i$ ：

从 $Ω$ 查询恶意车辆 $V^k_b$ 假名索引的集合
替换所有假名为 “0”，将 $H(''0'')$ 存储在当前区块中相应索引的叶节点中
更新默克尔根、上链
删除该集合并在 $Ω$ 中标记为 “Revoked”

2 安全性证明

2.1 形式化证明

$Proof$ 假设敌手 𝒜 能伪造消息 $\{M ^ j_ a, P ID ^ j_ a, AD _j, W ^ j_ a, σ ^ j_ a, T ^ j_ a\}$ ，给定一个 ECDLP 的实例 $(P,Q = x \cdot P)$ ，由挑战者 𝒞 模拟敌手 𝒜 的查询。

$Setup$ - $Oracle$ : 𝒞 设置 $TAG_j ←Q$ 并将 $Params$ 发给 𝒜 ；
$h_1$ - $Oracle$ : 𝒞 维护形如 $(m_1, τ)$ 的空列表 $L_{h_1}$ 。在收到 𝒜 对消息 $m_1$ 的查询时， 𝒞 检查 $L_{h_1}$ 中是否存在元组 $(m_1, τ)$ 。若存在，返回 $τ = h_1(m_1)$ 给 𝒜 ；否则选取 $τ ∈ \mathbb{Z}_q$ ，将其存储在 $L_{h_1}$ 中，并将 $τ$ 发给 𝒜 ；
$h_2$ - $Oracle$ : 𝒞 维护形如 $(PID ^j_ a ∥ T ^j_ a, τ)$ 的空列表 $L_{h_2}$ 。𝒞 选取 $τ ∈ \mathbb{Z}_q$ ，将其存储在 $L_{h_2}$ 中，并将 $τ = h_2 (PID ^j_ a ∥ T ^j_ a)$ 发给 𝒜 ；
$h_3$ - $Oracle$ : 𝒞 维护形如 $(W ^ j_ a, M ^ j_ a, AD _j, P ID ^ j_ a, T ^ j_ a, τ)$ 的空列表 $L_{h_3}$ 。𝒞 选取 $τ ∈ \mathbb{Z}_q$ ，将其存储在 $L_{h_3}$ 中，并将 $τ = h _3 (W^ j_ a ∥ M^ j_ a ∥ AD_j ∥ P ID ^ j_ a ∥ T ^ j_ a)$ 发给 𝒜 ；
$Sign$ - $Oracle$ : 收到 𝒜 的带有消息 $M^ j_ a$ 的查询后，𝒞 选取 $σ ^ j_ a,α ^ j_ a , β ^ j_ a ∈ \mathbb{Z}^*_q$ , 选取一点 $P ID^j_{a,2}$ ，计算 $P ID^j_{a,1} = σ ^ j_ a \cdot P - α ^ j_ a \cdot T AG_j - β ^ j_ a \cdot W^ j_ a$ 。𝒞 将 $(P ID ^ j_ a, T ^ j_ a, α^ j_ a)$ 和 $(W ^ j_ a, M ^ j_ a, AD_j, P ID ^ j_ a, T ^ j_ a, β ^ j_ a)$ 分别添加进 $L_{h_2}$ 和 $L_{h_3}$ 。最后，𝒞 向 𝒜 发送消息 $\{M ^ j_ a, P ID ^ j_ a, AD _j, W ^ j_ a, σ ^ j_ a, T ^ j_ a\}$ 。由于方程①始终成立，𝒞 模拟生成的签名与认证车辆生成的签名是不可区分的。

2.2 非形式化证明

消息认证：接收消息 $\{M ^ j_ a, P ID ^ j_ a, AD _j, W ^ j_ a, σ ^ j_ a, T ^ j_ a\}$ 后，验证者可先通过区块链检查 $P ID ^ j_ a$ 合法性，再通过验证等式 $σ ^ j_ a \cdot P = PID^j_{a,1} + α^ j_ a \cdot TAG_j$ $+ β ^ j_ a \cdot W ^ j_ a$ 是否成立来检查消息有效性和完整性。
不可链接性：假名 $P ID ^ j_ a$ 由 OBU 选取 $κ ^j_ a$ 秘密生成，敌手无法从假名中推断出车辆的真实身份；车辆能生成多个假名，敌手无法将多个消息或假名与同一车辆关联。
不可伪造性：由于 ECDLP 问题的困难性，且每个新传输消息必须嵌入一个与全局时钟同步的新时间戳，使验证者能检测到签名是否存在伪造。
条件隐私保护：若车辆 $V^j_a$ 被检测为恶意的，一方面
$KGC_j$ 追责：计算 $VID^j_a = PID^j_{a,2} ⊕ h_1(PID^j_{a,1} \cdot Tag_{j}) ⊕ AD_{j}$ 另一方面，由于 CDHP 的困难性，具有 $Tag_{j}$ 和 $P ID ^ j_ a$ 的车辆或 RSU 均无法计算 $PID^j_{a,1} \cdot T_{agj}$ 并推断出 $VID^j_a$ 。
不可否认性：由于签名的不可伪造性，车辆无法否认自己已发送了一条消息；一旦发现不当行为，验证者可在 KGC 帮助下揭示其身份。

3 方案评价

3.1 MACPP 多域认证方案评估

3.1.1 计算开销

结论：

在假名和密钥生成和单条消息验证阶段，MACPP 优于其他方案；
MDPA 在消息签名阶段更有效率，但它不支持对多条签名的批量验证；
当车辆数目达到 200 时，各阶段的计算时间分别为 455.75ms、354.36ms、177.54ms 和 90.05ms；
本文方案批量验证的计算复杂度不受车辆异构性及车辆分布的影响。随车辆数量的增加，MACPP 的表现更佳。

3.1.2 通信开销

结论：
MACPP 的通信开销优于其他方案，其开销为车辆广播的已签名消息，假名和密钥生成与验签阶段均在本地执行，无网络流量。

举例：方案中， $AD_j$ 、 $GD_i$ 、所选随机数和时间戳大小均设置为 4 字节，哈希输出、素数 $p$ 和阶数 $q$ 的大小为 32 字节，群 $G$ 中的元素为 64 字节。设 $S_m$ 为消息大小。则车辆 $V ^j _a$ 需向附近车辆和 RSU 广播 $\{M ^ j_ a, P ID ^ j_ a, AD _j, W ^ j_ a, σ ^ j_ a, T ^ j_ a\}$ ,
其中 $P ID^j_a=\{P ID^j_{a,1},P ID^j_{a,2}\}$ 由 $P ID^j_{a,1}, W^ j_ a ∈ G$ , $\ P ID^j_{a,2}, AD_j, σ^j_a ∈ \mathbb{Z}^*_q$ ， $T ^j_ a$ 为时间戳，方案的通信开销为 $64×2 + 4×4 + S_m = 144 + S_m$ 字节

3.2 BAPM 假名管理方案评估

假名的存储和撤销本质上是对默克尔树叶节点的更新操作，因此分别改变更新操作和假名的数量，观察计算开销与存储开销的变化。
结论：
DSMT 具有比不同叶子大小（ $2^{16}$ 、 $2^{20}$ 和 $2^{24}$ ）的稀疏默克尔树更低的计算开销和存储开销

3.3 区块链性能评估

性能指标：

延迟：对新提交到区块链中的区块达成共识所花费的时间
吞吐量：在区块链网络中每秒提交的有效交易数
结论：
由于在共识过程中耗费的时间增加，更多的对等节点会导致平均延迟增加、吞吐量降低；
平均延迟和吞吐量随发送速率增加呈线性增长，直到验证队列达到容量。