随着车联网技术的发展及移动设备感知能力的提高，基于车辆位置信息的空间众包^[1]作为一种新兴的服务模式，引起了广泛关注，例如实时打车(Uber)、交通道路监测(Waze)^[2]、地图映射(open street maps)^[3]等.

空间众包以平台为中心的服务器分配任务模式(server assigned tasks)^[4]，通过空间众包服务器收集任务信息和车辆位置信息，执行任务分配. 传统的集中式空间众包服务器^[5]潜在的单点故障、易遭受恶意攻击和不可信等问题，导致任务分配难以可靠、安全地进行. 车辆位置信息隐含了车辆用户的家庭住址、兴趣爱好和生活习惯等敏感信息^[6]. 若攻击者在任务分配时进行攻击，则可能导致大量用户的敏感信息被泄露，严重威胁用户隐私的安全. 任务具有时效性^[7]，为了使请求车辆及时获取更多的信息，需要提高任务的分配效率. 在避免集中式空间众包服务器制约的情况下，如何为车联网空间众包设计具有隐私保护、高效的任务分配方法是影响车联网空间众包发展的关键问题. 本文设计区块链架构下具有隐私保护的车联网空间众包任务分配方法. 基于区块链^[8]实现分布式可信的车联网空间众包系统，采用分布式双陷门公钥密码^[9]，移动边缘服务器和路侧单元利用各自拥有的部分强私钥，对任务位置密文和工人车辆位置密文进行任务分配，实现位置隐私保护. 利用该任务分配方法可以对不同密钥加密的位置密文进行计算，系统不需要在任务分配过程在线为车辆分发密钥.

空间众包的核心是保证任务分配安全、可靠的完成. 当前，针对任务分配的研究工作，一方面利用区块链的特点，设计分布式可信的空间众包任务分配方法. 另一方面，利用泛化、差分隐私和数据加密技术保护位置隐私.

利用区块链实现分布式可信空间众包系统^[10-12]，可以有效地解决空间众包服务器不可信和单点故障带来的问题，因而该系统逐渐成为一种趋势.

Wang等^[13]提出基于区块链的能源生产和交易众包系统，创建智能合约来记录交易，提供能源交易的可靠性. Pinto等^[14]借助区块链为物联网众包，构建去中心化的公钥基础设施，允许节点验证自身与其他网络节点交互的可靠性. Wu等^[15]为众包设计基于区块链的保护隐私任务分配方法，称为BPTM；结合智能合约与可搜索加密，实现身份的匿名性和可靠的任务分配. Zhang等^[12]提出基于区块链的车联网分布式空间众包系统，通过参与车辆多次与区块链交互进行任务分配，虽然工人车辆不需要报告他们的位置，可以自主地选择合适的任务，但可能导致某些任务永远不会被分配，而某些任务被冗余分配. 在车联网空间众包场景中，由于车辆高速移动、计算存储能力低的特点，发布任务至工人车辆完成的过程，存在时延和计算开销过大的问题；因此，如何在分布式可信的车联网空间众包服务中设计高效任务分配方法是一个挑战.

位置隐私保护技术主要包括泛化、差分隐私和数据加密. 泛化^[16]使用空间匿名区域代替精确位置，满足用户隐私的需求. Niu等^[17]提出虚拟位置选择算法，实现用户的K-匿名；提出增强的虚拟位置选择算法，以便扩大、掩蔽区域，但是位置的泛化影响了空间众包任务分配的精确性.

差分隐私技术^[18]在原位置信息中加入噪声. To等^[19-20]基于差分隐私技术，保护工人位置. 在加入噪音保护位置的同时，降低了工人位置的准确性及任务分配的正确性.

数据加密^[21-23]主要是利用同态加密算法将位置隐私信息进行加密，在密文上计算得到任务分配的最后结果. 该方法不牺牲位置的精确性进行任务分配. Shen等^[21]基于加法同态加密和混淆电路实现具有隐私保护的任务分配，但仅保护工人的位置隐私. 攻击者可以根据任务包含的位置，推断出工人的位置. Liu等^[23]利用同态算法加密任务和工人位置，在密文下计算工人位置与任务位置之间的距离. 传统同态加密只能基于同一密钥加密的位置信息进行任务分配，忽略了车辆在空间众包中发布任务或完成任务的不同情况，导致相关位置信息在共享密钥的车辆之间泄露^[24]，不能满足车联网空间众包车辆位置隐私的保护需求.

简单位置编码算法(simple location encoding algorithm，SLE)^[25]能够将位置坐标转换成整数. 该算法主要基于经纬度位置 $ \left( {\rm{{lon,lat}}} \right) $，给定精度 $ {d_i} $进行位置坐标转换. 算法的主要步骤如下.

1）将 ${\rm{lon、lat}}$分别转换至 $ \left[ {0,360} \right] $和 $ \left[ {0,180} \right] $，转换方式是 ${\rm{plon}} = {\rm{lon}} + 180$， ${\rm{plat}} = {\rm{lat}} + 90$.

2）将plon、plat 通过精度 $ {d_i} $处理成2个整数： ${\rm{plon}} = {\rm{plon}} \times {10^{{d_i}}},{\rm{plon}} \in \left[ {0,360 \times {{10}^{{d_i}}}} \right];\,$ ${\rm{plat}} = {\rm{plat}} \times {10^{{d_i}}} $， ${\rm{plat}} \in \left[ {0,180 \times {{10}^{{d_i}}}} \right]$.

3）将这2个整数计算成为1个整数： ${l_i} = {\rm{plon}} \times {10^{\left( {{d_i} + 3} \right)}} + {\rm{plat}}$，其中 $ {l_i} $为表示位置的整数.

分布式双陷门公钥密码(distributed two-trapdoor public-key cryptosystem，DT-PKC)^[9]是同态密码系统，支持在不同密钥生成的密文中作有限次加法、乘法、除法等计算. 算法的主要步骤如下. 在DT-PKC中， $ p $和 $ q $是2个大素数， $ N = pq $， $L\left( x \right) = {{(x - 1)}}/{N}$，强私钥 $ {\rm{SK}} = \lambda $可以用来解密所有的密文，为了防止强私钥泄露导致整个系统的安全崩溃， $ {\rm{SK}} = \lambda $被分为 $ {\rm{S}}{{\rm{K}}^{\left( j \right)}} = {\lambda _j}\left( {j = 1,2} \right) $，将 $ {\lambda _1} $发送给移动边缘服务器， $ {\lambda _2} $发送给路侧单元. 强私钥的解密过程由2部分组成. 加解密过程如下.

1)加密：对于明文 $ m \in {Z_N} $，私钥 ${\rm{sk}} = {\theta _i}$，公钥 $ {\rm{pk}} = \left( {N,g,{h_i}} \right) $，其中 $ h_i = {g^{{\theta _i}}}\bmod {N^2} $. 选择随机数 $ r \in \left[ {1,{N \mathord{\left/ {\vphantom {N 4}} \right. } 4}} \right] $，通过公钥计算 $ {C_{i,1}} = {g^{r{\theta _i}}}\left( {1 + mN} \right)\bmod {N^2} $， $ {C_{i,2}} = {g^r}\bmod {N^2} $，得到密文 $ {\left[ m \right]_{{\rm{pk}}}} = \left\{ {{C_{i,1}},{C_{i,2}}} \right\} $.

2)解密：对于密文 $ {\left[ m \right]_{{\rm{pk}}}} = \left\{ {{C_{i,1}},{C_{i,2}}} \right\} $，移动边缘服务器用 $ {\lambda _1} $进行部分解密，计算过程是 $ {{\rm{CT}}_i}^{\left( 1 \right)} = {\left( {{C_{i,1}}} \right)^{{\lambda _1}}} = {g^{r{\theta _i}{\lambda _1}}}\left( {1 + mN{\lambda _1}} \right)\bmod {N^2} $，该部分解密过程记为 $ {\text{PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{{\left[ m \right]}_{{\rm{pk}}}}} \right) $. 将 $ {\left[ m \right]_{{\rm{pk}}}} $与 $ {\text{PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{{\left[ m \right]}_{{\rm{pk}}}}} \right) $发送到路侧单元，路侧单元用 $ {\lambda _2} $进行解密，计算过程是 ${\rm{C}}{{\rm{T}}_i}^{\left( 2 \right)} = {\left( {{C_{i,1}}} \right)^{{\lambda _2}}} = {g^{r{\theta _i}{\lambda _2}}}\left( {1 + mN{\lambda _2}} \right)\bmod {N^2}$，则明文为 $m = L\left( {{\rm{C}}{{\rm{T}}_i}^{\left( 1 \right)} \cdot {\rm{C}}{{\rm{T}}_i}^{\left( 2 \right)}} \right)$，该部分解密过程记为算法 ${\text{PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{\rm{C}}{{\rm{T}}_i}^{\left( 1 \right)};{{\left[ m \right]}_{{\rm{pk}}}}} \right)$.

DT-PKC满足的同态性质是加法同态性质和乘法同态性质. 加法同态性质为 $ {\left[ {{m_1}} \right]_{{\rm{pk}}}} \cdot {\left[ {{m_2}} \right]_{{\rm{pk}}}} = {\left[ {{m_1} + {m_2}} \right]_{{\rm{pk}}}} $，乘法同态性质为 $ {\left( {{{\left[ m \right]}_{{\rm{pk}}}}} \right)^{N - 1}} = {\left[ { - m} \right]_{{\rm{pk}}}} $.

如图1所示，分布式可信车联网空间众包系统主要包括以下4个实体：可信中心(trusted center，TC)、移动边缘服务器(mobile edge server，MES)、路侧单元(road side unit，RSU)以及车辆. TC负责系统初始化，负责为实体生成密钥，分发密钥. MES是车联网环境下的边缘服务器，可以与其范围内的多个RSU通信，方法中MES作为区块链节点，多个MES形成联盟链. RSU是车联网的基础设施，一般部署在各个路段的路边或交叉路口，具有数据计算处理能力，通过有线信道与MES连接，使用专用短程通信(dedicated short range communication，DSRC)与车辆通信. 方法中车辆既可以是发布任务的请求车辆，也可以是执行任务的工人车辆.

如图1所示，在分布式可信车联网空间众包系统中，包括以下内容. 1）TC为其他实体生成密钥、分发密钥. 2）请求车辆用DT-PKC加密任务位置，通过RSU转发将任务发布至区块链. 3）工人车辆用DT-PKC加密位置并通过其通信范围的RSU，将密文位置信息发布至MES，假设位置信息是真实的. 4）MES获取链上发布的任务，与其通信范围内任一个RSU协作在位置密文上进行任务分配，假设MES和RSU是半可信的，且不会合谋，它们诚实地执行任务，但可能尝试获取位置信息.

在分布式可信的车联网空间众包系统中，任务分配作为空间众包中的关键环节，如何安全、高效地实现是车联网空间众包服务的重要研究内容，任务分配具体需要满足以下2个目标.

1)位置隐私保护. 在任务分配过程中，根据发布的任务位置信息分配合适的工人车辆，车辆位置作为用户的重要隐私信息，不应该被直接暴露使用；因此，车辆位置信息在任务分配过程中不应该被泄露.

2)高效的任务分配. 车联网环境下存在大量具有时效性的任务，需要被高速移动的工人车辆迅速接收完成，快速的任务分配可以最大化任务分配结果，使得工人车辆可以及时地完成请求车辆发布的任务；因此，高效的任务分配方法是感知任务高效执行的前提.

为了实现车联网空间众包具有隐私保护的高效任务分配，设计基于区块链的分布式可信空间众包系统. 采用DT-PKC算法，MES和RSU利用各自拥有的部分强私钥对任务位置策略密文和工人车辆位置密文进行匹配，实现具有隐私保护的任务分配方法. 该任务分配方法可以对不同密钥加密的位置密文进行计算，系统不需要在任务分配过程中在线为车辆分发密钥，减少了车辆的通信开销.

车联网空间的众包流程如图2所示. 提出的方法主要包含以下4个阶段：系统初始化、请求车辆发布任务、工人车辆提交车辆位置，MES和RSU协同进行任务分配. 为了便于说明，表1给出方法主要使用的符号及含义.

在初始化阶段，TC运行算法 $ {\text{Setup}}\left( {{1^k}} \right) $生成系统参数. TC输入安全参数 $ k $，生成系统公共参数. 该算法选择满足 $ \ell \left( p \right) = \ell \left( q \right) = k $的大质数 $ p $和 $ q $. 通过计算 $p' = {{(p - 1)}}/{2}$和 $q' ={{(q - 1)}}/{2}$，得到强质数 $ p' $和 $ q' $. 计算 $ N = pq $和 $ \lambda = {{\left( {{\rm{lcm}}\left( {p - 1,q - 1} \right)} \right)} \mathord{\left/ {\vphantom {{\left( {lcm\left( {p - 1,q - 1} \right)} \right)} 2}} \right. } 2} $（其中lcm表示最小公倍数），随机选择 $ a \in Z_{{N^2}}^ * $，计算 $ g = - {a^{2N}} $得到生成元 $ g $， $ g $的阶是 $ {{\left( {{q_1} - 1} \right)\left( {{q_2} - 1} \right)} \mathord{\left/ {\vphantom {{\left( {{q_1} - 1} \right)\left( {{q_2} - 1} \right)} 2}} \right. } 2} $，定义函数 $L\left( x \right) = {{(x - 1)}}/{N}$.

TC根据车辆 $ i $的注册信息，随机为车辆 $ i $选择 $ {\theta _i} \in \left[ {1,{N \mathord{\left/ {\vphantom {N 4}} \right. } 4}} \right] $，计算 $ {h_i} = {g^{{\theta _i}}}\bmod {N^2} $，为车辆 $ i $分发公钥 $ {{\rm{pk}}_i} = \left( {N,g,{h_i}} \right) $及对应的私钥 $ {{\rm{sk}}_i} = {\theta _i} $.

该系统的强私钥 $ {\rm{SK}} = \lambda $，TC运行算法 ${\text{SkeyS}}$将 $ \lambda $随机分为2部分. 部分强私钥表示为 ${\text{S}}{{\text{K}}^{\left( j \right)}} = {\lambda _j} \left( {j = 1,2} \right)$，必须满足 $ {\lambda _1} + {\lambda _2} \equiv 0\bmod \lambda $和 ${\lambda _1} + {\lambda _2} \equiv 1 \bmod {N^2}$， ${\lambda _1}$分发给MES， ${\lambda _2}$分发至MES通信范围内的RSU.

请求车辆 $ Q $发布空间众包任务前，需要将其中的任务位置坐标转换成整数，表示任务位置. 采用简单位置编码算法(SLE)，对任务位置进行处理. 假设请求任务的位置为 $ \left( {{\rm{lon}},{\rm{lat}}} \right) $，给定精度 $ {d_Q} $，通过 $ {\text{SLE}}\left( {{\rm{lon}},{\rm{lat}}} \right) $得到整数 $ {l_Q} $，用 $ {l_Q} $表示任务位置策略.

为了保护任务位置的机密性，请求车辆 $ Q $选择随机数 $ \alpha \in \left[ {1,{N \mathord{\left/ {\vphantom {N 4}} \right. } 4}} \right] $，通过公钥 $ {{\rm{pk}}_Q} = \left( {N,g,{h_Q}} \right) $加密任务位置，具体计算如下： $ {C_{Q,1}} = {g^{\alpha {\theta _Q}}}\left( {1 + {l_Q}N} \right)\bmod {N^2} $ ， $ {C_{Q,2}} = {g^\alpha }\bmod {N^2} $，得到任务位置密文 $ {\left[ {{l_Q}} \right]_{{{\rm{pk}}_Q}}} = \left\{ {{C_{Q,1}}, } \right. \left. {{C_{Q,2}}} \right\} $. 在得到任务位置密文后，请求车辆 $ Q $随即生成任务T， ${T \text{ = tID}}\parallel {{D}}\parallel {\left[ {{l_Q}} \right]_{{{\rm{pk}}_Q}}}\parallel {{M}}\parallel \left[ {{{{t}}_{\rm{s}}},{{{t}}_{\text{e}}}} \right]$，其中 $ {\text{tID}} $为任务的标识号， ${{D}}$为任务的详细描述， ${{M}}$表示奖励政策， $\left[ {{{{t}}_{\text{s}}},{{{t}}_{\text{e}}}} \right]$为任务答案提交的有效时期. 奖励政策设计应考虑吸引更多的工人车辆参与^[26].

请求车辆 $ Q $发送 ${{T}}$到附近的RSU，RSU将其发送到MES. MES将 ${{T}}$嵌入到事务中，并发布到区块链. 在其他的矿工收到该交易并验证合法性后，在最新的区块中添加该任务.

考虑到车联网的高移动性，车辆每次进入RSU通信范围内将自己的位置加密发送，申请成为工人车辆. 假设工人车辆 $ W $的位置坐标为 $\left( {{\rm{lon}},{\rm{lat}}} \right)$且给定精度 $ {d_W} $，通过 ${\text{SLE}}\left( {{\rm{lon}},{\rm{lat}}} \right)$算法计算得到整数 $ {l_W} $，用 $ {l_W} $表示工人车辆位置. 为了保护工人车辆位置的机密性，工人车辆 $ W $选择随机数 $ \beta \in \left[ {1,{N \mathord{\left/ {\vphantom {N 4}} \right. } 4}} \right] $，通过公钥 ${\rm{p}}{{\rm{k}}_W} = \left( {N,g,{h_W}} \right)$加密位置，计算过程如下： $ {C_{W,1}} = {g^{\beta {\theta _W}}}\left( {1 + {l_W}N} \right)\bmod {N^2} $， $ {C_{W,2}} = {g^\beta }\bmod {N^2} $， 得到密文 ${\left[ {{l_W}} \right]_{{\rm{p}}{{\rm{k}}_W}}} = \left\{ {{C_{W,1}},{C_{W,2}}} \right\}$. 工人车辆 $ W $通过附近RSU向MES提交 ${\text{recor}}{{\text{d}}_W}= {\text{ recI}}{{\text{D}}_W}\parallel {\text{has}}{{\text{h}}_W}\parallel {{{t}}_W}\parallel {\left[ {{l_W}} \right]_{{\rm{p}}{{\rm{k}}_W}}}$，其中 ${{{t}}_W}$为时间戳， ${\text{has}}{{\text{h}}_W}{{ = H}}\left( {{{\left[ {{l_W}} \right]}_{{\rm{p}}{{\rm{k}}_W}}}} \right)$， $ {\text{recI}}{{\text{D}}_W} $为标志号.

MES可以获得通信范围内n个工人车辆提交的位置信息，从链上获取任务 $ {{T}} $后，TC通过请求车辆 $ Q $和n个工人车辆的公钥计算联合公钥 $ {\rm{p}}{{\rm{k}}_\Sigma } $， ${\rm{p}}{{\rm{k}}_\Sigma } = \left( {N,g,{h_\Sigma } = {g^{{\theta _Q} + \Sigma _{W = 1}^n{\theta _W}}}} \right)$，分发给MES和RSU.

为了判断任务位置密文与工人车辆位置密文是否相同，MES持有 ${\lambda _1}$与RSU持有 ${\lambda _2}$共同计算：

$ \begin{split} & {\left[ {{u_1}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\text{SLT}}\left( {{{\left[ {{l_W}} \right]}_{{\rm{p}}{{\rm{k}}_W}}};{{\left[ {{l_Q}} \right]}_{{\rm{p}}{{\rm{k}}_Q}}}} \right) , \\& {\left[ {{u_2}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\text{SLT}}\left( {{{\left[ {{l_Q}} \right]}_{{\rm{p}}{{\rm{k}}_Q}}};{{\left[ {{l_W}} \right]}_{{\rm{p}}{{\rm{k}}_W}}}} \right), \\ & {\left[ {f_1^ * } \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\text{SMD}}\left( {{{\left[ 1 \right]}_{{\rm{p}}{{\rm{k}}_\Sigma }}} \cdot {{\left( {{{\left[ {{u_1}} \right]}_{{\rm{p}}{{\rm{k}}_\Sigma }}}} \right)}^{N - 1}};{{\left[ {{u_2}} \right]}_{{\rm{p}}{{\rm{k}}_\Sigma }}}} \right),\\ & {\left[{f}_{2}^{\ast }\right]}_{{\rm{p}}\rm{k}_{\Sigma }}=\text{SMD}\left({\left[{u}_{1}\right]}_{{\rm{p}}\rm{k}_{\Sigma }}\text{;}{\left[1\right]}_{{\rm{p}}\rm{k}_{\Sigma }}\cdot {\left({\left[{u}_{2}\right]}_{{\rm{p}}\rm{k}_{\Sigma }}\right)}^{N-1}\right) . \end{split}$

算法1显示了多密钥位置密文比较算法SLT,算法2显示了多密钥位置密文相加算法SAD，算法3显示了多密钥位置密文相乘算法SMD.

MES计算并输出 $ {\left[ f \right]_{{{\rm{pk}}_\Sigma }}} $.

$ {\left[ f \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\left[ {{u_1} \oplus {u_2}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\left[ {f_1^ * } \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} \cdot {\left[ {f_2^ * } \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} .$

如果 $ f = 0 $，则说明为请求任务分配到合适的工人车辆；否则，该工人车辆不满足请求任务的位置策略. 合适的工人车辆将对应的任务答案提交至链上，请求车辆从链上获取，完成空间众包服务.

算法1 多密钥位置密文比较（SLT）

1） 输入 ${\left[ x \right]_{{\rm{p}}{{\rm{k}}_a}}}$ ${\left[ y \right]_{{\rm{p}}{{\rm{k}}_b}}}$.

2） 输出 ${\left[ {{u_i}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$.

3）MES计算（参考算法2）：

　　 ${\left[ {{x_1}} \right]_{{\rm{p}}{{\rm{k}}_a}}} = {\left( {{{\left[ x \right]}_{{\rm{p}}{{\rm{k}}_a}}}} \right)^2} \cdot {\left[ 1 \right]_{{\rm{p}}{{\rm{k}}_a}}} = {\left[ {2x + 1} \right]_{{\rm{p}}{{\rm{k}}_a}}},$

　　 ${\left[ {{y_1}} \right]_{{\rm{p}}{{\rm{k}}_b}}} = {\left( {{{\left[ y \right]}_{{\rm{p}}{{\rm{k}}_b}}}} \right)^2} = {\left[ {2y} \right]_{{\rm{p}}{{\rm{k}}_b}}},$

　　 ${\left[ l \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\rm{SAD}}\left( {{{\left[ {{y_1}} \right]}_{{\rm{p}}{{\rm{k}}_b}}};{{\left( {{{\left[ {{x_1}} \right]}_{{\rm{p}}{{\rm{k}}_a}}}} \right)}^{N - 1}}} \right).$

4） MES选择随机数 $ r $，同时满足 $ \ell \left( r \right) < {{\ell \left( N \right)} \mathord{\left/ {\vphantom {{\ell \left( N \right)} 4}} \right. } 4} $，计算 $ {\left[ {{l_1}} \right]_{{{\rm{pk}}_\Sigma }}} = {\left( {{{\left[ l \right]}_{{{\rm{pk}}_\Sigma }}}} \right)^r} $， ${K = \text{ PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{{\left[ {{l_1}} \right]}_{{{\rm{pk}}_\Sigma }}}} \right)$，将K发送给RSU.

5）RSU使用 $ {\lambda _2} $解密 ${{K}}$，得到 $ {l_1} $.

若 $ \ell \left( {{l_1}} \right) > {{\ell \left( N \right)} \mathord{\left/ {\vphantom {{\ell \left( N \right)} 2}} \right. } 2} $，则RSU令 $ u' = 1 $，否则RSU令 $ u' = 0 $. RSU 使用 ${\rm{p}}{{\rm{k}}_\Sigma }$ 加密 $ u' $，将 ${\left[ {u'} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$发送到MES.

6）MES收到 $ {\left[ {u'} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} $后计算：

　　　 ${\left[ {{u_i}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} = {\left[ 1 \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} \cdot {\left( {{{\left[ {u'} \right]}_{{\rm{p}}{{\rm{k}}_\Sigma }}}} \right)^{N - 1}} = {\left[ {1 - u'} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$.

若 $ {u_i} = 0 $，则表明 $ x \geqslant y $；若 $ {u_i} = 1 $，则表明 $ x < y $.

7）结束.

算法2 多密钥位置密文相加（SAD）

1）输入 ${\left[ x \right]_{{\rm{p}}{{\rm{k}}_a}}}$ ${\left[ y \right]_{{\rm{p}}{{\rm{k}}_b}}}$.

2） 输出 ${\left[ {x + y} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$.

3） MES选择2个随机数 $ {r_a}、{r_b} \in {Z_N} $计算：

　　 ${{X = }}{\left[ x \right]_{{\rm{p}}{{\rm{k}}_a}}} \cdot {\left[ {{r_a}} \right]_{{\rm{p}}{{\rm{k}}_a}}} = {\left[ {x + {r_a}} \right]_{{\rm{p}}{{\rm{k}}_a}}}，$

　　 ${{Y = }}{\left[ y \right]_{{\rm{p}}{{\rm{k}}_b}}} \cdot {\left[ {{r_b}} \right]_{{\rm{p}}{{\rm{k}}_b}}} = {\left[ {y + {r_b}} \right]_{{\rm{p}}{{\rm{k}}_b}}} ，$

　　 ${{{X}}^{\prime} =\text{ PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{X}} \right) ，$

　　 ${{{Y}}^{\prime}=\text{ PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{Y}} \right)$.

MES将 ${{{{X}}、{{X}}^{\prime}、{{Y}}、{{Y}}^{\prime}}}$发送给RSU.

4） RSU收到 ${{{{X}}、{{X}}^{\prime}、{{Y}}、{{Y}}^{\prime}}}$后计算：

　　　 ${X^{\prime \prime} \text{= PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{{{{X}}^{\prime};{{X}}}}} \right),$

　　　 ${Y^{\prime \prime}\text{ = PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{{Y^\prime;Y}}} \right),$

　　　 ${{{{S}} = {{X}}^{\prime \prime}}} + {{{{Y}}^{\prime \prime}}}.$

RSU加密 ${{S}}$为 ${\left[ {{S}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$，并将 ${\left[ {{S}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$发送到MES.

5）MES计算 ${{R}} = {r_a} + {r_b}$，加密得到 ${\left[ {{R}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$后，计算 ${\left[ {{S}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}} \cdot {\left( {{{\left[ {{R}} \right]}_{{\rm{p}}{{\rm{k}}_\Sigma }}}} \right)^{N - 1}} = {\left[ {{{S - R}}} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}{{ = }}{\left[ {x + y} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}.$

6）结束.

算法3 多密钥位置密文相乘（SMD）

1）输入 $ {\left[ x \right]_{{\rm{p}}{{\rm{k}}_a}}} $ ${\left[ y \right]_{{\rm{p}}{{\rm{k}}_b}}}$.

2） 输出 ${\left[ {x \cdot y} \right]_{{\rm{p}}{{\rm{k}}_\Sigma }}}$.

3） MES选择4个随机数 $ {r_x}、{r_y}、{R_x}、{R_y} \in {Z_N} $计算：

　　 ${{X = }}{\left[ x \right]_{{\rm{p}}{{\rm{k}}_a}}} \cdot {\left[ {{r_x}} \right]_{{\rm{p}}{{\rm{k}}_a}}} ,$ ${{Y = }}{\left[ y \right]_{{\rm{p}}{{\rm{k}}_b}}} \cdot {\left[ {{r_y}} \right]_{{\rm{p}}{{\rm{k}}_b}}},$

　　 ${{S}} = {\left[ {{R_x}} \right]_{{\rm{p}}{{\rm{k}}_a}}} \cdot {\left( {{{\left[ x \right]}_{{\rm{p}}{{\rm{k}}_a}}}} \right)^{N - {r_y}}} = {\left[ {{R_x} - {r_y} x} \right]_{{\rm{p}}{{\rm{k}}_a}}},$

　　 ${{T}} = {\left[ {{R_y}} \right]_{{\rm{p}}{{\rm{k}}_b}}} \cdot {\left( {{{\left[ y \right]}_{{\rm{p}}{{\rm{k}}_b}}}} \right)^{N - {r_x}}} = {\left[ {{R_y} - {r_x} y} \right]_{{\rm{p}}{{\rm{k}}_b}}} ,$

　　 ${{{X}}_1}{=\text{PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{X}} \right),$ ${{{Y}}_1}{ =\text{ PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{Y}} \right) ,$

　　 ${{{S}}_1}{\text{ = PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{S}} \right)$， ${{{T}}_1}{\text{ = PD}}{{\text{O}}_{{\text{S}}{{\text{K}}^{\left( 1 \right)}}}}\left( {{T}} \right).$

MES将 ${{{X}}_1}、{{{Y}}_1}、{{{S}}_1}、{{{T}}_1}、{{X、Y、S、T}}$发送给RSU.

4）RSU接收 ${{{X}}_1}、{{{Y}}_1}、{{{S}}_1}、{{{T}}_1}、{{X、Y、S、T}}$后计算

　　　 $h = {\text{PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{{{X}}_1}{{;X}}} \right) \cdot {\text{PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{{{Y}}_1}{{;Y}}} \right)$，

　　　 ${{{S}}_2} = {\text{PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{{{S}}_1}{{;S}}} \right),$ ${{{T}}_2} = {\text{PD}}{{\text{T}}_{{\text{S}}{{\text{K}}^{\left( 2 \right)}}}}\left( {{{{T}}_1}{{;T}}} \right)$.

RSU用 ${\rm{p}}{{\rm{k}}_\Sigma }$加密 $h、{{{S}}_2}、{{{T}}_2}$，分别表示为 ${h_1} = {\left[ h \right]_{{{}}{{{{\rm{pk}}}}_\Sigma }}},$ ${{{S}}_3} = {\left[ {{{\text{S}}_2}} \right]_{{}{{{\rm{pk}}}_\Sigma }}},$ ${{{T}}_3} = {\left[ {{{{T}}_2}} \right]_{{}{{{\rm{pk}}}_\Sigma }}}$，将 ${h_1}、{{{S}}_3}、{{{T}}_3}$发送到MES.

5）MES收到 ${h_1}、{{{S}}_3}、{{{T}}_3}$，计算 ${{{S}}_4} = {\left( {{{\left[ {{r_x}\cdot {r_y}} \right]}_{{{}}{{{{\rm{pk}}}}_\Sigma }}}} \right)^{N - 1}}$， ${{{S}}_5} = {\left( {{{\left[ {{R_x}} \right]}_{{{}}{{{{\rm{pk}}}}_\Sigma }}}} \right)^{N - 1}}$ 和 ${{{S}}_6} = {\left( {{{\left[ {{R_y}} \right]}_{{}{{{\rm{pk}}}_\Sigma }}}} \right)^{N - 1}}.$

最后计算：

${h_1} \cdot {T_3} \cdot {S_3} \cdot {S_4} \cdot {S_5} \cdot {S_6}=$

${\left[ { {h + \left( {{R_x} - {r_y} \cdot x} \right) + \left( {{R_y} - {r_x} \cdot y} \right) - {r_x} \cdot {r_y} - {R_x} \cdot {R_y}} } \right]_{{{\rm{pk}}_\Sigma }}}=$

${\left[ {x \cdot y} \right]_{{{\rm{pk}}_\Sigma }}}.$

6）结束.

与传统的集中式空间众包不同，利用区块链发布和获得任务，避免集中式空间众包服务器易遭受恶意攻击、单点故障的问题. 这种分布可信空间众包服务方式具有较好的可扩展性和可靠性. 对于车辆而言，即使某车辆伪造任务信息，这些信息也会被其他MES在共识过程中发现. 位置信息是经过同态加密的密文形式传输，外部敌手即使窃取了数据，也无法进行解密，获取到可用的位置信息. DT-PKC的安全性直接依赖于双陷门加密系统，在DDH困难性假设的前提下^[27]，双陷门加密系统是语义安全的.

MES与RSU基于任务位置与工人位置协作完成任务分配，MES与RSU是半可信实体，它们依据具有隐私保护的车联网空间众包任务分配方法参与协同任务分配工作，但是有兴趣获得车辆的位置信息. 任务位置与工人位置均基于DT-PKC同态加密算法加密成为密文，MES和RSU各自拥有的部分强私钥只能对密文进行部分解密，因而无法得到任务位置与工人位置信息. 在DT-PKC算法中，强私钥拆分的安全性可以通过Shamir秘密共享得到保证，因此保证位置信息在任务分配过程中不被MES与RSU泄露.

实验通过charm-crypto、gmpy2和libnum库的python编程语言，实现提出的方法. 实验设备的配置如下：CPU为Intel Core i5 @ 2.5 GHz，内存为4 GB，操作系统为Ubuntu18.

在车联网，RSU的通信范围半径为500 m^[28]，通信范围内的车辆数量约为100辆^[29]. 实验模拟某个RSU通信范围内的车辆发布任务，进行空间众包任务分配的情况. 假设各任务要求的位置上存在工人车辆，且同一时刻，每辆车仅提交一个任务.

实验在基于数据加密保护隐私的空间众包任务分配方法中，选择3篇包含同态加密的典型方法^{[12, 21-22]}进行比较分析. Zhang等^[12]在车联网空间众包中，使用同态加密、零知识证明和基于圆的位置验证，完成具有隐私保护的任务分配. Shen等^[21] 提出半可信空间众包服务器，利用同态加密和Yao’s两方协议比较任务位置密文和工人位置密文，实现安全的任务分配. Liu等^[22]基于同态加密和ElGamal加密算法实现隐私保护，在任务和工作人员的位置密文中计算距离，进行任务分配. 选取3个评价指标，比较各方法实现空间众包的有效性和效率. 1)任务分配成功率：系统在任务的有效时间内完成任务分配个数与总任务个数的比值. 当RSU通信范围内所有车辆同时提交任务，即总任务个数为100时，将任务的有效时间作为变量，对比各方法的任务分配成功率. 2)整体的计算时间开销指标：将车辆提交任务的数量作为变量，对比各方法从提交任务至完成任务分配需要的时间. 3)任务分配的计算时间开销指标：将车辆提交任务的数量作为变量，对比各方法在任务分配过程中需要的时间.

1)任务分配成功率. 车联网空间众包在不同任务类型的限定时间内收集与地理位置相关的感知数据，完成面向时空约束的群智感知任务. 其中任务类型主要分为安全类任务和非安全类任务. 前者传播实时安全相关信息，最大时延为100 ms^[30]；后者改善车辆用户的驾驶体验，减少道路拥堵，缩短出行时间. 针对各类型任务的有效时间不同，分别对比各方法的任务分配成功率. 如图3(a)所示为各方法在安全类任务有效时间 (100 ms) 内的任务分配成功率R_t，如图3(b)所示为各方法在非安全类任务有效时间(10000 ms) 内的任务分配成功率. 图中，t₁为任务的有效时间. 结果显示，面对不同类型任务的有效时间约束，采用该方法提高了任务分配成功率. 这表明该方法可以不受任务类型的限制，有效地完成任务分配.

如图3所示，各方法的任务分配成功率均随着任务的有效时间增加而提高，特别是在图3(b)中，当任务的有效时间为10000 ms时，该方法、文献[12]方法、文献[22]方法的任务分配成功率均为1. 这是因为在实际的空间众包过程中，任务的有效时间越大，表明寻找合适工人车辆的时间越多，找到合适工人车辆的可能性越高.

如图3(a)所示，当任务的有效时间由50 ms增加至100 ms时，该方法的任务分配成功率由0.52提高至1，文献[12]方法的任务分配成功率由0.33提高至0.67，文献[22]和文献[21]方法的任务分配成功率均低于0.1. 这是因为文献[22]和文献[21]方法均为了保护用户的隐私安全，产生了较大的计算开销；文献[22]方法为了在任务分配过程中保护用户的隐私，多次使用同态加密ElGamal加密算法；文献[21]方法利用Yao’s两方协议ADD与CMP电路，通过电路实现2个整数的加法与比较，对电路计算过程中所有门电路上的计算值进行加密，实现用户的位置隐私保护. 两者均延长了为任务分配合适工人的时间，导致任务分配成功率较低. 该方法的任务分配成功率高于文献[12]方法，原因是该方法利用DT-PKC，可以支持对不同车辆 (密钥) 的密文数据进行任务分配，减少了系统为各个车辆实时更新且分发密钥的计算开销，降低了车辆通信的时间损耗，加快为任务分配合适的工人，提升了任务分配成功率.

2)计算时间开销. 随着密钥位数的增大及任务个数N_t的增多，各方法整体的计算时间t₂如图4所示. 结果显示，面临更多的任务和更大的密钥位数，该方法整体的计算时间开销较低，增长趋势较缓慢，具有优势.

如图4(a)所示，当密钥位数为128位时，随着任务数量由10逐渐增加到100，整体的计算时间由13.38 s增大到133.74 s^[21]，文献[12]方法、文献[22]方法与该方法的计算时间开销均低于14.71 s. 这是因为Shen等^[21]使用传统同态加密算法加密位置隐私信息，在任务分配阶段利用Yao’s两方协议 ADD与CMP电路，通过电路实现两个整数的加法与比较，同时对电路计算过程中所有门电路上的计算值进行加密，开销较大.

如图4(b)所示，当密钥位数为256位时，在任务数量增加至100的情况下，该方法整体的计算时间开销仅为6.02 s，文献[12]、文献[21] 方法和文献[22]方法的整体计算时间开销分别达到39.70、166.07和79.37 s，这是因为文献[12, 21, 22]方法均需要额外生成系统密钥，确保请求车辆和工人车辆的位置信息可以在密文上处理. 该方法在系统初始化时为参与用户分发各自的密钥即可实现密文处理，保护了参与用户位置隐私. 该方法在任务分配阶段，MES、RSU协同进行任务分配，用户只需要加密信息并提交发布，不需要与TC额外交互通信.

如图4(c)所示，当方法密钥位数为512位时，与图4(a)、(b)比较可知，文献[22]方法的整体计算时间开销增长趋势高于文献[21]方法. 因为文献[22]方法多次使用ElGamal加密算法与同态加密算法，导致随着密钥位数的增加，密钥生成，分发的计算时间开销越来越大.

如图5所示为任务分配阶段的计算时间t₃. 可以看出，当面对更多的任务时，本文方法为任务分配合适的工人所需要的时间最短.

如图5(a)所示，文献[21]方法在任务分配阶段的计算时间开销最高，为了实现位置隐私保护的任务分配，该方法利用Yao’s两方协议ADD与CMP电路，对电路计算过程中所有门电路上的计算值进行加密. 如图5(b)所示，为了明显区分该方法与文献[12] 、文献[22]方法在任务分配阶段的计算时间开销. 结果显示，当任务数量为100时，文献[12]方法需要0.15 s，是该方法的1.52倍；文献[22]方法需要1.32 s，是该方法的13.38倍. 该方法通过MES、RSU协同采用DT-PKC的子协议，在保护位置隐私的同时为任务分配合适的工人，与文献[12]方法相比，不会因为请求车辆对工人车辆的不信任，需要与区块链多次交互对工人车辆计算的任务分配结果进行额外的验证. 与文献[22]方法相比，不需要多次同态加密计算，因而该方法避免了由位置隐私保护带来的较大开销.

针对车联网空间众包存在信息安全和隐私泄露的问题，提出区块链架构下具有隐私保护的任务分配方法. 引入区块链技术，削弱空间众包服务器对车辆用户数据的控制；通过DT-PKC在密文的情况下进行任务分配，降低了隐私泄露的可能性. 实验表明，该方法在整体计算时间开销与任务分配计算时间开销方面有优势.

在接下来的研究中，对任务分配的策略进行进一步的研究，在保证任务分配安全、高效的前提下，提高任务分配效益和服务质量.