Patent ID: 9009089
Filing Date: 2015-04-14
Classification: G06F

Abstract:
1. A system for secure pattern matching, the system comprising: one or more processors and memory having instructions encoded thereon such that when the instructions are executed, the one or more processors perform operations of: receiving, as input, a pattern P from a first set of processors, wherein the pattern P comprises a set of characters of an alphabet Σ; receiving, as input, a text T from a second set of processors, wherein the text T comprises a set of characters of the alphabet Σ; causing the first set of processors to construct a matrix CDV, having a plurality of rows, based on values computed for each character in Σ that are determined by each character's position in the pattern P; causing the first set of processors to send an encrypted matrix E(CDV) and a pattern matching threshold to the second party, wherein E( ) denotes additive homomorphic encryption; causing the second set of processors to process each character in the text T and retrieve from the encrypted matrix E(CDV) a corresponding row of the encrypted matrix E(CDV), resulting in an encrypted vector; causing the second set of processors to multiply the encrypted vector with an encrypted activation vector E(AV) having a set of entries; causing the second set of processors to multiply the pattern matching threshold homomorphically to each of the entries in the activation vector AV to generate a result; causing the second set of processors to exponentiate the result by a random number to blind each entry in the set of entries of E(AV), resulting in creation of E(AV causing the second set of processors to send E(AV causing the second set of processors to decrypt E(AV providing to the first set of processors where the pattern P matches T, if at all.