关键字 |
| 对称加密算法，基于排名的搜索，多字符串匹配，相关性评分，隐私保护，云计算。 |
介绍 |
| 云计算是一项不断发展的技术，它改变了IT企业的计算方式。它将软件和数据带到集中的数据中心，在那里，大量用户可以按使用付费来访问信息。这对存储的数据构成了安全威胁。数据机密性可能会受到损害，必须加以注意。因此，在将数据外包给云服务器之前，有必要对数据进行加密。这使得数据利用成为一项具有挑战性的任务。传统的搜索机制提供布尔搜索对加密数据进行搜索，当用户数量和存储在云中的数据文件数量很大时，这种搜索不适用。它们还带来了两个主要问题，一个是用户为了找到所需的相关文档而必须进行的后处理，另一个是当检索所有与关键字匹配的文件时，在当前场景中不希望出现的网络流量。而本文提出的关键词排名搜索，克服了这些问题。 |
| 本文的表述如下。第2节对相关工作进行了总结。建议的系统和架构图将在第3节中介绍。该方案分为加密模块、字符串匹配模块、索引模块和排序模块，这些模块在第3节中也有讨论。第四部分给出了未来想法和建议的要点。 |
相关的工作 |
| 如何使云服务提供商能够高效地在加密文件中搜索关键字，同时为用户提供高效的搜索结果，维护数据隐私，是一个重要的研究问题。我们对以下论文进行了研究。 |
搜索加密云数据的实用技术 |
| 本文讨论了序列扫描搜索技术[1]，该技术可以在不丢失数据机密性的情况下对存储在云端的加密数据进行搜索。该技术可以证明是安全的，并且隔离了查询结果，因此服务器不知道搜索结果之外的任何内容。它还支持服务器控制搜索等功能，用户搜索单词时不向服务器显示它的隐藏查询支持。使用安全的可搜索对称加密[7]和伪随机序列生成机制，可以有效地扫描和搜索加密数据，而不会丢失数据隐私。所提出的方案非常灵活，可以进一步扩展以支持与布尔运算符结合的搜索查询、接近性查询、包含正则表达式的查询、关键字是否存在等。但是，对于需要大量存储空间的大型文档和场景，该技术具有很高的时间复杂性。 |
公钥加密与关键字搜索 |
| Dan Boneh提出了一种搜索使用公钥加密系统[2]加密的云数据的解决方案。其思想是在每个文件中安全地附加或标记相关的关键字。这将避免需要完全解密文件，并节省扫描整个文件以检查关键字是否存在的时间。文件加密采用公钥加密算法[2]，关键字加密采用PEKS算法。检索包含关键字W的文档时，只发送Trapdoor (W)到服务器。他提出了两种构造该格式的方法，一种使用双线性映射，另一种使用雅可比符号。该方案的问题是，必须处理所有文件的每个标记以查找匹配项。 |
布尔对称可搜索加密 |
| 目前讨论的大多数技术都只关注单个关键字匹配，但在实时场景中，用户可能会输入多个单词。Tarik Moataz提出了一个解决方案来解决在加密云数据上搜索多个关键字的挑战。布尔对称可搜索加密(BSSE)[11]的构造主要基于关键字字段的正交化，根据Gram-Schmidt过程。基本的布尔运算是:析取、合取和否定。 |
模糊关键字搜索 |
| 传统的搜索技术仅基于精确的关键字匹配检索文件，但模糊关键字搜索技术通过支持用户键入关键字时出现的常见拼写错误和格式不一致来扩展这一特性。使用该方法时，保证了精确关键字搜索过程中数据的私密性。基于通配符的技术[4]用于创建用于匹配相关文档的高效模糊关键字集。关键字集是使用Edit Distance算法创建的，该算法量化了单词的相似性。这些关键字集消除了生成所有模糊关键字的需要，而不是根据相似度生成，从而减少了存储和表示开销。所提供的搜索结果基于精确匹配搜索失败时生成的模糊关键字数据集。 |
提出了系统 |
| 我们提出了一种有效的方案，使云服务提供商(CSP)能够确定与用户搜索的关键字相关的文件，对它们进行排名，并在不知道任何关于云的信息的情况下发送最相关的文件。我们的模式由三个实体组成:数据所有者、不可信的云服务器和本地可信服务器。数据所有者是数据存储在云服务器上的人，他也被授权搜索他的文件。云服务器是一种不受信任的服务器，它提供存储服务，数据所有者以加密形式存储其文档。受信任的本地服务器存储为文件创建的索引。系统架构如图1所示。我们假设用户的授权和用于加密的密钥由本地可信服务器管理。 |
符号: |
| 1.C (f1, f2， ..，Fn) : Files to be uploaded in cloud server. |
| 2.W (w1, w2， ..，wi):从C中提取的关键字。 |
系统架构 |
 |
加密算法 |
| 由于我们不打算对外包文件执行任何操作来搜索关键字，因此我们可以使用任何现有的轻量级对称密钥加密算法并将数据文件卸载到云端。我们使用DES加密文件，然后将其外包。 |
字符串匹配算法 |
| Aho-Corasick被发现是多字符串匹配的有效算法，它可以找到将外包给不受信任的云服务器的文件中出现的所有模式。 |
| 该算法由两部分组成: |
| 第一部分是根据我们想要搜索的关键字构建树(trie)，第二部分是使用之前构建的树搜索关键字的测试。树是一个有限状态机，它是由有限数量的状态和这些状态之间的转换组成的行为的确定性模型。在构建树的第一阶段，将关键字添加到树中，其中根节点只是一个占位符，并包含指向其他字母的链接。树是一组关键字的关键字树K是一棵根树T，这样T的每条边都用一个字符标记，节点外的任意两条边都有不同的标签。 |
| 建设对于关键字W = {W1，…Wk} and n = Σ= |Wi|。 |
| 从根节点开始 |
| 依次插入关键字W，如下所示: |
| 从根节点开始，按照Wi字符标记的路径: |
| •如果路径在Wi之前结束，通过为Wi的剩余字符添加新的边和节点来继续它 |
| •Wi在路径终端节点的存储标识i。这显然需要O(|W1| +…+ |Wk|) = O(n)时间 |
| 查找弦的P: |
| 从根开始，尽可能沿着P字符标记的路径;如果路径指向一个带标识符的节点，则P为关键字。如果路径在P之前结束，则该字符串不在关键字集中。这显然需要O (|P|)时间。 |
| 要外包的文件被提供给trie。在trie中查找每个单词，以检查它是否是关键字，并存储出现的次数。然后将此值传递到下一个阶段，即索引。 |
索引 |
| 索引创建为对应于每个关键字的映射列表[10]。特定关键字的列表包含以下详细信息: |
| 1.具有特定关键字的文件的文件id |
| 2.每个文件的术语频率，表示关键字在文件中出现的次数。这衡量了该文件中关键字的重要性。 |
| 3.每个文件的长度 |
| 4.每个文件的相关性得分 |
| 5.具有特定关键字的文件数 |
| 可以使用B+树等数据结构来存储这些数据。词频、文件长度、关键字的文件数量用于通过评分机制计算每个文件的相关性得分，评分机制将在后面的排名模块中讨论。 |
| 前面的文章讨论了架构[5][6]，其中索引和文件都以加密形式存储在不受信任的服务器中。每当用户搜索一个单词时，请求就被发送到不受信任的服务器，该服务器搜索索引并将为该单词创建的整个映射发送给用户。用户有解密和请求基于索引中的相关性评分信息检索最相关的文件的开销。这将占用大量带宽和往返时间。为了减少开销，提出了一种将索引以纯文本形式存储在本地可信服务器上的新体系结构。当用户搜索一个单词时，该单词被发送到本地可信服务器，可信服务器搜索索引，找出最相关的文件，并向非可信服务器请求要检索的文件并发送给用户，从而保证了非可信服务器中的数据机密性。 |
| 无论何时存储数据文件，都会对其进行预处理，以使用从数据文件中提取的关键字(使用前面讨论的多字符串匹配算法)生成包含上述详细信息的索引。创建索引的方案如下: |
| 1.对于每个属于关键字集W的wi，生成F(wi)，它表示包含wi的文件id |
| 2.对于每一个wi€W |
| 对于1 <= j <= |F(wi)| |
| 计算文件Fij的分数(借助于后面讨论的评分机制)并存储为Sij |
| 用文件id id(Fij)存储它，文件|Fij|的长度为(id(Fij) || |Fij| || Sij)在I(wi)中，这是特定单词wi的索引列表 |
| 更新包含关键字的文件总数，索引列表为(I(wi)||N) |
| 单词在文件中的位置也被考虑为文件排序。因此，标题中包含关键字的文件被认为比内容中包含关键字的文件更相关。然后将相关性评分存储在索引中，以便每当用户请求单词w时，可以使用该评分检索前'k'个相关文件。 |
排名 |
| 存储并索引文档之后，下一个重要的功能是使用可用的详细信息对它们进行排序，以便用户检索最相关的“k”个文档。为此，我们需要为每个文件计算一个数值分数。在IR社区中，最广泛使用的排名函数是基于TF X IDF规则，其中TF代表术语频率，它表示一个关键字在文件中出现的次数，IDF代表逆文档频率，它被定义为包含该词的文件数量与服务器中出现的文件总数的比率。 |
| 排名函数[5]使用: |
| 得分(W,Fi) = Σ 1/|Fi|。(1 + ln fi,t)(1 + N/ft) |
| W:要计算分数的关键字 |
| fi,t:文件fi中术语的频率 |
| |Fi|:文件长度 |
| N:集合中的文件总数。 |
结论 |
| 本文通过引入排序关键字搜索方案，解决了使用布尔搜索技术时产生的后处理开销和不必要的网络流量问题。该方案生成索引，帮助用户在安全的环境中搜索他的文档。匹配关键字搜索的文件将进一步根据相关分数进行排名，这些分数由术语频率、文件长度等计算得出。 |
| 对项目的进一步扩展可以由 |
| 1.支持多用户环境，在该场景中有一个额外的实体，即数据用户，被授权访问其他用户的文件。可以修改授权机制和密钥交换方法以支持相同的功能。 |
| 2.允许在输入关键字时出现的轻微打字错误和格式不一致。这可以通过引入前面讨论过的模糊关键字机制来实现。 |
| 3.布尔对称搜索技术可以在不改变现有架构的情况下支持多个关键字搜索。 |
参考文献 |
- 宋，瓦格纳，佩瑞格。:《加密数据搜索的实用技术》。“IEEE安全与隐私研讨会论文集”(2000)。
- D.博内，G. D. Crescenzo, R. Ostrovsky和G. Persiano。: "使用关键字搜索的公钥加密。“EUROCRYP Proc.”04,LNCS卷3027。施普林格(2004)。
- 研究。Chang和M. Mitzenmacher。:“保护远程加密数据的关键字搜索隐私。《ACNS学报》2005年05期。
- 李俊杰，王强，王成，曹宁，任凯，娄伟。:“云计算加密数据的模糊关键字搜索。”《IEEE INFOCOM 10小型会议》(2010)论文集。
- 王成，曹宁，任凯，娄伟。:“为外包云数据提供安全高效的排名关键字搜索。”IEEE并行和分布式系统汇刊，第23卷，no. 1。8(2012)。
- 曹c, n, k . Ren, j . Li w·卢。:“加密云数据的安全排名关键字搜索。《ICDCS手册》10(2010)。
- R.柯特莫拉，J. A.加雷，S.卡马拉和R.奥斯特洛夫斯基。:“可搜索的对称加密:改进的定义和有效的构造。”见《ACM CCS》06(2006)。
- Remya Rajan。:“高效且保护隐私的云存储服务多用户关键字搜索。”国际先进技术与工程研究杂志(IJATER)， ISSN 2250 - 3536，第2卷，第4期(2012)。
- Zeeshan Ahmed Khan, R.K Pateriya报道。:“多模式字符串匹配方法”比较分析(2012)。
- i。h。威腾，a。莫法特，t。c。贝尔。:“管理千兆字节:压缩和索引文档和图像。”摩根·考夫曼出版社，旧金山(1999)。
- Tarik Moataz和Abdullatif Shifka。: "布尔对称可搜索加密。"
|
菜单
