 Computer Science and Application 计算机科学与应用, 2013, 3, 127-133 http://dx.doi.org/10.12677/csa.2013.32022 Published Online April 2013 (http://www.hanspub.org/journal/csa.html) Oblivious Fuzzy Keyword Search Based on Blind GDH Signature* Fei Han, Jing Qin# School of Mathematics, Shandong University, Jinan Email: hanf1987@163.com, #qinjing@sdu.edu.cn Received: Feb. 11th, 2013; revised: Mar. 1st, 2013; accepted: Mar. 16th, 2013 Copyright © 2013 Fei Han, Jing Qin. This is an open access article distributed under the Creative Commons Attribution License, which permits unre- stricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: As Cloud Computing becomes prevalent, data privacy has been a bottleneck of Cloud Computing. When using Cloud Computing, users need to implement a large amount of data search. So the security of search is a key point of protecting user’s data privacy. This paper mainly concentrates on the searchable encryption scheme. In order to guarantee the security property, a user needs to hide the keywords and the files he/she wants to search. In 2004 Wakaha Ogata and Kaoru Kurosawa proposed a secure searchable encryption scheme, named as oblivious keyword search (OKS), based on Chaum’s blind signature. However we find their scheme connecting only one keyword with the data file that is encrypting the data file with its keyword. And then if a data file con tains several keywords, we need to repeat the encryption with every keyword. Th is is quite inefficient. We solve th is problem by constructing a new OKS scheme from blind signature based on GDH assumption and connect data files with all its possible keywords. Furthermore, when users are searching by keywords, they might fail to get the desire data files, owing to mismatching the exact key- words. Aiming to solve this problem, we extend our scheme to an oblivious fuzzy keyword search (OFKS) scheme, allowing a user securely search data files through fuzzy keywords. Compare to the original scheme, our scheme pos- sesses more practicality and has been fuzzy keyword supported. Keywords: Blind GDH Signature; Oblivious Transfer Protocol; Oblivious Keyword Search; Fuzzy Keyword ; Oblivious Fuzzy Keyword Search 基于盲 GDH 签名的无记忆模糊关键词搜索* 韩 斐，秦 静# 山东大学数学学院，济南 Email: hanf1987@163.com, #qinjing@sdu.edu.cn 收稿日期：2013 年2月11 日；修回日期：2013 年3月1日；录用日期：2013 年3月16 日 摘 要：在云计算中，用户在计算过程中的数据安全问题已经成为制约云计算发展的一个瓶颈。本文针对云计 算中的加密搜索问题，提出一个有效的加密搜索方案。在搜索过程中，为保证用户的数据安全，用户需要隐藏 搜索的关键词以及搜索返回的结果。Wakaha Ogata和Kaoru Kurosawa在2004 年提出了一个基于盲 RSA 签名的 无记忆关键词搜索(OKS)方案，提供了安全的加密搜索，然而该方案中每个数据文件只能关联一个关键词。本文 改进了原方案，我们的方案基于盲 GDH 签名，同时使无记忆关键词搜索方案可以在一个数据文件中同时关联多 个关键词供用户搜索。此外，用户在搜索的过程中，可能因为关键词不能完全匹配而导致搜索失败，针对这一 问题我们将该方案扩展为无记忆模糊关键词搜索(OFKS)方案，使得用户能够对模糊关键词进行正确且安全的搜 索操作.相比较原来的方案，我们的方案提供了更有效的搜索方式及对模糊关键词搜索的支持。 *基金项目：国家自然科学基金面上项目(61272091)，山东省自然科学基金一般项目(ZR2012FM005，ZR2011FL027，Y2007A13)。 #通讯作者。 Copyright © 2013 Hanspub 127  基于盲 GDH 签名的无记忆模糊关键词搜索 Copyright © 2013 Hanspub 128 关键词：盲GDH 签名；OT 协议；无记忆关键词搜索；模糊关键词；无记忆模糊关键词搜索 1. 引言 在当今信息急速膨胀的时代，尽管计算机的处理 速度发展很快，但仍然不能满足人们对大量数据进行 高速处理的需求。由此，出现了云计算服务。这满足 了人们对于高速处理大量数据的要求。然而，云计算 还存在很多的安全隐患和实施限制。[1]阐述了云计算 在实施和发展过程中需要克服的十大困难。这里，我 们致力于解决云计算中的保密问题。众所周知，用户 在海量的数据中进行计算需要进行大量的搜索操作。 基于安全性考虑，用户不能泄露搜索使用的关键词及 搜索结果，同时服务器也不允许用户得到除搜索信息 之外的其他信息。因此我们需要一个安全的加密搜索 方案以保证两方的安全性。 目前出现的加密搜索方案分为基于公共数据库 和秘密数据库两种情况。基于秘密数据库的加密搜索 方案，存在分别基于公钥和私钥的加密搜索方案。例 如，[2]提出了基于公钥加密的搜索方案——带关键词 搜索的公钥加密(PEKS)，该方案以一个邮件系统为实 例，发送方在发送邮件的同时发送对应关键词的公钥 加密密文 PEKS 以供接收方搜索，接收方生成需搜索 的关键词的陷门信息。最后运行验证算法，从而得到 搜索的结果。但是该方案的安全实施必须建立在发送 方诚实的建立关键词的 PEKS的基础上。如果发送方 为了其非法目的，私自篡改对应邮件的关键词，则接 收方无法正确的完成搜索操作。[3,4]提出了基于私钥 加密的加密搜索方案。在[3]的协议中，用户将已加密 的数据上传到服务器中，同时给出了对应关键词在文 档中可能出现的位置。随后，用户使用搜索方案进行 顺序扫描，得到所需的搜索结果。该方案的局限性在 于，用户将数据上传给服务器以备以后使用，而不是 服务器持有原始数据。同时，用户还泄露了一些信息 给服务器，如某关键词可能出现的位置。同时，许多 更贴近于实际的搜索方案也被提出了，如[5]提出了安 全且高效的排序搜索方案，该协议通过引入一个一对 多保序映射实现了搜索结果的排序功能，同时加入了 相关性检测机制，排序结果的验证机制等功能。[6] 将连接词的搜索引入到了可搜索加密中，使用户可以 进行多关键词搜索。 对于公共数据库中的安全搜索方案，[7]给出了一 个经典的搜索方案——私有数据检索(PIR)。该方案 中，用户在两个乃至多个均保存有数据文件的数据库 中同时进行搜索操作以保证搜索的保密性。这样可以 保证用户搜索过程和返回结果的安全性。然而在搜索 过程中，服务器的安全性没有得到保证，通过搜索， 用户可能得到多于所需数据的额外信息。同时，该方 案需多个服务器同时持有副本，这也限制了方案的实 用性。[8 ]对PIR 进行了一系列的改进和完善，通过错 误校验码的解码算法有效的提升了协议的效率和鲁 棒性。 L L. Xu等[9]引入属性的概念构造了具有访问控 制功能的 OT 协议，增强了 OT 协议服务器方的控制 能力，增强了协议的灵活度。W. Ogata等[10]提出了根 据OT 协议构造了一个可行的安全加密搜索方案—— 无记忆关键词搜索(OKS)。该方案使用盲RSA 签名以 及OT 协议构造了一个安全的加密搜索方案，在搜索 过程中，服务器对每个文件与相关关键词的签名数据 进行异或，一起发送给用户，用户对需搜索的关键词 进行随机化操作，发送给服务器，服务器对接收的数 据签名后返回给用户，用户进行解随机化操作，得到 对应关键词的签名，随后进行匹配操作得到搜索的文 件。该方案保证了用户和服务器的安全性。然而，该 方案存在一定的局限性，在加密过程中，每个密文仅 支持一个关键词的加密搜索。若一个文件存在多个关 键词，须对该文件进行多次加密。显然，大多数文件 都不仅仅存在一个关键词。该方案采用了盲 RSA 签 名方案，在该方案中，用户必须选择一个公钥 e大于 模数 n或者保证(n, e) = 1。 本文采用盲 GDH 签名作为搜索过程中的盲化方 案，盲 GDH 签名没有上述盲 RSA 签名的安全问题， 同时在相同的安全要求下，盲 GDH 签名的签名长度 小于盲 RSA 签名的签名长度，这将有效的提高本协 议的效率。本文提出的 OKS 协议将一个文件与它的 多个关键词整合在一起，使用户可以搜索这个文件中 的所有关键词，以验证是否为需要的文件，提高了用 户的搜索能力。用户在执行搜索操作时，可能因输入 错误或无法确定要搜索的确切关键词，导致所要搜索  基于盲 GDH 签名的无记忆模糊关键词搜索 的关键词没有包含在服务器保存的关键词集合中，最 终搜索失败。本文根据[11]中的模糊关键词搜索算法， 使用“编辑距离”定义了一个模糊关键词构造算法， 在所提出的 OKS 协议的基础上构造了一个无记忆模 糊关键词搜索(OFKS)协议，进一步增强了协议的搜索 能力。 2. 预备知识 2.1. 盲GDH签名 2.1.1. GDH 在这里我们使用 GDH 的变体 co-GDH[12]。下面 简要阐述 co-GDH，详见[12]。 令，为两个 阶循环群 1 G2 GP g 。其中 g1为 的生成元，g2为 的生成元。 1 G 2 G 为 到的同构映 射，有 1 G2 G 12 g g 。存在以下两个计算困难问题： Computational co-Diffie-Hellman (co-CDH) prob- lem on G1，G2：给定22 2 ,a g gG， 作为输入， 计算 。 1 hG 1 a hG Decisional co-Diffie-Hellman (co-DDH) problem on G1，G2：给定 22 2 ,a g gG ， 作为输入，若 ，则输出 1，否则输出 0。当输出为 1时，我们 称 1 ,b hh G ab 22 ,,, ab g ghh是一个 co-Diffie-Hellman 四元组。 我们称一个循环群对 ，为一个(τ,t,ε)-Gap co-Diffie-Hellman 群对(co-GDH group pair)，若满足以 下条件： 1 G2 G 1) ，的计算及 到的映射 1 G2 G1 G2 G 可以在最 多τ时间内完成。 2) 上的 co-DDH 问题可以在最多 τ的时 间内解决。 12 ,GG 3) 不存在算法可以 , -解决 ，上的 co-CDH 问题。 1 G2 G 当是一个 12 ,GG ,,t -Gap co-Diffie-Hellman 群对时，我们称 是一个 1 G ,,t -Gap co-Diffie- Hellman群(GDH gr oup)。 2.1.2. 盲签名 盲签名是签名方案的重要组成部分。用户通过选 取一个随机数将数据随机化后发送给签名者，签名者 对该数据签名后返回给用户，用户通过“解随机化” 还原出所需的数据签名。在这一过程中，签名者除了 得到了一个有效的签名外，无法获得任何其他的信 息，由此保证了用户的数据安全。最早的签名方案是 由Chaum 提出的基于 RSA 的签名方案[13]。在[12]中 Boneh 等给出了一个基于 co-GDH 的盲签名方案。方 案如下： 12 ,GG 是一个 ,,t -Gap co-Diffie-Hellman群 对。 12 GGp 1 :0,1 。签名 σ是G1的一个元素。 H G 是一个全域 Hash 函数。 该方案由五个算法组成。 1) 密钥生成算法：随机选取 R p x Z ，计算 2 x y g。公钥是 2 yG 。私钥是 x 。 2) 随机化消息算法：用户选择要签名的消息 M ， 选择随机数 R p rZ ，计算 r M HM g 。 3) 签名算法：给定一个 p x Z，签名者接受消息 0, 1M ， x M 。得到的签名就是 ，发送 给用户。 4) 解随机化算法：用户收到 ，计算 r y ， 并输出签名对 ,M 。 验证算法：对于公钥 ， 2 yG 0,1M ，签名 1 G ，计算 M1 GhH ，验证 2,,,gyh 是一 个有效的 co-GDH 四元组。若成功，则签名有效，否 则签名失败。 2.1.3. GDH的安全性 [14]中给出了关于 ct-CDH 问题及假设的定义如 下： 定义 1：Chosen-target Com putati onal Diffie-Hellm an (ct-CDH)问题和假设： ct-CDH 问题：令 G为一个 阶群， p R p x Z ， x y g :0,1H ，从 Hash 函数族中随机选取一个 Hash函数 。敌手 B持有 ，并可以访问 随机预言机，可以得到上的随机点 以及加密预 言机 G G T ,,H,pgy Gi z x 。令q别为 B访问随机预言机和加密预 言机的次数。 , tH q分 B攻击 ct-CDH 问题的优势 ct-CDH G A DVB 定义为 以下事件的概率：B通过访问 次随机预言机和 t q H q次 加密预言机后 H t qq il 。成功输入了 1个有效的签名， 及生成了一个元素的集合Vv ，其中， 对所有的1 11 ,,,, ll j vj 1，有，使 得 i jt i q x ij vz，各 不相同。 i v ct-CDH 假设是指不存在多项式时间能力的敌手 Copyright © 2013 Hanspub 129  基于盲 GDH 签名的无记忆模糊关键词搜索 B能够以不可忽略的优势 ct-CDH G A DVB 解决 ct-CDH 问 题。在此，GDH 问题就包含在 CDH问题中，所以我 们可以将 GDH的安全性规约到 ct-CDH问题的安全性 上。 定义 2：我们称 ct-CDH 问题是困难的，若对于 具有多项式时间计算能力的敌手B，它的优势 ct-CDH G A DVB 是可忽略的。 定理 1：如果在群 G上的ct-CDH 问题是困难的， 则G上的 GDH 问题也是困难的，那么我们称 GDH 盲签名是安全的，即可以抵抗选择消息攻击下的再一 次伪造攻击。 3. 无记忆关键词搜索(OKS) 我们将提出一个基于盲GDH 签名的 OKS 协议， 该协议使得用户可以搜索一个文档中的所有关键词。 我们假设服务器持有一些保密数据供用户进行关键 词搜索。为保证安全性，用户不允许服务器知晓自己 要搜索的关键词和返回的数据文件。 一个是一个服务器 S和用户U之间的两方 协议。在这个协议中，用于与服务器在由 n个数据组 成的数据库集合中进行k次搜索。令 为保密 数据集合，W为保密数据中关键词的集合，对于每个 数据文件 ，其包含的关键词集合为 n k OKS i c 1,, n cc 12 ,, ii ww W 。 承诺阶段，S承诺了n个数据 ，其中 ，在这一阶段，服务器须根据 i 生成一个随机数，以保证 被安全加密。 1,, n BB 12 ,, , ii i Bww c i p i i c 传输阶段，包括 k次传输。每次传输过程中，U 选择关键词 ，通过交互式运算得到 。其中定义 l w 1lk Search l w Search i lj wiww w 。 选择阶段，用户 U根据传输阶段返回的 ，与 服务器S进行一个基于 协议的 交互操作，即，S持有 n个数据 ，U持有 i， 执行协议，从 S中获取 ，而对其他 Searchi 1n OT 1n OT p ,ij p 1,, n p i pi ，同 时，S不能获取 i的值，然后解密得到需要的搜索结 果 。 i c 在这一过程中，用户没有得到额外的信息，而数 据提供者也不能得到关于关键词 的信息。更 形式化的定义协议的安全性如下： 1,, k ww 用户的安全性：我们称该协议对于用户是安全 的，若对于任意恶意的数据提供方 ， S 11 ,, ,, kk ww ww ， 对 ， S1,, k ww 1,, k ww运行的视图计算不可区分的。 数据提供方的安全性：引入一个理想情况Ideal World 与实际情况 Real Wo rld进行对比。理想情况中， 有一个可信第三方(TTP)收到 1,, n B B。然后将用户 的搜索结果 Search l w 返回给用户。 定义 3：我们称一个协议对于数据库是 l -安全 的，若对于任意恶意用户 U，存在一个模拟器 A在Ideal World 中充当用户的角色，使得对于任意多项式时间 区分器 D， output1PslrD' output1AsPr 'DU 若 l 是一个可忽略函数，则这个协议对于数据库是 安全的。 定义 4：我们称一个 协议是安全的，若该 协议对于用户和服务器都是安全的。 n k 1 ,, ,IpgHG OK S 3.1. 基于盲 GDH 签名的 OKS 协议 令G为一个伪随机数生成器，H1，H2为两个 Random Oracle。全局信息 ， 由服务 器私有，私钥 2 H s kx ，公钥 ， 1 ,, ,,p g HGy pk x y g 。 承诺阶段：对于 中的每个关键词 i ci j w，计算 1 j x i ij K Hw，同时选择一个 Hash 函数2 H ，计算 in 2i pHi1 发送给 ，生成 ，随后对所有 的文件进行承诺，计算 12 || |||| iiiii EGpcKK ， 传输阶 1,, n pp 用户收到 将12 ,,EE 后， , n E用户。 段：第 l次传输中， 12 ,,, n EE E 选择一个随机数 R p rZ ，对于要搜 l w 索的关键词 ，计算 r 1 ll K Hw g ，将 l K 发送给服务器。服 计算 l 务器 x ll x 1r K K Hwy ，将 l K 发送给用户。 用户计算 r ll K Ky ，得到关于l w的签名l K 。将 收 到的 i EE|| i K 拆分 12 ,, i ，得到对应每个i c的所有关键词 的签名，使用 li KK K 进行匹配，对于任意的i， 若 j li K K 定需要的文件为i c，并得到密文 i E，则确 。 段：引入一个安全的1n O协议，用户与服选择阶 务器 T 服务器 进行安全的交互运算。用户将所需文件的序号i 发送给服务器，服务器从生成的 1,, n pp中，选择 i p 发送给用户。由于使用 1n OT 协议， 无法得知用 户需要那个文件，而用户法得到除了 i p之外的其 他文件。用户得到 i p后，计算 i Gp ，进而计算 也无 ii i cEGp 得到模糊关键词匹配件i c。 的文 Copyright © 2013 Hanspub 130  基于盲 GDH 签名的无记忆模糊关键词搜索 Copyright © 2013 Hanspub 131 基于盲 GD 3.2. OKS协议的安全性 每次传输状态返回的 i值正确的概率至 少为 H签名的 OKS 协议框架见图1。 为空。 假设U首次向查询pi。 G 1) 若 mod x K Hw p，则 A随机选择一个 E*， 使得 i EGp x 。 正确性： 1n ，基于 1n OT 的安全性，我们得到搜索正确 2) 若 mod K Hw p，则 2l 的概率至少为 若w在QA-list列表中，则直接运行 4)。否则令 1cnt cnt 。 12l。 n 用户的安 S无法 全性： 得到关于的任何 信息 中被盲 难的 H1查询w，则 A随机选择， 3) 若，则 A将一个随机值赋给1cnt k i Gp。 否则 A向可信第三方(TTP)发出关于w的Search请求， 并得到结果 wSearch ，A将添加到 QA-list 列表中。 ,Searchw w 1,, k ww ，因为这些关键词在盲GDH 方案 化了。 数据库的安全性：我们在假设 ct-CDH 问题是困 情况下使用 Real World/Ideal World方法证明数据 库的安全性。假设存在一个恶意用户U ，U 向S提出 k次查询请求，在 Ideal World中假设存在一个模拟器 A。承诺阶段，A生成 12 ,, ,,,pgH Hyx，并将1 ,, ,pgH y发 送给U ，同时，A随机 , n E，也 。 传输阶段， A进行与 S相同后 A将U 的输 出作为自己的输出。 A模拟 H1：若U 向 生成 12 ,,EE 的操作， 发送给U 最 4) 假定关键词 w已存在于 QA-list 中，即 ,Search -wwQA list。 若 Searchiwi ，则 A设置 ，否 则，A随机选取一个值赋给。 ii GpEc i Gp 令Fail 为的时间。若 Fail不发生，则 A可以很好的模拟 G实现协议运算。而Fail 失败的概 率Pr(Fail)是U能够成功的进行关于盲 GDH 签名的 基于选择明文攻击的再一次伪造攻击的概率。由定理 1，我们知道若 ct-CDH 问题是困难的，则盲GDH 签 名是安全的，从而若ct-CDH 是困难的，则 A的输出 与U的输出是计算不可区分的。这就证明了上述 OKS 安全的。 1cnt k w y 1w y Hw。 H2： A模拟 若向H2查询 i，则 A随机选择 ， 使得 模拟：假设先向 H1，H2提出查询请求， 随后向 U i p 2i pHi。 AG U G发送对 i p的请求。令cnt = 0，QA-list 列表 是 Figure 1. The framework of OKS scheme 图1. OKS协议框架  基于盲 GDH 签名的无记忆模糊关键词搜索 4. 无记忆模糊关键词搜索(OFKS 用户在实施搜索的过程中，不可避免的会出现输 入错误，或不能确定要搜索的确切关键词。因此我们 引入模糊关键词的概念来完善 OKS 协议。我们使用 Edit Distance来定义关键词w的模糊度 d，生成的模糊 关键词集合记为 。Edit Distance指，由字符串A 转换到字符串 B最小的字符操作数，字符操 作包括：在A中增加一个字符，在A中删去一个字符， 将A的某个字符转换成另一个字符。如关键词 word 与关键词 ward d = 1，word 与wrd 的模糊 度也为 d = 1。若时，显然 OFKS 协议即上述的 OKS 协议。假设我们需要搜索关键词word，根据模糊 关键词集合构造算法 见附录)可以生成一个关于 word 的模糊关键词集合 。 然后对生成的关键词集合运行OFKS 协议。 4.1. OFKS协议 协议背景与上述OKS 协议类似。假设服务器持 有秘密数据供用户搜索。秘密数据集合为， 其中每个 中包含的关键词集合为 ) ,wd S 所经过的 的模糊度为 d = 0 ( S word,1 word,ord ,wrd,wod,wor 12 ,,, n cc c 12 ,, ii W i cww ， 每个关键词 i j w 12 ,,w 生成的模糊关键 ，则对于每个 词集合为 ，对应所有关键词 i j w Sw 的模糊关 集合为 ii jj 键词 i c i i ij j cwW 1，H2为两个 G，H2由 w SS 服务器私 。假 Random 有， 设G为一个 Oracle。全 私钥 伪随机数 器， 局信息 1 gH 生成 Ip H ,,, s kx ， 公钥 1 pk H ,y，,,g,Gp x y g ，服务器保留 H2。 承诺阶段：预先协商用户与服务器搜索过程的关 键词的模糊度d。此处我们假设 d = 1，当 d > 1时类 似。服务器使用下述的算法对每个关键词 i j w 于每个 生成相关 的模糊关键词集合 ，对 12 ,, i j ii jj w Swwi j h w计 算 1 x ii jh jh KHw 每个 i，计算i 有的文件进行承诺， ，同时选择一个 Has 2 pHi，生成 1,, hH2于 ，随后 函数 ，对 对所 n pp ii EGp || i K，将 12 ,,,EE 11 || i i K 发送给用 ||c n E 121 2 || |||| ii jj KK 户。 传输阶段：在第 l次传输，用户收到 后，选择一个随机数 12 ,,, n EE E R p rZ 键词构造算法 ，对于要搜索的关键词 算关于 l w l w，使用模糊关 [8]，计 的模 算 糊关键词集合 ，分别计 12 ,, lll wSw r 1lklk K Hw 计算 g，将 lk 12 ,, ll KK 1lk 发送给服务器。服务 器分别 r xx lk K KHwy ， 将所有的 lk K 发送给用户。用户计算 r lk lk K Ky ，得到关于 l w 的 模糊关键词的签名 的 12 ,, ll KK ，将收到 || K ii EE 拆 分得到对应每个才i c 1 , l K 的所有模糊关键词 2 , l 12 ,,, ii KKKK ，用 l w的模糊 11 121 ,,, , iii KK K i jh 关键词的签 , i 进行 名 12 ,, ll KK 与上述的 对于任意的 i，若有 2jj K匹配， lk K K ，则得到需要的文件 i E 。 选择阶段：这 与服务器进行 要得到的数据 i p 选择 i p发送给用 得知用户需要 外其他的文件。 算 里采用一个安全的 互操作。用户提 从生成的 由于使用 1n OT ，而用户也无 i p后，计算 1n OT 协议， 供给服务器 12 ,,,pp 服务器 法得到除了 i Gp ， 用 n p 无法 i p 进而计 户 想 中， 之 安全的交 ，服务器 户。 那个文件 用户得到 协议， i ii cGpE 件i c。 4.2. OFKS的安全性 定理 2：假设 也是安全的。 证明：OFKS 键词的数目， 的安全性证明 5. 总结 本文首先介绍 在承诺和传输阶段 行盲签名，然 需数据文件的 使得用户与服 OT 协议的安全性质 而服务器也无 密的完成加密搜索。 多个关键词整 索。另外，基 词搜索的支持，提 协议，该协议 索，扩展了协 参考文献 [1] A. Fox, R. Grif 得到根据模糊关键词搜索得到的 S协议是安全的， 比OKS 协议 模糊关键词， 证明OFKS 协 了基于盲GDH 签名 户和服务器分 关键词的签名 选择阶段，引 安全的进行交 用户只能得到 户的信息。因 同时，该协议将 ，使用户可以 关联多个关键词的情况下对单个关键词进行加密搜 搜索习惯， 出了关于模糊 的进行对模糊 范围。 ) Above the clouds: A Ber 文 ， 进 所 ， 过 件， 保 的 时 键 S 搜 d OK 协议相 即增加了 同样可以 ，用 后用户对 序号，在 务器可以 ， 法得到用 合在一起 于用户的 能够有效 议的使用 (References fith. 则OKFS 仅仅 此OKS 的安全。 的OKS 别对其关键词 进行匹配得到 了OT 互式运算 对应的文 该协议能够 一个数据文件 在数据文件同 对模糊关 关键词搜索的 关键词的加密 keley view 协议 增加了关 协议 协议 协议 ，通 OK of clou ， 因 议 入 序号 此 增加了 Copyright © 2013 Hanspub 132  基于盲 GDH 签名的无记忆模糊关键词搜索 computing. Technical Report No. UCB/EECS-20 sity of California, Berkeley, 2009, 28. 09-28, Univer- [2] D. Boneh, G. Di Crescenzo, R. Ostrovsky, et al. Public key en- l Co work SecuritSpringer- g, 2005: 442-455. short trapdoor. Intelligence and Securityati9: e, Milwaukee, 23- rg and N. Hlly robust pri X conf mion, 2012: 16. [9] L. L. Xu, F. G. Zhang. Oblivious transfer with threshold access control. Journal of Informa 28(3): [10] W. Ogawa. Oblivious keyword se t0(2): 356-3 aang, et al. Enabliting. . —ASIACRYPT 2. . tracea in Crypto, 1982, 82: 199-2blind an-group signatur ra03, 200 46. cryption with keyword search. In: Advances in Cryptology- Eurocrypt 2004. Berlin/Heidelberg: Springer, 2004: 506-522. [3] D. X. Song, D. Wagner and A. Perrig. Practical techniques for searches on encrypted data. Proceedings of IEEE Symposium on Security and Privacy, Berkeley, 14-17 May 2000: 44-55. [4] Y. C. Chang, M. Mitzenmacher. Privacy preserving keyword searches on remote encrypted data. ACNS’05 Proceedings of the 3rd Internationanference on Applied Cryptography and Net- y, Verlag, Berlin/Heidelber [5] C. Wang, N. Cao, K. Ren, et al. Enabling secure and efficient ranked keyword search over outsourced cloud data. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(8): 1467-1479. [6] Z. Chen, C. Wu, D. Wang, et al. Conjunctive keywords search- able encryption with efficient pairing, constant ciphertext and Informcs, 2012, 729 176-189. [7] B. Chor, O. Goldreich, E. Kushilevitz, et al. Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Scienc25 October 1995: 41-50. [8] C. Devet, I. Goldbeeninger. Optimavate information retrieval. Proceedings of the 21st USENIer- ence on Security syposium, USENIX Associat tion Science and Engineering, 2012, 555-570. ata, K. Kurosarch. Journal of Complexiy, 2004, 271. [11] J. Li, Q. Wng, C. Wng efficient fuzzy keyword search over encrypted data in cloud compu Proceedings of IEEE INFOCOM’10 Mini Conference, San Diego, 2009: 593. [12] D. Boneh, B. Lynn and H. Shacham. Short signatures from the Weil pairingAdvances in Cryptology2001, 2001: 514-53 [13] D Chaum. Blind signatures for unble payments. Advances ptology: Proceedings of Cry03. [14] A. Boldyreva. Threshold signatures, multisignatures and signatures based on the gap-Diffie-Hellme scheme. Public Key Cryptogphy—PKC 202, 2567: 31- Copyright © 2013 Hanspub 133 |