基于同态加密的密文数据库统计模型的设计与实现.doc

基于同态加密的密文数据库统计模型的设计与实现陈志伟 1，2，白健 1，2，杨亚涛 2，李子臣 2 （1. 西安电子科技大学，陕西西安 710071 ；2. 北京电子科技学院，北京 100070）摘 要 ：文章针对基于同态技术密文数据库统计的设计与实现进行了详细的阐述。文章利用同态加密技术，设计了两种对密文数据库进行精确统计和范围统计的模型，解决了服务器端密文数据检索和统 计的问题，并对模型的正确性进行了证明，实验仿真证明了模型的可行性。关键词 ：同态加密 ；密文统计 ；RSA ；paillier ；密文检索中图分类号 ：TP393.08 文献标识码 ：A 文章编号 ：1671-1122（2013）03-0012-04The Encrypted Database Statistical Method based onHomomorphism EncryptionCHEN Zhi-wei1,2, BAI Jian1,2, YANG Ya-tao2, LI Zi-chen2( 1. Xidian University, Xi an Shanxi 710071, China;2. Beijing Electronic Science & Technology Institute, Beijing 100070, China )Abstract: In this paper, we described the Encrypted database statistical method based on homomorphism encryption. In this paper, based on homomorphism encryption, we design two encrypted database statistical method, one is for accurate statistics, and another is for range statistics. So that, we solve the query and statistical question about encrypted database. At the end, we also prove the correctness of this method and the simulation experiment make out that this technology is feasibility.Key words: homomorphic encryption; ciphertext statistics; RSA; paillier; ciphertext query0 引言同态加密是秘密同态的一个子集。秘密同态的思想由 Rivest、Adleman 和 Dertouzos 等 1 提出。全同态加密一直是梦寐以求的希望解决的问题。全同态加密能够在没有解密密钥的条件下，对密文进行任意形式的操作，以实现对应的本文利用具有同态性质的密码体制，构造了一种密文数据库统计的方法，并进行仿真测试。仿真测试采用了 Client/Ser结构，使用 MFC 将其实现，并对其效率进行分析。1 背景分析在提出基于同态技术的密文数据库统计方法之前，首先来回顾与本文方法相关的基础知识，同态加密方案和一些文数据库统计方案。1.1 同态加密体制Sander 和 Tschudin 在文献 2 中定义了整数范围上的加法、乘法同态加密方案（Homomorphic Encryption Scheme，H乘法同态确保了两个变量加密后的计算结果与加密前的计算结果相同。 HES 的简单描述如下 ：设 R，S 是两个环，R 表示明文空间，S 表示密文空间，我们给出如下定义 ：E ：R S算出 E(x+y)，而不需要知道 x, y 的值。2）乘法同态 ：如果从 E (x)和 E ( y) 通过乘法计算可以计 算出 E(xy)，而不需要知道的 x, y 值。3）混合乘法同态 ：如果从 E (x)和 y 通过混合乘法计算E(xy)=E(x)y，可以计算出 E(xy)，而不需要知道 x 的值。 全同态加密是在同态加密的基础上提出的。如果一个加密算法满足下面的运算条件，就被称作完全同态加密算法 ：；M 指明文空间， 指任意的一种运算， 表 示只对密文 操作，不需将密文信息解密成明文来运算。1.2 密文数据库统计密文数据库的统计离不开密文检索，如何根据密文的特征对其明文信息进行检索，进而实现密文数据项的统计，是国 内外学者的研究重点。文献 3 中提出了一种线性检索 算法， 并采用对称加密算法实现。对于每一个数据项对应的密文信息，生成一串长度小于其长度的伪随机序列和由伪随机序列即 密文信息确定的校验序列。伪随机序列的长度与校验序列长 度之和等于密文信息的长度。对伪随机序列及检验序列对密 文信息再次加密。在统计过程中，用户提交满足条件的明文信 息所对应的密文信息序列，服务器端进行模 2 加校验，把符 合条件的密文项个数记录下来，进而完成了明文数据项的统计。 线性检索方法在大数据集的情况下难以应用，而且仅能完成 特定密文的判别，无法完成对密文的范围统计。文献 4 中 B oneh 等人描述了一种基于关键词的公钥检索 方案，即对关键词用公钥进行加密，生成供搜索的密文。这 种方案在关键词的提取能否代表整个密文和关键词密文之间 的数量计算问题上还未解决。文献 5 提出了安全索引策略， 该方案缺陷是需要生成大量的密钥序列，随着检索次数增多，每一次检索付出的搜索代价也会上升，统计效率会大大下降。实际应用中很难被接受。2011 年 1 月，MIT 研究生 R.A.Popa 和 N.Zeldovich 等人提 出了一个加密数据库思想 6，文中设计了一种对数据进行层层 加密的洋葱式加密方案（Onions of encryption），该方案是由保 序加密 OPE（Order Per-serveing encryption）和同态加密体制 HOM（Hom-omorphic encryption）构成，其中同态加密部分采 用了一些具有单一乘同态或单一加同态的密码体制来构造，文 中还把 SQL 操作分为 JOIN、RND、SEARCH 等，利用四套洋 葱式数据加密方案（Onion Eq、Onion Ord、Onion Add、Onion Search）对数据进行分类处理，从而实现了对密文的同态操作，大大提高了检索效率。我们在这种思路的启发下，利用 Paillier和 R SA 的同态特性，对密文进行不同的同态操作，实现了对Paillier 初始化 ：1）随机的选取两个素数 p 和 q，且满足。2）计算和。3）选取随机数 g，且能保证存在，其中函数 L 定义为钥为 (, )。此时，公钥为 (n, g)，私Pa i l l ier 加 解 密 ：对 于 明 文，则 ：，并 选 择 随机 数加密过程为 ：。Pa i l l ier 同 态 性 分 析 :，解密过程为 ：对 于 明 文 m1, m2，加 密 后，得 此 时， 有到， 故 Paillier 公钥密码体制满足加法同态特性。RSA 初始化 :1） 随 机 选 择 两 个 大 的 质 数 p 和 q，p 不等 于 q，计 算N=pq。2）根 据欧 拉函数，不大于 N 且与 N 互质的整数个数为 ( p -1) (q-1)，选择一 个整数 e 与( p -1) (q-1) 互质，并且 e 小于 ( p-1)(q-1)。3）用以下这个公式计算 d:时，(N, e) 是公钥，(N, d) 是私钥。此R SA 加解密 : 明文信息为 m，密文信息为 c，则加密过程为，解密.RSA 同 态 性 分 析 : 对 于 明 文 m1, m2，加 密 后，可 以 得到， 此 时，故 R SA 公 钥密码，体制满足乘法同态特性。为了 更 好 的 利 用 Pai ll ier 和 R SA 的 同 态 特 性， 本 方 案中 Pai ll ier 和 R SA 加密均未使用任何形式的填充方案，对于 Pa i l l ier 加密，未经填充的方案能够保持密文加法和减法同态 特性，并用于精确检索中的密文比较 ；对于 R SA 加密，未填 充的方案使密文保持了与明文一致的大小关系，进而用于范围 检索统计中。3 统计模型设计为了防止明文信息泄漏，用户把密文存到云计算服务提供商的服务器，但是往往需要服务提供商提供存储内容的搜索 和统计服务，此时，服务器只能对存储的密文进行操作，或利 用一些辅助参数来实现用户的搜索和统计需要。本文正是基方案。其中，表 1 是存储在数据库中的密文数据，属性 1 列采用了 Pa i l l ier 进行加密。属性1 副本列仍然是对属性1 中内容 的加密，但是采用了 R SA 进行。属性1 和属性1 副本中的明 即： 文数据均取自（实际应用中属性 可能不在这个范围内，还可以表达为 ：但可以采用一定的映射方法将其映射在这个域内）。表1 基于Paillier和RSA的密文数据库从上式可以看出只有当时，每一项中的够等于 1。此时，剩余项就能与一项匹配上，完成检索，模型中的求商步骤利用了 P减法同态特性，实现了在不解密的情况下用密文的检索匹配。从中选取任意随机数能够实现3.1 精确统计模型初始化阶段 ：假设所有的用户 User 和查询者 Q 都是可信的，只有云计算服务器提供商不可信，且用户与查询者都持 有 Paillier 的私钥 (N, g)，方案中，所有的用户与查询者不采用据项在不同随机数选取下的密文不同，造成服务器的混淆，一定程度上也降低了检索请求泄漏。3.2 范围统计模型除了精确检索统计外，有时我们需要对一定范围传统的 Pai ll ier 加密随机数选取方式从进行随机选取，此时，进行检索和统计。由于 Pa i l l ier 的密文有随机数的参而是对 进行了重定义 ：系统用户的最大承载量为会导致明文到密文映射后，明文对应的密文大小关，剩余的 3 个随机数是分配持原来的大小顺序。所以，为了实现对范围的查询，给查询者 Q 用于数据混淆（使同一个查询值在服务器端可以以3 种不同的形式出现），并且，普通用户由系统指定随机数了 RSA 进行加密，得到了属性 1 副本。初始化阶段 ：假设查询者为用户，且为，服务器端只持有公钥。中选 取 随 机数 ，用 授权 Q 统计其是可信 的， 而云 计 算服 务 器 提 供商是 不 可信的。查询 阶 段 ：查 询 者 Q 从于此次的查询项加密。用户组RS A 的公 钥钥。和私钥 d，服务器 提 供商仅持有内容，这时会把数匹配值 ：中每 个用户加密时采用的随机交给 Q，Q 得到所有随 机 数 后 计 算出查 询查询 阶 段 ：当 用 户 Ui 要查 询 Vi 上下范 据 时，我 们 只 需 要 把通过用 户 Ui 所对 应的 提交给 服 务 器， 然 后，计 算 出范围 内，对其它行的该列进行检是否落在这个域内，统计落在域内的数据项的个数值即为最后的统计结果。， ，若 Q 要对数据库属性 1 中的所有值等于 的项进行检索正确性分析 ：把属性 1 副本中的所有数据项以统计，则需要用随机数采用 Pa i l l ier 的私钥对和进行加密得发送到服务的形式表达为 ：到。然后把器端。服务器端收到查询向量后，对数据项进行匹配，首先遍检索的密文值范围可以表达为 ：历表 1 属性 1 中的数据项，计算每个数据项和的商得，若 Vi 满足不等式 ：到，比较和则有 ：统计其中相等项的个数记为 Re su lt，将其返回客户端，Re su lt可见满足条件的 肯定能在对其密文的检测中物理地址用户属性 1属性 1 副本 属性 n0091U1EP (V1)ER (V1) Data0092U2EP (V2)ER (V2) Data 00EFUnEP (Vn)ER (Vn) Data图1 对表内1/100的匹配数据项精确统计时的耗时始的 RSA 和 Paillier 加密算法，并完成了一些功能函数的设计。系统使用 1024bit 的 R SA 和 512bit 的 Paillier，服务器的数据 存储部分采用的是 O racle10g 标准版。服务器环境为 ：A M D Athlon(TM) II X2 250 Processor 双核 CPU，DDR3 1333MHz 2G 内存，Windows XP SP3，Visual C+ 2010。实验设计了 6 个表，数据量分别在 1104 以内，2104 以 内，4104 以内，8104 以内，16104 以内，32104 以内。然后， 采用两种方案对这 6 个表进行一些特定的统计，方案一使用 基于 Paillier 和 RSA 同态性存储并统计的方式，方案二使用明 文形式存储并统计的方式，图 1 是两种方案在对表内含 1/100 的匹配数据项进行的精确统计耗时对比图。图 2 是两种方案 在对表内含 1/100 的匹配数据项进行范围统计的耗时对比图。确统计的耗时是采用明文形式统计的 2 倍左右，前者主要把时间消耗在了求匹配值和求商操作上。图 2 中两条折线几乎出 现在了一个位置，说明进行范围检索时同态性方案的耗时并 没有明显的增加，这和查询的提交项数目有关系，方案一只是 提交了一个查询项，进行一次加密操作即可。所以，随着数据 项的增加并没有太多的额外时间消耗。5 结束语本文 分 析了 现 有 的 密文 检 索 方 案， 然 后对 Pa i l l i e r 和R S A 密码体制进行了的同态性分析，提出了基于两者同态性 质的精确统计模型和范围统计模型，实现了在服务器端全密 文情况下的信息检索和统计，同时能够 保证用户的隐私不被 泄露。由实验仿真分析可以看到，随数据量的增长精确统计 和范围统计的耗时虽然有所增加，但是在一定数量数据项内 的统计效率还是可以接受的。对于“数据项中小数 形式数据 项的统计”和“统计范围的边界取整”等情况的处理，以及 设计用来提高系统安全性的明文填充方案将会是下一步研究 的重点。 （责编 程斌）参考文献 ：1 R. Rivest, L. Adleman and M. Dertouzos. On data banks and privacy homomorphismsC. In Foundations of Secure Computation, 1978.169-180.2 T. Sander, C. Tschudin. Protecting Mobile Agents Again-st Malicious HostsC. In the Proceedings of the 1998 IEEE Sy-mposium of Research in Security and Privacy. Oakland, 1998.3 D.Song, D.Wagner and A.Perrig. Practical Techniques for Searches on Encrypted Data C.Proceedings of the IEEE Symposium on Security and Privacy(S&P00), May 14-17,2000, Berkeley, CA,USA. Piscataway, NJ. 4 D.Boneh, G.Crescenzo and R.Ostrovsky, et al. Public Key E