Patent ID: 8402263

Claim:
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 of the HMM for the current element and an encryption of a transition probability to the state of the HMM using additive homomorphism to produce a set of encrypted products; determining a maximum 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 of the HMM for a next element as a product of the maximum encrypted product and the encryption of a log-probability of the current element of the observation sequence corresponding to the state of the HMM; 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.