时控性加密（timed-release encryption，TRE）^[1]作为一种可指定未来解密时间的密码原语，可用于时间敏感性场景^[2-5]。现实生活中的很多场景都需要提前指定解密时间的服务，比如密封投标^[1]、网络竞赛^[2]、密文检索^[6-8]、云端保密数据定时获取^[9-11]等。TRE由May^[12]于1993年提出，并由Rivest等^[1]于1996年对该密码原语进行完善，奠定了TRE的基础^[13]。后续研究者不断提出各种完善TRE和扩展TRE应用领域的方案。

TRE最初的构造方法分为时间锁难题（time-lock puzzles，TLP）^[12,14]和可信代理^[15]两类，后来代理又演变出基于交互式时间服务器^[9,16]和基于非交互式时间服务器^{[2-4,6-7,10-11,17-19]}的方法。其中：TLP方法需要耗费大量算力且解密时间很难做到精确性；基于可信代理的方法中，可信代理知道解密消息的密钥，需要服务器完全可信，这在现实中很难做到；基于交互式时间服务器的方法无上述问题，但无法保护接收者身份隐私；基于非交互式时间服务器的方法可保证用户身份隐私，也是后续大部分具有时间服务器的TRE方案采用的方式。非交互式时间服务器模式由Chan等^[2]于2005年首次提出，在该方案中，时间服务器与收发双方均无交互，以此实现收发双方的匿名性。2008年，Cheon等^[3]将安全TRE公钥密码系统的概念进行形式化，并证明使用基于身份加密（identity-based encryption，IBE）构造的非交互TRE方案都可实现安全TRE。2010年，Paterson等^[4]首次提出一种可将解密时间控制在一个指定时间区间的非交互TRE。2015年，袁科等^[6]将非交互TRE技术用于解决云环境下的文件分享问题。2021年，Huang等^[19]提出一种基于属性和时间参数控制的从云端向用户群共享数据的非交互广义TRE方案。

上述非交互式时间服务器模式中，时间服务器采用周期性地广播时间陷门，以实现时间陷门的分发，因此可保证接收者身份的隐私性。但该方法存在的问题是：1）若时间服务器广播的时间跨度太大，会导致细粒度不够，部分用户的解密时间无法满足；2）若跨度太小，会导致时间服务器负担很大且网络流量大大增加。并且，在问题1）情况下，如果让无对应时间陷门的用户直接交互式地向时间服务器进行查询，又会暴露查询者身份。针对此问题，目前尚无解决方案。因此，亟需设计出一种新的TRE方案，在时间服务器粗粒度广播时间陷门满足大部分用户需求的前提下，实现用户匿名查询任意其他时间的陷门。可提供匿名访问性的洋葱路由（onion routing，OR）技术可为研究者们提供一种解决思路。

洋葱路由通过构造洋葱路由路径来传递信息，路径上的每个路由节点均只能获得上一跳和下一跳的信息，以此保证用户的身份隐私，但存在节点失效的问题。2007年，Kate等^[20]基于配对进行洋葱路由电路的构造，在保持其余节点不变的情况下，通过替换失效节点信息来解决节点失效问题。但该方案在解决节点失效时需重新加密备选节点，耗时较大。目前的洋葱路由方案^[21-22]均存在不能快速解决节点失效的问题。而广播加密（broadcast encryption，BE）^[23]是一种能够实现多个用户可解密的高效加密技术，可为路由节点失效问题提供一种解决思路。

综上，本文提出一种时控性加密匿名查询机制（anonymous query timed-release encryption，AQ-TRE），以解决时控性加密中接收者的身份隐私保护问题，使得接收者能够匿名与时间服务器进行交互获得陷门而不被识别身份。在该方案中，基于洋葱路由和广播加密技术，实现在TRE方案中匿名查询时间陷门的同时，避免洋葱路由节点失效问题的出现。

1 预备知识

对本文所用的数学及密码学知识进行简要说明。

1.1 DLP和ECDLP

有限域上的离散对数问题（discrete logarithm problem，DLP）和有限域椭圆曲线群上的离散对数问题（elliptic curve DLP，ECDLP）是公钥密码学算法和很多密码协议的安全性保证。

定义1 （DLP问题）　假设 $ p $ 和 $ q $ 为两个素数， $ G $ 为阶为 $ p $ 的有限域 $ {\mathbb{Z}}_{q} $ 上的乘法群，其生成元为g。给定一个元素 $ y\in G $ ，求解整数 $ x\in {\mathbb{Z}}_{q}^{*} $ ，使得 $ y={g}^{x} $ 。

定义2（ECDLP问题）　假设 $ p $ 和 $ q $ 为两个素数， $ {G}_{1} $ 为椭圆曲线群的一个 $ p $ 阶加法子群，其生成元为P。给定一个元素 $ Q\in {G}_{1} $ ，求解 $ x\in {\mathbb{Z}}_{q}^{*} $ ，使得 $ Q=xP $ 。

1.2 双线性对

定义3 （双线性对问题）　假设 $ {G}_{1} $ 和 $ {G}_{2} $ 为有限域上的两个 $ p $ 阶群，其中， $ {G}_{1} $ 为椭圆曲线离散对数加法群， $ {G}_{2} $ 为离散对数乘法群， $ p $ 为素数。则双线性映射 $ e:{G}_{1}\times {G}_{2}\to {G}_{2} $ 满足以下性质：

1）双线性。对于所有的 $ P,Q,R\in {G}_{1} $ ，有：

$\begin{aligned}& e\left(P+Q,R\right)=e\left(P,R\right)e\left(Q,R\right),\\ & e\left(P,Q+R\right)=e\left(P,Q\right)e\left(P,R\right) \end{aligned}$

(1)

2）非退化性。如果 $ P $ 为 $ {G}_{1} $ 的生成元，则 $ e\left(P,Q\right) $ 是 $ {G}_{2} $ 的生成元。

3）可计算性。对于 $ {G}_{1} $ 中任意的 $ P $ 和 $ Q $ ，存在一个有效的算法计算 $ e\left(P,Q\right) $ 。

根据以上双线性对的基本性质，可以推导出本方案需要用到的双线性性质：

$ {\;\;\;\;\;\;\;\;\;\;e\left(aP,bQ\right)=e\left(bP,aQ\right)=e{\left(P,Q\right)}^{ab},a,b\in {\mathbb{Z}}_{p}^{*} }$

(2)

1.3 BDH问题

双线性迪菲–赫尔曼（bilinear Diffie–Hellman，BDH）问题在TRE的方案设计中具有重要作用。

定义4（BDH问题）　给定 $ P,aP,bP,cP\in {G}_{1} $ ，其中 $ \left(a,b,c\right)\in {\mathbb{Z}}_{p}^{*} $ ，计算 $ w=e{\left(P,P\right)}^{abc}\in {G}_{2} $ ，其中， $ e $ 为一个双线性映射， $ P $ 为 $ {G}_{1} $ 的生成元，群 $ {G}_{1} $ 和 $ {G}_{2} $ 如定义3所述。

若 $\mathit{\rm Pr}[A\left(P,aP,bP,cP\right)=e{\left(P,P\right)}^{abc}]\ge \varepsilon$ ，则敌手 $ A $ 解决BDH问题的优势为 $\varepsilon$ ，而 $\varepsilon$ 可以忽略不计。

1.4 基于身份的公钥基础设施

在Boneh和Franklin^[24]基于身份的加密初始设置中，可信密钥生成中心（key generation center，KGC）使用用户的已知身份 $ I{D}_{i} $ 为用户生成公私钥对。基本操作包括Setup和Extact两个算法。KGC运行BDH参数生成器来生成两个群和一个双线性对。它选择一个任意生成器，并定义两个杂凑函数 $ {H}_{1}:{\left\{\mathrm{0,1}\right\}}^{*}\to {G}_{1}^{*} $ 和 ${H}_{2}:{G}_{2}\to {\left\{\mathrm{0,1}\right\}}^{n}$ 。

1）Setup即系统初始化。KGC选择一个随机数 $ s $ 并设置 $ {P}_{\text{pub}}=sP $ 。然后，KGC公布系统参数 $params = \{{G}_{1}, $ $ {G}_{2}, q,P,{P}_{\text{pub}},{H}_{1},{H}_{2}\}$ ，并将 $ s $ 作为主密钥保存。

2）Extact即私钥提取。用户向KGC提交其身份信息标志 $ I{D}_{i} $ 。KGC计算 $ {Q}_{ID}={H}_{1}\left(ID\right) $ 作为用户的公钥，并向用户返回其私钥 $ {S}_{ID}=s{Q}_{ID} $ 。

2 基于洋葱路由的时控性加密匿名查询机制

给出基于广播加密和洋葱路由的时控性加密匿名查询模型以及具体方案。

2.1 基于洋葱路由的时控性加密匿名查询模型

该模型的目标是，通过洋葱路由实现用户匿名查询时间陷门，即任一授权用户向时间服务器请求时间陷门，时间服务器向用户返回时间陷门而不能获得用户的具体身份信息。为了解决所选洋葱路由节点失效的问题，本文基于广播加密和洋葱路由技术，给出解决方案。

假设所有用户和时间服务器（time server，TS）均视为洋葱路由网络中的一个节点。路由节点将自己的公钥等节点信息提交给目录服务器（directory server，DS）。在临近指定的解密时间，用户Bob通过洋葱路由匿名向时间服务器发送时间陷门请求，时间服务器接收到陷门请求后，按原路将对应时间的时间陷门 $ {S}_{T} $ 返回给Bob。构造洋葱的具体过程为：Bob通过其洋葱代理（onion proxy，OP）节点从目录服务器DS中选择足够的路由节点，并获得它们的节点信息。OP利用所选节点信息对陷门请求时间T进行层层加密构造形如式（3）～（5）的洋葱（onion），加密顺序与节点在电路中出现的顺序相反。式（3）为最内层陷门请求密文，由时间服务器的公钥 $t{{s}_{\text{pub}}}$ 进行加密。

${C}_{0}'={E}_{t{s}_{\text{pub}}}(T) $

(3)

式（4）为洋葱明文：

$ {O_n} = \langle {( {I{P_{{O_{{\rm{R}}\_n - 1}}}},I{P'_{{O_{{\rm{R}}\_n - 1}}}},I{P''_{{O_{{\rm{R}}\_n - 1}}}}} ),{C'_{n - 1}},{K_{{\rm{b}}\_n}}} \rangle ,n = \{ {3,2,1} \} $

(4)

式中： ${I{P_{{O_{{\rm{R}}\_n - 1}}}} {\text{、}}I{P'_{{O_{{\rm{R}}\_n - 1}}}} {\text{、}}I{P''_{{O_{{\rm{R}}\_n - 1}}}}}$ 为下层节点地址； ${C'_{n - 1}} $ 为下层节点均可解密的洋葱密文； ${K_{{\rm{b}}\_n}}$ 为反向密钥，是一种由用户生成的对称密钥，被各中间节点保存并用于返回时对数据进行层层加密。式（5）为对洋葱明文进行广播加密获得的洋葱密文，每层洋葱路由节点均可对其解密并剥去一层。

$ {{{{C}}}'_{n}}=\left( {U}',{V}' \right)=\left( {r}'P,{{O}_{n}}\oplus H_2 \left( e\left( {{P}_{\text{pub}}},{{{r}}}'{{Q}_{{{v}_{1}}}} \right) \right) \right),n=\left\{ 3,2,1 \right\} $

(5)

在洋葱传递的同时，构建一条从发送者到接收者的路由路径。且每一层洋葱都具有备用洋葱节点以避免节点失效，而用户对于每层洋葱只需要进行一次广播加密，位于该层内的所有节点均可使用自己的私钥进行解密。本文称此种基于洋葱路由的时控性加密匿名查询方案为AQ-TRE系统，如图1所示。

定义5 　交互式AQ-TRE系统包括发送方、接收方用户、时间服务器、目录服务器、密钥生成中心KGC和洋葱路由节点6个实体，以及算法8元组 ${\xi _{{\rm{AQ - TRE}}}} =$ (Setup,BE_KeyGen,User_KeyGen,TRE_Enc,BE_Enc,BE_Dec,TS_Rel,TRE_Dec)。其中8个算法简述如下：

1）Setup即系统初始化。输入安全参数，生成时间服务器的公私钥对 $ \left(t{s}_{\text{pub}},t{s}_{\text{priv}}\right) $ ，并输出通用系统参数。

2）BE_KeyGen即所有路由节点的密钥生成。生成广播加密的主密钥 $ {s}'$ 和各路由节点的公私钥对 $ \left({Q}_{i},{S}_{i}\right) $ 。

3）User_KeyGen即TRE用户密钥生成。生成各用户的公私钥对 $ \left(upk,usk\right) $ 。

4）TRE_Enc即TRE发送方消息加密。使用 $ t{s}_{\text{pub}} $ 和 $ upk $ 生成消息M在时间T后才能解密的密文 $ C $ 。

5）BE_Enc即路由节点广播加密。使用 $ {Q}_{i} $ 、 $ P $ 和 $ {P}_{\text{pub}} $ 等参数，生成所选节点均可解密的洋葱密文 $C'_n$ 。

6）BE_Dec即路由节点解密。使用 $ {S}_{i} $ 等参数，生成密文 $C'_n$ 对应的洋葱明文 $ {O}_{n} $ 。

7）TS_Rel即时间陷门生成和原路返回。使用参数 $ t{s}_{\text{priv}} $ 生成时间T对应的时间陷门 $ {S}_{T} $ 。

8）TRE_Dec即接收方在指定时间解密。使用 $ {S}_{T} $ 和 $ usk $ 等参数，生成密文 $ C $ 所对应的明文 $ M $ 。

2.2 AQ-TRE具体构造方案

AQ-TRE具体的构造方案包括下述8个算法的构造：

1）系统初始化Setup。给定一个安全参数 $ k\in {\mathbb{Z}}^{+} $ ，系统执行系列操作：

① 输入k，生成一个素数 $ p $ 、同为 $ p $ 阶的加法群 $ {G}_{1} $ 和乘法群 $ {G}_{2} $ ，以及一个双线性映射 $ e:{G}_{1}\times {G}_{2}\to {G}_{2} $ 。

② 选择杂凑函数 $ {H}_{1}:{\left\{\mathrm{0,1}\right\}}^{*}\to {G}_{1}^{*} $ ， ${H}_{2}:{G}_{2}\to {\left\{\mathrm{0,1}\right\}}^{l}$ 。其中 $ l $ 为明文长度。明文空间为 $M={\left\{\mathrm{0,1}\right\}}^{{{l}}}$ ，密文空间为 $ C={G}_{1}^{*}\times {\left\{\mathrm{0,1}\right\}}^{*} $ 。随机选择一个生成元 $ P\in {G}_{1}^{*} $ ，其阶为大素数p。时间服务器随机生成一个数 $ s\in {\mathbb{Z}}_{p}^{*} $ 作为其私钥，并公开时间服务器公钥 $ t{s}_{\text{pub}}=sP $ 。

③ 输出系统参数 $params=\{p,{G}_{1},{G}_{2},e,l,P,t{s}_{\text{pub}}, $ $ {H}_{1},{H}_{2}\}$ 。

2）所有路由节点的密钥生成BE_KeyGen。对于任意一个路由节点，KGC执行下列操作：

① 计算节点公钥 $ {Q}_{i}={H}_{1}\left(I{D}_{i}\right)\in {G}_{1}^{*} $ 。

② 设置节点私钥 ${S}_{i}={s}{{'}}{Q}_{i}$ ，其中 ${s}{{'}}\in {\mathbb{Z}}_{p}^{*}$ 为随机选择的主私钥，并设置主公钥 ${P}_{\text{pub}}={s}{{'}}P$ 。

③通过某种安全方式将主公钥和各公私钥对发至相应节点用户。

之后，节点用户将主公钥及其公钥提交给目录服务器。

3）TRE用户密钥生成User_KeyGen。用户生成随机数 $ u\in {\mathbb{Z}}_{p}^{*} $ ，作为该用户私钥 $ usk=u\in {\mathbb{Z}}_{p}^{*} $ ，输入公共参数 $ P $ ，计算出该用户的公钥 $ upk=uP $ 。

4）TRE发送方消息加密TRE_Enc。给定消息M、用户公钥 $ upk=uP $ 、时间服务器公钥 $ t{s}_{\text{pub}}=sP $ 和发布时间 $ T={\left\{\mathrm{0,1}\right\}}^{*} $ ，发送方随机选取 $ r\in {\mathbb{Z}}_{p}^{*} $ ，生成密文 $ C = $ $\left\langle {U,V} \right\rangle = \left\langle {rP,M \oplus {H_2}\left( K \right)} \right\rangle$ ，其中， $ U=rP $ ， $K=e(r{H}_{1}\left(T\right), $ $ uP+sP)=e{\left({H}_{1}\left(T\right),P\right)}^{r\left(u+s\right)}$ 。

5）路由节点广播加密BE_Enc。OP从目录服务器处获取所需的9个节点信息（主公钥、节点公钥、节点IP），并将所选节点分为3组以构造3层的洋葱。每组节点用户组 ${U_{\rm{G}}} = \left( {{u_{{\rm{G}}\_i}}|{u_{{\rm{G}}\_i}}{\rm{ = }}I{D_i},i = 1,2,3} \right)$ ，且每个节点都有一对公私钥 $ \left({Q}_{i},{S}_{i}\right) $ 。其中，每层洋葱的构造均使用BE_Enc加密内层洋葱，以保证每层路由节点都可以进行解密。

在对每层洋葱进行加密时，OP随机选取 ${r}{{'}}\in {\mathbb{Z}}_{p}^{*}$ 并根据该层节点公钥，计算 ${Q}_{{v}_{1}}={\displaystyle\sum\limits_{i=1}^{n}}{Q}_{i}$ ， $ {Q}_{{v}_{2}}={Q}_{1}+{Q}_{2} $ ， $ {Q}_{{v}_{3}}={Q}_{1}+{Q}_{3} $ 及密文 $\left\langle{U}_{i}'(1\le i\le n),{V}{{'}} \right\rangle $ ，其中， $ U_{1}'={r}{{'}}P $ ， $ U_{i}'={r}{{'}}{Q}_{{v}_{i}} $ ， $ 2\le i\le N $ 。该层洋葱明文构造如式（4）所示，对应的洋葱密文如式（5）所示。

6）路由节点解密BE_Dec。节点收到基于广播加密的洋葱后，使用其私钥 $ {S}_{i} $ ，计算

$\begin{aligned}[b] {{O}_{n}}=&{V}'\oplus {{H}_{2}}( e( {{{{U}}}'_{1}},{{S}_{i}} )\cdot e( {{P}_{\text{pub}}},{{{{U}}}'_{2}}+{{{{U}}}'_{3}}-{{{{U}}}'_{i}} ) )= \\ & {V}'\oplus {{H}_{2}}( e( {r}'P,{s}'{{Q}_{i}} )\cdot e( {{P}_{\text{pub}}},{{{{U}}}'_{2}}+{{{{U}}}'_{3}}-{{{{U}}}'_{i}} ) )= \\ & {V}'\oplus {{H}_{2}}( e( {s}'P,{{{r}}}'{{Q}_{i}} )\cdot e( {{P}_{\text{pub}}},{{{{U}}}'_{2}}+{{{{U}}}'_{3}}-{{{{U}}}'_{i}} ) )= \\ & {V}'\oplus {{H}_{2}}( e( {{P}_{\text{pub}}},{{{r}}}'{{Q}_{i}} )\cdot e( {{P}_{\text{pub}}},{{{{U}}}'_{2}}+{{{{U}}}'_{3}}-{{{{U}}}'_{i}} ) )= \\ & {V}'\oplus {{H}_{2}}( e( {{P}_{\text{pub}}},{{{r}}}'( {{Q}_{{{v}_{2}}}}+{{Q}_{{{v}_{3}}}}-{{Q}_{{{v}_{i}}}}+{{Q}_{i}} ) ) )= \\ & {V}'\oplus {{H}_{2}}( e( {{P}_{\text{pub}}},{{{r}}}'( {{Q}_{1}}+{{Q}_{2}}+{{Q}_{1}}+{{Q}_{3}}-\\&( {{Q}_{1}}+{{Q}_{i}} )+{{Q}_{i}} ) ) )\text{=} \\ & {V}'\oplus {{H}_{2}}( e( {{P}_{\text{pub}}},{{{r}}}'( {{Q}_{1}}+{{Q}_{2}}+{{Q}_{1}}+{{Q}_{3}}-\\&{{Q}_{1}}-{{Q}_{i}}+{{Q}_{i}} ) ) )= \\ & {V}'\oplus {{H}_{2}}( e( {{P}_{\text{pub}}},{{{r}}}'( {{Q}_{1}}+{{Q}_{2}}+{{Q}_{3}} ) ) )\text{=} \\ & {V}'\oplus {{H}_{2}}( e( {{P}_{\text{pub}}},{{{r}}}'{{Q}_{{{v}_{1}}}} ) ) \\[-10pt] \end{aligned}$

(6)

依次得到内层洋葱明文 $ {O}_{3} $ 、 $ {O}_{2} $ 、 $ {O}_{1} $ 并获得对应的反向密钥 ${K}_{{\rm{b}}\_2}$ 、 $ {K}_{{\rm{b}}\_1} $ 、 $ {K}_{{\rm{b}}\_0} $ 。本方案使用3层基于广播加密的洋葱，层层解密获得最内层洋葱密文为陷门请求 $ {C}_{0}'={E}_{t{s}_{\text{pub}}}\left(T\right) $ ，之后，将 $ {C}_{0}' $ 发送给时间服务器。

7）时间陷门生成和原路返回TS_Rel。当 $ {C}_{0}' $ 在临近解密时间到达时间服务器（由于接收方是在临近解密时间发起的时间陷门查询）时，时间服务器解密获得请求时间 $ T $ ，同时构造了一条从用户代理到时间服务器的路径，其中每个节点都拥有本节点的上一跳和下一跳的信息。时间服务器根据T生成时间陷门 $ {S}_{T}=s\cdot {H}_{1}\left(T\right) $ ，使用其私钥加密后按照原路返回陷门信息，路径中每个节点使用对应的反向密钥 ${K}_{{\rm{b}}\_n}$ 进行加密并发送给上一跳节点。

8）接收方在指定时间解密TRE_Dec。OP接收到回复洋葱后，使用各层洋葱对应的密钥及时间服务器的公钥进行解密，获得时间陷门 $ {S}_{T} $ 。接收方根据给定的密文 $ C=\left\langle {U,V} \right\rangle $ ，使用其私钥 $ u $ 和时间陷门 $ {S}_{T} $ 计算

$ \begin{aligned}[b] {K^\prime } =& e\left( {U,{S_T} + u{H_1}(T)} \right)=\\ & e\left( {rP,s{H_1}(T) + u{H_1}(T)} \right)=\\ & e\left( {rP,(s + u){H_1}(T)} \right)=\\ & e{\left( {P,{H_1}(T)} \right)^{r(s + u)}}= K \end{aligned} $

(7)

输出明文 $M = V \oplus {H_2}\left( {K'} \right)$ 。

以上为算法的具体设计，需要说明的是，在洋葱传递过程中，洋葱持有者 $U_{{o}_{{\rm{h}}}}$ 通过依次向下层的3个路由节点发送会话请求的方式来确认响应节点；确认后，停止发送会话请求并向该节点发送洋葱密文。其中会话请求由杂凑承诺来实现。确认响应节点的方式为： $U_{{o}_{{\rm{h}}}}$ 向 ${O}_{{\rm{R}}\_n}$ 发送一个随机数 ${r}{''}\in {\mathbb{Z}}^{\mathbb{*}}$ ， ${O}_{{\rm{R}}\_n}$ 接收到 ${r}''$ 则返回 $h=H\left({r}''\right)$ ， $U_{{o}_{{\rm{h}}}}$ 校验 $ h $ 是否等于 $H\left({r}''\right)$ ，若相等则视为响应成功。

3 性能分析 3.1 安全性分析

给出本方案的安全模型。在本文提出的AQ-TRE方案中，假定所选洋葱节点和时间服务器都是“诚实但好奇的”：它们都能按照规则要求履行自己的职责，不会主动地相互勾结，但都试图通过自己所获得的信息，分析并推测查询用户的身份信息。本方案中的其他实体（如目录服务器和KGC），对用户的匿名性无法构成威胁。而恶意攻击者会监听通信信道，企图非法获得用户的身份信息以及破坏通信。

下面针对AQ-TRE方案可能遇到的威胁进行安全性分析，以证明本方案的安全性足以保证用户在保持匿名前提下能够成功进行时间陷门的查询。

定理1 　本方案中所选洋葱路由节点和时间服务器能够推测出查询用户的身份信息的概率是可忽略的。

证明：对于路由节点而言，本方案使用的洋葱路由网络，其中的每个节点都只能知道该节点的上一跳和下一跳路由节点，并按照自己的职责对洋葱进行转发，很难知道整个路由的信息，从而无法得知洋葱的构造者也就是发送者的身份。每个洋葱节点均无法确定本节点在路径中的位置，以及是否为路径中的关键节点（入口节点或出口节点），从而无法接受贿赂。

对于时间服务器而言，由于其接收到的是层层解密后的陷门请求，只能获得传递给自己消息的节点的信息；在返回陷门时，也只能按照原路径发给最后一跳路由节点。与时间服务器交互的只有最后一跳的路由节点，因此其无法推断发送请求的用户身份信息。定理得证。

定理2 　本方案中窃听者根据窃听内容可推测出的信息是可忽略的/可以防止监听攻击。

证明：本方案在洋葱网络内部进行陷门请求消息的传递时，可以防止监听攻击。在请求陷门阶段，窃听攻击者在洋葱路由网络内窃听到的信息只能反映相邻两个洋葱路由器之间的通信，而无法获得整个路径的路由信息。洋葱路由网络内部的数据在进行传输的时候是经过层层加密的，即在网络内部传输的数据至少经过了一次加密（使用时间服务器公钥 $ t{s}_{\text{pub}} $ 进行加密）。攻击者在不知道时间服务器私钥的情况下不可能构造出所请求陷门的时间。在返回陷门阶段，即使在极端情况下，攻击者获得了路径上所有洋葱路由节点的信息，仍无法在没有用户私钥的情况下解密消息。

而在洋葱路由网络之外，窃听攻击者获得的密文是使用ECC加密算法加密过的，要获得其中的密文就意味着他必须要破译ECC加密算法。而对于目前的技术来说，破解ECC加密算法是非常困难的。从而保证了本方案在洋葱路由网络之外亦可以防止监听攻击。定理得证。

定理3 　本方案中路由节点共谋攻击成功的概率是可忽略的。

证明：假设攻击者提前在路由节点中部署大量恶意节点进行共谋攻击。这些恶意节点在未被攻击者启用时依靠真实的身份信息伪装成可信节点，并在被攻击者启用时试图通过互相共享信息以获得所传递的消息或分析出消息来源。本方案中使用的是基于广播加密的洋葱路由路径构造方式，选择节点的方式是随机的。另外，路由节点在收到洋葱之前不知道自己是否为被选取节点。

假设目录服务器中共有m个节点，其中，恶意节点的数量为n，用户需从中选择9个节点来构造洋葱。当用户选择的节点中恶意节点的数量大于或等于3时，攻击者可发动共谋攻击。其成功的概率为：

$ {\;\dfrac{{\rm C}_{m-n}^{6}\cdot {\rm C}_{n}^{3}}{{\rm C}_{m}^{9}}\cdot \dfrac{1}{{\rm C}_{9}^{3}}+\dfrac{{\rm C}_{m-n}^{5}\cdot {\rm C}_{n}^{4}}{{\rm C}_{m}^{9}}\cdot \dfrac{{\rm C}_{4}^{3}}{{\rm C}_{9}^{3}}+\cdots +\dfrac{{\rm C}_{m-n}^{1}\cdot {\rm C}_{n}^{8}}{{\rm C}_{m}^{9}}\cdot \dfrac{{\rm C}_{8}^{3}}{{\rm C}_{9}^{3}}+\dfrac{{\rm C}_{n}^{9}}{{\rm C}_{m}^{9}}。}$

由此可知，如果n值远小于m值，则攻击者攻击成功的概率可以忽略不计。在现实应用中，除非攻击者不计代价地部署恶意节点，否则n远小于m。由此，理智的攻击者不会发起共谋攻击。因此，本方案可抗路由节点共谋。定理得证。

定理4 　本方案可以抵御重放攻击。

证明：在本方案中，每个节点收到洋葱并将其解密后均可获得对应的反向密钥，该反向密钥存在一个有效期，时间到达之前，节点将保存该反向密钥，在收到重放攻击所发送的洋葱时，解密获得相同的反向密钥后将丢弃该洋葱，不予传递。以此来保证基于Tor的TRE陷门请求始终是新鲜的、限时的，可以对抗重放攻击。定理得证。

定理5 　本方案与一般Tor方案相比具有较强的鲁棒性。

证明：本方案的目标是向时间服务器发送请求并及时接受返回陷门以解密消息。若恶意攻击者想要进行暴力攻击，其成功攻击具有时间限制，攻击者需在一定时间内完成破解。若攻击者想要通过恶意破坏某些节点以达到目的，本方案中的广播加密技术可以解决这一问题，即若某一或某些节点被攻击者恶意破坏，本方案可以自动使用备用节点构建路径且无需重新加密。定理得证。

综上所述，本方案可以抵抗单点推测、监听攻击、共谋攻击、重放攻击并具有较强的鲁棒性，安全性足够保证用户在保持匿名的前提下成功地进行时间陷门的查询。

3.2 效率分析

将AQ-TRE方案与现有的解决了节点失效的洋葱路由方案，即Kate等^[20]的基于配对的洋葱路由（pairing-based onion routing，PB-OR）方案，进行解决节点失效的耗时比较。为了对比更直观，列举各方案中的基本操作，并计算其对应耗时。

本文的程序运行环境为：Intel(R) Core(TM) i7-2600 CPU 3.4 GHz处理器，8 GB内存，Microsoft Visual Studio 2010。在此运行环境中，基于MIRACL大数运算库并以987 654 321为随机数种子进行运算。具体地，椭圆曲线采用的是有限域 $ {F}_{q} $ （ $ q $ 为一个512位的大素数）上的超奇异椭圆曲线E： ${y}^{2}={x}^{3}+1{{\rm{mod}}}\;q$ （其素数阶 $ p $ 为一个160位的素数）；双线性映射采用Tate对算法，将上述椭圆曲线离散对数子群映射到 $ {F}_{{q}^{2}} $ 上的离散对数子群（阶数仍为素数 $ p $ ）。运算得出1次 $ G_1 $ 上的点乘运算 $ {\rm{PM}}_{\rm{ec}} $ 的运行时间大约为1.855 2 ms。为使计算结果不与计算机性能相关，以 $ {\rm{PM}}_{\rm{ec}} $ 的耗时为基本比重，计算AQ-TRE和PB-OR方案中相关基本运算相对于 $ {\rm{PM}}_{\rm{ec}} $ 运算的计算成本如表1所示。表1中，BP表示双线性配对运算， $ {\rm{PA}}_{\rm{ec}} $ 表示 $ {G}_{1} $ 上的加减运算， ${\rm{Ex}}{{{\rm{p}}}_{\text{dl}}}$ 表示 $ {G}_{2} $ 上的幂运算， ${\rm{Xor}}$ 表示 ${\text{lb }p }$ 长的比特串异或运算， ${ \rm{Mul}}_{\rm {d1}} $ 表示 $ {G}_2 $ 上的乘法运算， ${\text{Mul}} $ 表示 $\mathbb{Z}_{p}^{*} $ 上的模乘运算， $ {H}_{1} $ 表示将任意长度的二进制字符串映射到 $ {G}_{1} $ ， $ {H}_{2} $ 表示将 $ {G}_{2} $ 元素映射到由0和1组成的 ${\rm{lb}}\;p$ 长度的字符串。

为进行效率对比，假设在PB-OR方案中构造的是3层洋葱路由，且为了达到与本方案同样的效率，因此需要假设每层洋葱均失效两次。失效节点表现为发送消息无反应，不涉及解密操作，由发送者重新选择备用节点并发送。为了更加精确，本文将AQ-TRE方案中的BE_Enc和BE_Dec阶段与PB-OR方案创建电路阶段时的加密和解密阶段进行比较。

在AQ-TRE方案中，假设用户已经选择所需9个节点的信息（主公钥、公钥、IP地址），并将其分为3组，每组节点均使用广播加密进行加密，即BE_Enc阶段，需要进行以下操作：① ${Q_{{v_1}}} = \displaystyle\sum\limits_{i = 1}^n {{Q_i}} ={Q_1} + {Q_2} + {Q_3}$ ， $ {Q}_{{v}_{2}}= $ $ {Q}_{1}+{Q}_{2}$ ， ${Q_{{v_3}}} = {Q}_{1}+{Q}_{3}$ ，共包含4个 $ \rm{ {PA}_{ec}} $ 操作，计算成本为0.028 4；② ${U'_1} = r'P $ ， ${U'_{2}}={r}{{'}}{Q}_{{v}_{2}}$ ， $ {U'_{3}}{{}}={r}{{'}}{Q}_{{v}_{3}} $ ，共包含3个 $\rm{ P{M}_{ec}}$ 操作，计算成本为3；③ $V' = {O_n} \oplus$ ${H}_{2}\left(e\left({P}_{\text{pub}},{r}{{'}}{Q}_{{v}_{1}}\right)\right)$ ，包含1个 $ \rm{ {PM}_{ec}} $ 、1个BP、1个 $ {H}_{2} $ 、1个 ${\rm{Xo{r}}}$ 操作，计算成本为4.444 6；综上，总成本为7.473 0。由于每层洋葱均需要进行一次广播加密，故BE_Enc阶段的计算总成本为7.473 0×3=22.419 0。将构建好的洋葱发送给每层路由节点后，有效节点需要使用自己的私钥进行解密操作 $ {{O}_{n}}={V}'\oplus {{H}_{2}}\left( e\left( {{U}_{1}'},{{S}_{i}} \right) \right.\cdot $ $e\left. \left( {{P}_{\text{pub}}},{{U}_{2}'}+{{U}_{3}'}-{U_{i}'} \right) \right)$ ，共涉及2个BP、2个 $ \rm{ {PA}_{ec}} $ 、1个 $ {H}_{2} $ 、1个 ${\rm{Xo{r}}}$ 、1个 $ \rm{{Mul}_{dl}} $ 操作，故BE_Dec阶段的计算成本为6.833 5×3=20.500 5。因此，AQ-TRE方案解决节点失效的相对耗时共为42.919 5。

对于PB-OR方案，在其加密阶段，假设用户对电路中的路由节点选择完毕，则需对其中每个节点进行以下操作 $ {P}_{Ui}={r}_{i}U $ ， $ {{\gamma }^{ri}_{vi}}=e{\left(U,{Q}_{vi}\right)}^{s{r}_{i}} $ ，其中涉及1个 ${\rm{ P{M}_{ec} }}$ 、1个Mul、1个 ${\rm{Ex{p}_{{\rm{dl}}} }}$ 、1个BP操作，计算成本为4.692 2×3=14.076 6。生成洋葱后发送给路由节点，节点需使用用户假名 $ {r}_{i}U $ 和自己的私钥 $ {d}_{{v}_{i}} $ 计算 $ e\left({r}_{i}U,{d}_{{v}_{i}}\right) $ ，其中涉及1个BP操作3.372 1。对于PB-OR方案的加密阶段，每一个节点失效时，需重新加密该更新节点共1+2+3=6次。故加密阶段每层节点失效两次的计算成本为2×(14.076 6+6×4.692 2)=84.459 6。对于PB-OR方案的解密阶段，每一个节点失效时，重复前面所有的操作即共解密0+1+2=3次。故解密阶段每层节点失效两次的计算成本为2×(3.372 1×3)=20.232 6。因此，PB-OR方案解决节点失效的相对耗时共为104.692 2。

基于表1，对比AQ-TRE和PB-OR方案解决节点失效的计算成本，如表2所示。

由表2可以看出，在上述场景下，AQ-TRE方案与PB-OR方案相比，时间效率提高了约59%。实际上，本方案可以解决每层洋葱失效两个节点的情况，而保持效率不变，同时又具有很好的可扩展性。

另外，为展示本方案中节点个数与节点失效导致的路径失效概率的关系及节点个数与计算复杂度的关系，将本方案中每层选取的节点个数由3个扩展到n个，上述关系如图2所示。

由图2可知，随着每层节点数量的增加，路径的失效概率呈指数下降，而计算复杂度呈线性上升。因此，在使用本方案进行匿名查询时，可根据实际需求对节点数进行适当调整。AQ-TRE方案在n取3且无节点失效的情况下的整体计算成本如表3所示。

4 总结和展望

为了解决用户匿名查询时间陷门的问题，本文提出一种匿名查询方案AQ-TRE。在AQ-TRE方案中，用户通过在洋葱路由网络中构造的路由路径将陷门请求发送至时间服务器，时间服务器接收到请求后按照原路返回时间陷门给用户。该方案的每一个实体均无法获得用户的身份信息，实现了匿名查询。同时，针对洋葱路由可能存在的节点失效问题引入广播加密方法，提高了解决节点失效问题的效率。安全性分析表明，本方案在所提的安全模型下，能够抵抗单点推测、监听攻击、重放攻击以及共谋攻击。基于MIRACL大数运算库，与解决节点失效相关方案进行效率对比实验，结果表明本方案效率更高。同时，将本方案中的每层节点数进行扩展以展示在实际应用中节点数对路径失效概率以及计算复杂度的影响，并给出本方案的整体计算成本。

本文基于洋葱路由设计TRE的匿名查询时间陷门的方案，但目前洋葱路由网络是由因特网用户自愿组成的，可靠性有待提高。因此，在未来的工作中，考虑将区块链中的节点来代替洋葱路由网络中的节点，利用区块链的不可否认性可靠地完成时间陷门的查询。