# US 2012/0254612 A1 · Privacy-Preserving Probabilistic Inference Based on Hidden Markov Models

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254612 A1
- Document ID: US20120254612A1
- Status: Published application
- Kind: A1
- Application number: 13/076,410
- Filed: 2011-03-30
- Published: 2012-10-04
- Earliest claimed: 2011-03-30
- Assignees: Mitsubishi Electric Research Laboratories, Inc.
- Inventors: Shantanu Rane; Wei Sun; Manas A. Pathak; Bhiksha Raj
- Web page: https://patentgrep.com/patent/US20120254612A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## 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

### Claim 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.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
transmitting the log-probability of the observation sequence to the client.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

The method of claim 1, wherein the HMM λ is defined according to λ=(A, B, Π) wherein A=(aij) is a state transition matrix, aij is a transition probability from a state Si to a state Sj, wherein 1≦i, j≦N, and N is a number of states of the HMM, wherein B=(b1, b2, . . . , bN) is a matrix of probabilities of observations, bj is a column vector of the matrix of probabilities over alphabet of the observation sequence, j=1, 2, . . . , N, wherein Π=(π1, π2, . . . , π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=1Nαt(l)alj),
wherein a function ξ(.) is an encryption function of the additively homomorphic cryptosystem, l is an index of a state Sl, l=1, 2, . . . , N, wherein αt(l) is the likelihood of the observation sequence of the previous element xt at a state Sl, and alj is the transition probability from the state Sl to the state Sj 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 bj(xt+1)),
wherein xt+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
ξ

(
log


α
t
+
1

(
j
)
)
=
ξ

(
log

∑
l
=
1
N

α
t

(
l
)

a
ij
)
·
ξ

(
log


b
j

(
x
t
+
1
)
)
.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

The method of claim 5, wherein the HMM λ is defined according to λ=(A, B, Π), wherein A=(aij) is a state transition matrix, aij is a transition probability from a state Si to a state Sj, wherein 1≦i, j≦N, and N is a number of states of the HMM, wherein B=(b1, b2, . . . , bN) is a matrix of probabilities of observations, bj is a column vector of the matrix of probabilities over alphabet of the observation sequence, j=1, 2, . . . , N, wherein Π=(π1, π2, . . . , π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 bj+γtj, wherein the receiving the encryption includes:
receiving ξ(log bj+γ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 bj(xt)) of each element xt according to (log bj(xt)+γtj)·ξ(−γtj).

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

The method of claim 7, wherein each element includes a d-dimensional vector xt of mel frequency cepstral coefficients, such that log bj(xt)=ztTWjzt, wherein bj is a column vector of a matrix of probabilities over the alphabet of the observation sequence, an observation vector zt=[xtT,1]T, wherein T is a transpose operator, 1≦j≦N, and N is a number of states of the HMM, Wj is a matrix of a multivariate Gaussian distribution, wherein the determining includes:
determining, in response to receiving an encryption of products zm(t)zn(t) of elements of the observation vector, the encryption of the log-probability ξ(log bj(xt)) according to
ξ(log bj(xt))=ξ(ztTWjzt)
using at least one property of an additive homomorphism, wherein zm(t), zn(t) are elements of the observation vector zt, m, nε{1, 2, . . . , d+1}.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 1)

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.

### Claim 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.

### Claim 14 (depends on 13)

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

### Claim 15 (depends on 13)

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.

### Claim 16 (depends on 15)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.
