最新论文笔记(+10)：Enabling Reliable Keyword Search in Encrypted Decentralized Storage with Fairness/TDSC18

Enabling Reliable Keyword Search in Encrypted Decentralized Storage with Fairness (以公平方式在加密去中心化存储中实现可靠的关键字搜索)

在本篇论文中，作者利用智能合约在区块链上记录加密搜索的日志，并设计了一个公平的协议来处理争议和发放公平的付款，以动态高效的可搜索加密方案为例，保留加密的搜索能力，并加强了生态系统的健康，从而激励服务对等节点做出贡献。

• 原文链接：Enabling Reliable Keyword Search in Encrypted Decentralized Storage with Fairness

主要贡献：

• 1）将动态高效、安全的关键字搜索引入加密的去中心化存储中，以实现安全和动态更新、同时减少用于公平支付的区块链的执行和存储开销。
• 2）以鼓励加密搜索服务中值得信赖的行为，并制定具体方案的公平性和可验证性。
• 3）对其在加密搜索过程中的延迟和以太坊上的交易成本进行实验测试，实验结果验证了该算法的搜索效率。

一、写作背景

从本文可知，像Storj和Sia这样的去中心化存储系统面临来自客户端和服务节点的严重威胁。例如服务节点可能会返回部分或错误的结果，而客户端可能会故意诽谤服务节点以避免付款，以及缺少关键字搜索等具有表现力的功能，用户目前只能通过自己的标识符获取加密文件。因此，需要考虑外包文件和索引的位置？，需要与现有的去中心化存储平台兼容？，需要同时考虑不诚实的客户端和不诚实的服务对等节点？。以上几种问题都可能导致不必要的通信或计算开销，故启用加密搜索使得开发工作量降至最低。

主要解决两大挑战：1）如何在分布式平台中部署可搜索加密功能？2）在去中心化的平台，客户和服务方都有可能是不诚实的。

二、 主要内容

本文通过集成可搜索加密技术，在分布式存储中实现有效的加密搜索服务，减少查询延迟和通信开销。此外，作者通过实施一个由智能合约支持的健康生态系统来解决不诚实客户端和不诚实服务对等节点，并通过进一步的定制设计来最小化区块链上的计算和存储开销。

• 1）在分布式存储中支持加密关键字搜索，并提供高效的更新：作者指出需要保持文件和索引的局域性，以便每个文件及其索引位于同一个服务对等节点中，因为在不同的服务对等节点之间造成额外的搜索延迟和通信开销。
• 2）公平的支付：除加密搜索功能之外，还需激励服务对等节点提供可靠的关键字搜索。实现这个需要自然想法是让客户端提供搜索服务付费，但是这种支付策略在分布式存储中是不安全的，因为谁先采取行动，谁就会有作恶的风险。

2.1 系统模型

作者提出的去中心化存储加密关键字搜索框架由三种类型的参与者组成，即客户端、服务对等节点和仲裁群体。客户是服务请求者，他们想要外包他们的个人文件，然后享受内容搜索服务，而服务对等节点是出租他们的计算资源，以赚取回报的单个节点。而仲裁节点是由诚实的服务对等节点构成，成员可变化，故本系统中的对等节点可以在不同的合约中切换其角色。

2.2 基本流程：

• 1）初始化：令 F : { 0 , 1 } k × { 0 , 1 } ∗ → { 0 , 1 } k F:\{0, 1\}^k \times \{0, 1\}^* \to \{0,1\}^k F:{0,1}k×{0,1}∗→{0,1}k是一个安全伪随机函数（PRF）， H : { 0 , 1 } k × { 0 , 1 } ∗ → { 0 , 1 } k H: \{0,1 \}^k \times \{0, 1\}^* \to \{0, 1\}^k H:{0,1}k×{0,1}∗→{0,1}k是基于密钥的哈希函数，$H$是一个抗碰撞性的MSet 哈希函数，$(Enc,Dec)$是一个满足安全选择明文攻击（CPA）加密方案。接下来，客户端C和服务对等放交互并达成协议，通过在区块链上建立智能合约记录服务信息，包括客户端C账户地址和合约服务节点S在区块链上的服务，服务时长，每个关键词搜索操作结算的服务费。

• 2）文件添加：首先，在上传文件之前被加密，同时客户端为每个文件贴上唯一标识，并对其建立一个可搜索索引，以支持安全关键字搜索。将加密文件和索引一起发送到签约的服务对等节点，可搜索索引的元数据将作为证据锚定在区块链上。
  
  

• 3）关键词搜索：完成上传后，客户端可以构造搜索token并向区块链发出搜索token以进行安全查询。一旦注意到发布了一个搜索token，约定的服务对等端将从区块链检索搜索token，并使用索引执行搜索操作，以获得结果，即匹配的文件标识。然后，将相应的加密文件作为查询答案发送回请求的客户端，服务对等端也将搜索结果的元数据记录到区块链以获取锚定证据和触发这个操作的时间锁定支付。
  
  

• 4）公平仲裁：当且仅当服务对等方如实的提供正确的查询服务时，才会获得上述的回报。特别的，将启用一个两层身份验证机制来验证返回的搜索结果。返回的结果的验证首先由客户机在锁定时间内本地执行。若客户端检测到不正确的结果，他可以向仲裁群体发送一个判断请求，以进行公正的判断。仲裁群体是由一组服务对等节点组成，这些服务对等节点自愿为维护系统的健康运行服务，即防止不诚实的客户拒绝支付服务费用。仲裁群体可以基于先前锚定在区块链上的证据，通过重新执行争议中的搜索操作，公正地判断合约服务对等方返回的搜索结果的正确性。当客户端和服务对等方都忠诚地行为，则仲裁方不参与，并且合约会在锁定时间后自动完成每个查询服务的付款。

2.3 安全目标

• 1）Confidentiality：为了公平地阐述文件的机密性和查询关键词，定义了三个泄露函数，即$L_{add},L_{search},L_{encrypt}$。其次定义：
  • $Theorem1$：若$(Enc,Dec)$在语义上是安全的，并且$F,H$是安全的$PRF$，则是$(L_{add},L_{search},L_{encrypt})$针对随机谕言机模型中的自适应选择关键词攻击是安全的。
  • $Proof$：目标是证明PPT敌手无法区分现实和理想模型中搜索查询过程。
• 2）Soundness：为了使客户端用结果验证，使用set hash函数来安全地聚合所有文件的set hash摘要，并将聚合的摘要与之前记录在客户端本地清单中的摘要进行比较。
• 3）Judgment Fairness：利用区块链作为不可变日志来锚定文件添加过程的元数据以及关键词搜索过程的搜索token和结果元数据。因此，当客户端向仲裁者群体发出判断请求时，每个冲裁者节点可以检查提供的添加token的有效性，重新执行争议搜索操作，并公平地做出决定是否接受客户端请求的判断。

判断公平性需要仲裁群体中所有节点之间达成共识才能确定一个判断结果。这里遵循拜占庭投票机制，即为每个仲裁节点分配一票，利用阈值N来达成共识的判断。如果客户端的判断请求有效，即合约服务节点确实提供了错误的搜索结果，则锁定支付并暂停，因为诚实的冲裁群体将通过投票的阈值帮助暂停支付过程。此外，这也意味着如果客户端的判断请求无效，即合约服务节点确实提供了正确的搜索结果，则不会停止锁定支付，因为诚实仲裁群体将没有足够的投票。

2.4 实验评估

实验环境：使用python和Solidity构建以太坊智能合约，共2000多行代码。采用Python加密库和Fernet对称加密算法，密钥为256字节。python内置SHA-256哈希函数，3.4GHz四核CPU、16GBRAM、一个256GB SSD和Linux 16.04操作系统。使用本地模拟网络TestRPC使用以太坊区块链测试智能合约。

• 1）更新和搜索性能：使用谷歌1w个最常见的查询创建数据集，使用最大的人口普查数据集包含100w条记录$(w,id)$对，其中$w$表示关键字，$id$表示文件标识符。
  
  上图绘制了构建添加token的处理延迟，具有不同数量的$(w,id)$对。从图中可知，处理延迟随着要处理的$(w,id)$对的增加而增加，但是创建具有100w个$(w,id)$对的加密数据库的处理时间少于25秒，这是实用的，并且比基于基本倒排索引的构造显示出明显的优势。
  
  上图绘制了三个不同数据集执行0.5w、1w、1.5w、2w和2.5w次独立查询时每0.5个查询的瓶颈搜索延迟。从图中可知，每0.5次查询的平均搜索延迟随着之前执行更多查询并在搜索索引w种编入索引而迅速缩小，因此可以进行最佳检索。当2.5w次随机选择查询时，最小EDB种的平均搜索延迟为460ms，从长远来看，当所有独立关键字都被查询和索引时，搜索延迟会变得最优。另外，还可以观察到重新执行搜索操作时仲裁节点的操作延迟，当线性扫描最大的数据集100w大约需要14秒。作者认为这种操作延迟是可以接受的，因为只有客户端发出判断请求时才会执行公平判断。
• 2）合约构建和评估：如下图展示了在以太坊上实施智能合约的成本评估。对于文件添加过程，由两个添加交易$tran{s}_{add}^C$和$tran{s}_{add}^S$发送的$(h^{{}^{\prime }},H({\delta }_f)$元组将在区块链上产生存储成本。对于搜索操作，合约会触发$t$时间锁定的计划调用并冻结预先定义的金额，从而得到第一部分的区块链成本。
  
  若客户端没有要求判断，或者冲裁者群体判断不需要进一步补偿，则在预定时间通过公共事件$Transfer$完成支付调用在时间t触发，它由搜索成本评估的第二部分表示。函数judge的开销评估仲裁者群体撤销支付时的计算成本，若仲裁群体的暂停投票超过预定义的阈值N，则由共识投票过程触发，其中N是仲裁群体大小是阈值参数。
• 3)与现有动态可搜索加密方案的比较：可以看出，本方案与其他方案对比，在搜索和更新的计算开销和通信开销差不多的情况下，进一步实现了支付的公平性和可验证性。
  

三、 总结与思考

总结：本文利用公有链在客户端和服务端之间创建智能合约，先存储客户端的存款，若提供了正确的搜索结果，则触发自动支付存储，并支持对链下服务节点生成的结果进行验证。智能合约锚定搜索操作的元数据作为不可否认的证据，并在客户端和服务对等节点之间发生争议时执行判断操作。将结果检测过程卸载给客户端，并向提供请求的搜索服务对等节点发出有时间锁定的支付。在锁定时间内，客户端可以进行结果验证，判断结果是否正确，并向仲裁群体发出判断请求。一个仲裁群体将启动公平的判断程序，基于先前锚定的证据来解决争议，即如果确认服务对等节点是不诚实的，则停止计时支付。

思考：

• 使用区块链技术的话，要尽量减少它的存储开销和计算开销；
• 本方案只支持单关键字搜索，不支持多关键字搜索；
• 本文很巧妙的一个点是只有客户端决定结果有异议时才申请仲裁，而非每次都要仲裁，这样节省了开销；
• 此外，本方案是否适用多用户对多服务节点的场景，好像只能一对一？
• 如何保证仲裁群体是自愿的呢？是否考虑激励。