
本书系统地介绍了可搜索加密基本概念、基本理论和相应的密码方案构造,基本涵盖了可搜索对称加密、可搜索公钥加密的各方面内容。本书共6章,第1章、第2章主要介绍了密码学的数学基础与可证明安全理论;第3章、第4章分别介绍了可搜索对称加密和可搜索公钥加密的基本概念,并详细地给出了一些可搜索加密方案的经典设计;第5章介绍了抗量子计算可搜索加密方案的设计;第6章主要介绍了目前可搜索加密方案在实际部署时可能面临的一些安全性风险,并介绍了相应的防御措施等。本书可以作为高等院校网络空间安全、计算机科学、数学等学科专业的科研工作者与研究生学习可搜索加密理论的参考书,也可以作为信息安全企事业单位可搜索加密方面研发人员的专业读物。
序 伴随着云计算、物联网、人工智能、区块链、量子计算等信息技术的迅猛发展,以大数据为核心的数据科学催生了第三代信息化浪潮,并推动社会经济从农业、工业经济向数字经济跨越,实现了信息技术与经济社会的深度融合。作为数据科学的核心,数据资源的基础和战略地位显而易见。然而,数据作为生产要素在推动生产生活数字化的同时,由数据泄露和数据的不规范使用所引发的各行业的安全问题越发严峻。全国人大常委会陆续通过并施行了《中华人民共和国数据安全法》等一系列法律,为维护数据安全提供了有力的法律保障。 密码技术是解决数据安全问题的关键。加密后的数据可以有效地抵制数据入侵、泄露。然而,加密在给数据带来机密性的同时,也在相当程度上损害了数据的可用性,为数据发挥生产要素重要作用推动数字经济发展带来了新挑战。其中,首要的就是数据的检索问题。当需要查找某些具体文件时,用户需要先下载所有数据再解密查找相关文档。这种方法浪费了大量的计算机资源,尤其是对于在云端存储的密文数据的信息检索更加困难。因此,实现加密数据的高效检索是当前急需解决的重要问题。 为了实现加密数据的可检索性,可搜索加密的概念应运而生。它旨在让用户无须解密密文数据而直接对其检索,达到如同对明文搜索的效果。经过近些年的发展,可搜索加密技术逐步走向成熟,被认为是构建加密数据库搜索模块的核心技术,能为隐私数据提供安全的检索服务。然而,由于可搜索加密技术本身的复杂性,可搜索加密要真正落地商用还有待我们做出巨大的努力。本书介绍了目前主流的可搜索加密技术,系统地回顾了可搜索加密技术的发展史、研究现状,探讨了其未来的发展方向,为有意向在本领域深耕的研究者提供引导,也为相关的从业者快速了解本领域提供便利的条件。 本书作者长期从事密码学方面的理论与应用研究工作,承担了国家自然科学基金、江苏省自然科学基金等科研项目,在国内外重要学术刊物及国际会议上发表学术论文多篇,在公钥密码、数字签名、同态加密、密文检索、联邦学习、抗量子计算密码等方面取得丰硕的研究成果。本书反映了南京理工大学代数与密码课题组近年来研究可搜索加密的成果,汇集了课题组在可搜索加密领域所做的努力。本书的出版有助于不断完善密文检索的理论和技术体系,并进一步推动我国商用密码技术的推广和可搜索加密技术的实际应用。希望本书能够得到学术界与产业界的认可,为读者带来一些新的视角。 刘凤玉 许满武 2022年6月 前言 随着云技术与大数据的快速发展,广泛且长期存在的各种企业数据与用户隐私的泄露使得如何确保信息安全备受关注。近年来,频频爆发的用户、企业甚至国家层面的数据泄露事件更是将对网络空间安全学科的建设和数据隐私保护技术的探索推到了前沿。信息安全问题造成的人民财产受损、金融市场动荡以及国际关系不稳定使我们坚信没有信息安全就没有国家安全。全国人大常委会相继通过并颁布了《中华人民共和国网络安全法》(2016年)、《中华人民共和国密码法》(2019年)、《中华人民共和国数据安全法》(2021年)、《中华人民共和国个人信息保护法》(2021年)等多部法律,以此维护网络空间主权和国家安全、社会公共利益,保护公民、法人和其他组织的合法权益,促进经济社会信息化健康发展。 作为信息安全的重要环节,数据安全一直是人们关注的重点。数据是信息的载体,保证数据的机密性尤为重要。一般来说,利用密码学算法加密隐私数据是最直接的保护隐私数据的方法。然而,这种防护机制却是以损失数据的可用性为代价的。直接表现是用户无法再对数据进行有意义的常规操作,如搜索、统计等。为了解决这个问题,附带丰富的实际功能的密码技术被提出,特别是可搜索加密技术,它被认为是解决密文检索、构造加密数据库的最有效的方法。可搜索加密技术是实现加密数据可用性的基础。在数据安全领域,可搜索加密技术由于在保证数据安全的基础上引入了密文检索的功能而备受关注。可搜索加密技术丰富的查询功能与完备的功能体系使其在密文数据库的安全建设方面具有重要的理论研究意义和广阔的应用前景。本书主要从业界需求的角度出发,在研究、分析现有的可搜索加密算法的基础上,对基于不同检索模型的可搜索加密方案的功能性和安全性进行了相关的研究和探讨。 本书具有如下特色: (1)以“学”为中心,本书的书写过程也是课题组重新学习可搜索加密技术的过程,我们希望能够为科技工作者提供一本可搜索加密技术的入门书籍,使他们能够轻松愉悦地完成对可搜索加密技术的学习。 (2)以“理”为纲,本书将密码设计建立在经典的数学理论上,展示如何以优美的数学语言展示可搜索加密技术的无穷魅力。 (3)以“用”为本,一切理论基础都应回归实践生活中,本书以可搜索加密技术的实际应用为本,阐述可搜索加密技术的来源与发展,向读者传达设计者的设计初衷,源于实践,归于实践。 尽管有不少可搜索加密研究成果,但是大部分都以科技论文的形式呈现,侧重于解决实际的科学问题。缺乏一本书来系统地阐述可搜索加密技术的发展历程,并从密码应用的角度来阐述学术界和工业界的一些前沿工作,于是我们撰写了本书。 本书主要依托课题组近年来在可搜索加密领域所积累的一些研究工作,参考了一些经典方案,结合课题组和工业界对加密数据库的思考与探索撰写而成。本书共有6章,具体是:第1章密码学的数学基础,第2章可证明安全理论与基础,第3章可搜索对称加密,第4章可搜索公钥加密,第5章抗量子计算可搜索加密,第6章可搜索加密的应用。 在编写本书的过程中,得到了梅琳、张盼、徐承志、薛少康,位雪、杨蒙蔚、陶洪耀、陈相全、刘克毅等研究生的帮助。 本书是在国家自然科学基金项目“密文数据生态联盟建设和安全防护体系研究(62072240)”、江苏省自然科学基金项目“可搜索加密机制授权管理技术与安全理论的研究(BK20210330)”、山西省基础研究计划项目“面向云存储的抗量子计算攻击可搜索加密技术研究(20210302124273)”、国家自然科学基金项目“面向异源数据的可搜索加密方案的性能优化与安全分析研究”(62202228)的资助下完成。 作 者 2022年6月
第1章 密码学的数学基础 1 1.1 数论与有限域 1 1.2 椭圆曲线与双线性映射 3 1.3 格理论 5 1.3.1 格与抽样算法 5 1.3.2 LWE问题及相关结论 7 1.4 信息熵 8 1.5 密码学函数 9 参考文献 10 第2章 可证明安全理论与基础 13 2.1 可证明安全概述 13 2.1.1 可证明安全理论 13 2.1.2 密码学原语与安全模型 13 2.2 随机预言机模型 16 2.2.1 基本概念 16 2.2.2 基于随机预言机的代表性研究成果——公钥加密方案 17 2.3 标准安全模型 17 2.4 经典的困难问题 18 2.5 访问协议与基于属性的加密技术 21 参考文献 22 第3章 可搜索对称加密 24 3.1 可搜索对称加密概述 24 3.2 几个经典的可搜索对称加密方案 25 3.2.1 Curtmola的基于逆向索引的可搜索对称加密方案 25 3.2.2 Cash的支持动态更新的可搜索对称加密方案 31 3.2.3 支持物理删除的动态可搜索对称加密方案 39 3.2.4 跨域搜索的多授权可搜索对称加密方案 49 参考文献 62 第4章 可搜索公钥加密 65 4.1 可搜索公钥加密概述 65 4.2 几个经典的可搜索公钥加密方案 66 4.2.1 Boneh的基于关键词的可搜索公钥加密方案 66 4.2.2 Boneh的支持区间查询、子集查询的可搜索公钥加密方案 71 4.2.3 指定测试者的可搜索加密方案 88 参考文献 95 第5章 抗量子计算可搜索加密 98 5.1 抗量子计算密码技术概述 98 5.2 几个格上可搜索加密方案 99 5.2.1 Behnia等人的基于LWE问题与NTRU结构的 可搜索加密方案 99 5.2.2 格上基于身份的多写模式可搜索加密方案 109 5.2.3 格上抗关键词猜测攻击的连接关键词可搜索加密方案 122 5.2.4 格上关键词可撤销的可搜索加密方案 130 参考文献 141 第6章 可搜索加密的应用 147 6.1 加密数据库与可搜索加密 147 6.2 泄露滥用攻击与防护技术 149 6.3 强化的填充技术 154 参考文献 157