Papers

Peer-reviewed
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

Volume
8544
Number
First page
338
Last page
353
Language
English
Publishing type
Research paper (international conference proceedings)
DOI
10.1007/978-3-319-08344-5_22
Publisher
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.

Link information
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 information
  • 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

Export
BibTeX RIS