Patent Document ID: 9009089
Application ID: 13749683
Patent Status: 1

Claim One:
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 S ); causing the second set of processors to send E(AV S ) to the first set of processors; causing the second set of processors to decrypt E(AV S ); and providing to the first set of processors where the pattern P matches T, if at all.