Cryptology ePrint Archive: Report 2020/931

Homomorphic string search with constant multiplicative depth

Charlotte Bonte and Ilia Iliashenko

Abstract: String search finds occurrences of patterns in a larger text. This general problem occurs in various application scenarios, f.e. Internet search, text processing, DNA analysis, etc. Using somewhat homomorphic encryption with SIMD packing, we provide an efficient string search protocol that allows to perform a private search in outsourced data with minimal preprocessing. At the base of the string search protocol lies a randomized homomorphic equality circuit whose depth is independent of the pattern length. This circuit not only improves the performance but also increases the practicality of our protocol as it requires the same set of encryption parameters for a wide range of patterns of different lengths. This constant depth algorithm is about 10 times faster than the prior work. It takes about 5 minutes on an average laptop to find the positions of a string with at most 50 UTF-32 characters in a text with 1000 characters. In addition, we provide a method that compresses the search results, thus reducing the communication cost of the protocol. For example, the communication complexity for searching a string with 50 characters in a text of length 10000 is about 347 KB and 13.9 MB for a text with 1000000 characters.

Category / Keywords: cryptographic protocols / secure computation, homomorphic encryption, string search, pattern matching, batching, equality circuit

Original Publication (with minor differences): CCSW 2020

Date: received 28 Jul 2020, last revised 1 Sep 2020

Contact author: ilia at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20200901:091630 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]