Threshold searchable symmetric encryption
A data owner can provide shares of a cryptographic key to N key servers. The N key servers can store the shares of a cryptographic key from the data owner such that T shares of the cryptographic key can be used to reconstruct the cryptographic key. A client computer can send a blinded query to T key servers of the N key severs, wherein the T key servers can encrypt a blinded query of a client computer using the share of the cryptographic key to determine a partial encryption. The client computer can receive T partial encryptions, assemble T partial encryptions to form an encrypted blinded query, and deblind the encrypted blinded query. The client computer can then use the encrypted query to perform a search on encrypted data of a remote database server using a searchable symmetric encryption scheme.
1 . A method of performing a threshold searchable symmetric encryption comprising performing, by a client computer:
transmitting a blinded query to T key server computers of N key server computers, wherein the N key server computers store shares of a cryptographic key from a data owner computer, wherein T is an integer less than or equal to N, wherein T shares are required to reconstruct the cryptographic key, wherein the blinded query is generated from a query configured to be sent to a remote database server that stores encrypted data;
receiving, from the T key server computers, T partial encryptions of the blinded query, wherein each of the T partial encryptions is generated by applying a first cryptographic function to the blinded query using a respective share of the T shares of the cryptographic key;
generating an encrypted query token by deblinding and assembling the T partial encryptions; and
performing an encrypted search on the remote database server using the encrypted query token;
wherein performing the encrypted search includes transmitting the encrypted query token to the remote database server, wherein the remote database server is configured to perform a search using the encrypted query token on the encrypted data to obtain an encrypted response;
wherein the encrypted query token is generated using a hash function, and wherein the remote database server is configured to use a lookup table to determine the encrypted data corresponding to the encrypted query token.
2 . The method of claim 1 , wherein the method further comprises:
receiving, by a primary user device, a first biometric information from a user,
generating, by the primary user device, a biometric template using the first biometric information and a secret-public key pair,
transmitting, by the primary user device, a public key of the secret-public key pair to the remote database server,
transmitting, by the primary user device, shares of a secret key of the secret-public key pair and the biometric template to N signing computers such that any combination of T shares are required to reconstruct the secret key.
3 . The method of claim 2 , further comprising performing, by the client computer:
receiving a second biometric information from the user,
receiving a challenge from the remote database server,
transmitting the second biometric information and the challenge to T signing computers among the N signing computers,
receiving T signed shares of the challenge from the T signing computers, wherein the T signed shares of the challenge are generated by the T signing computers in response to the second biometric information and the biometric template matching,
assembling the T signed shares of the challenge to configure a complete signature,
transmitting the complete signature to the remote database server, wherein the remote database server is configured to authenticate the client computer for access to the T key server computers by validating the complete signature using the public key.
4 . The method of claim 3 , wherein the primary user device is the client computer.
5 . The method of claim 3 , wherein the N signing computers are the N key server computers.
6 . The method of claim 3 , wherein the encrypted data is data encrypted by the data owner computer using the cryptographic key.
7 . The method of claim 3 , wherein the first biometric information includes measurement of first biometric features of the user and the second biometric information includes measurement of second biometric features of the user.
8 . The method of claim 7 , wherein the biometric template includes a template vector, wherein the template vector comprises measured values of first biometric features.
9 . The method of claim 8 , wherein the second biometric information includes a measurement vector, wherein the measurement vector comprises measured values of the second biometric information of the user.
10 . The method of claim 9 , wherein the second biometric information and the biometric template matching includes matching shares of the template vector with the measurement vector.
11 . The method of claim 1 , wherein the method further comprises: receiving the encrypted response from the remote database server; blinding the encrypted response to determine a blinded encrypted response; transmitting the blinded encrypted response to the T key server computers of the N key server computers; receiving, from the T key server computers, T partial decryptions of the blinded encrypted response, wherein each of the T partial decryptions is generated by applying a second cryptographic function to the blinded encrypted response using the respective share of the T shares of the cryptographic key; and generating a decrypted response by deblinding and assembling the T partial decryptions.
12 . The method of claim 11 , wherein the first cryptographic function is a symmetric encryption algorithm and the second cryptographic function is a symmetric decryption algorithm.
13 . The method of claim 1 , wherein the cryptographic key is a symmetric key.
14 . The method of claim 1 , wherein the blinded query is transmitted to X key server computers, wherein the X is in a range of T<X≤N.
15 . A computer product comprising a non-transitory computer readable medium storing a plurality of instructions that when executed cause a computer system to perform a method of performing a threshold searchable symmetric encryption, the method comprising:
transmitting a blinded query to T key server computers of N key server computers, wherein the N key server computers store shares of a cryptographic key from a data owner computer, wherein T is an integer less than or equal to N, wherein T shares are required to reconstruct the cryptographic key, wherein the blinded query is generated from a query configured to be sent to a remote database server that stores encrypted data;
receiving, from the T key server computers, T partial encryptions of the blinded query, wherein each of the T partial encryptions is generated by applying a first cryptographic function to the blinded query using a respective share of the T shares of the cryptographic key;
generating an encrypted query token by deblinding and assembling the T partial encryptions; and
performing an encrypted search on the remote database server using the encrypted query token;
wherein performing the encrypted search includes transmitting the encrypted query token to the remote database server, wherein the remote database server is configured to perform a search using the encrypted query token on the encrypted data to obtain an encrypted response;
wherein the encrypted query token is generated using a hash function, and wherein the remote database server is configured to use a lookup table to determine the encrypted data corresponding to the encrypted query token.
16 . A system comprising:
a non-transitory computer readable medium; and
one or more processors configured to execute instructions stored on the non-transitory computer readable medium to perform a method of performing a threshold searchable symmetric encryption, the method comprising:
transmitting a blinded query to T key server computers of N key server computers, wherein the N key server computers store shares of a cryptographic key from a data owner computer, wherein T is an integer less than or equal to N, wherein T shares are required to reconstruct the cryptographic key, wherein the blinded query is generated from a query configured to be sent to a remote database server that stores encrypted data;
receiving, from the T key server computers, T partial encryptions of the blinded query, wherein each of the T partial encryptions is generated by applying a first cryptographic function to the blinded query using a respective share of the T shares of the cryptographic key;
generating an encrypted query token by deblinding and assembling the T partial encryptions; and
performing an encrypted search on the remote database server using the encrypted query token;
wherein performing the encrypted search includes transmitting the encrypted query token to the remote database server, wherein the remote database server is configured to perform a search using the encrypted query token on the encrypted data to obtain an encrypted response;
wherein the encrypted query token is generated using a hash function, and wherein the remote database server is configured to use a lookup table to determine the encrypted data corresponding to the encrypted query token.