【质数内积编码方案设计案例3700字】

质数内积编码方案设计案例综述目录TOC\o"1-3"\h\u18819质数内积编码方案设计案例综述 112391.1方案介绍 149291.1.1基本思想及方案构建 1300851.1.2向量构造及向量匹配 2312601.1.3正确性分析 6118691.2方案介绍 7161211.2.1基本思想 7273241.2.2方案构造 8239671.2.3正确性分析 101.1方案介绍1.1.1基本思想及方案构建本节将介绍方案构造，方案在选择密文攻击下是语义安全的[12]。该方案建立在索引向量编码和查询向量编码上，其基本思想是编码查询关键字或索引关键字为一个向量，这些元素都设置为整数或者整数的倒数，确保只有当两个关键词相似时，向量的内积才是一个整数。方案是用户和云服务器之间的一个协议。方案一般由四个部分组成，分别是GenKey，BuildIndex，Trapdoor，Search。：云用户输入一个安全参数，输出一个秘密密钥SK。：给定一个具有个关键词的集合，云用户利用秘密密钥对文件中的关键词集合生成索引并进行加密，生成一个被加密的索引集合。：给定一个具有需要查询的搜索关键词集合，云用户使用秘密密钥SK为搜索关键词集合生成一个陷门。：云服务器将陷门与被加密的索引共同运算，如果陷门与索引匹配，则输出1，否则输出0。1.1.2向量构造及向量匹配下面将详细介绍索引向量编码、查询向量编码和向量匹配过程。在介绍向量编码之前，先简单介绍后面可能会用到的相关符号，如表1.1所示。表1.1方案相关符号及说明符号说明一组文件的集合一组含m个关键词的集合一组含n个密文文件的集合所有关键词中的最大长度文件的m个关键词文件的索引搜索向量中的个关键词搜索向量的陷门含有26个英文字母的集合填充字符集，且与集合A没有交集长度为L的质数序列详细的索引向量编码算法如下图1.1所述，第一步（(1)-(2)）首先用集合S中的字符将索引关键词填充至关键词最大长度L。填充之后，第二步（（3）-（4））将索引向量的每一个元素初始化为1。第三步（（5）-（7））将指定质数的倒数放置在索引向量的适当位置。比如，关键词第l（）个字符对应的质数是，对应索引向量的位置是。然后索引向量对应的位置将乘以对应的质数，即。图1.1索引向量编码算法详细的搜索向量编码算法如下图1.2所述，第一、二步（1-4）为填充步骤和初始步骤，与索引向量编码的第一、二步一致。第三步（5-15）将把指定的素数放在搜索向量的适当位置。对于关键词的第l个字符，这里有两种情况，如果该字符不为通配符“*”时，将计算，并且在这个位置乘以对应的质数，即。如果该字符为通配符“*”时，则将搜索向量上所有元素的值都乘以该位置的质数。图1.2搜索向量编码算法图1.3和图1.4展示了向量编码和向量匹配的一个样例，假设文件与关键字的关系如图1.3-(a)所示，此时云用户发出查询请求和去搜索合适的文件。给定关键词最长长度为，随机数序列为，填充字符集合。图1.4描述了索引向量编码和搜索向量编码的过程。下面将用索引关键词“key”和搜索关键词“k*y”描述向量编码和向量匹配的过程。在向量编码第一步中，用字符“A”和“B”填充两个关键词，使其最大长度为5。第二步分别将两个d维向量和中的所有元素初始化为1。对于索引关键词“key”，素数的倒数摆列如下，因为“k”是第一个字符，所以将乘以1/3；因为“e”是第二个字符，所以将乘以1/5；因为“y”是第三个字符，所以将乘以1/7；因为“A”是第四个字符，所以将乘以1/11；因为“B”是第五个字符，所以将乘以1/13；对于搜索关键词“k*y”，质数按如下顺序排列：因为“k”是第一个字符，所以将乘以3；因为“*”是第二个字符，且“*”是通配符，那么集合A和S中的任意元素都可能位于这个位置，所以该向量上所有元素即全部乘以5；因为“y”是第三个字符，所以将乘以7；因为“A”是第四个字符，所以将乘以11；因为“B”是第五个字符，所以将乘以13；由于质数的不可分解性，所以两个向量内积是一个整数（等于21）。结果与两个关键词相似的事实是一致的。当需要多关键词搜索时，方案也支持AND和OR查询方式。查询方式为AND意味着只有当搜索词集合包含在某文件的关键词集合内时，该文件才会被返回给用户。查询方式为OR意味着当搜索词集合和某文件的关键词集合有交集时，该文件就会被返回。给定图1.4所示的索引/查询向量，对应的搜索词矩阵如图1.3-(b)所示。如果的查询方式是AND，则文件将被返回，因为只有在在每个列中有一个整数元素；如果的查询方式是OR，则文件都将被返回，因为中至少有一个整数元素。如果的查询方式是AND，则文件将被返回，因为只有在每个列中有一个整数元素。如果的查询方式是OR，则文件都将被返回，因为文件和都至少有一个整数元素。由此可以看出方案也具有支持布尔搜索的功能。图1.3关键词搜索过程图1.4向量编码1.1.3正确性分析本条将介绍方案搜索原理的正确性。设表示英文字母和填充字符的并集，其中U[i]表示U中的第i个元素。首先考虑一个文件和一个搜索关键词中仅含有单个关键词的情形，分别表示为和。如果出现以下情况，基本PIPE方案被认为是不正确的：如果索引关键词和搜索关键词相似，关键词向量和搜索关键词向量的内积不是一个整数。如果索引关键词和搜索关键词不相似，关键词向量和搜索关键词向量的内积是一个整数。对于情形1，不是一个整数意味着中至少有一个倒数不能被消除。由于BuildIndex的构造，表示U[i]是的第i个字符。如果1/不能被消除，那么就一个不能被整除的整数。由于搜索向量编码运算的构造规则，不会是通配符“*”，也不会是U[i]。因此两个关键词不相似，情形1是不正确的。对于情形2，是一个整数意味着中所有倒数都能被消除。由于表示U[i]是的第i个字符。会等于或者一个能被整除的数。由于搜索向量编码运算的构造规则，是通配符“*”或者U[i]。因此情形2也是不正确的，综上所述，方案在文件或搜索关键词中仅含单个关键词的情况是正确的。当扩展到多关键词设置时，方案的正确性推导如下：结果矩阵第k行第l列的元素是的内积，如果中的第k个索引关键词和中的第l个搜索关键词相似，那么的结果将是一个整数。当查询方式为AND时，如果每一列都至少有一个整数，则中每一个索引关键词至少和中的一个搜索是相似的，那么搜索关键词和索引关键词对应的文件相匹配。当查询方式为OR时，如果结果矩阵至少有一个整数，那么中至少有一个索引关键词和中的一个搜索关键词是相似的。综上所述，在文件或搜索关键词中含多个关键词的情况是正确的。1.2方案介绍1.2.1基本思想本节将介绍方案。前面已经介绍过PIPE方案是基于安全KNN结构构造的，但是安全KNN结构难以抵抗线性分析，因此提出了去抵抗线性分析，从KNN的构造可知，索引向量和查询向量的内积可以通过它们的加密形式计算出来：，其中只有索引向量p中的d个元素对云服务器是未知的。在已知背景模型中，云服务器能够通过有效的背景信息推断某些明密文对。正如Yao等人[27]所证，一个敌手拥有d个查询向量及其加密形式的向量后能够通过求解线性方程回复索引向量。为了抵抗这种攻击，将查询向量扩展到随机矩阵，从而在内积结果中加入噪声。发起这种攻击的困难来自于构造正确方程的可能性极小。对于所有的索引向量有:。解决方案基于以下关键技术：1、矩阵编码查询。搜索向量首先由搜索向量编码算法（见图1.5）产生，再通过搜索矩阵编码算法（见表3.4）生成一个d*s的矩阵。对于，搜索矩阵编码算法将设置到第l行的随机一个位置，并且用随机数填满其他位置，要求满足以下几个条件：Condition1：的每一列至少有向量中的一个元素。Condition2：第l行随机数之和应该等于，记为，其中或者为一个质数，且要求该质数不在质数序列P中。图1.5搜索矩阵编码算法2、相似性的确定。给定一个由关键词生成的索引向量、一个由关键词生成的搜索矩阵，一个通过计算得到的中间向量。如果一行中所有相加，即，和如果为一个整数，那么关键词和被认为是相似的。1.2.2方案构造方案和方案最大的区别在于和，下面将介绍这两个部分：：搜索序列含有个关键词，云用户任意选择一个整数。为了对中的个关键词加密并得到一个的矩阵，他将执行以下操作：对第k个关键词使用搜索向量编码算法（见图1.2）生成一个d维向量对d维向量使用搜索矩阵编码算法（见图1.5）生成一个d*s的矩阵对于，将搜索词矩阵元素的赋值为。其中是个搜索向量的结合（例子可见图1.6-(a)）：给定一个索引矩阵和搜索矩阵。再做匹配运算时，云服务器将产生一个的中间矩阵，即。矩阵由的中间向量组成（见图3.3-(c)），元素表示。为了确定搜索向量是否与文件匹配，需要执行以下操作：首先构造一个结果矩阵对于和，设置，且（见图1.6-(b)）当查询方式为AND时，如果每列至少有一个整数时，则输出1，否则输出0；当查询方式为OR时，如果至少有一个整数时，则输出1，否则输出0；图1.6展示了一个PIPE-s方案的简单构造，假如s=3，搜索关键词的搜索矩阵为，如图1.6-(a)所示，的前s列为，的后s列为。正如图1.3-(b)矩阵一样，图1.6-(b)为结果矩阵，图1.3-(c)为中间变量矩阵图1.6方案构造样例1.2.3正确性分析方案的正确性是基于假设查询矩阵中引入的随机性不会影响结果的