第４０卷第３期２０２２年５月 贵州师范大学学报（自然科学版）ＪｏｕｒｎａｌｏｆＧｕｉｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅｓ）
Ｖｏｌ．４０．Ｎｏ．３
Ｍａｙ．２０２２引用格式：胡震宇，邓伦治，高岩，等．一个指定验证者的基于身份可搜索认证加密方案［Ｊ］．贵州师范大学学报（自然科学版），２０２２，４０（３）：５６ ６３．［ＨＵＺＹ，ＤＥＮＧＬＺ，ＧＡＯＹ，ｅｔａｌ．Ａｄｅｓｉｇｎａｔｅｄｔｅｓｔｅｒｉｄｅｎｔｉｔｙ ｂａｓｅｄｓｅａｒｃｈａｂｌｅａｕｔｈｅｎｔｉｃａｔｅｄｅｎｃｒｙｐ ｔｉｏｎｓｃｈｅｍｅ ［Ｊ］．ＪｏｕｒｎａｌｏｆＧｕｉｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅｓ），２０２２，４０（３）：５６ ６３．］一个指定验证者的基于身份可搜索认证加密方案
胡震宇１，邓伦治２
，高 岩２，施虹宇２，武亚颖１
（１．贵州师范大学大数据与计算机科学学院，贵州贵阳 ５５００２５；２．贵州师范大学数学科学学院，贵州贵阳 ５５００２５） 摘要：可搜索加密是实现密文检索的重要密码学工具。在强安全模型下提出一个新的指定验证者的基于身份可搜索认证加密方案并在标准模型中证明了其安全性。由于新方案不使用双线性对和哈希到点两种常用高成本运算，与现有同类方案相比，新方案的运算成本更低，因此更符合实际需要。关
键
词：基于身份密码学；可搜索加密；椭圆曲线；标准模型；云存储
中图分类号：ＴＰ３９１ 文献标识码：Ａ 文章编号：１００４—５５７０（２０２２）０３－００５６－０８ＤＯＩ：１０．１６６１４／ｊ．ｇｚｎｕｊ．ｚｒｂ．２０２２．０３．０１０
Ａｄｅｓｉｇｎａｔｅｄｔｅｓｔｅｒｉｄｅｎｔｉｔｙ ｂａｓｅｄｓｅａｒｃｈａｂｌｅ
ａｕｔｈｅｎｔｉｃａｔｅｄｅｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅ
ＨＵＺｈｅｎｙｕ１，ＤＥＮＧＬｕｎｚｈｉ２
，ＧＡＯＹａｎ２，ＳＨＩＨｏｎｇｙｕ２，ＷＵＹａｙｉｎｇ
１（１．ＳｃｈｏｏｌｏｆＢｉｇＤａｔａａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｇｕｉｚｈｏ
ｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｇｕｉｙａｎｇ，Ｇｕｉｚｈｏｕ５５００２５，Ｃｈｉｎａ；
２．ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃａｌＳｃｉｅｎｃｅｓ，ＧｕｉｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｇｕｉｙａｎｇ，Ｇｕｉｚｈｏｕ５５００２５，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｓｅａｒｃｈａｂｌｅｅｎｃｒｙｐｔｉｏｎｉｓａｎｉｍｐｏｒｔａｎｔｃｒｙｐｔｏｇｒａｐｈｉｃｔｏｏｌｆｏｒｃｉｐｈｅｒｔｅｘｔｒｅｔｒｉｅｖａｌ．Ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｎｅｗｄｅｓｉｇｎａｔｅｄｔｅｓｔｅｒｉｄｅｎｔｉｔｙ ｂａｓｅｄｓｅａｒｃｈａｂｌｅａｕｔｈｅｎｔｉｃａｔｅｄｅｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅｕｎｄｅｒｔｈｅｅｎｈａｎｃｅｄｓｅｃｕｒｉｔｙｍｏｄｅｌａｎｄｐｒｏｖｅｓｉｔｓｓｅｃｕｒｉｔｙｉｎｔｈｅｓｔａｎｄａｒｄｍｏｄｅｌ．Ｓｉｎｃｅｔｈｅｎｅｗｓｃｈｅｍｅｄｏｅｓｎｏｔｕｓｅｔｈｅｔｗｏｅｘｐｅｎｓｉｖｅｏｐｅｒａｔｉｏｎｓ（ｉ．ｅ．，ｂｉｌｉｎｅａｒｐａｉｒｉｎｇａｎｄｈａｓｈｔｏｐｏｉｎｔｏｐｅｒａｔｉｏｎｓ），ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｅｘｉｓｔｉｎｇｓｉｍｉｌａｒｓｃｈｅｍｅｓ，ｔｈｅｎｅｗｓｃｈｅｍｅｉｓｍｏｒｅｅｆｆｉｃｉｅｎｔａｎｄｍｏｒｅｉｎｌｉｎｅｗｉｔｈａｃｔｕａｌｎｅｅｄｓ．Ｋｅｙｗｏｒｄｓ：ｉｄｅｎｔｉｔｙ ｂａｓｅｄｃｒｙｐｔｏｇｒａｐｈｙ；ｓｅａｒｃｈａｂｌｅｅｎｃｒｙｐｔｉｏｎ；ｅｌｌｉｐｔｉｃｃｕｒｖｅ；ｓｔａｎｄａｒｄｍｏｄｅｌ；ｃｌｏｕｄｓｔｏｒａｇ
ｅ
０ 引言
如今，信息技术的发展带来了数据量的迅速膨胀，对于各种机构和网络个人用户，云存储服务的广泛应用成为一种必然趋势。虽然云存储的使用极大方便了数据的管理和分享，但是上传到云服务
器上的数据面临丢失、恶意修改和泄露的风险，因
此上传到云服务器上的数据常为加密数据。大量的加密数据带来了密文检索困难的问题，而对所有密文进行解密并在明文上进行检索不符合现实需求。因此，在密文上进行检索是一项必要的研究内容。
６
５收稿日期：２０２２－０１－０３
基金项目：国家自然科学基金项目（６１９６２０１１）
通讯作者：
邓伦治（１９７９－）男，博士，教授，博士生导师，研究方向：密码学，Ｅ ｍａｉｌ：ｄｅｎｇｌ
ｕｎｚｈｉ＠１６３．ｃｏｍ．
为了解决密文检索问题，Ｓｏｎｇ等［１］在２０００年提出了可搜索加密（Ｓｅａｒｃｈａｂｌｅｅｎｃｒｙｐｔｉｏｎ，ＳＥ）的概念并给出了一个具体方案。在可搜索加密体制中，存在数据发送者、数据接收者和云服务器（即数据验证者）３个实体。数据发送者将作为加密文件索引的关键词密文与该文件一同上传至云服务器。在检索密文时，数据接收者对所需文件关键词生成搜索陷门并提交给云服务器，云服务器使用验证算法验证搜索陷门是否与现存关键词密文匹配，若匹配成功则返回搜索陷门所成功匹配关键词密文对应的文件，否则搜索失败。在检索过程中，关键词明文信息不会被泄露。但文献［１］的方案是一个对称加密方案，由此带来的密钥分配复杂性使其不适合数据分享情景。为此，Ｂｏｎｅｈ等［２］在２００４年提出了第一个公钥可搜索加密（Ｓｅａｒｃｈａｂｌｅｐｕｂｌｉｃｋｅｙｅｎｃｒｙｐｔｉｏｎ，ＳＰＥ）。之后，Ｂａｅｋ等［３］进一步提供了一个无安全信道的ＳＰＥ框架，数据接收者可以通过公共信道向服务器发送搜索陷门。但是为了认证用户公钥，基于传统公钥设施构建的ＳＰＥ方案需要一个第三方可信机构来为用户发放证书。由此，Ａｂｄａｌｌａ等［４］扩展了Ｓｈａｍｉｒ［５］提出的基于身份公钥密码学概念，提出一个基于身份的可搜索加密（Ｉｄｅｎｔｉｔｙ ｂａｓｅｄＳＥ，ＩＢＳＥ）方案，在该密码体制中，私钥生成中心（Ｐｒｉｖａｔｅｋｅｙｇｅｎｅｒａｔｏｒ，ＰＫＧ）利用用户的身份信息（如工号、证件号码、姓名等）为用户生成公钥和私钥，省去了证书发放的问题。随后，一系列基于身份的可搜索加密方案被提出。［６－７］ 由于日常语言习惯，用来作为加密文件索引的关键词空间较小。当截获一个关键词搜索陷门时，拥有匹配测试权限的敌手可以利用数据接收者的公钥为所有可能的关键词生成关键词密文并尝试与所截获陷门匹配，直到成功为止。这种攻击被称为关键词猜测攻击（Ｋｅｙｗｏｒｄｓｇｕｅｓｓｉｎｇａｔｔａｃｋｓ，ＫＧＡ）［８－９］。抵御ＫＧＡ的一种可行方案是指定验证者，即只有被指定的实体才能进行匹配测试算法。但是该方法必须保证指定验证者是可信的，否则其仍可进行如上描述的关键词猜测攻击。为了解决这个问题，Ｈｕａｎｇ等［１０］提出了可搜索认证加密（Ｓｅａｒｃｈａｂｌｅａｕｔｈｅｎｔｉｃａｔｅｄｅｎｃｒｙｐｔｉｏｎ，ＳＡＥ）概念。在该类方案［１０－１１］中，关键词加密算法要用到数据发送者的私钥，因此只有数据发送者才能生成有效密文。２０１９年，Ｌｉ等［１２］提出了一个指定验证者的基于身份可搜索认证加密（Ｄｅｓｉｇｎａｔｅｄｔｅｓｔｅｒｉｄｅｎｔｉ ｔｙ ｂａｓｅｄＳＡＥ，ＤＩＢＳＡＥ），在该方案中，只有指定验证者才能进行匹配测试算法，但指定验证者无法生成有效密文来进行ＫＧＡ，即可以抵御内部关键词猜测攻击。
在依赖随机谕言模型的安全性证明中，哈希函数被一个人为构造的列表所替代，此类方案在现实中可能是不安全的［１３－１４］，而标准模型允许通过直接运算哈希函数来获得哈希值，因此在现实中有更高的安全性。本文提出了一个基于强安全模型的ＤＩＢＳＡＥ方案并在标准模型下证明了其安全性。另外，由于新方案不使用双线性对运算和哈希到点运算，因此该方案与同类方案相比具有更高效率。
１ 准备知识
定义１ ｐ，ｑ为２个大素数，Ｅ／Ｆ
ｐ
是１个椭圆曲线，Ｇ为该椭圆曲线上１个ｑ阶加法循环。Ｐ∈Ｇ为Ｇ的１个生成元，给定１个元组（Ｐ，ａＰ，ｂＰ，
Ｘ），其中ａ，ｂ∈Ｚ
ｑ
且未知，则判定性Ｄｉｆｆｉｅ Ｈｅｌｌ ｍａｎ（ＤｅｃｉｓｉｏｎａｌＤｉｆｆｉｅ Ｈｅｌｌｍａｎ，ＤＤＨ）问题是判断Ｘ＝ａｂＰ是否成立。
２ 方案定义
本节我们将给出本方案的方案模型和安全性模型。
２ １ 方案模型
一个ＤＩＢＳＡＥ方案由如下５个多项式时间算法组成：
１）系统参数生成算法Ｓｅｔｕｐ：输入安全参数δ，ＰＫＧ通过此算法生成并公布系统参数ｐａｒｍ。
２）用户密钥生成算法ＵｓｅｒＫｅｙＧｅｎ：输入系统
参数ｐａｒｍ、实体地址ＩＤ合规管理系统
ｉ
，ＰＫＧ利用此算法为用户
ＩＤ
ｉ
生成并发送公钥Ｒ
ＩＤｉ
和私钥ｄ
ＩＤｉ
。
３）关键词密文生成算法ｄＩＢＳＡＥ：输入全局参
数ｐａｒｍ、数据发送者地址ＩＤ
Ｓ
及其私钥ｄ
ＩＤＳ
、数据
接收者的地址ＩＤ
Ｒ
及其公钥Ｒ
ＩＤＲ
、指定验证者地址
ＩＤ
ｄＳ
及其公钥Ｒ
ＩＤｄＳ
和索引关键词ｗ，数据发送者
ＩＤ
Ｓ
通过该算法生成关键词密文Ｃ
ｗ
作为相关加密
文件的索引与该文件一起上传指定服务器ＩＤ
ｄＳ
。
４）搜索陷门生成算法Ｔｒａｐｄｏｏｒ：输入全局参数
ｐａｒｍ、数据发送者地址ＩＤ
Ｓ
及其公钥Ｒ
ＩＤＳ
、数据接
收者地址ＩＤ
Ｒ
及其私钥ｄ
ＩＤＲ
、指定验证者地址ＩＤ
ｄＳ
７
５
第３期胡震宇，邓伦治，高 岩，等：一个指定验证者的基于身份可搜索认证加密方案
及其公钥ＲＩＤｄＳ和搜索关键词ｗ′，数据接收者ＩＤＲ利用该算法输出搜索陷门Ｔｗ′
。５）匹配测试算法ＭａｔｃｈＴｅｓｔ：输入全局参数ｐａｒｍ、数据发送者地址ＩＤＳ、数据接收者地址ＩＤＲ、指定验证者地址ＩＤｄＳ及其私钥ｄＩＤｄＳ、关键词密文Ｃｗ和搜索陷门Ｔｗ′，指定服务器ＩＤｄＳ通过该算法输出结果＂０＂或＂１＂。其中，＂０＂代表搜索失败，＂１＂代表
搜索成功。若搜索成功，ＩＤｄＳ将对应加密文件发送给数据接收者ＩＤＲ。２ ２ 安全性模型
本部分我们将给出ｄＩＢＳＡＥ方案的安全模型。在ＤＩＢＳＡＥ中存在内部和外部两类敌手，其分别定义为：
１）ＡＯ（外部敌手）：具体指除指定服务器ＩＤｄＳ
之外的任何人。
２）ＡＩ（内部敌手）：具体指指定服务器ＩＤｄＳ。一个Ｄ
ＩＢＳＡＥ方案应该满足在关键词猜测攻击下的关键词密文不可区分性（Ｃｉｐｈｅｒｔｅｘｔｉｎｄｉｓｔｉｎ ｇｕｉｓｈａｂｉｌｉｔｙｕｎｄｅｒｔｈｅｋｅｙｗｏｒｄｇｕｅｓｓｉｎｇａｔｔａｃｋｓ，ＣＩＮＤ ＫＧＡ）和在关键词猜测攻击下的陷门不可区分性（Ｔｒａｐｄｏｏｒｉｎｄｉｓｔｉｎｇｕｉｓｈａｂｉｌｉｔｙｕｎｄｅｒｔｈｅｋｅｙｗｏｒｄｇｕｅｓｓｉｎｇａｔｔａｃｋｓ，ＴＩＮＤ ＫＧＡ）。这两类安全性分别保证多项式敌手无法通过关键词猜测攻击从关键词密文和搜索陷门中获得有用的关键词信息。
ＣＩＮＤ ＫＧＡ和ＴＩＮＤ ＫＧＡ以如下几个对抗游戏定义。
定义２ （ＣＩＮＤ ＫＧＡ）没有多项式时间敌手ＡＯ或ＡＩ可以以不可忽略的优势赢得以下游戏，则称一个ｄＩＢＳＡＥ方案满足ＣＩＮＤ ＫＧＡ。
游戏１ （针对ＡＯ的ＣＩＮＤ ＫＧＡ）挑战者Ｃ与ｄＩＢＳＡＥ中的敌手ＡＯ进行如下游戏：
初始化 挑战者Ｃ设置安全参数δ，输出主密钥ｓ和系统参数ｐａｒｍ并发送ｐａｒｍ给ＡＯ。
第一阶段 本阶段敌手ＡＯ适应性地向挑战者Ｃ做一系列查询，具体描述如下：
ＵＰＫ Ｑｕｅｒｙ：当ＡＯ提交实体ＩＤｉ时，Ｃ返回ＩＤｉ
的公钥ＲＩＤｉ
。ＳＫ Ｑｕｅｒｙ：当ＡＯ提交ＩＤｉ时，Ｃ返回ＩＤｉ
的私钥ｄＩＤｉ
。ｄＩＢＳＡＥ Ｑｕｅｒｙ：ＡＯ提交元组（ＩＤＳ，ＩＤＲ，ＩＤｄＳ
，ｗ）时，Ｃ返回发送者为ＩＤＳ，接收者为ＩＤＲ，指定验证者为ＩＤｄＳ的关于关键词ｗ的关键词密文Ｃｗ
。ＴＤ Ｑｕｅｒｙ：当ＡＯ提交元组（ＩＤＳ，ＩＤＲ，ＩＤｄＳ
，ｗ）时，Ｃ返回发送者为ＩＤＳ，接收者为ＩＤＲ，指定验证者为ＩＤｄＳ的关于关键词ｗ的搜索陷门Ｔｗ
。挑战 ＡＯ提交元组（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ
ｄＳ，ｗ０
，ｗ１（≠ｗ０）），条件是ＡＯ没有在第一阶段中对ＩＤ
ｄＳ
做ＳＫ Ｑｕｅｒｙ。Ｃ随机选择ω∈｛０，１｝，返回对应实
体关于关键词ｗω的关键词密文Ｃ ｗω
。第二阶段 ＡＯ继续进行一系列第一阶段的各
项操作，条件是ＡＯ不能对ＩＤ
ｄＳ做Ｓ
Ｋ Ｑｕｅｒｙ。猜测 敌手ＡＯ提交ω′，若ω′＝ω，则称敌手ＡＯ在游戏１
中获胜。敌手ＡＯ在游戏１
中的优势被定义为：ＡｄｖＣＩＮＤ－ＫＧＡ
ＡＯ
兔毛纱线＝｜Ｐｒ［ω′＝ω］－１
２
｜。游戏２ （针对ＡＩ的ＣＩＮＤ ＫＧＡ）挑战者Ｃ与ｄＩＢＳＡＥ中的敌手ＡＩ进行如下游戏：
初始化 挑战者Ｃ设置安全参数δ，输出主密钥ｓ和系统参数ｐａｒｍ并发送ｐａｒｍ给ＡＩ
。第一阶段 本阶段敌手ＡＩ适应性地向挑战者Ｃ做一系列如游戏１中ＡＯ可做的查询。
挑战 ＡＩ提交元组（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ ｄＳ，ｗ０
，ｗ１（≠ｗ０
）
），条件是：１）ＡＩ没有对ＩＤｉ∈｛ＩＤ Ｓ，ＩＤ Ｒ｝
进行ＳＫ Ｑｕｅ ｒｙ。
２）ＡＩ没有对（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ ｄＳ，ｗｉ
）（ｉ＝０，１）进行ＴＤ Ｑｕｅｒｙ。
Ｃ随机选择ω∈｛０，１｝，返回对应实体关于关
键词ｗω的关键词密文Ｃ
ｗω
。第二阶段 ＡＩ继续进行一系列第一阶段的各项操作，条件是：
１）ＡＩ不能对ＩＤｉ∈｛ＩＤ Ｓ，ＩＤ
Ｒ｝
进行ＳＫ Ｑｕｅ ｒｙ。
２）ＡＩ不能对（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ ｄＳ，ｗｉ
）（ｉ＝０，１）进行ＴＤ Ｑｕｅｒｙ。
猜测 敌手ＡＩ提交ω′，若ω′＝ω，则称敌手ＡＩ在游戏２
中获胜。敌手ＡＩ在游戏２
中的优势被定义为：ＡｄｖＣＩＮＤ－ＫＧＡＡＩ
＝｜Ｐｒ［ω′＝ω］－１
２
｜。定义３ （ＴＩＮＤ ＫＧＡ）没有多项式时间敌手ＡＯ和ＡＩ可以以不可忽略的优势赢得以下游戏，则称一个ｄＩＢＳＡＥ方案满足ＴＩＮＤ ＫＧＡ。
游戏３ （针对ＡＯ的ＴＩＮＤ ＫＧＡ）挑战者Ｃ与ｄＩＢＳＡＥ中的敌手ＡＯ进行如下游戏：
初始化 同游戏１。第一阶段 同游戏１。
８
５ 贵州师范大学学报（自然科学版） 第４０卷
挑战 ＡＯ提交元组（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ
ｄＳ，ｗ０
，ｗ１（≠ｗ０）），条件是ＡＯ没有在第一阶段中对ＩＤ
ｄＳ
做ＳＫ Ｑｕｅｒｙ。Ｃ随机选择ω∈｛０，１｝，返回对应实
体关于关键词ｗω的搜索陷门Ｔ
ｗω
。第二阶段 ＡＯ继续进行一系列第一阶段的各项操作，条件是ＡＯ不能对Ｉ
Ｄ
ｄＳ
做ＳＫ Ｑｕｅｒｙ。猜测 敌手ＡＯ提交ω′，若ω′＝ω，则称敌手ＡＯ在游戏３
中获胜。敌手ＡＯ在游戏３中的优势被定义为：Ａｄｖ
ＴＩＮＤ－ＫＧＡ
ＡＯ
＝｜Ｐｒ［ω
′＝ω］－１
２
｜。游戏４ （针对ＡＩ的ＴＩＮＤ ＫＧＡ）挑战者Ｃ与ｄＩＢＳＡＥ中的敌手ＡＩ进行如下游戏：
初始化 同游戏２。第一阶段 同游戏２。
挑战 ＡＩ提交元组（ＩＤ Ｓ
，ＩＤ Ｒ
，
柴草气化炉
ＩＤ ｄＳ
，ｗ０，ｗ１
（≠ｗ０
）），条件是：１）ＡＩ没有在第一阶段中对ＩＤｉ∈｛ＩＤ
Ｓ
，ＩＤ Ｒ
｝做ＳＫ Ｑｕｅｒｙ。
２）ＡＩ未对（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ ｄＳ，ｗｉ
）（ｉ＝０，１）进行ｄＩＢＳＡＥ Ｑｕｅｒｙ或ＴＤ Ｑｕｅｒｙ。
Ｃ随机选择ω∈｛０，１｝，返回对应实体关于关
键词ｗω的搜索陷门Ｔ
ｗω
。第二阶段 ＡＩ继续进行一系列第一阶段的各项操作，条件是：
１）ＡＩ不能对ＩＤｉ∈｛ＩＤ Ｓ，ＩＤ
Ｒ｝做ＳＫ Ｑｕｅｒｙ。２）ＡＩ不能对（ＩＤ Ｓ，ＩＤ Ｒ，ＩＤ ｄＳ，ｗｉ
）（ｉ＝０，１）进行ｄＩＢＳＡＥ Ｑｕｅｒｙ或ＴＤ Ｑｕｅｒｙ。
猜测 敌手ＡＩ提交ω′，若ω′＝ω，则称敌手ＡＩ在游戏４
中获胜。敌手ＡＩ在游戏４
水稻脱粒机中的优势被定义为：ＡｄｖＴＩＮＤ－ＫＧＡ
ＡＩ
＝｜Ｐｒ［ω′＝ω］－１
２
｜。３ 方案描述
３ １ 具体方案
（１）Ｓｅｔｕｐ（δ）：输入安全参数δ，ＰＫＧ选择Ｆｐ
上的一个大素数ｑ阶加性循环Ｇ和Ｇ的一个生
成元Ｐ。ＫＧＣ随机选择ｍｓｋ＝ｓ∈Ｚ ｑ作为主密钥，
计算系统公钥Ｐ０＝ｓＰ，选择４个安全的哈希函数：
ｈ０：Ｚ ｑ×Ｇ→Ｚ
ｑ，
ｈ１：Ｚ ｑ×Ｚ ｑ×Ｚ ｑ×Ｇ×Ｚ ｑ→Ｚ ｑ，
ｈ２：Ｇ×Ｚ ｑ×Ｚ ｑ×Ｚ ｑ×Ｇ×Ｚ ｑ→Ｚ
ｑ，ｈ３：Ｇ×Ｚ ｑ×Ｚ ｑ×Ｚ ｑ×Ｇ→Ｚ ｑ，公布系统参数ｐａｒｍ＝（δ，ｑ，Ｇ，Ｐ，Ｐ０，ｈ０，ｈ１
，ｈ２，ｈ３
）。（２）ＵｓｅｒＫｅｙＧｅｎ（ｐａｒｍ，ＩＤｉ
）：输入元组（ｐａｒｍ，ＩＤｉ），ＰＫＧ随机选择ｒＩＤｉ∈Ｚ
ｑ，计算ＩＤｉ的公钥ＲＩＤｉ
＝ｒＩＤｉＰ和私钥ｄＩＤｉ＝ｒＩＤｉ＋αＩＤｉ·ｓ，其中αＩＤｉ＝ｈ０（ＩＤｉ，ＲＩＤｉ）。ＰＫＧ公布ＲＩＤｉ并通过安全信道发送ｄＩＤｉ
给实体ＩＤｉ。（３）ＤＩＢＳＡＥ（ｐａｒｍ，ＩＤＳ，ｄＩＤＳ，ＩＤＲ，ＲＩＤＲ
，ＩＤｄＳ，ＲＩＤｄＳ，ｗ）：输入元组（ｐａｒｍ，ＩＤＳ，ｄＩＤＳ，ＩＤＲ，ＲＩＤＲ，ＩＤｄＳ，ＲＩＤｄＳ
，ｗ），数据发送者ＩＤＳ做如下操作：１）随机选择ｔ∈Ｚ
ｑ。
２）计算Ｃ１＝ｔ
Ｐ，μ＝ｈ１（ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ｄＩＤＳ（ＲＩＤＲ＋αＩＤＲＰ０），ｗ），ρ＝ｔ（ＲＩＤｄＳ＋αＩＤｄＳＰ０
），Ｃ２＝ｈ２（Ｃ１，ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ρ，μ）。３）输出关键词密文Ｃｗ＝（Ｃ１，Ｃ２
）。（４）Ｔｒａｐｄｏｏｒ（ｐａｒｍ，ＩＤＳ，ＲＩＤＳ，ＩＤＲ，ｄＩＤＲ
，ＩＤｄＳ，ＲＩＤｄＳ，ｗ′）：输入元组（ｐａｒｍ，ＩＤＳ，ＲＩＤＳ，ＩＤＲ，ｄＩＤＲ，ＩＤｄＳ，ＲＩＤｄＳ
，ｗ′），数据接收者ＩＤＲ做如下操作：１）随机选择ｌ１，ｌ２∈Ｚ
防尘服ｑ。
２）计算Ｔ１＝ｌ１Ｐ，ρ′＝ｌ１（ＲＩＤｄＳ＋αＩＤｄＳＰ０），μ′＝ｈ１（ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ｄＩＤＲ（ＲＩＤＳ＋αＩＤＳＰ０），ｗ′），Ｔ２＝ｌ２ｈ３（Ｔ１，ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ρ′），Ｔ３＝ｌ２＋μ′。３）输出搜索陷门Ｔｗ′＝（Ｔ１，Ｔ２，Ｔ３
）。（５）ＭａｔｃｈＴｅｓｔ（ｐａｒｍ，ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ｄＩＤｄＳ
，Ｃｗ，Ｔｗ′）：输入元组（ｐａｒｍ，ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ｄＩＤｄＳ，Ｃｗ，Ｔｗ′）指定服务器ＩＤｄＳ做如下操作：
１）计算ｈ＝ｈ３（Ｔ１，ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ｄＩＤｄＳＴ１
），θ１＝ｄＩＤｄＳＣ１
，θ２＝Ｔ３－Ｔ２ｈ－１
。２）验证Ｃ２＝ｈ２（Ｃ１，ＩＤＳ，ＩＤＲ，ＩＤｄＳ，θ１，θ２
）是否成立。若等式成立，输出结果＂１＂，否则，输出结果＂０＂。３ ２ 正确性
θ１＝ｄＩＤｄＳＣ１＝（ｒＩＤｄＳ＋αＩＤｄＳｓ）ｔＰ＝ｔ（ＲＩＤｄＳ
＋αＩＤｄＳＰ０）＝ρ，ｄＩＤｄＳＴ１＝（ｒＩＤｄＳ＋αＩＤｄＳｓ）ｌ１Ｐ＝ｌ１（ＲＩＤｄＳ＋αＩＤｄＳＰ０）＝ρ′，ｄＩＤＲ（ＲＩＤＳ＋αＩＤＳＰ０）＝ｄＩＤＲｄＩＤＳ
Ｐ＝ｄＩＤＳ（ＲＩＤＲ＋αＩＤＲ
Ｐ０），θ２＝Ｔ３－Ｔ２ｈ－１
＝μ′。易知，当ｗ′＝ｗ时Ｃ２＝ｈ２（Ｃ１，ＩＤＳ，ＩＤＲ，ＩＤｄＳ
，θ１，θ２
）成立，因此本方案是正确的。９
５ 第３期胡震宇，邓伦治，高 岩，等：一个指定验证者的基于身份可搜索认证加密方案
４ 安全性证明
定理１ 在ＤＤＨ问题下，新方案满足ＣＩＮＤ ＫＧＡ，该定理将分引理１和引理２在标准模型下证明。
引理１ ＡＯ是ｄＩＢＳＡＥ中的外部敌手，假设ＡＯ
可以以一个不可忽略的优势ε在游戏１中获胜，则Ｃ可以以优势ε′＝
ε
ＱＵ
解决ＤＤＨ问题，其中ＱＵ为ＵＰＫ Ｑｕｅｒｙ的次数。
证明 假设有一个ＤＤＨ问题的元组（Ｐ，ａＰ，ｂＰ，Ｘ），Ｃ将在游戏１中担当挑战者来判断Ｘ＝ａｂＰ是否成立。
初始化 输入安全参数δ，Ｃ通过Ｓｅｔｕｐ算法
生成主密钥ｓ和系统参数ｐａｒｍ＝（δ，ｑ，Ｇ，Ｐ，Ｐ０，ｈ０，ｈ１，ｈ２，ｈ３）然后发送系统参数ｐａｒｍ给ＡＯ。
第一阶段 Ｃ对ＡＯ所做的一系列如下操作进行回应。在Ａ的每一次其他查询前都需要进行ＵＰＫ Ｑｕｅｒｙ。Ｃ维护几张初始为空的列表来存储查询和回复（该要求在本节均适用）。
ＵＰＫ Ｑｕｅｒｙ：Ｃ维护元组形式为（ＩＤｉ，ｒＩＤｉ，ＲＩＤｉ
）的列表ＬＵ，当ＡＯ输入ＩＤｉ时，Ｃ在列表ＬＵ中查（ＩＤｉ，ＲＩＤｉ）并返回ＲＩＤｉ。如果没有对应条目，Ｃ做如下操作：
１）在第ｊ次创建条目时，Ｃ添加（ＩＤｊ
，⊥，ａＰ）到ＬＵ。
２）ＩＤｉ≠ＩＤｊ时，Ｃ随机选择ｒＩＤｉ
∈Ｚ
ｑ
，计算ＲＩＤｉ＝ｒＩＤｉＰ，添加（ＩＤｉ，ｒＩＤｉ，ＲＩＤｉ
）到ＬＵ。ＳＫ Ｑｕｅｒｙ：当ＡＯ提交ＩＤｉ时，若ＩＤｉ＝ＩＤｊ
，游戏中止。否则，Ｃ通过调用ＵｓｅｒＫｅｙＧｅｎ算法返回ｄＩＤｉ
给ＡＯ。ｄＩＢＳＡＥ Ｑｕｅｒｙ：当ＡＯ提交（ＩＤＳ，ＩＤＲ，ＩＤｄＳ，ｗ），Ｃ调用ｄＩＢＳＡＥ算法得到Ｃｗ并将其返回给ＡＯ。
ＴＤ Ｑｕｅｒｙ：当ＡＯ提交（ＩＤＳ，ＩＤＲ，ＩＤｄＳ
，ｗ），Ｃ调用Ｔｒａｐｄｏｏｒ算法得到Ｔｗ并将其返回给ＡＯ。
挑战 ＡＯ输出满足游戏１要求的元组（ＩＤ
Ｓ，ＩＤ Ｒ，ＩＤ ｄＳ，ｗ０，ｗ１（≠ｗ０））。如果ＩＤ
ｄＳ＝ＩＤｊ
，Ｃ随机选择ω∈｛０，１｝并进行如下操作。否则，Ｃ失败并停止。
１）在列表ＬＵ中出（ＩＤ Ｓ，ｒＩＤ Ｓ，ＲＩＤ Ｓ
），（ＩＤ
Ｒ，ＲＩＤ Ｒ
）和（ＩＤｊ，ａＰ）。２）计算
αＩＤ Ｓ＝ｈ０（ＩＤ
Ｓ
，ＲＩＤ Ｓ），αＩＤ Ｒ＝ｈ０（ＩＤ Ｒ
，ＲＩＤ Ｒ
），αＩＤｊ＝ｈ０（ＩＤｊ，ａＰ），ｄＩＤ Ｓ＝ｒＩＤ Ｓ＋αＩＤ Ｓ
ｓ。３）令Ｃ
１＝ｂＰ，计算ρ＝Ｘ＋αＩＤｊ勇猛的圣灵肩垫
ｓｂＰ，μ＝ｈ１（ＩＤ Ｓ，ＩＤ
Ｒ，ＩＤｊ，ｄＩＤ Ｓ（ＲＩＤ Ｒ＋αＩＤ ＲＰ０），ｗω），Ｃ ２＝ｈ２（Ｃ １，ＩＤ Ｓ，ＩＤ
Ｒ，ＩＤｊ，ρ，μ）。４）输出密文Ｃ ｗω
＝（Ｃ １，Ｃ ２）。第二阶段 ＡＯ可以在满足游戏１要求的情况下重新进行第一阶段中的各项查询。
猜测 ＡＯ输出ω′，如果ω′＝ω，则称ＡＯ在游戏１中获胜。
解决ＤＤＨ问题 如果ＡＯ获胜Ｃ输出＂１＂，否则输出＂０＂。如果Ｘ＝ａｂＰ，有
ρ＝Ｘ＋αＩＤｊｓｂＰ＝ｂ（ａＰ＋αＩＤｊＰ０
）＝ｂ（ＲＩＤ ｄＳ＋αＩＤ ｄＳＰ０
）。因此Ｃ
ｗω
是一个有效的密文，而ＡＯ赢得游戏１的优势为ε，所以
Ｐｒ［Ｃ→１｜Ｘ＝ａｂＰ］＝Ｐｒ［Ｃ→１｜ω′＝ω］＝１
２
＋ε。由于Ｃ
ｗω
的各部分在ω＝０或ω＝１时的分布相同，所以ＡＯ没有除猜测外的额外优势去区分ω，即：
Ｐｒ［Ｃ→１｜Ｘ≠ａｂＰ］＝Ｐｒ［ω′＝ω｜Ｘ≠ａｂＰ］＝１２
。概率分析令ＱＵ，ＱＳＫ分别为ＵＰＫ Ｑｕｅｒｙ，ＳＫ Ｑｕｅｒｙ的次数，一些事件定义如下：
Ｅ１：ＡＯ没有对ＩＤｊ进行Ｓ
Ｋ Ｑｕｅｒｙ。Ｅ２：ＩＤ ｄＳ＝ＩＤｊ
。Ｐｒ［Ｅ１
］＝ＱＵ－ＱＳＫ
ＱＵ
，Ｐｒ［Ｅ２｜Ｅ１］＝１
ＱＵ－ＱＳＫ
，
Ｐｒ［ＣＳｕｃｃｅｓｓ］＝Ｐｒ［Ｅ１Ｅ２］＝Ｐｒ［Ｅ１］Ｐｒ［Ｅ２｜Ｅ１
］＝
１
ＱＵ
。因此，ＡＯ如果可以在游戏１中以不可忽略的优势ε获胜，则Ｃ可以判断等式Ｘ＝ａｂＰ是否成立的优势为ε′＝
ε
ＱＵ
。引理２ ＡＩ是ｄＩＢＳＡＥ中的内部敌手，假设ＡＩ
可以以一个不可忽略的优势ε在游戏２中获胜，则Ｃ可以以优势ε′＝
２ε
ＱＵ（ＱＵ－
１）解决ＤＤＨ问题，
其中ＱＵ为Ｕ
ＰＫ Ｑｕｅｒｙ的次数。证明 假设有一个ＤＤＨ问题的元组（Ｐ，ａＰ，
０
６ 贵州师范大学学报（自然科学版） 第４０卷
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议