基于区块链的证书撤销系统的私有状态检索

二、预备阶段

A.区块链

 区块链本质上是一个分布式的仅附加交易账簿，由区块链网络中参与共识的所有节点共同维护。节点负责验证事务并将事务打包到新块中，新块还包含前一块的散列、时间戳和版本信息。在网络中的节点之间达成共识后，每个节点将新块附加到自己的分类账副本中，其中的交易不能伪造或篡改。

B.私人信息检索

 私有信息检索(PIR)[9]允许客户端从不受信任的数据库服务器检索数据库记录，同时对服务器隐藏记录的身份。PIR协议旨在为客户端提供与下载整个数据库相同的机密性。在传统的PIR协议中，服务器必须扫描整个数据库以响应每个客户端查询。否则，服务器将获知客户端对未被触及的记录不感兴趣。这种线性的服务器端成本已经成为PIR协议实际应用的障碍。

 离线/在线PIR。最近的工作构建了离线/在线PIR协议[10]、[11]，它们通过将繁重的线性时间计算转移到离线预处理阶段来降低在线计算成本。具体地说，离线阶段发生在客户端决定提取哪个数据库记录之前。客户端向服务器发送预处理请求，服务器执行离线预处理并生成提示作为响应。然后，客户端将提示存储在其本地存储中。在线阶段发生在客户端决定获取哪条记录之后。客户端使用提示构造查询，以检索其所需的记录并为将来的查询更新其提示。

C.分层数据库

 在离线/在线PIR协议中，客户端保存在离线阶段生成的提示，并且每次数据库更新都会使其本地提示无效。一个简单的解决方案是在每次更新后为每个客户端生成新的提示。但是，如果数据库频繁更新，重新生成提示的巨大成本将抵消使用离线/在线PIR协议的好处。

 我们使用分层数据库[10]来解决这个问题。其思想是将一个有n条记录的数据库转换成log n层，第m层最多包含2^m条记录。最初，n条记录存储在最底层，其他所有层都是空的。更新操作是自上而下的，因此只有当上面所有层都溢出时，层才会更改。

 随着数据库的变化，只有上层频繁变化，但由于容量较小，它们用于重新生成提示的预处理成本相对较低。较低层的前处理成本较高，变化相对较少。因此，每次更新的平均预处理成本保持在较低水平。

三、问题陈述

A.系统模型

 如图1所示，我们的方案涉及四种实体：CA、区块链节点、Web服务器和客户端。

（1）CA负责为Web服务器颁发和吊销证书。要吊销证书，CA需要向区块链节点提交签名的吊销请求。

（2）区块链节点验证来自CA的吊销请求，并将其打包成新的块，在达成共识后添加到区块链中。节点维护分层数据库并响应来自客户端的PIR查询。

（3）Web服务器向CA申请公钥证书并向客户端提供Web服务。

（4）客户端(例如，浏览器)向Web服务器请求证书并向区块链节点发送PIR查询，以在与Web服务器建立安全连接之前验证证书状态。

B.威胁模型

 我们的威胁模型如下。

（1）CA具有潜在的恶意。由于CA大多由第三方运营以获取利润，我们假设CA是自私的，在对他们有利的时候可能会行为不端。

（2）区块链节点诚实但好奇，即节点遵循定义的协议规范，但会观察访问模式并试图推断客户端的敏感信息。

（3）我们假设攻击者可以泄露一些CA的私钥来签署欺诈性撤销。对手还可以对区块链网络发起攻击，以控制部分节点，但不能控制区块链网络中超过51%的计算能力。

C.设计目标

 鉴于上述威胁模型，为了确保我们的方案能够以安全、私密而高效的方式工作，以下要求是必不可少的。

（1）正确性。如果所有实体都正确执行规定的协议，客户端应该始终收到正确的答案并恢复正确的撤销信息。

（2）隐私。在我们的多服务器设置中，只要提示生成器服务器是诚实的，控制其他服务器的对手除了查询的数量之外，什么也不知道。

（3）效率。系统应能够高效地处理证书吊销并响应客户端查询，以最大限度地减少客户端感受到的延迟并增加峰值吞吐量。

（4）责任。恶意行为应该是不可否认的和负有责任的。

（5）兼容性。为了消除实际应用的障碍，该方案应与现有的公钥基础设施生态系统兼容。

四、MOO-PIR：多服务器在线/离线PIR

 离线/在线PIR协议通过将繁重的计算转移到离线预处理阶段，显著提高了峰值吞吐量并减少了查询延迟。现有技术的离线/在线PIR方案在两个服务器设置[10]中实现亚线性在线服务器端计算，其中，只要对手控制两个服务器中的最多一个，就保证了客户端隐私。在这一部分中，我们对这些方案进行了改进，提出了一种新的多服务器离线/在线PIR方案，该方案即使在部分服务器串通的情况下也能保护客户的查询隐私，更适合于基于区块链的证书撤销场景。

 假设数据库由$n$条记录$D1, …, D_n$组成，$k$个服务器持有数据库的相同副本 ($k \ge 2$)。服务器分为两组：$SS_0 \leftarrow {S_1,…, S_m }$ 用于预处理以生成提示，$SS_1 \leftarrow {S{m+1},…, S_k}$ 用于回答客户查询 ($0<m<k$)。我们将$ \lambda $定义为安全参数。此外，为了简单起见，我们将$\sqrt{n}$和$n / m$等表达式视为整数。

 离线阶段。在决定获取哪个记录之前，客户端将预处理请求发送到$SS0$中的服务器。每个服务器从数据库索引${1,…,n}$中随机采样$T=\lambda \sqrt{n} / m$个索引集$I_1, \ldots, I_T$，每个大小为$\sqrt{n}$ ，并计算每组索引$I_t$的奇偶性，为$P_t=\bigoplus{j \in It} D_j$。然后服务器将$I_1, \ldots, I_T$及其对应的奇偶校验词$P_1, \ldots, P_T$作为$T$个Hint，并将其发送给客户端。客户端总共接收$T^{\prime}=m \cdot T=\lambda \sqrt{n}$个hint，并在本地存储中存储hints $\leftarrow\left(\left(I_1, P_1\right), \ldots,\left(I{T^{\prime}}, P_{T^{\prime}}\right)\right)$。

 在线阶段。一旦客户端决定获取第$i$个数据库记录$Di$，就是找到一个索引集$I_t$，其中包含$i$，并通过集合$I_t$和$I_t \backslash{i}$的奇偶校验词恢复$D_i$。集合$I_t$与$P_t$可以在$SS_0$给出的hints中找到，因此客户端只需要从$SS_1$中获得$P_t^i=\bigoplus{j \in I_t \backslash{i}} D_j$即可。

 常见策略。客户随机采样一些假的索引以进行混淆，并构建索引集$q{m+1}, \ldots, q_k$，作为$k-m$个查询，每个大小为$\sqrt{n}-1$，使得集合$I_t \backslash{i}$中的每个真实索引总共出现奇数次，并且每个假的索引出现偶数次。然后客户端将这些查询发送到$SS_1$中的$k - m$个服务器，服务器计算奇偶校验词$W{m+1}, \ldots, Wk$作为响应。由于只有真实索引出现的奇数次，因此$W{m+1} \oplus \cdots \oplus Wk=\left(\bigoplus{j \in I_t \backslash{i}} D_j\right)=P_t^i$。客户端可以将第$i$条记录恢复为：

$$P_t \oplus\left(W_{m+1} \oplus \cdots \oplus W_k\right)=P_t \oplus P_t^i=D_i$$

 例如，假设$n = 16$、$k = 6$和$m = 3$。如果客户端想要获取第$5$个数据库记录$D5$，第一步是找到一个包含$5$的索引集，例如 $I_t = {1, 5, 9, 11}$，其对应的奇偶校验$P_t=D_1 \oplus D_5 \oplus D_9 \oplus D{11}$。客户端随机采样假的索引$x$、$y$、$z$并构建查询$q4 \leftarrow{1, x, y}$，$q_5 \leftarrow{9, y, z}$和$q_6 \leftarrow{11, z, x}$，然后将它们发送到服务器$\left{S_4, S_5, S_6\right}$，计算奇偶校验词$W_4 \leftarrow D_1 \oplus D_x \oplus D_y$，$W_5 \leftarrow D_9 \oplus D_y \oplus D_z$，$W_6 \leftarrow D{11} \oplus D_z \oplus D_x$作为响应。在接收到这些响应后，客户端可以恢复$P_t \oplus\left(W_4 \oplus W_5 \oplus W_6\right)=D_5$。

 由于每个查询都会将有关索引集$It$的一些信息泄漏到$SS_1$中的服务器，因此客户端无法重用它，而是重新生成一个新的集合 $I{new}$，其中包含每个查询后的$i$。为了获得相应的奇偶校验词$P{new}$，客户端将$I{n e w} \backslash{i}$发送到$SS0$中的任何服务器之一，该服务器响应奇偶校验词$W{new}$。然后客户端计算$P{\text {new }} \leftarrow W{\text {new }} \oplus Di$，并用$\left(I{n e w}, P_{n e w}\right)$替换$\left(I_t, P_t\right)$。

 在上述常见策略中，客户端发送到$SS_0$的集合永远不会包含所需的索引$i$，发送到$SS_1$的集合有很高的可能性不包含$i$。如果客户端总是使用这种查询策略，服务器将学习客户端对哪些数据库条目不感兴趣，从而泄露有关$i$的信息。因此，我们使用罕见的策略来防止这种泄漏。我们设置使用每种策略的概率，使得整体概率分布隐藏客户端的期望索引$i$。

 罕见的策略。客户端以$2(\sqrt{n}-1) / n$的小概率随机采样包含$i$的索引集$I{new}$、索引$r \in I{n e w} \backslash{i}$和$r^{\prime} \in I{n e w} \backslash{r}$，以及一个位$b \in{0,1}$。随后，客户端构造两个查询$Q_b \leftarrow\left(I{n e w} \backslash\right.{i}, r)$和$Q{\bar{b}} \leftarrow\left(I{\text {new }} \backslash{r}, r^{\prime}\right)$。与常见策略类似，客户端将$Q0$发送到$SS_0$中的任何服务器之一，并根据$Q_1$构造$k-m$个查询，发送到$SS_1$中的服务器。服务器返回奇偶校验词$W_0, W{m+1}, \ldots, Wk$以及数据库记录$D_r$和$D{r’}$。然后客户端可以将第$i$条记录恢复为$W0 \oplus\left(W{m+1} \oplus \cdots \oplus Wk\right) \oplus D_r=\left(\bigoplus{j \in I{\text {new }} \backslash{i}} D_j\right) \oplus\left(\bigoplus{j \in I_{\text {new }} \backslash{r}} D_j\right) \oplus D_r=D_i$。

 为了隐藏客户是否使用常见策略或罕见策略，客户端将虚假索引发送到公共策略中的服务器，以模仿其在罕见策略中的行为。

 备注。为了减少离线阶段的通信和存储成本，我们可以使用伪随机生成器来生成索引集，因此每个索引集都可以压缩为伪随机种子。此外，为了减少客户端在hint中搜索其所需索引$i$的时间，客户端可以存储哈希表，该哈希表将索引映射到hint中的索引集。

五.系统设计

 为了实现第三节提到的设计目标，我们提出了一种新的证书撤销方案，可以有效地解决安全和隐私问题。对于安全性，我们将当前的PKI体系结构与区块链技术相结合。所有撤销信息都必须由区块链节点验证，并且可以由公众审计。对于隐私，我们使用第四节中提出的MOO-PIR协议来隐藏客户端查询的撤销信息。在高层次上，我们的方案涉及初始化、撤销、数据库更新和验证四个阶段。

A.初始化

 在这个阶段，CA 生成他们的公共私钥对来发布和撤销证书。CA a 生成其公私钥对$\left(p k_a, s k_a\right)$，并发布公钥$pk_a$到区块链节点和客户端，以验证签名。Web服务器还生成它们的密钥对，并适用于来自CA的公钥证书。此外，区块链节点必须初始化一个空的分层数据库，并为每个层维护一个时间戳。哈希函数$\mathcal{H}:{0,1}^* \rightarrow{0,1}^\gamma$在初始化阶段也被协商。

B.撤销

 在一些特殊情况下，web服务器的私钥被破坏或其从属关系的变化，ca必须撤销他们向该服务器颁发的证书并发布撤销信息。

 假设 CA a 必须撤销certs $\leftarrow\left{\right.$ cert $_1, \ldots$, cert $\left._m\right}$。对于每个$\operatorname{cert}_i(0<i \leq m)$，a提取其预定过期日期$date_i$并计算哈希值$\operatorname{hash}_i \leftarrow \mathcal{H}\left(\right.$ cert $\left._i\right)$。然后 a 使用其私钥$sk_a$将其身份$ID_a$与撤销信息$revo \leftarrow (((hash_1, date_1))$一起签名，以获得签名$sig$。最后，CA a将撤销请求$\left(\left(I D_a\right.\right.$, revo $)$, sig $)$发送给区块链节点中的任何一个。

 一旦区块链节点 p 从 CA a 接收撤销请求$\left(\left(I D_a\right.\right.$, revo $)$, sig $)$，它首先使用公钥$pk_a$验证签名$sig$。如果撤销有效，节点创建一个具有$\left(\left(I D_a\right.\right.$, revo $)$, sig $)$的交易，并将其广播到区块链网络中的所有其他节点。交易将被打包成一个新块，在节点达成共识后将附加到区块链。一旦在区块链上记录撤销$\left(\left(I D_a\right.\right.$, revo $)$, sig $)$，节点p将交易地址返回给CA a。

C.数据库更新

 由于区块链结构在执行查询时效率低下，区块链节点在客户端的查询友好的数据库中维护撤销信息。在离线/在线PIR协议中，每个数据库更新会使客户端本地存储中的hint无效，因此我们使用分层数据库来降低重新生成hint的成本。在我们的方案中，更新分层数据库有两种操作。

 插入。一旦将新块附加到区块链，每个节点遍历新块中的所有交易来收集证书撤销并将它们插入到分层数据库中。记录存储在分层数据库中，并作为键值对。对于撤销信息$(hash,date)$，节点以32位哈希前缀为key，完整信息$(hash、date)$为值。分层数据库的插入操作从上到下。节点首先将新的键值对$(K, V )$添加到最顶层。如果这样的插入会导致层溢出，节点将该层中的所有键值对刷新到下一层，依此类推，直到所有层都低于它们的最大容量。如果底层溢出，节点会在下面创建一个新的数量翻倍的层。

 一旦新块附加到区块链，区块链节点就会执行插入，以确保它们的数据库版本在整个过程中保持一致。在完成插入后，节点更新已修改的层的时间戳。

 删除。当客户端从想要访问的 Web 服务器接收证书时，它首先验证过期日期和 CA 的签名，因此过期的证书将直接视为无效。由于客户端从未验证过期证书是否被撤销，节点可以删除过期证书的撤销信息，释放存储空间。删除是在刷新阶段执行的。在将层中的记录移动到下一层之前，节点检查每条记录的过期日期并直接丢弃过期撤销。

D.验证

 为了在客户端验证撤销信息时有效地保护查询隐私，我们使用第IV节中提出的新型多服务器离线/在线PIR协议MOO-PIR来构建验证过程。

 MOO-PIR 的离线预处理阶段可以在客户端初始化（例如浏览器安装）之后执行。客户端选择$k$个区块链节点形成PIR服务器集$SS_0$和$SS_1$，然后将预处理请求发送给$SS_0$中的节点。节点将分层数据库中的每一层都视为一个子数据库来执行预处理，并返回hint以及一个哈希表（将32位哈希前缀映射到数据库索引）作为响应。客户端在其本地存储中存储hint和哈希表，并维护一个时间戳$\tau$来记录最后一个预处理请求的时间。

 当客户端收到想要访问的网站的证书时，它首先检查过期日期和CA的签名，然后验证证书是否被撤销。客户端计算cert的哈希值哈希，并在哈希表中搜索其32位前缀。如果表格中不存在前缀，则 cert 是有效的。否则，证书可能被撤销或不撤销(假阳性)，因此客户端应该使用相应的数据库索引$i$来执行我们的MOO-PIR在线查询，从区块链节点私下获取前缀的撤销信息。

 最重要的是，客户端必须通过将其时间戳$\tau$发送到$SS_0$中的任何一个节点来确保其hint是最新的。节点检查所有层的时间戳是否早于$\tau$，对于时间戳晚于$\tau$的层，返回正响应或新的hint和哈希表。然后客户端可以使用新的hint来执行MOO-PIR协议的在线查询阶段。客户端首先找到一个索引集，其中包含索引$i$并构建查询来检索相应层中第$i$个记录。为了隐藏所需记录的哪一层，客户端还为其他层构建虚假查询。然后客户端将其查询发送到$SS_1$中的$k - m$个区块链节点，并从$SS_0$中的任何一个节点请求一个新的hint。

 在接收到节点的所有响应后，客户端恢复记录$(hash’,date’)$，并将$hash’$与$hash$进行比较。如果$hash = hash’$，则查询结果正确，证书 cert 已被撤销。如果$hash \ne hash’$且前32位相等，则查询结果正确，并且 cert 尚未撤销。否则，查询结果不正确，并且存在欺诈或篡改的响应。