基于以太坊的格上属性基可搜索加密方案

王 想，陈燕俐

(南京邮电大学 计算机学院，南京 210042)

0 引 言

2000年，文献[1]第1次提出了可搜索加密(searchable encryption, SE)技术。可搜索加密技术实现了在不解密数据密文的情况下，利用加密关键字与关键字陷门进行快速匹配的功能，保证了存储在云端的数据的安全性，因而受到了极大的关注和研究。2004年，文献[2]首次提出了公钥可搜索加密技术。结合了属性基加密技术(attribute-based encryption, ABE)[3-4]和可搜索加密技术的属性基可搜索加密方案(attribute-based searchable encryption, ABSE)[5]实现了对搜索用户的有效控制，即只有满足访问策略的授权用户才可以进行密文搜索，有效提高云端密文数据的共享效率及安全性。ABE方案可分为2类：密文策略的属性基加密方案(ciphertext-policy attributed-based encryption，CP-ABE)和密钥策略的属性基加密方案(key-policy attributed-based encryption，KP-ABE)，CP-ABE将用户私钥对应一个属性集，密文对应一个访问结构；KP-ABE中密文对应一个属性集，密钥对应一个访问结构，当且仅当用户的属性集满足访问结构时，用户才能解密密文。同样属性基可搜索加密也可分为密钥策略的属性基可搜索加密和密文策略的属性基可搜索加密。2013年，文献[5]将CP-ABE技术与SE结合构造了密文策略的属性基可搜索加密方案。2014年，文献[6]提出了密钥策略的属性基可搜索加密方案。2016年，文献[7]提出了一个具有高效用户撤销功能的属性基可搜索加密方案。2017年，文献[8]提出了一种分布式多属性授权机构下具有有效撤销功能的属性基可搜索加密方案。

传统的属性基可搜索加密方案大部分是基于双线性配对设计的，随着量子计算机的到来，此类方案的安全性将受到威胁，而格密码系统不仅可抗量子计算攻击，安全性更高，并且由于其线性结构，相对更加高效。2016年，文献[9]提出了格上属性基可搜索加密的思想，但没有给出具体实现方案，并且方案是基于KP的，加密者不可以直接决定谁有权进行密文搜索。2017年，文献[10]提出一种可支持多用户的格上模糊信息可搜索加密方案。2018年，文献[11]提出了格上基于身份的可搜索加密方案。2019年，文献[12]提出了一种格上的公钥可搜索加密方案。

目前的属性基可搜索加密方案大部分是基于云存储模式设计的。传统的云存储模式以集中存储方式运行，因而单点故障可能直接导致系统崩溃。以太坊作为一个开源且具有智能合约功能的公共区块链平台，具有去中心化、安全可靠的特点，可以保证用户和服务器之间交易的公平性，且基于以太坊技术的分散存储方法可以解决传统云存储系统中单点故障问题。文献[13]提出了一种基于以太坊的属性基可搜索加密方案，方案实现了数据所有者代替私钥生成器为用户生成密钥，但该方案是基于双线对技术，不可抗量子攻击。本文方案参考了该思想，提出一种基于以太坊的安全、灵活、高效的格上属性基可搜索加密方案。

1 系统模型和形式化定义

1.1 系统模型

文献[14]提出智能合约在区块链中的应用，智能合约是一种旨在以数字方式执行合约谈判的计算机程序。智能合约可以是任何类型的计算机程序。由于以太坊的特性，所有操作在以太坊中都是透明和可靠的。

IPFS(interplanetary file system)是一种点对点分布式文件系统[15]，旨在将所有计算设备与文件系统连接起来。IPFS中没有中央服务器，数据可分布并存储在世界的不同地方，且各节点间不需要相互信任，不存在单点故障问题。将文件上传到IPFS系统后会获得唯一的文件哈希字符串，通过该字符串可以检索文件。本方案中将加密文件存储在IPFS中。

本方案系统模型如图1，这里不考虑以太坊上的矿工和IPFS中的存储节点。指向智能合约的双箭头表示智能合约部署在以太坊上。模型主要包括2个实体：数据拥有者DO、数据访问者DU。数据拥有者主要职责如下：初始化系统公共参数、主密钥；在以太坊上部署智能合约；代替私钥生成器处理用户的注册请求，为用户生成私钥以避免密钥滥用以及隐私泄漏；负责将密文上传至IPFS。此外，还需将从文件中提取的关键字加密成加密关键字放置到智能合约中。用户从嵌有私钥的以太坊交易中提取出私钥，并利用私钥生成关键字陷门上传到智能合约。基于以太坊的智能合约实现了分散存储系统IPFS中密文的关键字搜索匹配功能。用户根据智能合约返回的结果从IPFS中下载文件。

图1 系统模型Fig.1 System model

方案系统模型具体描述如下。

1)用户向数据拥有者发出注册请求；

2)数据拥有者收到用户的注册请求，根据用户属性集为用户生成私钥，并使用共享密钥加密私钥[16]，将被加密私钥嵌入到以太坊交易单中；

3)数据拥有者通过安全通道向用户发送自己的以太坊账户地址，智能合约地址，智能合约ABI，智能合约源代码相关的交易ID以及嵌有用户私钥的交易单ID；

4)数据拥有者将已加密文件上传到IPFS并为已加密的文件选择关键字，数据拥有者记录IPFS返回的文件存储位置；

5)数据拥有者为所选关键字生成加密关键字并将其存储到智能合约中；

6)用户从以太坊中读取与私钥相关的交易单，使用共享密钥获取私钥；

7)用户生成要匹配的关键字陷门并调用智能合约进行关键字匹配；

8)智能合约根据用户提交的关键字陷门进行匹配搜索并返回给用户相关结果；

9)用户根据智能合约返回的匹配结果向IPFS提供文件的存储位置。

10)IPFS将对应文件返回给用户。

1.2 方案形式化定义

基于以太坊的格上属性基可搜索加密方案包括以下5个算法，分别对应5个函数。

1)Setup算法：对应Setup(1λ)函数，输入安全参数λ，生成系统公共参数pp和主密钥msk。

2)KeyGen算法：对应KeyGen(pp,msk,L)函数，输入公共参数pp，主密钥msk，用户的属性集L。数据所有者判断用户的身份是否合法。若用户身份合法，数据所有者将用户的账户地址添加到智能合约的授权用户集合中。数据所有者根据用户属性集L为用户生成私钥key。

3)KWEncrypt算法：对应KWEncrypt(pp,M,w)函数，输入公共参数pp，访问结构M和关键字w∈{0,1}l1，数据所有者对关键字w∈{0,1}l1生成加密关键字Iw并将Iw存储在智能合约中。

4)Trapdoor算法：对应Trapdoor(pp,key,w′)函数，输入公共参数pp，用户私钥key，要搜索的关键字w′∈{0,1}l1，用户生成关键字陷门tw′并调用智能合约进行关键字匹配。

5)Test算法：对应Test(pp,Iw,tw′)函数，输入公共参数pp，加密关键字Iw，关键字陷门tw′，智能合约首先判断用户是否属于授权用户集，若不属于，拒绝搜索请求；若属于，则进行关键字匹配并返回结果。

2 方案安全模型

本方案在语义上是安全的，这意味着方案可以保证密文不可区分。密文不可区分性是指恶意测试者和外部对手无法区分由他们选择的2个挑战关键字的加密关键字。在本文的安全模型中，为了证明方案可以保证密文不可区分，定义安全模型如下。

Setup：挑战者C通过调用系统建立算法获取公共参数pp和相应的主密钥msk，并运行KeyGen算法为敌手A生成私钥keyA，C发送(pp,keyA)提供给A。

A自适应地向C发出不同的询问：

KeyGen Query：只要A向C发出注册请求，C运行KeyGen算法得到相应的私钥key并返回给A；

Trapdoor Query：只要A对关键字w做出询问，C运行Trapdoor算法得到关键字w的陷门Tw并返回Tw给A；

Challenge：执行过一定数量的上述询问后，A发送(w0,w1)给C，其中w0，w1是2个被挑战的关键字。C选择b∈{0,1}且利用wb生成加密关键字Iwb且返回Iwb给A。

Guess：A输出b′∈{0,1}，当且仅当b′=b时A赢得游戏。

3 方案具体描述

方案主要介绍加密关键字的匹配搜索，包括5个算法：初始化(Setup)，私钥生成，加密关键字，生成关键字陷门，匹配关键字。本文对文件的加密解密以及用户根据智能合约返回的匹配结果向IPFS提供文件的存储位置，IPFS将对应文件返回给用户部分描述省略。

Setup(1λ): 输入安全参数λ，方案中参数q≥2，n=n(λ)，m≥5nlogq，σ∈R，δ∈R，α∈R。属性域U={attr1,…,attrk}是属性全集，k是属性全集中属性的总数量。对于∀attri∈U,Vi={vi,1,…,vi,ki}是属性attri所有可能值的集合，其中ki是属性attri可能值的数量。DO生成系统公共参数pp和主密钥msk。

公共参数pp=(A,{Avi,j}1≤i≤k,1≤j≤ki,u,H1)，主密钥msk={TA}。

KeyGen(pp,msk,L): 输入公共参数pp，主密钥msk，用户的属性集L={L1,…,Lk}，其中，每个Li代表属性attri的对应的集合Vi中的一个值。DO为用户生成私钥keyL。

当一个用户给DO发送注册请求时，他需要提供自己的以太坊账户的公钥(即账户地址)。DO判断用户的身份是否合法，若用户身份合法，添加用户的账户地址到智能合约的授权用户集合并进行以下流程。

2)设置AL=A(FL)-1。

设置私钥keyL=(eL,AL)。

DO根据用户的以太坊账户公钥生成分享密钥，并使用分享密钥利用AES算法加密用户私钥keyL生成CTusk。DO将CTusk嵌入交易TXusk并广播TXusk到以太坊上。

DO利用安全信道传输自己的以太坊账户公钥、交易单ID、智能合约的地址、ABI和源码给用户。用户可以验证部署在以太坊上的智能合约。

KWEncrypt(pp,M,w): 输入公共参数pp，访问策略M={M1,…,Mk}，其中Mi代表访问结构中属性attri对应的集合Vi中的一个值，关键字w∈{0,1}l1，DO生成加密关键字Iw。

2)AM=A(FM)-1,FM‖w=AM(H1(w))-1。

DO将加密关键字Iw=(c0,c1)存储在智能合约中。

Trapdoor(pp,keyL,w′): 输入公共参数pp，用户私钥keyL，要搜索的关键字w′∈{0,1}l1，用户生成关键字陷门tw′。

用户根据DO的以太坊账户公钥计算出分享密钥并从以太坊中取出TXusk利用AES算法算出私钥keyL。用户生成关键字陷门：

1)T←NewBasisDel(AL,H1(w′),eL,σ)；

2)tw′←SamplePre(ALH1(w′)-1,T,u,δ)[19]，其中，(ALH1(w′)-1)tw′=u。

用户提交关键字陷门tw′到智能合约，智能合约执行Test算法。

Test(pp,Iw,tw′): 输入公共参数pp，加密关键字Iw，关键字陷门tw′。此部分由智能合约执行。

4 正确性分析和安全性证明

4.1 正确性分析

1)若用户的属性集满足访问结构，那么AM=AL；若w=w′，即H1(w)=H1(w′)，则

至此，方案正确性得到证明，可以确保用户属性集满足访问结构以及w=w′才能够成功匹配。

4.2 安全性证明

方案在判定性(Zq,n,Ψα)-LWE[20]的困难假设下，可以在随机预言模型中实现密文不可区分性。

定理基于格的可搜索加密方案在随机预言模型中的自适应选择关键字攻击下实现密文不可区分，前提是判定性(Zq,n,Ψα)-LWE问题的困难假设成立。

证明假设在随机预言模型中存在一个具有不可忽略概率ε打破密文不可区分性的对手A，我们构建了一个具有不可忽视概率解决判定性(Zq,n,Ψα)-LWE问题的挑战者C。

A在Trapdoor询问前可以自适应地基于预言机H1为任何关键字w进行H1询问。

Trapdoor询问：一旦接收到A发来的(w,AS,keyS)，C首先查找L1，若在L1中，C可以获得Rw，C调用NewBasisDel(AS,H1(w),keys,σ)和SamplePre(AsH1(w)-1,T,u,δ)， 并返回门限tw给A。

Guess阶段：A输出b′←{0,1}。

5 方案性能分析

5.1 理论分析

本方案与传统属性基可搜索加密方案[7-8]、格上公钥可搜索加密方案[12]、格上基于身份可搜索加密方案[11]的性能比较结果如表1。

表1 方案性能比较Tab.1 Performance comparison of schemes

从表1可以看出，和文献[7-8]方案相比，本文方案利用格密码体制实现，不需要双线性配对运算且可抗量子攻击，安全性大大提高。与文献[11-12]相比，本文方案具有更灵活的访问控制结构，能更好地适用于一对多的应用场景。

5.2 实验仿真

本方案与传统属性基可搜索加密方案[7-8]的仿真实验比较如图2，图3。仿真实验使用JPBC(java pairing based cryptography library)，该库可实现在Java中基于配对的密码系统的数学运算。实验环境为Windows 10系统，硬件配置为Intel Core 2 i5 CPU，4GB RAM。

计算开销主要包括关键字加密KWEncrypt算法和关键字匹配Test算法的计算开销，从图2和图3中可以看出，随着属性个数的增加，文献[7-8]的计算开销增长较快，而本文方案基本保持不变，因此，本文方案与文献[7-8]方案相比，计算效率更高。本文方案比传统的基于属性可搜索加密方案更轻量级的主要原因是方案建立在格理论的基础上，只需要进行矩阵间简单的加法和乘法运算，无须进行运算开销较大的双线性配对和模幂运算。

图2 关键字加密KWEncrypt计算开销Fig.2 Keyword encryption algorithm KWEncrypt calculation overhead

图3 关键字匹配Test计算开销Fig.3 Keyword matching algorithm Test calculation overhead

6 结束语

本文结合了分散存储系统IPFS、格理论和属性基的加密技术，实现了基于以太坊的格上属性基可搜索加密方案。本文主要贡献如下。

1)针对传统属性基可搜索加密方案大部分是基于双线性配对技术提出，不可抗量子攻击，存在一定安全威胁这一问题，本方案利用格密码体制提出一个新的属性基可搜索加密方案，和传统方案相比不仅安全性更高，且更加高效。

2)本文方案中的数据所有者为数据用户分配密钥，拥有对加密共享数据唯一控制权，这一做法可避免传统方案由于密钥托管问题造成的密钥滥用以及隐私泄露。同时，使用以太坊管理用户密钥，这使得用户可随时从以太坊中读取相应的交易数据，并对其进行解密获得自己的密钥信息。

3)鉴于传统属性基可搜索加密方案中存在云服务提供商不可信情况下关键字搜索结果不可靠问题，本文方案将加密关键字存储在以太坊的智能合约中且利用智能合约实现关键字搜索匹配。一旦部署智能合约，将只有在搜索到正确的匹配结果时，用户才需要支付服务费。因此，方案解决了在传统云存储中搜索服务提供商可能不会诚实返回搜索结果的问题。

4)本文方案不仅可以抵抗量子攻击，而且与现有的基于双线性映射设计的可搜索加密方案相比更加高效。

对于未来的工作，计划研究利用新颖的基于格的加密技术，进一步增强所提方案的安全性、灵活性并提高方案的性能。