Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption
Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption
复制标题
DOI：
10.1007/978-3-319-08344-5_22
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Masaya Yasuda;Takeshi Shimoyama;Jun Kogure;K. Yokoyama;Takeshi Koshiba
中科院分区：
文献类型：
--
作者：
Masaya Yasuda;Takeshi Shimoyama;Jun Kogure;K. Yokoyama;Takeshi Koshiba
基本的模式匹配问题是找到模式在文本中出现的位置。我们给出了几个计算，使客户端从数据库中获得匹配结果，使数据库不能学习任何有关客户端的查询模式的信息。对于这样的计算，我们应用Brakerski和Vaikuntanathan提出的有点同态加密的加密密钥变体方案（MPTO 2011），它可以支持加密数据上有限数量的多项式加法和乘法。为了提高效率，我们还利用了Yasuda等人（CCSW 2013）介绍的包装方法。虽然他们只处理二进制向量的基本问题，但我们解决了更复杂的问题，如非二进制向量的近似和通配符模式匹配。为了证明我们的方法的效率，我们实现了加密方案的安全通配符模式匹配的DNA序列。我们的实现表明，客户端可以在通用PC上在不到一秒的时间内私下搜索长度为16，500的真实世界基因组。
The basic pattern matching problem is to find the locations where a pattern occurs in a text. We give several computations enabling a client to obtain matching results from a database so that the database can not learn any information about client’s queried pattern. For such computations, we apply the symmetric-key variant scheme of somewhat homomorphic encryption proposed by Brakerski and Vaikuntanathan (CRYPTO 2011), which can support a limited number of both polynomial additions and multiplications on encrypted data. We also utilize the packing method introduced by Yasuda et al. (CCSW 2013) for efficiency. While they deal with only basic problems for binary vectors, we address more complex problems such as the approximate and wildcards pattern matching for non-binary vectors. To demonstrate the efficiency of our method, we implemented the encryption scheme for secure wildcards pattern matching of DNA sequences. Our implementation shows that a client can privately search real-world genomes of length 16,500 in under one second on a general-purpose PC.