論文

査読有り
2014年

Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption

INFORMATION SECURITY AND PRIVACY, ACISP 2014
  • Masaya Yasuda
  • ,
  • Takeshi Shimoyama
  • ,
  • Jun Kogure
  • ,
  • Kazuhiro Yokoyama
  • ,
  • Takeshi Koshiba

8544
開始ページ
338
終了ページ
353
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-319-08344-5_22
出版者・発行元
SPRINGER-VERLAG BERLIN

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.

リンク情報
DOI
https://doi.org/10.1007/978-3-319-08344-5_22
DBLP
https://dblp.uni-trier.de/rec/conf/acisp/YasudaSKYK14
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000345511900022&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/conf/acisp/acisp2014.html#conf/acisp/YasudaSKYK14
ID情報
  • DOI : 10.1007/978-3-319-08344-5_22
  • ISSN : 0302-9743
  • eISSN : 1611-3349
  • DBLP ID : conf/acisp/YasudaSKYK14
  • Web of Science ID : WOS:000345511900022

エクスポート
BibTeX RIS