开放科学（资源服务）标志码（OSID）：

0 概述

随着人工智能技术的提高，传统汽车行业与信息技术相结合^[1]促进了无人驾驶领域的发展。无人驾驶车辆通过各种传感器的组合感知周围环境，同时利用人工智能算法对车道及路径进行规划，以控制车辆开往目的地^[2]。无人驾驶方式能够有效地减少交通事故的发生，缓解交通拥堵及管理压力，也可以使行动不方便的老年人和残疾人等弱势群体出行更加便利^[3]。地图是无人驾驶车辆的核心部件，也是车道及路径规划的关键。与传统数字地图不同，无人驾驶车辆地图不仅要求地图信息覆盖精确全面，还要求对地图信息进行快速更新^[4]。由于无人驾驶地图更新需要大量路况数据予以支持，若未及时上传数据或上传错误数据则会导致系统错误。目前，基于卫星图像的数字地图^[5]得到了广泛的应用，它能够保证地图中道路信息的正确性，但是无法做到实时更新^[6]，难以满足无人驾驶车辆对于地图与路况高精度和实时性的要求。路况信息一旦出现错误，则会造成无人驾驶车辆失控，产生严重的后果，而且容易发生单点故障，导致整个地图系统不可用。多方车辆需要共同协作以实时发送路况信息，提高地图的更新效率，从而为无人驾驶车辆提供实时路况更新服务。服务器根据相关路况信息对地图进行更新，但是车辆用户数庞大且来源复杂，无法确保数据来源的安全性及可靠性。

近年来，主流的安全信任管理方案是使用认证来确保数据来源的安全性，通过信任管理确保数据的可靠性。信任管理是指通过对车辆发送的数据进行分析处理，并结合车辆的历史信任值对该消息的可信度进行评估，同时对特定的车辆采取奖励或者惩罚措施，并将相应结果返回给服务器。同时，一些安全性问题也逐渐显现，例如车辆的隐私问题及恶意车辆的攻击。

本文将无证书签名、信任管理、区块链技术引入到无人驾驶车辆的地图中，提出一种信任管理方案用于无人驾驶的地图更新。利用无证书签名实现车辆的匿名认证，保证车辆身份的可验证性及不可否认性，并结合区块链技术和信任管理设计分布式信任管理机制，通过对路况信息数据进行评估，确保数据的可靠性和完整性。

1 相关工作

随着城市智能交通的发展，无人驾驶车辆因其具有低能耗、自动化等特点，成为近年来智能交通系统的研究热点。无人驾驶车辆通过地图更新服务器对从多方接收到的数据进行分析处理，但是地图更新服务器无法确保数据来源的安全性及可靠性。因此，合理的认证算法和信任管理机制的设计成为研究热点。

文献[7]提出一种安全高效的无人驾驶车辆地图更新方案，利用群智感知模型、签密和代理重加密技术对感知数据进行签密，并将加密数据存储在车辆雾节点中，经过云服务平台上传给地图公司。但群智感知模型容易泄露车辆数据及位置隐私，给用户带来较大的安全隐患。

为了保护车辆的隐私并实现认证功能的应用，研究人员提出使用匿名证书进行认证。文献[8]提出一种在城市场景有效的假名证书分发方案。假名证书可以满足隐私保护需求，但是存在证书分发、撤销及存储等问题，使得匿名证书认证方案开销过大，效率降低。文献[9]提出基于群签名的身份认证协议，可以有效地保护车辆的隐私信息，但群管理员权限过大并且车辆需要在群组内频繁更新通信密钥，存在严重的安全隐患问题，并且增加了通信开销。文献[10-11]通过消息认证码使得认证的处理速度更快且效率更高，但是无法实现不可否认性，带来了安全隐患。恶意车辆可以否认其发出的错误消息，存在严重的交通问题。

为解决上述问题，文献[12]提出无证书签名（Certificateless Signature，CLS）。在无证书签名中，密钥生成中心（Key Generation Center，KGC）只生成用户的部分私钥，用户需选择一个秘密值与其部分私钥共同生成独立的私钥，从而确保签名的安全。文献[13]将无证书签名引入到车联网场景，为车联网中的用户提供有条件的隐私，但是该方案不能抵抗恶意KGC的攻击。文献[14]设计一种在计算性Diffie-Hellman问题假设下用于车联网场景的CLS方案，但是该方案不能抵抗恶意KGC攻击。文献[15]提出用于车联网中的CLAS方案，但文献[16]指出CLAS方案存在无法抵抗恶意KGC攻击、追踪性不足等安全性问题。文献[17]提出一种用于车联网的高效和安全的无证书签名基础认证方案，但是该方案不能抵抗公钥替换攻击，给车联网带来极大的安全隐患。

认证可以验证消息发送者的合法性，却无法保证消息内容的可靠性。某些攻击者控制某些节点，使其具备某些恶意行为，例如故意发送虚假消息等。信任模型的建立可以有效解决车辆节点在网络中的恶意行为，减少虚假数据在网络中的传播。传统的集中式信任管理容易引起单点故障，导致系统瘫痪。随着区块链技术的快速发展，研究人员将区块链技术引入到信任管理中，提出基于区块链的分布式信任管理方案。分布式信任管理机制能够打破传统集中式信任管理机制带来的局限性。文献[18]提出一种车联网中的基于区块链的交通事故验证和信任验证机制，使用POE共识算法对交通事故结果进行共识，共识结束后，通过RSU（Road Side Unit）将共识结果广播至相邻区域的车辆，并且存储在区块链的事件将被永久保存以供公众访问。文献[19]提出一种基于区块链的边缘计算可信数据管理方案，可以支持基于矩阵的多通道数据分段和隔离，用于敏感或隐私数据保护，将交易负载存储在区块链上，同时通过智能合约使得受保护的区块链数据和交易的条件访问以及解密查询。文献[20]提出一种基于联盟链的车联网资源共享范例，并提出一种轻量级的信誉证明机制。文献[21]提出一个基于区块链的信任管理系统，车辆对消息发起者进行信任评估，获得其信任值，并定期将信任值上传到附近的RSU。RSU将信誉值打包成块，并将该块添加到区块链上。文献[22]提出一种隐私感知匿名声誉系统，防止车辆公布虚假消息。文献[23]在车辆之间利用区块链技术建立信任，将信任值打包成块，并将PoW共识与PoS共识相结合，将块存储在区块链中。文献[24]设计一个基于区块链的位置隐私保护信任管理模型，构建匿名区域来保证车辆的隐私安全。文献[25]构建一个基于区块链的匿名信誉系统，通过2个区块链能够有效实现证书的匿名性。文献[26]提出一种基于区块链的可信位置隐私保护方案，设计基于狄利克雷分布的信任管理方法，通过区块链更新车辆信任值，以便任何车辆在必要时访问其他车辆的历史信任信息。文献[27]提出一种可扩展的基于区块链的车联网信任管理协议，使用区块链和智能合约给可信车辆注册提供保障，通过DPoW共识算法对车辆传入的数据进行扩展。上述方案均侧重于可信车辆的信任管理，未对车辆进行身份认证，存在非法车辆的恶意攻击及故意上传错误路况信息的问题，并且在区块链中使用的共识机制效率降低，难以满足繁忙的车联网系统的效率需求，容易出现路况信息积压等情况，导致无人驾驶地图无法实时更新。

针对上述问题，本文提出一个用于无人驾驶地图更新的信任管理系统，使用无证书签名保证消息发送者的合法性，并利用基于区块链的信任管理确保消息内容的可靠性以及地图更新的实时性。本文方案能够实现匿名认证和有条件的隐私保护，确保在发生恶意事件后，可以追溯到恶意车辆的真实身份，并将区块链技术与信任管理相结合，确保不可篡改信任的数据，可以有效防止恶意车辆攻击。根据安全性和效率评估，本文方案在车联网中是安全且高效的。

2 预备知识 2.1 椭圆曲线

在有限域$ {F}_{p} $上的椭圆曲线$ E $是一个满足$ {y}^{2}={x}^{3}+Ax+B\ \mathrm{m}\mathrm{o}\mathrm{d}\ p $且包含无穷远点$ O $的有限循环群。其中$ A\mathrm{、}B\in {F}_{p} $，$ 4{a}^{3}+27{b}^{2}\ne 0\ \mathrm{ }\mathrm{m}\mathrm{o}\mathrm{d}\ p $，$ (x, y) $为满足上述条件椭圆曲线$ E $上的点。

2.2 困难问题

椭圆曲线离散对数问题（Elliptic Curve Discrete Logarithm Problem，ECDLP）是给定大素数$ q $，取阶为$ q $的群$ G $和椭圆曲线$ E $，其中$ P $为$ G $的任意一个生成元。已知$ P\mathrm{、}aP\in G $，计算$ a\in {Z}_{q}^{\mathrm{*}} $。

计算性Diffie-Hellman问题（Computational Diffie-Hellman Problem，CDHP）是给定大素数$ q $，取阶为$ q $的群$ G $，$ P $为$ G $的任意一个生成元。任意给定$ a\mathrm{、}b\in {Z}_{q}^{\mathrm{*}} $，已知$ P\mathrm{、}aP\mathrm{、}bP\in G $，计算$ abP\in G $。

2.3 无证书签名方案

本文设计的无证书签名方案参数信息如表 1所示。

本文方案使用的算法主要有以下7个：

1）系统初始化（setup）。可信任中心（Trusted Center，TA）将安全参数$ \lambda $作为输入运行此算法，并输出系统参数$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s} $保存系统主密钥$ s $。

2）假名生成算法。TA使用车辆$ {V}_{i} $的真实身份$ {I}_{\mathrm{I}{\mathrm{D}}_{i}} $作为输入运行此算法，并输出车辆$ {V}_{i} $的假名$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $。

3）部分私钥提取算法。TA使用车辆$ {V}_{i} $假名$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $作为输入运行算法，输出该车辆的部分私钥转换值$ {F}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $及部分公钥$ {D}_{i} $。

4）设置秘密值算法。车辆$ {V}_{i} $选择随机数，并将该数作为其秘密值。

5）设置车辆密钥算法。车辆$ {V}_{i} $执行该算法，并输出其公私钥对$ ({K}_{\mathrm{p}{\mathrm{k}}_{i}}, {K}_{\mathrm{s}{\mathrm{k}}_{i}}) $。

6）签名算法。车辆$ {V}_{i} $执行该算法，使用消息$ {m}_{i}, ({K}_{\mathrm{p}{\mathrm{k}}_{i}}, {K}_{\mathrm{s}{\mathrm{k}}_{i}}), $$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $作为输入并输出消息签名对$ ({m}_{i}, {\delta }_{i}) $。

7）签名验证算法。路边单元RSU执行该算法，使用$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}\mathrm{、}{K}_{\mathrm{p}{\mathrm{k}}_{i}}\mathrm{、}{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}\in {\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}, $将$ {\delta }_{i}, T $作为输入，其中$ T $为当前的时间戳，若签名有效则输出Valid，否则输出Invalid。

2.4 无证书签名的安全模型

本文设计的无证书签名方案主要有以下2种类型：1）类型I，敌手Adv-1为恶意的车辆，它不能获取系统的主密钥，但可以替换合法车辆的公钥；2）类型II，敌手Adv-2为诚实但有好奇心的TA，它不能替换车辆的公钥，但可以自己生成系统参数。

方案的安全性由挑战者$ C $和敌手Adv之间的游戏进行界定。

2.4.1 游戏I

该游戏由挑战者$ {C}_{\mathrm{I}} $和敌手Adv-1进行交互完成，$ {C}_{\mathrm{I}} $维护用户列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $的交互过程分为3个阶段：

1）初始化阶段。挑战者$ {C}_{\mathrm{I}} $输入安全参数$ \lambda $，运行系统初始化算法，生成系统参数params和主密钥$ s $。$ {C}_{\mathrm{I}} $安全保存$ s $，并将params发送给Adv-1。

2）询问阶段。在此阶段，敌手Adv-1在多项式时间内适应性地向挑战者$ {C}_{\mathrm{I}} $进行如下询问：（1）Hash询问，Adv-1输入任何数据，$ {C}_{\mathrm{I}} $将对应的hash值输出给Adv-1；（2）创建用户询问，Adv-1输入一个身份$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $，$ {C}_{\mathrm{I}} $查询$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，检查该用户是否已被创建，若该用户已被创建，则给Adv-1返回$ {K}_{\mathrm{p}{\mathrm{k}}_{i}} $；否则$ {C}_{\mathrm{I}} $运行部分私钥提取算法、设置秘密值算法、设置车辆密钥算法以获得元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，然后将$ {K}_{\mathrm{p}{\mathrm{k}}_{i}} $返回给Adv-1，并将该元组添加到$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中；（3）秘密值询问，Adv-1输入一个身份$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $，$ {C}_{\mathrm{I}} $查询$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，返回相应的秘密值，若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $的公钥已被替换，则终止本次询问；（4）替换公钥询问，Adv-1输入一个身份$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $和一个新的公钥$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\text{'}}=({X}_{i}^{\text{'}}, {D}_{i}^{\text{'}}) $，用$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\text{'}} $替换原本的公钥$ {K}_{\mathrm{p}{\mathrm{k}}_{i}} $，$ {C}_{\mathrm{I}} $记录该替换；（5）部分私钥询问，Adv-1输入一个身份$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $，$ {C}_{\mathrm{I}} $查询$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，返回相应的私钥；（6）签名询问，Adv-1输入一个身份，$ {C}_{\mathrm{I}} $运行签名算法生成消息$ m $的签名$ {\delta }_{i} $，该签名满足$ \mathrm{V}\mathrm{e}\mathrm{r}(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, $ $ {m}_{i}, T, {\delta }_{i})=\mathrm{V}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d} $。

3）伪造阶段。Adv-1输出伪造的消息签名对$ ({I}_{\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, $ $ {m}_{i}^{\mathrm{*}}, {\delta }_{i}^{\mathrm{*}}) $。$ \mathrm{V}\mathrm{e}\mathrm{r}(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {I}_{{}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, T, {\delta }_{i}^{\mathrm{*}})=\mathrm{V}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d} $，Adv-1不能提交关于目标用户$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的部分私钥询问。若同时满足这2个条件，则称Adv-1赢得了此游戏。

2.4.2 游戏II

该游戏由挑战者$ {C}_{\mathrm{I}\mathrm{I}} $和敌手Adv-2进行交互完成的，交互过程主要有3个阶段：1）初始化阶段，挑战者$ {C}_{\mathrm{I}\mathrm{I}} $输入安全参数$ \lambda $，运行系统初始化算法，生成系统参数$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s} $和系统主密钥$ s $，$ {C}_{\mathrm{I}\mathrm{I}} $将$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}, s $发送给Adv-2；

2）询问阶段，在此阶段，敌手Adv-2可自适应性地向$ {C}_{\mathrm{I}\mathrm{I}} $提交Hash询问、创建用户询问、秘密值询问、部分私钥询问、签名询问，询问过程与游戏I一致；3）伪造阶段，Adv-2输出伪造的消息签名对$ ({I}_{\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, {\delta }_{i}^{\mathrm{*}}) $，若同时满足$ \mathrm{V}\mathrm{e}\mathrm{r}(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {I}_{{}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, T, {\delta }_{i}^{\mathrm{*}})=\mathrm{V}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d} $和Adv-2不能提交关于目标用户$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $对消息$ {m}_{i}^{\mathrm{*}} $的签名询问的条件，则称Adv-2赢得了此游戏。

3 系统模型

本文主要研究用于无人驾驶地图更新的信任管理方案。本文方案的系统模型如图 1所示。

车联网中的车辆首先与路边单元RSU相互认证，确认对方合法身份后，RSU接收车辆发送的路况信息并根据车辆的历史信任值及距离远近对路况信息的可信度进行判断。RSU将判断后的正确路况信息发送给地图更新服务器，地图更新服务器结合相关信息实时更新地图，并通过区块链更新相关车辆的信任值。在本文方案中，车辆和RSU都需在可信任中心（Trusted Center，TA）中进行注册。车辆与RSU交互前互相验证，确保双方都是在TA中注册过的合法用户。车辆确认RSU身份后，向RSU发送消息签名，RSU验证签名后，对消息进行处理，分析该消息的可信度，根据可信度对车辆的信任值进行更新，并将最终路况信息发送给地图更新服务器。地图更新服务器通过RSU反馈的路况信息对地图进行实时更新。车辆和RSU的认证算法流程如图 2所示。

本文方案主要由以下4个部分组成：1）TA为可信机构，负责系统初始化、RSU和车辆的注册，本文中的TA是不完全可信的，主要负责系统的建立以及为车辆生成部分私钥，当发生纠纷时，TA可以通过恶意车辆的伪身份恢复出车辆的真实身份；2）地图更新服务器，需要大量的路况数据来实时更新地图，通过RSU上传的相关路况信息，实时更新地图；3）RSU为路边单元，安装在路侧的基础设施，具有良好的存储和计算能力；4）车辆，车联网中的每个车辆都安装一个车载单元（On Board Unit，OBU），OBU具有无线通信能力，允许车辆与RSU通信。

3.1 系统初始化

系统初始化是输入安全参数$ \lambda $，TA运行初始化算法，生成$ q $阶加法循环群，$ P $为$ G $的生成元。TA随机选择系统主私钥$ s\in {Z}_{q}^{\mathrm{*}} $，系统追踪私钥$ {s}^{\text{'}}\in {Z}_{q}^{\mathrm{*}} $，计算$ {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}=sP $作为系统的主公钥，$ {P}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}}={s}^{\text{'}}P $作为追踪公钥，选择哈希函数$ H:{\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\to {Z}_{q}^{\mathrm{*}} $，$ {H}_{1}:G\to {Z}_{q}^{\mathrm{*}} $，$ {H}_{2}:{\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\times {\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\times G\times G\to {Z}_{q}^{\mathrm{*}} $，$ {H}_{3}:{\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\times {\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\times G\times G\times {Z}_{q}^{\mathrm{*}}\times {\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\to {Z}_{q}^{\mathrm{*}} $，则系统的公共参数$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}=(P, q, G, $ $ {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {P}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}}, H, {H}_{1}, {H}_{2}, {H}_{3}) $。TA输出公共参数$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s} $并秘密保存系统主私钥$ s $。

3.2 注册阶段 3.2.1 车辆注册

车辆$ {V}_{i} $的真实身份为$ {I}_{\mathrm{I}{\mathrm{D}}_{i}} $。车辆选择随机数$ {z}_{i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}={z}_{i}P $，$ {J}_{i}={I}_{\mathrm{I}{\mathrm{D}}_{i}}\mathrm{⊕}{z}_{i}{P}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}} $，并向TA发起注册请求，$ \mathrm{r}\mathrm{e}\mathrm{q}=\{{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}, {J}_{i}\} $发送给TA。车辆注册主要分为假名生成和部分私钥生成。假名生成是TA收到车辆发送的请求后，首先计算$ {I}_{\mathrm{I}{\mathrm{D}}_{i}}={J}_{i}\mathrm{⊕}{s}^{\text{'}}{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}} $，$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{\mathrm{i}, 2}}={I}_{\mathrm{I}{\mathrm{D}}_{i}}\mathrm{⊕}{H}_{1}({s}^{\text{'}}{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}, {T}_{i}) $，则车辆的假名为$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}=({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}, {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 2}}, {T}_{i}) $，其中$ {T}_{i} $为证明车辆假名有效的时间戳。部分私钥生成是TA选择随机数$ {d}_{i}\in {\mathrm{Z}}_{q}^{\mathrm{*}} $，计算$ {D}_{i}={d}_{i}P $，$ {h}_{1, i}={H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}) $，$ {h}_{1}^{\text{'}}={H}_{1}\left(s{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}\right) $，$ {F}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={d}_{i}+s{h}_{1, i}-{h}_{1}^{\text{'}} $。TA将$ \mathrm{r}\mathrm{e}\mathrm{t}=\{{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {F}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}\} $返回给车辆$ {V}_{i} $。

3.2.2 RSU注册

RSU-i向TA发送注册请求$ \mathrm{r}\mathrm{e}\mathrm{q}={I}_{\mathrm{I}{\mathrm{D}}_{\mathrm{R}\mathrm{S}{\mathrm{U}}_{i}}} $。TA收到RSU-i发送的请求后，选取随机数$ {w}_{i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {W}_{i}={w}_{i}P $，$ {h}^{″}=H\left({I}_{\mathrm{I}{\mathrm{D}}_{\mathrm{R}\mathrm{S}{\mathrm{U}}_{\mathrm{i}}}}\right) $，$ {\mu }_{i}={w}_{i}+s{h}^{″} $，将$ \mathrm{r}\mathrm{e}\mathrm{t}=({I}_{\mathrm{I}{\mathrm{D}}_{\mathrm{R}\mathrm{S}{\mathrm{U}}_{i}}}, {W}_{i}) $返回给RSU，并将$ ({\mu }_{i}, {T}^{\text{'}}) $上传到区块块链中的RSU注册列表。其中$ {T}^{\text{'}} $为证明RSU注册有效期的时间戳。

3.3 车辆公私钥生成

车辆公私钥生成包括部分私钥验证和秘密值生成。车辆$ {V}_{i} $收到TA的返回值后，计算车辆部分私钥$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}} $，$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}={F}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}+{H}_{1}\left({z}_{i}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}}\right) $，并计算$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}P $，若$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}P={D}_{i}+{h}_{1, i}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}} $，通过验证，车辆生成其秘密值。车辆选择随机数$ {x}_{i} $作为其秘密值，计算$ {X}_{i}={x}_{i}P $，则车辆$ {V}_{i} $的公钥$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}=({X}_{i}, {D}_{i}) $，私钥为$ {K}_{\mathrm{s}{\mathrm{k}}_{i}}=({x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $。

3.4 车辆与RSU通信 3.4.1 车辆签名生成

在车辆与RSU通信前，首先访问区块链RSU注册列表，然后查看其时间戳是否在有效期内，并获得$ {\mu }_{i} $，计算$ {\mu }_{i}P $。若$ {\mu }_{i}P={W}_{i}+{h}^{″}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}} $，则验证通过，确定RSU合法并选择与RSU通信。

车辆选择随机数$ {u}_{i} $，计算$ {U}_{i}={u}_{i}P $，$ {h}_{2, i}={H}_{2}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, $ $ {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}) $，$ {h}_{3, i}={H}_{3}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, {h}_{2, i}, {T}_{i}) $，$ {s}_{i}={u}_{i}+{h}_{2, i}{K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}{x}_{i} $，则车辆关于消息$ {m}_{i} $的签名$ {\delta }_{i}=({U}_{i}, {s}_{i}) $，车辆将$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {m}_{i}, {T}_{i}, {\delta }_{i}) $发送给RSU。

3.4.2 消息签名对验证

RSU接收到车辆$ {V}_{i} $发送的消息签名对后，首先验证时间戳$ {T}_{i} $是否符合当前签名的时效，若时间戳有效，则对签名$ {\delta }_{i} $进行验证；然后计算$ {s}_{i}P $，若$ {s}_{i}P={U}_{i}+{h}_{2, i}({D}_{i}+{h}_{1, i}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}})+{h}_{3, i}{X}_{i} $，则验证通过，RSU接收消息$ {m}_{i} $。

3.5 信任评估

RSU定义车辆接收到的所有消息集合$ \{{M}_{1}, {M}_{2}, \cdots , {M}_{j}\} $，$ {M}_{j} $表示关于事件$ {e}_{j} $的所有消息的集合。车辆发送的消息$ {m}_{i} $中含有关于事件$ e $的相关信息。

RSU接收该车辆发送的消息$ {m}_{i} $，并在区块链中查询该车辆的历史信任值，计算该消息的可信度$ {c}_{i}^{j}={r}_{i}{e}^{-\beta {d}_{i}^{j}} $。RSU评估每一个关于事件$ {e}_{j} $的消息的可信度，构成集合$ {C}_{j}=\{{c}_{1}^{j}, {c}_{2}^{j}, \cdots , {c}_{n}^{j}\} $。

RSU利用贝叶斯推理模型来判断事件$ {e}_{j} $发生的概率$ p({e}_{j}/{C}_{j}) $，如式（1）所示：

$ p\left({e}_{j}/{C}_{j}\right)=\frac{p\left({e}_{j}\right)\times \prod\limits_{i=1}^{N}p\left({c}_{i}^{j}/{e}_{j}\right)}{p\left({e}_{j}\right)\times \prod\limits_{i=1}^{N}p\left({c}_{i}^{j}/{e}_{j}\right)+p\left({\stackrel{-}{e}}_{j}\right)\times \prod\limits_{i=1}^{N}p\left({c}_{i}^{j}/{\stackrel{-}{e}}_{j}\right)} $

(1)

若$ p({e}_{j}/{C}_{j}) $大于预设的阈值，则认为事件$ {e}_{j} $真实发生，并将该信息发送给地图更新服务器，地图更新服务器对相关路况信息进行更新。RSU根据判断结果，对发送消息的车辆进行评分：符合判断消息结果的产生一个正面评分，对不符合判断消息结果的消息产生一个负面评分。

因该消息的发布导致发送者信任值发生变化，变化量$ {{\mathit{\Delta}} }_{i}^{j} $如式（2）所示：

$ {{\mathit{\Delta}} }_{i}^{j}=\frac{{\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}}\times \mathrm{p}\mathrm{o}\mathrm{s}-{\omega }_{\mathrm{n}\mathrm{e}\mathrm{g}}\times \mathrm{n}\mathrm{e}\mathrm{g}}{\mathrm{p}\mathrm{o}\mathrm{s}+\mathrm{n}\mathrm{e}\mathrm{g}} $

(2)

其中：pos和neg分别为正面评分和负面评分的数量。这两类评分的权重由参数$ {\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}}\mathrm{、}{\omega }_{\mathrm{n}\mathrm{e}\mathrm{g}} $决定，如式（3）和式（4）所示：

$ {\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}}=\frac{Y\left(\mathrm{p}\mathrm{o}\mathrm{s}\right)}{Y\left(\mathrm{p}\mathrm{o}\mathrm{s}\right)+Y\left(\mathrm{n}\mathrm{e}\mathrm{g}\right)} $

(3)

$ {\omega }_{\mathrm{n}\mathrm{e}\mathrm{g}}=\frac{Y\left(\mathrm{n}\mathrm{e}\mathrm{g}\right)}{Y\left(\mathrm{p}\mathrm{o}\mathrm{s}\right)+Y\left(\mathrm{n}\mathrm{e}\mathrm{g}\right)} $

(4)

其中：$ Y(\cdot ) $为影响$ {\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}}\mathrm{、}{\omega }_{\mathrm{n}\mathrm{e}\mathrm{g}} $大小的函数。

信任值更新是根据信任值的变化量，对车辆的信任值进行更新，如式（5）所示：

$ {r}_{i}=\frac{1}{\mathrm{\pi }}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{n}({{\mathit{\Delta}} }_{i}^{j}-\theta )+\frac{1}{2} $

(5)

其中：$ \theta $为参数。

根据车辆的信誉值给予相应奖励，如式（6）所示：

$ {p}_{i}=p\times \frac{{r}_{i}}{\sum\limits_{i=1}^{N}{r}_{i}} $

(6)

其中：$ p $为此次信息上传的总奖励。奖励可以用来购买地图更新服务器提供的娱乐服务等。

3.6 信任值上链 3.6.1 矿工节点的选取

由于各个RSU独立承担信任评估工作，因此为保证各RSU保存数据的一致性，需要每隔一段时间采用共识机制来选择一个临时的中心节点，将产生新的区块广播给其他节点。

中心节点的选择是区块链系统中最关键的步骤。中心节点的选择方式主要有工作量证明（Proof-of-Work，PoW）、权益证明（Proof-of-Stake，PoS）、股份授权证明（Delegated Proof-of-Stake，DPoS）和瑞波（Ripple）共识机制。PoW即挖矿技术，通过计算出一个满足规则的随机数，获得本次的记账权。但是挖矿会造成大量的资源浪费，导致达成共识的周期延长。权益证明的基本原理是根据每个节点的所有权占比来决定产生区块的难度，在一定程度上缩短了挖矿时间，但是难以满足车联网中的实时性需求。DPoS的基本原理是将PoS中的记账者换为由指定节点数组成的小圈子，只有在圈子中的节点才能够获得记账权，在一定程度上缩短了达成共识的时间，但整个过程还是依赖于代币，实用性不强。瑞波共识机制是每个节点都会维护一个信任节点列表，并且只接受信任节点列表中节点的投票，可在短时间（秒级）内实现交易认证和确认^[28]，满足车联网中对于车辆信任值更新的实时性要求^[29-31]。

每个节点在达成共识开始时，尽可能多地收集需要共识的交易，并放到“候选集”中。每个节点对其信任节点列表中的“候选集”做一个并集，并对每一个交易进行投票。当各节点交流交易的投票结果达到一定投票比例时，交易会进入到下一轮共识中，未达到投票比例的交易会被丢弃或者进入到下一次共识过程的候选集中。在最终轮次中，所有投票超过80%的交易会被放到Merkle树型的已共识交易集中。

3.6.2 分布式共识

当系统形成交易集后，每个节点开始打包新的区块，并将当前区块号、共识交易集的Merkle树Hash、父区块Hash、当前时间戳和车辆信任值等信息放在一起，以计算一个区块Hash。每个节点将得到的区块Hash广播到其可见的节点，节点接收到它所有可信列表中其他节点广播发送的区块Hash之后，结合自己生成的区块Hash，对每一个区块Hash计算一个比例。如果某个Hash的比例超过80%的阈值，则这个Hash是达成共识后的区块Hash。如果自己的Hash与共识通过的Hash相同，则说明自己打包的区块得到了确认，是新的被共识过的区块，直接存储到本地，并且更新状态。如果自己的Hash与共识通过的Hash不同，则需要向某个区块Hash正确的节点索要新的区块信息，之后存储到本地并且更新当前状态。如果上面没有对某一区块Hash超过设定的阈值，那么重新开始共识过程，直到满足条件。

经过分布式共识，网络中各基站均具有一致的信任数据，从而为每辆车的信任评估提供有力依据。

3.7 激励服务

当车辆享受服务时，车辆向RSU发送请求，RSU转发给服务器，服务器查询其存储在区块链上的信任值和激励值，选择是否为其提供其他服务。

4 安全性分析 4.1 正确性

本文认证算法的正确性可通过以下等式验证：

$ \begin{array}{l}{s}_{i}P=({u}_{i}+{h}_{2, i}{K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}{x}_{i})P=\\ {U}_{i}+{h}_{2, i}({d}_{i}+{s}_{1, \mathrm{i}}^{\mathrm{s}\mathrm{h}})P+{h}_{3, i}{X}_{i}=\\ {U}_{i}+{h}_{2, i}({D}_{i}+{h}_{1, i}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}})+{h}_{3, i}{X}_{i}\end{array} $

(7)

4.2 安全性证明

认证算法的不可伪造性证明如下：

定理1    在随机预言机模型中，若存在一个挑战者$ {C}_{\mathrm{I}} $以$ \varepsilon $的优势攻破ECDLP问题，则存在一个概率多项式时间敌手Adv-1以$ {\varepsilon }^{\text{'}}\le \frac{1}{{p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{i}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}}}\varepsilon $的优势攻破本文方案。其中：$ {p}_{\mathrm{i}\mathrm{c}\mathrm{o}} $为创建用户询问过程中未发生$ {H}_{1} $碰撞的最小概率；$ {p}_{\mathrm{i}\mathrm{q}} $为敌手Adv-1未进行过$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的部分私钥问询$ {K}_{\mathrm{p}\mathrm{s}\mathrm{k}\left({I}_{R\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}\right)} $的概率；$ {p}_{\mathrm{e}\mathrm{q}} $为在伪造阶段中$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $的概率；$ {p}_{\mathrm{v}\mathrm{f}} $为列表$ {L}_{2}\mathrm{、}{L}_{3} $中存在$ {h}_{2, i}^{\mathrm{*}}\mathrm{、}{h}_{3, i}^{\mathrm{*}} $，且输出有效的伪造签名的概率。

证明   设$ {C}_{\mathrm{I}} $是一个椭圆曲线离散对数问题的挑战者，困难问题的输入为$ (G, P, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}=sP) $，其中$ s\in {Z}_{q}^{\mathrm{*}} $，挑战者$ {C}_{\mathrm{I}} $的目标是计算出$ s $。定义敌手Adv-1，在敌手Adv-1与挑战者$ {C}_{\mathrm{I}} $之间建立一个游戏。

1）初始化阶段

挑战者$ {C}_{\mathrm{I}} $建立初始为空的列表$ {L}_{1}\mathrm{、}{L}_{2}\mathrm{、}{L}_{3}\mathrm{、} $$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。$ {C}_{\mathrm{I}} $运行系统建立算法，将系统参数$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}=\{q, G, P, $$ {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {H}_{1}, {H}_{2}, {H}_{3}, H\} $发送给Adv-1。Adv-1选取车辆$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $为目标车辆。

2）询问阶段

询问阶段主要有$ {H}_{1} $询问、$ {H}_{2} $询问、$ {H}_{3} $询问、创建用户查询、秘密值询问、替换公钥询问、部分私钥询问、签名询问。

（1）$ {H}_{1} $询问。当$ {C}_{\mathrm{I}} $接收到Adv-1的哈希$ {H}_{1} $询问$ {H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}) $时，$ {C}_{\mathrm{I}} $查询列表$ {L}_{1} $。若$ {L}_{1} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $，则将$ h{}_{1, i} $返回给Adv-1；否则，$ {C}_{\mathrm{I}} $随机选择$ {h}_{1, i}\in {Z}_{q}^{\mathrm{*}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $上传到列表$ {L}_{1} $中，并将$ h{}_{1, i} $返回给Adv-1。

（2）$ {H}_{2} $询问。当$ {C}_{\mathrm{I}} $收到Adv-1的哈希$ {H}_{2} $询问$ {H}_{2}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}{m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}) $时，$ {C}_{\mathrm{I}} $查询列表$ {L}_{2} $。若$ {L}_{2} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}{m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}) $，则将$ h{}_{2, i} $返回给Adv-1；否则，$ {C}_{\mathrm{I}} $随机选择$ {h}_{2, i}\in {Z}_{q}^{\mathrm{*}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}{m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}) $上传到列表$ {L}_{2} $中，并将$ h{}_{2, i} $返回给Adv-1。

（3）$ {H}_{3} $询问。当$ {C}_{\mathrm{I}} $收到Adv-1的哈希$ {H}_{3} $询问$ {H}_{3}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}{m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T) $时，$ {C}_{\mathrm{I}} $查询列表$ {L}_{3} $。若$ {L}_{3} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}{m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $，则将$ h{}_{3, i} $返回给Adv-1；否则，$ {C}_{\mathrm{I}} $随机选择$ {h}_{3, i}\in {Z}_{q}^{\mathrm{*}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}{m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $上传到列表$ {L}_{3} $中，并将$ h{}_{3, i} $返回给Adv-1。

（4）创建用户查询。当$ {C}_{\mathrm{I}} $收到Adv-1的创建用户询问$ {C}_{\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}}\left({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\right) $时，$ {C}_{\mathrm{I}} $查询列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。若$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中包含$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，则将$ ({X}_{i}, {D}_{i}) $返回给Adv-1；否则，当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $时，$ {C}_{\mathrm{I}} $随机选择$ {x}_{i}\mathrm{、}{K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}} $、$ {h}_{1, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {X}_{i}={x}_{i}P $；当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $时，$ {C}_{\mathrm{I}} $随机选择$ {x}_{i}\mathrm{、}{d}_{i}\mathrm{、}{h}_{1, i}\in $ $ {Z}_{q}^{\mathrm{*}} $，计算$ {X}_{i}={x}_{i}P $，$ {D}_{i}={d}_{i}P $，并令$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}=\perp $。用户查看列表$ {L}_{1} $，若列表中包含$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\mathrm{、}{D}_{i}\mathrm{、}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}}\mathrm{、}{H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}) $并且$ {H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, $$ {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}})\ne {h}_{1, i} $，则终止程序；否则，将$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $上传到列表$ {L}_{1} $，$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, \perp ) $上传到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，并将$ ({X}_{i}, {D}_{i}) $返回给Adv-1。

（5）秘密值询问。当$ {C}_{\mathrm{I}} $收到Adv-1的秘密值询问$ {K}_{\mathrm{s}\mathrm{k}\left(\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}\right)} $时，若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，则终止程序；若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，检查列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。若列表中存在元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，则将秘密值$ {x}_{i} $返回给Adv-1；否则，$ {C}_{\mathrm{I}} $提交$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $的创建用户询问，得到元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，将该元组添加到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中，并将$ {x}_{i} $返回给Adv-1。

（6）替换公钥询问。若Adv-1试图用$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\text{'}}=({X}_{i}^{\text{'}}, {D}_{i}^{\text{'}}) $替换$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}=({X}_{i}, {D}_{i}) $，则$ {C}_{\mathrm{I}} $从列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中寻找元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，令$ {X}_{i}={X}_{i}^{\text{'}} $，$ {D}_{i}={{D}_{i}}^{\mathrm{\text{'}}} $，$ {x}_{i}=\perp $，$ \mathrm{p}\mathrm{s}{\mathrm{k}}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}=\perp $。将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, \perp ，\perp ) $上传到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中。

（7）部分私钥询问。当$ {C}_{\mathrm{I}} $收到Adv-1的部分私钥询问$ {K}_{\mathrm{p}\mathrm{s}\mathrm{k}\left(\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}\right)} $时，若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，则终止程序；若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，检查列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $；若$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, $$ {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，则将$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}} $返回给Adv-1；否则，$ {C}_{\mathrm{I}} $提交$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $的创建用户询问，得元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $。将该元组添加到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中，并将$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}} $返回给Adv-1。

（8）签名询问。当$ {C}_{\mathrm{I}} $接收到Adv-1的签名询问$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}) $时，$ {C}_{\mathrm{I}} $查询列表$ {L}_{1} $和$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $且已经被执行过公钥替换询问时，$ {C}_{\mathrm{I}} $从列表$ {L}_{1} $、$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中获取元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，其中$ {x}_{i}=\perp $，$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}=\perp $。$ {C}_{\mathrm{I}} $随机选择$ {s}_{i}\mathrm{、}{h}_{2, i}\mathrm{、}{h}_{3, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {U}_{i}={s}_{i}-{h}_{2}({D}_{i}+{h}_{1, i}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}})-{h}_{3}{X}_{i} $。$ {C}_{\mathrm{I}} $将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}) $添加到列表$ {L}_{2} $中，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $添加到列表$ {L}_{3} $中，并将签名$ {\delta }_{i}=({U}_{i}, {s}_{i}) $返回给Adv-1。当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $时，$ {C}_{\mathrm{I}} $从列表$ {L}_{1} $和$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中获取元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $和$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，$ {C}_{\mathrm{I}} $随机选择$ {u}_{i}\mathrm{、}{h}_{2, i}\mathrm{、}{h}_{3, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {U}_{i}={u}_{i}P $，$ {s}_{i}={u}_{i}+{h}_{2, i}{K}_{\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}{x}_{i} $，其中$ {H}_{2}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i})= $ $ {h}_{2, i} $，$ {H}_{3}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, {h}_{2, i}, T)={h}_{3, i} $。$ {C}_{\mathrm{I}} $将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}) $添加到列表$ {L}_{2} $中，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $添加到列表$ {L}_{3} $中，并将签名$ {\delta }_{i}=({U}_{i}, {s}_{i}) $返回给Adv-1。

3）伪造阶段

Adv-1停止询问并输出一个关于$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}) $的伪造签名$ {\delta }_{i}^{\mathrm{*}}=({U}_{i}^{\mathrm{*}}, {s}_{i}^{\mathrm{*}}) $。若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，$ {C}_{\mathrm{I}} $终止游戏；若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，$ {C}_{\mathrm{I}} $查询列表$ {L}_{1}\mathrm{、}{L}_{2}\mathrm{、}{L}_{3}\mathrm{、}{L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，并获取元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {{D}_{i}}^{\mathrm{*}}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}^{\mathrm{*}}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\mathrm{*}}, {U}_{i}^{\mathrm{*}}, {h}_{2, i}^{\mathrm{*}}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\mathrm{*}}, $ $ {U}_{i}^{\mathrm{*}}, {h}_{2, i}^{\mathrm{*}}, {T}^{\mathrm{*}}, {h}_{3, i}^{\mathrm{*}}) $及$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {X}_{i}^{\mathrm{*}}, {D}_{i}^{\mathrm{*}}, {x}_{i}^{\mathrm{*}}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}^{\mathrm{*}}) $。若$ {h}_{2, i}^{\mathrm{*}}\mathrm{、}{h}_{3, i}^{\mathrm{*}} $不在列表$ {L}_{2}\mathrm{、}{L}_{3} $中，则$ {C}_{\mathrm{I}} $终止游戏。假设Adv-1伪造成功，则可得$ {s}_{i}^{\mathrm{*}}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}}{K}_{\mathrm{s}{\mathrm{k}}_{i}}^{\mathrm{*}}+{h}_{3, i}^{\mathrm{*}}{x}_{i}^{\mathrm{*}}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}}({d}_{i}+{s}_{1}^{\mathrm{s}\mathrm{h}})+{h}_{3, i}^{\mathrm{*}}{x}_{i}^{\mathrm{*}} $。

根据分叉定理^[32]及上式，可得如下方程组：

$ \left\{\begin{array}{l}{s}_{i}^{\mathrm{*}, 1}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}, 1}({d}_{i}+{s}_{1}^{\mathrm{s}\mathrm{h}})+{h}_{3, i}^{\mathrm{*}, 1}{x}_{i}^{\mathrm{*}}\\ {s}_{i}^{\mathrm{*}, 2}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}, 2}({d}_{i}+{s}_{1}^{\mathrm{s}\mathrm{h}})+{h}_{3, i}^{\mathrm{*}, 2}{x}_{i}^{\mathrm{*}}\\ {s}_{i}^{\mathrm{*}, 3}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}, 3}({d}_{i}+{s}_{1}^{\mathrm{s}\mathrm{h}})+{h}_{3, i}^{\mathrm{*}, 3}{x}_{i}^{\mathrm{*}}\\ {s}_{i}^{\mathrm{*}, 4}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}, 4}({d}_{i}+{s}_{1}^{\mathrm{s}\mathrm{h}})+{h}_{3, i}^{\mathrm{*}, 4}{x}_{i}^{\mathrm{*}}\end{array}\right. $

(8)

根据该方程组可以求解出未知数$ {u}_{i}^{\mathrm{*}}, {d}_{i}, s, {x}_{i}^{\mathrm{*}} $。因此，$ {C}_{\mathrm{I}} $可以解出椭圆曲线离散对数问题的有效解$ s $，从而解决椭圆曲线离散对数问题。

4）伪造成功概率

事件$ {E}_{1} $：在伪造过程中，$ {C}_{\mathrm{I}} $没有终止过游戏1。

事件$ {E}_{2} $：Adv-1成功伪造了$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}) $的签名。

$ {C}_{\mathrm{I}} $成功解决ECDLP问题的优势为$ \varepsilon =\mathrm{P}\mathrm{r}[{E}_{1}\bigcap {E}_{2}]=\mathrm{P}\mathrm{r}\left[{E}_{1}\right]\mathrm{P}\mathrm{r}\left[{E}_{2}\right|{E}_{1}]=\mathrm{P}\mathrm{r}[{E}_{1}]{\varepsilon }^{\text{'}} $，其中$ {\varepsilon }^{\text{'}} $为Adv-1攻破本方案的优势。

根据游戏交互分析可得：在创建用户询问过程中未发生$ {H}_{1} $碰撞的概率至少为$ {p}_{\mathrm{i}\mathrm{c}\mathrm{o}}={\left(1-\frac{q{h}_{1}}{q}\right)}^{{q}_{\mathrm{e}\mathrm{q}}} $；敌手Adv-1没有进行$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的部分私钥问询$ {K}_{\mathrm{p}\mathrm{s}\mathrm{k}\left({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}\right)} $的概率为$ {p}_{\mathrm{i}\mathrm{q}}={\left(1-\frac{1}{{q}_{\mathrm{e}\mathrm{q}}}\right)}^{{q}_{\mathrm{p}\mathrm{p}\mathrm{q}}} $；伪造阶段$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的概率为$ {p}_{\mathrm{e}\mathrm{q}}=\frac{1}{{q}_{\mathrm{e}\mathrm{q}}} $；在列表$ {L}_{2}\mathrm{、}{L}_{3} $中存在$ {h}_{2, i}^{\mathrm{*}}\mathrm{、}{h}_{3, i}^{\mathrm{*}} $，输出有效的伪造签名的概率为$ {p}_{\mathrm{v}\mathrm{f}}=\left(1-\frac{q{h}_{2}}{q}\right)\left(1-\frac{q{h}_{3}}{q}\right) $。

$ {E}_{1} $发生的概率$ \mathrm{P}\mathrm{r}\left[{E}_{1}\right]\ge {p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{i}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}} $。则$ {C}_{\mathrm{I}} $成功解决ECDLP问题的优势$ \varepsilon =\mathrm{P}\mathrm{r}[{E}_{1}\bigcap {E}_{2}]=\mathrm{P}\mathrm{r}\left[{E}_{1}\right]\mathrm{P}\mathrm{r}\left[{E}_{2}\right|{E}_{1}]\ge {p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{i}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}}{\varepsilon }^{\text{'}} $。

因此，若$ {C}_{\mathrm{I}} $能够以$ \varepsilon $的优势解决ECDLP问题，则敌手以$ {\varepsilon }^{\text{'}}\le \frac{1}{{p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{i}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}}}\varepsilon $的优势攻破本文方案。

因为敌手Adv-1攻破本文方案的优势可忽略，所以本文方案能够抵抗类型I攻击者。

定理2    在随机预言机模型下，若存在一个挑战者$ {C}_{\mathrm{I}\mathrm{I}} $以$ \varepsilon $的优势攻破ECDLP问题，则存在一个概率多项式时间敌手Adv-2可以以$ {\varepsilon }^{\text{'}}\le \frac{1}{{p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{r}\mathrm{p}}{p}_{\mathrm{s}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}}}\varepsilon $的优势攻破本文方案。其中：$ {p}_{\mathrm{i}\mathrm{c}\mathrm{o}} $为创建用户在询问过程中未发生$ {H}_{1} $碰撞的最小概率；$ {p}_{\mathrm{r}\mathrm{p}} $为敌手Adv-2未进行过$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的部分私钥问询的概率；$ {p}_{\mathrm{s}\mathrm{q}} $为敌手Adv-2未进行过$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的秘密值问询的概率；$ {p}_{\mathrm{e}\mathrm{q}} $为伪造阶段中$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的概率；$ {p}_{\mathrm{v}\mathrm{f}} $为列表$ {L}_{2}\mathrm{、}{L}_{3} $中存在$ {h}_{2, i}^{\mathrm{*}}\mathrm{、}{h}_{3, i}^{\mathrm{*}} $且输出有效的伪造签名的概率。

证明   设$ {C}_{\mathrm{I}\mathrm{I}} $是一个椭圆曲线离散对数问题的挑战者，困难问题的输入为$ G, P, Q=xP $，其中$ x\in {Z}_{q}^{\mathrm{*}} $，挑战者$ {C}_{\mathrm{I}\mathrm{I}} $的目标是计算$ x $。本文定义敌手Adv-2，在敌手Adv-2与挑战者$ {C}_{\mathrm{I}\mathrm{I}} $之间建立一个游戏，两者的交互主要有4个阶段。

1）初始化阶段

挑战者$ {C}_{\mathrm{I}\mathrm{I}} $建立初始为空的列表$ {L}_{1}, {L}_{2}, {L}_{3}, {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。$ {C}_{\mathrm{I}\mathrm{I}} $运行系统建立算法，将系统参数$ \mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}=\{q, G, P, $ $ {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {H}_{1}, {H}_{2}, {H}_{3}, H\} $和系统主密钥$ s $发送给Adv-2。Adv-2选取车辆$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $作为目标车辆。

2）询问阶段

询问阶段主要有$ {H}_{1} $询问、$ {H}_{2} $询问、$ {H}_{3} $询问、创建用户查询、秘密值询问、替换公钥询问、部分私钥询问、签名询问。

（1）$ {H}_{1} $询问。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的哈希$ {H}_{1} $询问$ {H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}) $时，$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{1} $。若$ {L}_{1} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $，则将$ h{}_{1, i} $返回给Adv-2；否则，$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {h}_{1, i}\in {Z}_{q}^{\mathrm{*}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $上传到列表$ {L}_{1} $中，并将$ h{}_{1, i} $返回给Adv-2。

（2）$ {H}_{2} $询问。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的哈希$ {H}_{2} $询问$ {H}_{2}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}) $时，$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{2} $。若$ {L}_{2} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}) $，则将$ h{}_{2, i} $返回给Adv-2；否则，$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {h}_{2, i}\in {Z}_{q}^{\mathrm{*}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}) $上传到列表$ {L}_{2} $中，并将$ h{}_{2, i} $返回给Adv-2。

（3）$ {H}_{3} $询问。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的哈希$ {H}_{3} $询问$ {H}_{3}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T) $时，$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{3} $。若$ {L}_{3} $中存在$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $，则将$ h{}_{3, i} $返回给Adv-2；否则，$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {h}_{3, i}\in {Z}_{q}^{\mathrm{*}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, $ $ {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $上传到列表$ {L}_{3} $中，并将$ h{}_{3, i} $返回给Adv-2。

（4）创建用户查询。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的创建用户询问$ {C}_{\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}}\left({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\right) $时，$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。若$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $包含$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，则将$ ({X}_{i}, {D}_{i}) $返回给Adv-2；否则，当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $时，$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {x}_{i}\mathrm{、}{d}_{i}\mathrm{、}{h}_{1, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {X}_{i}={x}_{i}P $，$ {D}_{i}={d}_{i}P $，$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}={s}_{1, \mathrm{i}}^{\mathrm{s}\mathrm{h}}+{d}_{i} $；当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $时，$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {d}_{i}\mathrm{、}{h}_{1, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}={s}_{1, \mathrm{i}}^{\mathrm{s}\mathrm{h}}+{d}_{i} $，$ {D}_{i}={d}_{i}P $并令$ {X}_{i}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $，$ {x}_{i}=\perp $。$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{1} $，若列表中包含$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, $ $ {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}})) $且$ {H}_{1}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}})\ne $ $ {h}_{1, i} $，则终止程序；否则，将$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $上传到列表$ {L}_{1} $，将$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, \perp ) $上传到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，并将$ ({X}_{i}, {D}_{i}) $返回给Adv-2。

（5）秘密值询问。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的秘密值询问$ {K}_{\mathrm{s}\mathrm{k}\left({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\right)} $时，$ {C}_{\mathrm{I}\mathrm{I}} $验证Adv-2提交的身份。若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，则终止程序。若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，检查列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，若$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中存在元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，则将秘密值$ {x}_{i} $返回给Adv-2；否则，$ {C}_{\mathrm{I}\mathrm{I}} $提交$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $的创建用户询问，得到元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，将该元组添加到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中，并将$ {x}_{i} $返回给Adv-2。

（6）替换公钥询问。若Adv-2试图用$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\text{'}}=({X}_{i}^{\text{'}}, {D}_{i}^{\text{'}}) $替换$ {K}_{\mathrm{p}{\mathrm{k}}_{i}}=({X}_{i}, {D}_{i}) $，$ {C}_{\mathrm{I}\mathrm{I}} $验证$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $提交的身份。若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，则终止程序；否则$ {C}_{\mathrm{I}\mathrm{I}} $从列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中寻找元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，令$ {X}_{i}={X}_{i}^{\text{'}} $，$ {D}_{i}={{D}_{i}}^{\mathrm{\text{'}}} $，$ {x}_{i}={x}_{i}^{\text{'}} $，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}^{\text{'}}，\perp ) $上传到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中。

（7）部分私钥询问。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的部分私钥询问$ {K}_{\mathrm{p}\mathrm{s}\mathrm{k}\left({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\right)} $时，若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，则终止程序。若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，检查列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，若$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中包含元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，则将$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}} $返回给Adv-2；否则，$ {C}_{\mathrm{I}\mathrm{I}} $提交$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}} $的创建用户询问，得到元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，将该元组添加到列表$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中，并将$ {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}} $返回给Adv-2。

（8）签名询问。当$ {C}_{\mathrm{I}\mathrm{I}} $收到Adv-2的签名询问$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}) $时，$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{1} $和$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $。当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $且已经被执行过公钥替换询问时，$ {C}_{\mathrm{I}\mathrm{I}} $从列表$ {L}_{1} $、$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中获取元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，其中$ {x}_{i}=\perp $。$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {s}_{i}\mathrm{、}{h}_{2, i}\mathrm{、}{h}_{3, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {U}_{i}={s}_{i}-{h}_{2}({D}_{i}+{h}_{1, i}{P}_{\mathrm{p}\mathrm{u}\mathrm{b}})- $ $ {h}_{3}{X}_{i} $。$ {C}_{\mathrm{I}\mathrm{I}} $将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}) $添加到列表$ {L}_{2} $中，将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, h{}_{2, i}, T, {h}_{3, i}) $添加到列表$ {L}_{3} $中，并将签名$ {\delta }_{i}=({U}_{i}, {s}_{i}) $返回给Adv-2。当$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $时，$ {C}_{\mathrm{I}\mathrm{I}} $从列表$ {L}_{1} $、$ {L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $中获取元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {D}_{i}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {X}_{i}, {D}_{i}, {x}_{i}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}) $，$ {C}_{\mathrm{I}\mathrm{I}} $随机选择$ {u}_{i}\mathrm{、}{h}_{2, i}\mathrm{、}{h}_{3, i}\in {Z}_{q}^{\mathrm{*}} $，计算$ {U}_{i}={u}_{i}P $，$ {s}_{i}={u}_{i}+{h}_{2, i}{K}_{\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}{x}_{i} $，其中$ {H}_{2}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i})={h}_{2, i} $，$ {H}_{3}({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, $ $ {h}_{2, i}, T)={h}_{3, i} $。$ {C}_{\mathrm{I}\mathrm{I}} $将元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, {h}_{2, i}) $添加到列表$ {L}_{2} $中，将$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}, {m}_{i}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}, {U}_{i}, {h}_{2, i}, T, {h}_{3, i}) $添加到列表$ {L}_{3} $中，并将签名$ {\delta }_{i}=({U}_{i}, {s}_{i}) $返回给Adv-2。

3）伪造阶段

Adv-2停止询问并输出一个关于$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}) $的伪造签名$ {\delta }_{i}^{\mathrm{*}}=({U}_{i}^{\mathrm{*}}, {s}_{i}^{\mathrm{*}}) $。若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}\ne {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，$ {C}_{\mathrm{I}\mathrm{I}} $终止游戏；若$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $，$ {C}_{\mathrm{I}\mathrm{I}} $查询列表$ {L}_{1}\mathrm{、}{L}_{2}\mathrm{、}{L}_{3}\mathrm{、}{L}_{\mathrm{C}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{r}} $，并获取元组$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {{D}_{i}}^{\mathrm{*}}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {h}_{1, i}^{\mathrm{*}}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\mathrm{*}}, {U}_{i}^{\mathrm{*}}, {h}_{2, i}^{\mathrm{*}}) $、$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}, {K}_{\mathrm{p}{\mathrm{k}}_{i}}^{\mathrm{*}}, $ $ {U}_{i}^{\mathrm{*}}, {h}_{2, i}^{\mathrm{*}}, {T}^{\mathrm{*}}, {h}_{3, i}^{\mathrm{*}}) $及$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {X}_{i}^{\mathrm{*}}, {D}_{i}^{\mathrm{*}}, {x}_{i}^{\mathrm{*}}, {K}_{\mathrm{p}\mathrm{s}{\mathrm{k}}_{i}}^{\mathrm{*}}) $。若$ {h}_{2, i}^{\mathrm{*}}\mathrm{、}{h}_{3, i}^{\mathrm{*}} $不在列表$ {L}_{2}\mathrm{、}{L}_{3} $中，则$ {C}_{\mathrm{I}\mathrm{I}} $终止游戏。假设Adv-2伪造成功，则可得$ {s}_{i}^{\mathrm{*}}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}}{K}_{\mathrm{s}{\mathrm{k}}_{i}}^{\mathrm{*}}+{h}_{3, i}^{\mathrm{*}}{x}_{i}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}}{K}_{\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}^{\mathrm{*}}{x}_{i} $。

根据分叉定理^[32]及上式，可得如下方程组：

$ \left\{\begin{array}{l}{s}_{i}^{\mathrm{*}, 1}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}, 1}{K}_{\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}^{\mathrm{*}, 1}{x}_{i}\\ {s}_{i}^{\mathrm{*}, 2}={u}_{i}^{\mathrm{*}}+{h}_{2, i}^{\mathrm{*}, 2}{K}_{\mathrm{s}{\mathrm{k}}_{i}}+{h}_{3, i}^{\mathrm{*}, 2}{x}_{i}\end{array}\right. $

(9)

根据该方程组可以求解出未知数$ {u}_{i}^{\mathrm{*}}, {x}_{i} $。因此，$ {C}_{\mathrm{I}\mathrm{I}} $可以求解出椭圆曲线离散对数问题的有效解$ {x}_{i} $，从而解决椭圆曲线离散对数问题。

4）伪造成功概率

事件$ {E}_{1} $：在伪造过程中，$ {C}_{\mathrm{I}\mathrm{I}} $没有终止过游戏2。

事件$ {E}_{2} $：Adv-2成功地伪造了$ ({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}, {m}_{i}^{\mathrm{*}}) $的签名。

$ {C}_{\mathrm{I}\mathrm{I}} $成功解决ECDLP问题的优势$ \varepsilon =\mathrm{P}\mathrm{r}[{E}_{1}\bigcap {E}_{2}]= $ $ \mathrm{P}\mathrm{r}\left[{E}_{1}\right]\mathrm{P}\mathrm{r}\left[{E}_{2}\right|{E}_{1}]=\mathrm{P}\mathrm{r}[{E}_{1}]{\varepsilon }^{\text{'}} $，其中$ {\varepsilon }^{\text{'}} $为Adv-2攻破本方案的优势。

根据游戏交互分析可得：在创建用户询问过程中未发生$ {H}_{1} $碰撞的概率至少为$ {p}_{\mathrm{i}\mathrm{c}\mathrm{o}}={\left(1-\frac{q{h}_{1}}{q}\right)}^{{q}_{\mathrm{e}\mathrm{q}}} $；敌手Adv-2没有进行过$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的替换公钥问询的概率为$ {p}_{\mathrm{r}\mathrm{p}}={\left(1-\frac{1}{{q}_{\mathrm{e}\mathrm{q}}}\right)}^{{q}_{\mathrm{r}\mathrm{p}}} $；敌手Adv-2没有进行过$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的秘密值询问$ {K}_{\mathrm{s}\mathrm{k}\left({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}}\right)} $的概率为$ {p}_{\mathrm{s}\mathrm{q}}={\left(1-\frac{1}{{q}_{\mathrm{e}\mathrm{q}}}\right)}^{{q}_{\mathrm{s}\mathrm{q}}} $；伪造阶段$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}={I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}^{\mathrm{*}} $的概率为$ {p}_{\mathrm{e}\mathrm{q}}=\frac{1}{{q}_{\mathrm{e}\mathrm{q}}} $；在列表$ {L}_{2}\mathrm{、}{L}_{3} $中存在$ {h}_{2, i}^{\mathrm{*}}, {h}_{3, i}^{\mathrm{*}} $，输出有效的伪造签名的概率为$ {p}_{\mathrm{v}\mathrm{f}}=\left(1-\frac{q{h}_{2}}{q}\right)\left(1-\frac{q{h}_{3}}{q}\right) $。

$ {E}_{1} $发生的概率$ \mathrm{P}\mathrm{r}\left[{E}_{1}\right]\ge {p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{r}\mathrm{p}}{p}_{\mathrm{s}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}} $，则$ {C}_{\mathrm{I}\mathrm{I}} $成功解决ECDLP问题的优势$ \varepsilon =\mathrm{P}\mathrm{r}[{E}_{1}\bigcap {E}_{2}]=\mathrm{P}\mathrm{r}\left[{E}_{1}\right]\mathrm{P}\mathrm{r}\left[{E}_{2}\right|{E}_{1}]\ge {p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{r}\mathrm{p}}{p}_{\mathrm{s}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}}{\varepsilon }^{\text{'}} $。因此，若$ {C}_{\mathrm{I}\mathrm{I}} $能够结合$ \varepsilon $的优势解决ECDLP问题，则敌手能以$ {\varepsilon }^{\text{'}}\le \frac{1}{{p}_{\mathrm{i}\mathrm{c}\mathrm{o}}{p}_{\mathrm{r}\mathrm{p}}{p}_{\mathrm{s}\mathrm{q}}{p}_{\mathrm{e}\mathrm{q}}{p}_{\mathrm{v}\mathrm{f}}}\varepsilon $的优势攻破本文方案。

由于$ {C}_{\mathrm{I}\mathrm{I}} $攻破ECDLP的优势可忽略，因此敌手Adv-2攻破本文方案的优势可忽略。本文方案能够抵抗类型II攻击者。

4.3 其他安全需求

其他安全需求包括以下6个方面：1）认证性，认证性和完整性可以从定理1和定理2的不可伪造性中证明；2）匿名性，车辆在通信过程中，除了车辆自身和TA，其他实体都无法得知车辆的真实身份，由于本文方案使用车辆假名$ \mathrm{R}\mathrm{I}{\mathrm{D}}_{i} $进行通信，$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i}}=({I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}, {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 2}}, {T}_{i}) $，其中$ {I}_{\mathrm{I}{\mathrm{D}}_{i}}={J}_{i}\mathrm{⊕}{s}^{\text{'}}{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}} $，$ {I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 2}}={I}_{\mathrm{I}{\mathrm{D}}_{i}}\mathrm{⊕}{H}_{1}({s}^{\text{'}}{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}}, {T}_{i}) $，因此可以保护车辆的隐私，使车辆具有匿名性；3）可追踪性，当系统中注册过的车辆发送恶意信息等行为时，可信中心TA可以通过追踪密钥$ {s}^{\text{'}} $恢复车辆的真实身份$ {I}_{\mathrm{I}{\mathrm{D}}_{i}}={J}_{i}\mathrm{⊕}{s}^{\text{'}}{I}_{\mathrm{R}\mathrm{I}{\mathrm{D}}_{i, 1}} $；4）不可抵赖性，因为可信中心TA可以将车辆的真实身份和其假名联系起来，所以车辆无法否认其发过的任何一个消息；5）不可链接性，由于$ {u}_{i} $具有随机性，因此攻击者无法判断消息是否来自同一车辆，以保证车辆与消息之间具有不可链接性；6）抵抗重放攻击，在车辆发送的消息中存在时间戳，保证消息的新鲜度，在RSU与车辆通信前检查时间戳是否过期，以避免重放攻击。

5 仿真分析 5.1 服务功能对比

不同方案的服务功能对比如表 2所示，其中，“√”表示有服务功能，“×”表示无服务功能。由于地图更新需满足高精度和高效性的要求，需要大量的车辆提供路况信息，但车辆的身份和数据的可靠性难以得到保证。因此，本文设计具有匿名认证功能的信任管理方案可以解决该问题。

5.2 开销对比

本文从计算开销、通信开销和信任管理功能等方面对不同方案进行对比。为评估方案效率，本文选取由处理器内存16 GB的AMD Ryzen 7 5800H和Windows组成的硬件平台，通过仿真实验结果对比不同方法的开销。

为验证本文方案的有效性，本文将本文方案与文献[15, 17, 33-36]的方案进行对比。计算开销主要取决于签名算法和验证算法的计算量，通过Hash将计算量映射到点运算，根据双线性配对运算等算法执行的次数统计计算开销。各个运算的时间消耗如表 3所示。

文献[15, 34-36]提出的方案都涉及到了双线性配对运算和Hash映射到点运算，文献[33]的方案中签名算法和验证算法点乘运算次数较多。不同方案的计算开销对比如表 4所示。相比以上文献提出的方案，本文方案的签名开销和验证开销都具有优势。

不同方案的通信开销对比如表 5所示。本文用$ \left|G\right| $表示群$ G $上元素的长度，$ \left|{G}_{T}\right| $表示双线性群$ {G}_{T} $上元素的长度，$ \left|{Z}_{q}^{\mathrm{*}}\right| $表示域$ {Z}_{q}^{\mathrm{*}} $上元素的长度，$ \left|T\right| $表示当前时间戳的大小。从表 5可以看出，与其他方案相比，本文方案的通信开销较少，更能满足地图更新场景的实时性需求。

随着车辆数量的增加，不同算法的运行时间对比如图 3所示。从图 3可以看出，在注册阶段，当车辆个数达到100时，所需的注册时间仅为0.81 s，公私钥生成时间为0.8 s，签名生成时间约为1.5 s，签名验证时间为1.5 s。因此，本文算法具有高效性和较高的稳定性。

在不同函数$ Y(\cdot ) $影响下信任值偏移量的变化趋势如图 4所示。当负面评分占比小于50%时，由$ Y\left(x\right)={x}^{3} $控制的信任值偏移量比$ Y\left(x\right)=x $控制的高，说明当$ Y\left(x\right)={x}^{3} $时，少量的负面评分不会对信任值的偏移量产生较大的影响。因此，本文采用函数$ Y\left(x\right)={x}^{3} $控制信任值偏移量参数$ {\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}}\mathrm{、}{\omega }_{\mathrm{n}\mathrm{e}\mathrm{g}} $，使得信任值偏移量更符合多数车辆的判断结果。

信任值偏移量的变化对信誉值的影响如图 5所示。从图 5可以看出，当车辆发送诚实的消息时，本文方案与文献[37]方案的车辆信誉值增加，当车辆发送虚假消息时，车辆的信誉值下降。本文方案对虚假消息的敏感度高，车辆信誉值下降较快。当车辆继续发送诚实消息时，本文方案恢复速度缓慢，以防止开关攻击。因此，本文方案对车辆的恶意行为具有较高的防骗能力。

本文方案与文献[22-27]方案采用的共识机制、区块链类型、算力需求等方面进行对比，各方案的优缺点如表 6所示。

从表 6可以看出，本文使用Ripple算法作为共识机制，文献[22-23]使用的PoS+PoW算法能够给矿工和持币者两方提供和平共赢的机会，避免数字货币的集中化，但难以避免PoS和PoW带来的资源浪费问题。文献[24-26]使用PoW算法，需要大量的启动节点和算力来维护区块链。文献[27]使用的DPoW算法去中心化程度高，避免拥有算力的组织或者持币大户控制网络，并且能够保证较小的算力需求。而本文使用的Ripple算法，不需要挖矿，所需算力较小，能够满足无人驾驶地图更新的实时性需求。

本文对上述共识算法进行仿真，各共识算法运行时的CPU占用率对比如图 6所示。仿真结果表明，本文所使用的Ripple共识算法具有较小的CPU占用率，效率较高。

6 结束语

针对无人驾驶地图更新中存在的数据来源安全性和可靠性问题，本文提出一种具有认证功能的信任管理方案。利用计算开销和通信开销较少的无证书签名实现匿名认证，保证数据来源的安全性，同时对车辆的身份实现有条件的隐私保护。利用信任管理方案评估消息数据的可信度，确保数据的可靠性。消息数据都认证通过后，将数据发送给地图更新服务器，保证数据的准确性与安全性。仿真结果表明，本文信任管理方案具有较高的更新效率和防骗能力，在计算开销和通信开销方面具有一定的优势。后续将对本文使用的共识算法进行深入研究，为无人驾驶车辆提供更高效安全的地图更新服务。