Privacy-Preserving Probabilistic Inference Based on Hidden Markov Models

• US 20120254606A1
• Filed: 03/31/2011
• Published: 10/04/2012
• Est. Priority Date: 03/31/2011
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Sun, Wei, Rane, Shantanu
• Granted Patent: US 8,402,263 B2
• Time in Patent Office: Days
• US Class Current: 713/150
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 2209/50 Oblivious transfer
• CPC Class Codes: H04L 9/008 involving homomorphic encryption

Abstract

A most likely sequence of states corresponding to an observation sequence stored at a client is determined securely with respect to a HMM stored at a server. An encryption of a log-probability of the current element of the observation sequence is determined for each state of the HMM. A product of an encryption of the log-probability of the state for the current element, an encryption of a transition probability to the state, and the encryption of a log-probability of the current element of the observation sequence is determined iteratively, for each state of the HMM, to produce an encrypted matrix of indexes of the states; and the encrypted matrix is transmitted to the client.

Claims

1. A method for determining a most likely sequence of states corresponding to an observation sequence stored at a client, wherein the sequence of states is determined with respect to a hidden Markov model (HMM) stored at a server, wherein the client has a decryption key and an encryption key of an additively homomorphic cryptosystem, and the server has only the encryption key, comprising the steps of:

determining, for each state of the HMM, an encryption of a log-probability of a current element of the observation sequence;

determining, for each state of the HMM, a product of an encryption of the log-probability of the state for the current element and an encryption of a transition probability to the state using additive homomorphism to produce a set of encrypted products;

determining an encrypted product corresponding to a maximum product in the set of encrypted products and an encrypted index of the state corresponding to the maximum product;

transmitting the encrypted index to the client;

determining, for each state of the HMM, an encrypted log-probability of the state for a next element as a product of the encrypted product and the encryption of a log-probability of the current element of the observation sequence corresponding to the state; and

repeating the determining the encrypted product and the encrypted index, the transmitting the encrypted index, and the determining the log-probability for all elements of the observation sequence, wherein steps of the method are performed by the server.

2. The method of claim 1, wherein, for each state, further comprising:

determining a modification vector;

transmitting a column vector of log-probabilities of the elements of the observation sequence modified with the modification vector to the client;

receiving the encryption of the log-probability of each element of the observation sequence modified with the modification vector; and

removing the modification vector to produce the encryption of the log-probability of each element.

3. The method of claim 2, wherein the HMM λ

is defined according to λ

=(A,B,Π

), wherein A=(a_ij) is a state transition matrix, a_ij is a transition probability from a state S_i to a state S_j, wherein 1≦

i,j≦

N, and N is a number of states of the HMM, wherein B=(b₁,b₂, . . . , b_N) is a matrix of probabilities of observations, b_j is a column vector of the matrix of probabilities over alphabet of the observation sequence, j=1,2, . . . , N, wherein Π

=(π

₁,π

₂, . . . , π

_N) is an initial state probability vector of the HMM, wherein a function ξ

(.) is an encryption function of the additively homomorphic cryptosystem, wherein the determining the modification vector includes;

generating randomly the modification vector (γ

_tj) t=1,2, . . . , T, wherein the transmitting the column vector includes;

transmitting log b_j+γ

_tj, wherein the receiving the encryption includes;

receiving ξ

(log b_j(x_t)+γ

_tj), wherein a function ξ

(.) is an encryption function of the additively homomorphic cryptosystem, wherein the removing the modification vector includes;

determining the encryption of the log-probability ξ

(log b_j(x_t)) of each element x_t according to ξ

(log b_j(x_t)+γ

_tj)·

ξ

(−

γ

_tj).

4. The method of claim 1, wherein the determining the product of the encryption comprises:

determining the product of the encryption using at least one property of additive homomorphism.

5. The method of claim 4, wherein the determining the product of the encryption comprises:

determining the product of the encryption according to ξ

(log δ

_t(i)+log a_ij)=ξ

(log δ

_t(i))·

ξ

(log a_ij), wherein ξ

(log δ

_t(i)) is an encryption of a logarithm of probability of most probable state sequence ending in the state S_i for the current element x_t, ξ

(.) is an encryption function of the additively homomorphic cryptosystem, ξ

(log a_ij) is an encryption of a logarithm of the transition probability to the state S_i from the state S_j.

6. The method of claim 1, wherein the determining the encrypted product comprises:

determining the encrypted product using a secure multiparty computation (SMC) between the server and the client.

7. The method of claim 1, wherein the determining the encrypted product comprises:

determining the encrypted product using H-Comparison method.

8. The method of claim 1, wherein the determining the encrypted log-probability comprises:

determining ξ

(log δ

_t+1(j)) according to ξ

(log δ

_t+1(j))=ξ

(max_i[ log δ

_t(i)+log a_ij])·

ξ

(log b_j(x_t)), wherein log δ

_t+1(j) is a logarithm of the log-probability of the most probable state sequence ending in a state S_j for a next element x_t+1, ξ

(.) is an encryption function of the additively homomorphic cryptosystem, wherein max is a maximum operation, log δ

_t(i) is a logarithm of the log-probability of the most probable state sequence ending in a state S_i for the current element x_t, log a_ij is a logarithm of a transition probability from the state S_i to the state S_j.

9. A method for determining a most likely sequence of states corresponding to an observation sequence stored at a client, wherein the sequence of states is determined with respect to a hidden Markov model (HMM) stored at a server, wherein the client has a decryption key and an encryption key of an additively homomorphic cryptosystem, and the server has only the encryption key, wherein steps of the method are performed by the server, wherein at least one step is performed in encrypted domain using additive homomorphism, comprising the steps of:

determining, for each state of the HMM, an encryption of a log-probability of the current element of the observation sequence;

determining iteratively, for each state of the HMM, a product of an encryption of the log-probability of the state for the current element, an encryption of a transition probability to the state, and the encryption of a log-probability of the current element of the observation sequence to produce an encrypted matrix of indexes of the states; and

transmitting the encrypted matrix to the client, wherein steps of the method are performed by the server.

10. The method of claim 9, wherein the determining iteratively comprises:

determining a product of the encryption of the log-probability of the state for the current element and an encryption of a transition probability to the state using additive homomorphism to produce a set of encrypted products; and

determining an encrypted product corresponding to a maximum product in the set of encrypted products and an encrypted index of the state corresponding to the maximum product.

11. The method of claim 10, further comprising:

transmitting the encrypted index to the client.

12. The method of claim 10, further comprising:

determining, for each state of the HMM, an encrypted log-probability of the state for a next element as a product of the encrypted product and the encryption of a log-probability of the current element of the observation sequence corresponding to the state; and

repeating the determining the encrypted product and the encrypted index, the transmitting the encrypted index, and the determining the log-probability for all elements of the observation sequence, wherein steps of the method are performed by the server.

13. The method of claim 9, wherein the determining the encryption of the log-probability comprises:

determining a modification vector;

transmitting a column vector of log-probabilities of the elements of the observation sequence modified with the modification vector to the client;

receiving the encryption of the log-probability of each element of the observation sequence modified with the modification vector; and

removing the modification vector to produce the encryption of the log-probability of each element.

14. A server for determining a most likely sequence of states corresponding to an observation sequence stored at a client, wherein the sequence of states is determined with respect to a hidden Markov model (HMM) stored at the server, wherein the client has a decryption key and an encryption key of an additively homomorphic cryptosystem, and the server has only the encryption key, comprising:

a processor, wherein the processor is configured for;

determining, for each state of the HMM, an encryption of a log-probability of the current element of the observation sequence;

determining iteratively, for each state of the HMM, a product of an encryption of the log-probability of the state for the current element, an encryption of a transition probability to the state, and the encryption of a log-probability of the current element of the observation sequence to produce an encrypted matrix of indexes of the states; and

transmitting the encrypted matrix to the client, wherein steps of the method are performed by the server.

15. The server of claim 14, wherein the processor is further configured for:

determining a product of the encryption of the log-probability of the state for the current element and an encryption of a transition probability to the state using additive homomorphism to produce a set of encrypted products; and

determining an encrypted product corresponding to a maximum product in the set of encrypted products and an encrypted index of the state corresponding to the maximum product.

16. The method of claim 15, wherein the processor is further configured for transmitting the encrypted index to the client.

17. The method of claim 15, wherein the processor is configured for:

determining, for each state of the HMM, an encrypted log-probability of the state for a next element as a product of the encrypted product and the encryption of a log-probability of the current element of the observation sequence corresponding to the state; and

repeating the determining the encrypted product and the encrypted index, the transmitting the encrypted index, and the determining the log-probability for all elements of the observation sequence, wherein steps of the method are performed by the server.

18. The server of claim 14, wherein the processor is further configured for:

determining a modification vector;

transmitting a column vector of log-probabilities of the elements of the observation sequence modified with the modification vector to the client;

receiving the encryption of the log-probability of each element of the observation sequence modified with the modification vector; and

removing the modification vector to produce the encryption of the log-probability of each element.