Secure pattern matching using somewhat homomorphic encryption
Secure pattern matching using somewhat homomorphic encryption
复制标题
DOI：
10.1145/2517488.2517497
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Masaya Yasuda;Takeshi Shimoyama;Jun Kogure;K. Yokoyama;Takeshi Koshiba
中科院分区：
文献类型：
--
作者：
Masaya Yasuda;Takeshi Shimoyama;Jun Kogure;K. Yokoyama;Takeshi Koshiba
基本的模式匹配问题是找到模式在文本中出现的位置。近年来，安全模式匹配在保护隐私的DNA匹配和安全生物特征认证等领域受到了广泛的关注。本文的目的是利用同态加密提供一种实用的解决方案，同态加密是一种支持对加密数据进行某些操作的公钥加密。在本文中，我们使用了Lauter， Naehrig和Vaikuntanathan （ACM CCSW 2011）提出的某种同态加密方案，该方案支持对加密数据进行有限数量的加法和乘法。在他们的工作中，还提出了一些消息编码技术，使我们能够有效地计算整数的和和积。在此基础上，我们提出了一种新的打包方法，适用于对加密数据进行多个汉明距离值的高效计算。我们的主要扩展给出了两种类型的压缩密文，对压缩密文进行线性计算得到了我们想要的结果。我们用我们的包装方法实现了这个方案。我们的实验运行在Intel至强处理器3.07 GHz上，我们的软件库使用内联汇编语言编写C程序。我们的优化实现表明，对于长度为2048的二进制文本，文本或模式的打包加密、在打包密文上计算多个汉明距离值以及解密分别需要大约3.65毫秒、5.31毫秒和3.47毫秒的安全精确和近似模式匹配。总时间约为12.43 ms，在实际生活中具有较好的性能。我们的方法提供了更快的性能和更低的通信比最先进的工作几千位长度的二进制文本。
The basic pattern matching problem is to find the locations where a pattern occurs in a text. Recently, secure pattern matching has been received much attention in various areas, including privacy-preserving DNA matching and secure biometric authentication. The aim of this paper is to give a practical solution for this problem using homomorphic encryption, which is public key encryption supporting some operations on encrypted data. In this paper, we make use of the somewhat homomorphic encryption scheme presented by Lauter, Naehrig and Vaikuntanathan (ACM CCSW 2011), which supports a limited number of both additions and multiplications on encrypted data. In their work, some message encoding techniques are also presented for enabling us to efficiently compute sums and products over the integers. Based on their techniques, we propose a new packing method suitable for an efficient computation of multiple Hamming distance values on encrypted data. Our main extension gives two types of packed ciphertexts, and a linear computation over packed ciphertexts gives our desired results. We implemented the scheme with our packing method. Our experiments ran in an Intel Xeon at 3.07 GHz with our software library using inline assembly language in C programs. Our optimized implementation shows that the packed encryption of a text or a pattern, the computation of multiple Hamming distance values over packed ciphertexts, and the decryption respectively take about 3.65 milliseconds (ms), 5.31 ms, and 3.47 ms for secure exact and approximate pattern matching of a binary text of length 2048. The total time is about 12.43 ms, which would give the practical performance in real life. Our method gives both faster performance and lower communication than the state-of-the-art work for a binary text of several thousand bits in length.