Privacy-Preserving Probabilistic Inference Based on Hidden Markov Models

• US 20120254612A1
• Filed: 03/30/2011
• Published: 10/04/2012
• Est. Priority Date: 03/30/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: Rane, Shantanu, Sun, Wei, Pathak, Manas A., Raj, Bhiksha
• Granted Patent: US 8,433,892 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• 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 9/008 involving homomorphic encryption

Abstract

A probability of an observation sequence stored at a client is evaluated securely with respect to a hidden Markov model (HMM) stored at a server. The server determines, for each state of the HMM, an encryption of a log-probability of a current element of the observation sequence. Determines, for each state of the HMM, an encryption of a log-summation of a product of a likelihood of the observation sequence based on a previous element of the observation sequence and a transition probability to the state of the HMM. Determines an encryption of a log-likelihood of the observation sequence for each state as a product of the encryption of a log-summation and an encryption of a corresponding log-probability of the current element of the observation sequence; and determines an encryption of the log-probability of the observation sequence based on the log-likelihood of the observation sequence for each state.

Claims

1. A method for evaluating a probability of an observation sequence stored at a client 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 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, an encryption of a log-summation of a product of a likelihood of the observation sequence based on a previous element of the observation sequence and a transition probability to the state of the HMM, wherein the determining uses an H-SMC, wherein the H-SMC includes a secure multiparty computation using at least one property of additive homomorphism;

determining an encryption of a log-likelihood of the observation sequence for each state as a product of the encryption of a log-summation and an encryption of a corresponding log-probability of the current element of the observation sequence; and

determining an encryption of the log-probability of the observation sequence based on the log-likelihood of the observation sequence for each state, wherein steps of the method are performed by the server.

2. The method of claim 1, further comprising:

transmitting the log-probability of the observation sequence to the client.

3. The method of claim 1, wherein the H-SMC includes an H-LogSum method.

4. The method of claim 1, 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 the determining the encryption of the log-summation includes;

determining the encryption of the log-summation according to

ξ

(log Σ

_l=1^Nα

_t(l)a_lj),

wherein a function ξ

(.) is an encryption function of the additively homomorphic cryptosystem, l is an index of a state S_l, l=1, 2, . . . , N, wherein α

_t(l) is the likelihood of the observation sequence of the previous element x_t at a state S_l, and a_lj is the transition probability from the state S_l to the state S_j of the HMM, and wherein the determining the encryption of the log-probability of the current element of the observation sequence includes;

determining the encryption of the log-probability according to

ξ

(log b_j(x_t+1)),

wherein x_t+1 is the current element, and wherein the determining the encryption of the log-likelihood of the observation sequence ξ

(log α

_t+1(j)) is according to

5. The method of claim 1, further comprising:

determining a modification vector;

transmitting a column vector of log-probabilities of an alphabet 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.

6. The method of claim 5, 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 the determining the modification vector includes;

generating randomly the modification vector γ

_tj, wherein the transmitting the column vector includes;

transmitting log b_j+γ

_tj, wherein the receiving the encryption includes;

receiving ξ

(log b_j+γ

_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).

7. The method of claim 1, wherein each element in the observation sequence includes a vector with values having a multivariate Gaussian distribution, and wherein the determining the encryption of the log-probability of the current element comprises:

determining, for each state of the HMM, in response to receiving an encryption of a function of a current element, a product of the encryption of the function of the current element and a matrix of the multivariate Gaussian distribution.

8. The method of claim 7, wherein each element includes a d-dimensional vector x_t of mel frequency cepstral coefficients, such that log b_j(x_t)=z_t^TW_jz_t, wherein b_j is a column vector of a matrix of probabilities over the alphabet of the observation sequence, an observation vector z_t=[x_t^T,1]^T, wherein T is a transpose operator, 1≦

j≦

N, and N is a number of states of the HMM, W_j is a matrix of a multivariate Gaussian distribution, wherein the determining includes;

determining, in response to receiving an encryption of products z_m^(t)z_n^(t) of elements of the observation vector, the encryption of the log-probability ξ

(log b_j(x_t)) according to

ξ

(log b_j(x_t))=ξ

(z_t^TW_jz_t)

using at least one property of an additive homomorphism, wherein z_m^(t), z_n^(t) are elements of the observation vector z_t, m, nε

{1, 2, . . . , d+1}.

9. The method of claim 7, further comprising:

determining the log-probability of the observation sequence for each HMM stored at the server to produce a set of encrypted log-probabilities;

obfuscating the set of log-probabilities with an order-preserving matrix to produce an obfuscated set of encrypted log-probabilities;

transmitting the obfuscated set of log-probabilities to the client; and

transmitting to the client a keyword of the HMM corresponding to a particular log-probability selected by the client based on the obfuscated set of log-probabilities.

10. The method of claim 9, wherein the particular log-probability corresponds to a maximum probability of the observation sequence with respect to each HMM.

11. The method of claim 1, further comprising:

determining the encryption of the log-summation using an H-LogSum method having as an input a set of encryptions of a logarithm of a likelihood of an element of the observation sequence at each state of the HMM, and a set of transition probabilities to each state of the HMM.

12. The method of claim 1, further comprising:

determining the encryption of the log-probability of the observation sequence using an H-LogSum method having as an input the log-likelihood of the observation sequence for each state.

13. A method for evaluating a probability of an observation sequence stored at a client 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 iteratively a set of encryptions of a log-likelihood of elements of the observation sequence with respect to each state of the HMM using an H-SMC, wherein the H-SMC includes a secure multiparty computation using at least one property of additive homomorphism; and

determining, based on the set of encryptions, an encryption of the log-probability of the observation sequence with respect to the HMM using the H-SMC, wherein steps of the method are performed by the server.

14. The method of claim 13, wherein the H-SMC includes an H-LogSum method.

15. The method of claim 13, wherein the determining the set of encryptions comprises:

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

determining, for each state of the HMM, an encryption of a log-summation of a product of a likelihood of the observation sequence based on a previous element of the observation sequence and a transition probability to the state of the HMM, wherein the determining uses the H-SMC; and

determining an encryption of a log-likelihood of the observation sequence as a product of the encryption of a log-summation and the encryption of the log-probability.

16. The method of claim 15, further comprising:

determining the encryption of the log-summation using an H-LogSum method having as an input a set of encryptions of a logarithm of a likelihood of an element of the observation sequence at each state of the HMM, and a set of transition probabilities to each state of the HMM.

17. A server for evaluating a probability of an observation sequence stored at a client 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, wherein steps of the method are performed by the server, comprising:

a processor for determining iteratively a set of encryptions of a log-likelihood of elements of the observation sequence with respect to each state of the HMM using an H-SMC, wherein the H-SMC includes a secure multiparty computation using at least one property of additive homomorphism; and

for determining, based on the set of encryptions, an encryption of the log-probability of the observation sequence with respect to the HMM using the H-SMC.

18. The system of claim 17, wherein the H-SMC includes at least one or combination of an H-Logarithm method, an H-Exponent method, an H-LogSum method, an H-Comparison method, and an H-SumPartition method.