# US 2012/0254606 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/0254606 A1
- Document ID: US20120254606A1
- Status: Published application
- Kind: A1
- Application number: 13/076,424
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Mitsubishi Electric Research Laboratories, Inc.
- Inventors: Wei Sun; Shantanu Rane
- Web page: https://patentgrep.com/patent/US20120254606A1

## 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 2209/50: Oblivious transfer
- 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 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

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

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

The method of claim 2, 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 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 bj+γtj, wherein the receiving the encryption includes:
receiving ξ(log bj(xt)+γ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 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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 aij)=ξ(log δt(i))·ξ(log aij), wherein ξ(log δt(i)) is an encryption of a logarithm of probability of most probable state sequence ending in the state Si for the current element xt, ξ(.) is an encryption function of the additively homomorphic cryptosystem, ξ(log aij) is an encryption of a logarithm of the transition probability to the state Si from the state Sj.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

The method of claim 1, wherein the determining the encrypted product comprises:
determining the encrypted product using H-Comparison method.

### Claim 8 (depends on 1)

The method of claim 1, wherein the determining the encrypted log-probability comprises:
determining ξ(log δt+1(j)) according to ξ(log δt+1(j))=ξ(maxi[ log δt(i)+log aij])·ξ(log bj(xt)), wherein log δt+1(j) is a logarithm of the log-probability of the most probable state sequence ending in a state Sj for a next element xt+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 Si for the current element xt, log aij is a logarithm of a transition probability from the state Si to the state Sj.

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

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
transmitting the encrypted index to the client.

### Claim 12 (depends on 10)

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.

### Claim 13 (depends on 9)

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.

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

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 15)

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.

### Claim 18 (depends on 14)

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.
