Secure word search

Abstract

A method may include generating word string vectors for word strings in a document, obtaining encrypted word string vectors by encrypting the word string vectors, generating a search vector for a search query, obtaining an encrypted search vector by encrypting the search vector, calculating encrypted distances between the encrypted word string vectors and the encrypted search vector, obtaining a decrypted distance by decrypting an encrypted distance, and using the decrypted distance, determining a semantic match between the search query and the document.

What is claimed is: 
     
       1. A method, comprising:
 generating one or more word string vectors for one or more word strings in a document; 
 obtaining one or more encrypted word string vectors by encrypting the one or more word string vectors, wherein the one or more word string vectors represent meanings of the one or more word strings as points in a multi-dimensional semantic space; 
 generating a search vector for a search query, wherein the search vector is in a multi-dimensional semantic space; 
 obtaining an encrypted search vector by encrypting the search vector; 
 calculating one or more encrypted distances between the one or more encrypted word string vectors and the encrypted search vector; 
 obtaining a decrypted distance by decrypting an encrypted distance of the one or more encrypted distances; and 
 using the decrypted distance, determining a semantic match between the search query and the document, 
 wherein the one or more word string vectors and the search vector are each semantic representations of a natural language word string that includes a vector in the multi-dimensional semantic space with a value assigned to each dimension of the vector based at least partially on semantic co-occurrences in a corpus of natural language documents. 
 
     
     
       2. The method of  claim 1 , wherein the search query comprises a first search term and a second search term, the method further comprising:
 generating a first search term vector for the first search term; and 
 generating a second search term vector for the second search term. 
 
     
     
       3. The method of  claim 2 , further comprising:
 obtaining a first encrypted search term vector by encrypting the first search term vector; and 
 obtaining a second encrypted search term vector by encrypting the second search term vector, wherein the encrypted distance is calculated using the first encrypted search term vector and the second encrypted search term vector. 
 
     
     
       4. The method of  claim 3 , wherein the encrypted distance is calculated as an encrypted weighted sum of a first distance corresponding to the first search term vector and a second distance corresponding to the second search term vector, and wherein the weighted sum is calculated using homomorphic analogues of multiplication and addition applied to a first encrypted distance corresponding to the first search term vector and a second encrypted distance corresponding to the second search term vector. 
     
     
       5. The method of  claim 1 , wherein the semantic match is determined when the decrypted distance is less than a threshold distance. 
     
     
       6. The method of  claim 1 , further comprising:
 obtaining a multiplication result by combining the one or more encrypted distances together using a homomorphic analogue of multiplication defined by a homomorphic encryption scheme. 
 
     
     
       7. The method of  claim 6 , wherein the multiplication result is obtained by combining the one or more encrypted distances together using multiplication, wherein the homomorphic encryption scheme defines the homomorphic analogue of multiplication to be multiplication. 
     
     
       8. A system, comprising:
 a computer processor; 
 a repository comprising a search query and one or more documents comprising one or more word strings; 
 a vector manager executing on the computer processor configured to:
 generate one or more word string vectors for one or more word strings of a document of the one or more documents, wherein the one or more word string vectors represent meanings of the one or more word strings as points in a multi-dimensional semantic space; 
 generate a search vector for the search query, wherein the search vector is in the multi- dimensional semantic space; and 
 using a decrypted distance, determine a semantic match between the search query and the document; and a cryptography manager executing on the computer processor configured to: 
 obtain one or more encrypted word string vectors by encrypting the one or more word string vectors; 
 obtain an encrypted search vector by encrypting the search vector; 
 calculate one or more encrypted distances between the one or more encrypted word string vectors and the encrypted search vector; and 
 obtain the decrypted distance by decrypting an encrypted distance of the one or more encrypted distances, 
 
 wherein the one or more word string vectors and the search vector are each semantic representations of a natural language word string that includes a vector in the multi-dimensional semantic space with a value assigned to each dimension of the vector based at least partially on semantic co-occurrences in a corpus of natural language documents. 
 
     
     
       9. The system of  claim 8 , wherein the search query comprises a first search term and a second search term, and wherein the vector manager is further configured to:
 generate a first search term vector for the first search term; and 
 generate a second search term vector for the second search term. 
 
     
     
       10. The system of  claim 9 , wherein the search query comprises a first search term and a second search term, and wherein the cryptography manager is further configured to:
 obtain a first encrypted search term vector by encrypting the first search term vector; and 
 obtain a second encrypted search term vector by encrypting the second search term vector, wherein the vector manager calculates the encrypted distance using the first encrypted search term vector and the second encrypted search term vector. 
 
     
     
       11. The system of  claim 10 , wherein the cryptography manager is further configured to calculate the encrypted distance as an encrypted weighted sum of a first distance corresponding to the first search term vector and a second distance corresponding to the second search term vector, and wherein the weighted sum is calculated using homomorphic analogues of multiplication and addition applied to a first encrypted distance corresponding to the first search term vector and a second encrypted distance corresponding to the second search term vector. 
     
     
       12. The system of  claim 8 , wherein the vector manager is further configured to determine the semantic match when the decrypted distance is less than a threshold distance. 
     
     
       13. The system of  claim 8 , wherein the vector manager is further configured to:
 obtain a multiplication result by combining the one or more encrypted distances together using a homomorphic analogue of multiplication defined by a homomorphic encryption scheme. 
 
     
     
       14. The system of  claim 13 , wherein the vector manager is further configured to obtain the multiplication result by combining the one or more encrypted distances together using multiplication, wherein the homomorphic encryption scheme defines the homomorphic analogue of multiplication to be multiplication. 
     
     
       15. A non-transitory computer readable medium comprising instructions that, when executed by a computer processor, perform:
 generating one or more word string vectors for one or more word strings in a document, wherein the one or more word string vectors represent meanings of the one or more word strings as points in a multi-dimensional semantic space; 
 obtaining one or more encrypted word string vectors by encrypting the one or more word string vectors; 
 generating a search vector for a search query, wherein the search vector is in the multi-dimensional semantic space; 
 obtaining an encrypted search vector by encrypting the search vector; 
 calculating one or more encrypted distances between the one or more encrypted word string vectors and the encrypted search vector; 
 obtaining a decrypted distance by decrypting an encrypted distance of the one or more encrypted distances; and 
 using the decrypted distance, determining a semantic match between the search query and the document, 
 wherein the one or more word string vectors and the search vector are each semantic representations of a natural language word string that includes a vector in the multi-dimensional semantic space with a value assigned to each dimension of the vector based at least partially on semantic co-occurrences in a corpus of natural language documents. 
 
     
     
       16. The non-transitory computer readable medium of  claim 15 , wherein the instructions further perform:
 generating a first search term vector for the first search term; and 
 generating a second search term vector for the second search term. 
 
     
     
       17. The non-transitory computer readable medium of  claim 16 , wherein the instructions further perform:
 obtaining a first encrypted search term vector by encrypting the first search term vector; and 
 obtaining a second encrypted search term vector by encrypting the second search term vector, wherein the encrypted distance is calculated using the first encrypted search term vector and the second encrypted search term vector. 
 
     
     
       18. The non-transitory computer readable medium of  claim 17 , wherein the encrypted distance is calculated as an encrypted weighted sum of a first distance corresponding to the first search term vector and a second distance corresponding to the second search term vector, and wherein the weighted sum is calculated using homomorphic analogues of multiplication and addition applied to a first encrypted distance corresponding to the first search term vector and a second encrypted distance corresponding to the second search term vector. 
     
     
       19. The non-transitory computer readable medium of  claim 15 , wherein the semantic match is determined when the decrypted distance is less than a threshold distance. 
     
     
       20. The non-transitory computer readable medium of  claim 15 , wherein the instructions further perform:
 obtaining a multiplication result by combining the one or more encrypted distances together using a homomorphic analogue of multiplication defined by a homomorphic encryption scheme.