Efficient secure string search using homomorphic encryption

Abstract

An efficient search of a target string by a query string in homomorphically encrypted space. The target string may be encoded by reordering its characters into a plurality of target substrings, each encoding non-sequential characters of the target string separated by a periodic stride K and different target substrings having stride sequences offset relative to each other. The query string may be encoded into a plurality of query substrings, each defining a repeating sequence of a different respective character value in the query string. Each of the substrings may be homomorphically encrypted and hashed. The plurality of hashed encrypted target substrings and plurality of hashed encrypted query substrings may be compared to determine if there is a search result match. A rolling hash may iteratively update the plurality of hashed encrypted target substrings by one target string slot and the comparison may be repeated for each iterative update.