# Patent

## Title
System and method for recognizing speech securely using a secure multi-party computation protocol

## Abstract

A system and method recognizes speech securely using a secure multi-party computation protocol. The system includes a client and a server. The client is configured to provide securely speech in a form of an observation sequence of symbols, and the server is configured to provide securely a multiple trained hidden Markov models (HMMs), each trained HMM including a multiple states, a state transition probability distribution and an initial state distribution, and each state including a subset of the observation symbols and an observation symbol probability distribution. The observation symbol probability distributions are modeled by mixtures of Gaussian distributions. Also included are means for determining securely, for each HMM, a likelihood the observation sequence is produced by the states of the HMM, and means for determining a particular symbol with a maximum likelihood of a particular subset of the symbols corresponding to the speech.

## Background
FIELD OF THE INVENTION
This invention relates generally to speech recognition, and more particularly to recognizing speech securely.
BACKGROUND OF THE INVENTION
Secure Multi-Party Computation
With the widespread availability of communication networks, such as the Internet, it is now common to ‘outsource’ data processing tasks to third parties for a number of reasons. For example, the processing can be done at a reduced cost, or the third party has better computational resources or better technologies. One concern with outsourcing data processing is an inappropriate use of confidential information by third parties.
A user or client computer system, perhaps with limited data processing resources, desires to recognize speech. A third party or server computer system has some of the necessary resources. Conventionally, the client and the server are usually called Alice and Bob, respectively. Speech recognition could easily be a part of this trend, where now third-party servers provide speech recognition services for remote clients.
The private nature of speech data however is a stumbling block for such a development. Individuals, corporations and governments are understandably reluctant to send private speech through a network to another party that cannot be trusted.
It is desired to have the third party sever recognize the speech without revealing the speech to the third party. At the same time, the third party wants to keep its speech recognizer secret. For such applications, conventional cryptography protects only the speech during transport, and not the processing by the third party.
Secure multi-party computations (SMC) are often analyzed for correctness, security, and overhead. Correctness measures how close a secure process approaches an ideal solution. Security measures the amount of information that can be gained from the multi-party exchange. Overhead is a measure of complexity and efficiency.
A multi-party protocol between Alice and Bob is secure when privacy and correctness are guaranteed for both Alice and Bob. The protocol protects privacy when the information that is ‘leaked’ by the distributed computation is limited to the information that can be learned from the designated output of the computation.
In a semi-honest case, both parties follow the protocol as prescribed but may record all messages and subsequently deduce information not derivable solely from the protocol output. In the malicious case, however, no assumption is made about: the behavior of the parties. It: is required that the privacy of one party is preserved even in the case of an arbitrary behavior of another party. A protocol in the semi-honest case can be made secure in the malicious case when accompanied with zero-knowledge proofs that both parties follow the protocol.
Zero Knowledge Protocols
Zero-knowledge or secure multi-party protocols were first described by Yao, “How to generate and exchange secrets,” Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 162-167, 1986, incorporated herein by reference. Later, that: zero-knowledge technique was extended to other problems, Goldreich et al., “How to play any mental game—a completeness theorem for protocols with honest majority,” 19th ACM Symposium on the Theory of Computing, pp 218-229, 1987, incorporated herein by reference. However, those theoretical constructs are still too demanding to be of any use for practical applications.
Since then, many secure methods have been described, Chang et: al., “Oblivious Polynomial Evaluation and Oblivious Neural Learning,” Advances in Cryptology, Asiacrypt '01, Lecture Notes in Computer Science Vol. 2248, pages 369-384, 2001, Clifton et al., “Tools for Privacy Preserving Distributed Data Mining,” SIGKDD Explorations, 4(2); 28-34, 2002, Koller et al, “Protected Interactive 3D Graphics Via Remote Rendering,” SIGGRAPH 2004, Lindell et al., “Privacy preserving data mining,” Advances in Cryptology—Crypto 2000, LNCS 1880, 2000, Naor et al., “Oblivious Polynomial Evaluation.” Proc. of the 31st Symp. on Theory of Computer Science (STOC), pp. 245-254, May 1999, and Du et al., “Privacy-preserving cooperative scientific computations,” 4th IEEE Computer Security Foundations Workshop, pp. 273-282, Jun. 11, 2001, all incorporated herein by reference.
Secure Inner Dot Products
A large number of computer implemented methods and applications require that one computes an inner product. Therefore, protocols and procedures for determining a secure inner dot product (SIP) have been developed. It is understood that these protocols are known to those of ordinary skill in the art.
The protocols can be categorized broadly as cryptographic protocols and algebraic protocols. The protocols provide different levels of security and efficiency. Because the computational cost, in general, is constantly decreasing, the main concern in evaluating the protocols is security and communication costs.
Generally, an inner dot product of two vectors x and y produces two scalar values a and b according to xTy=a+b, where T is the transpose operator.
Cryptographic Protocols
Several methods are known for providing secure inner dot products, see B. Goethals, S. Lain, H. Lipmaa, and T, Mielikainen, “On private scalar product computation for privacy-preserving data mining,” C. Park and S. Chee, editors, Intl. Conference on Information Security and Cryptology, volume 2506 of Lecture Notes in Computer Science, pages 104-120, 2004; X Feigenbaum, Y. .Ishai, T. Malkin, K, Nissim, M. Strauss, and R, N. Wright, “Secure multi-party computation of approximations,” Proceedings of the Intl. Colloquium on Automata, Languages and Programming, volume 2076 of Lecture Notes in Computer Science, pages 927-938, 2001; R. Canetti, Y. Ishai, R. Kumar, M, K. Reiter, R. Rubinfeld, and R. N. Wright, “Selective private function evaluation with applications to private statistics,” Proceedings of the ACM symposium on principles of distributed computing, pages 293-304, 2001, all incorporated herein by reference.
The Goetbal, et al. protocol has as input private vectors x, y, belonging to Bob and Alice respectively, and as output the scalar values a and b such that a+b=xTy. During an initialization phase. Bob generates a private and public key pair (sk, pk). Bob sends pk to Alice. Then, for each i ε {1, . . . , d}. Bob generates a new random string ri, and sends ci=En(pk; xi, ri) to Alice. In response, Alice sets




  
    z
    ←
    
      
        ∏
        
          i
          =
          1
        
        d
      
      ⁢
      
        c
        i
        
          y
          i
        
      
    
  
  ,




generates a random plaintext b and a random nonce r′, and sends z′=z·En(pk; −b, r′) to Bob. Then, Bob determines a=De(sk; z′)=xTy−b. They describe a proof that the protocol is correct and secure. It can also be shown that the communication overhead is k′/τ, where k′ is the bit size of each encrypted message sent by Alice, and τ=└√{square root over (m/d)}┘ for a large m. In a homomorphic cryptosystem, typical values would be k′≈2048 and m≈21024, see Pascal Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” J. Stern, editor. Proceedings of Advances in Cryptology—EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 223-238,1999, and Ivan Damgard and Mads Jurik, “A generalization, simplification and some applications of Paillier's probabilistic public-key system,” Proceedings of the Intl. Workshop on Practice and Theory in Public Key Cryptography, volume 1992 of Lecture Notes in Computer Science, pages 119-136, 2001, all incorporated herein by reference.

Another protocol uses the technique of oblivious polynomial evaluation (OPE), see Moni Naor and Benny Pinkas, “Oblivious transfer and polynomial evaluation,” Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 245-254, 1999, incorporated herein by reference. The protocol uses an additive oracle, which computes every term xjyj of the dot product xTy and expresses the jth term as SAj+SBj. Alice and Bob receive SAj and SBj, respectively for all j. The result xTy is given by




  
    
      ∑
      
        i
        =
        1
      
      d
    
    ⁢
    
      S
      
        A
        i
      
    
  
  +
  
    
      ∑
      
        i
        =
        1
      
      d
    
    ⁢
    
      
        S
        
          B
          i
        
      
      .
    
  




Alice and Bob can implement the additive oracle using the OPE.

Canetti, et al. describe a protocol, which uses homomorphic encryption, for determining a weighted sum of a set of numbers from a data base. Feigenbaum, et al., describe a protocol to determine the L2 distance between two vectors, see Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. Strauss, and R. N. Wright, Secure multi-party computation of approximations,” Proceedings of the Intl. Colloquium on Automata, Languages and Programming, volume 2076 of Lecture Notes in Computer Science, pages 927-938, 2001, all incorporated herein by reference. Both of those protocols can be used to determine dot-products securely.
Algebraic Protocols
Algebraic protocols can also be used for determining secure dot products, However, most of these protocols leak some information, see W. Du and M, J. Atallah, “Privacy-preserving cooperative statistical analysis,” Proceedings of the 17th Annual Computer Security Applications Conference, December 2001; W. Du and Z. Zhan, “A practical approach to solve secure multi-party computation problems,” Proceedings of New Security Paradigms Workshop, Sep. 23-26 2002; I. Ioannidis, A, Grama, and M. Atallah, “A secure protocol for computing dot-products in clustered and distributed environments,” Proceedings of the Intl. Conf. on Parallel Processing, 2002; P. Ravikuniar, W. W, Cohen, and S, E. Fienberg, “A secure protocol for computing string distance metrics,” Proceedings of the Workshop on Privacy and Security Aspects of Data Mining, pages 40-46, Brighton, UK, 2004; and J. Vaidya and C. Clifton, “Privacy preserving association rule mining in vertically partitioned data,” Proceedings of the Intl. Conf on Knowledge Discovery and Data Mining. The properties and weaknesses of some of these protocols have been analyzed, see E. Kiltz, G, Leander, and J. Malone-Lee, “Secure computation of the mean and related statistics,” Proceedings of the Theory of Cryptography Conference, volume 3378 of Lecture Notes in Computer Science, pages 283-302, 2005 and B. Goethals, S. Laur, H. Lipmaa, and T. Mielikainen, “On private scalar product computation for privacy-preserving data mining,” C. Park and S. Chee, editors, Intl., Conference on Information Security and Cryptology, volume 2506 of Lecture Notes in Computer Science, pages 104-120, 2004, all incorporated herein by reference.
The basic idea in the protocols of Du, et al., is to express the vector x as a sum or M random vectors, i.e.,




  
    ∑
    
      m
      =
      1
    
    M
  
  ⁢
  
    
      u
      m
    
    .
  




For every m, Alice sends um concealed in a set of k random vectors. Bob computes the dot product with y for all the vectors, and adds a random number rm to all products. The results are sent to Alice. Alice and Bob repeat this M times. Finally, Alice and Bob have





  
    
      
        ∑
        
          m
          =
          1
        
        M
      
      ⁢
      
        
          (
          
            
              
                u
                m
                t
              
              ⁢
              y
            
            +
            
              r
              m
            
          
          )
        
        ⁢
        
          
        
        ⁢
        and
      
    
    ⁢
    
      
    
    -
    
      
        ∑
        
          m
          =
          1
        
        M
      
      ⁢
      
        r
        m
      
    
  
  ,




respectively, which when added gives the required result.

Du, et al. use random permutations, Let π(x) be a vector whose elements are a random permutations of elements of x. The product π(x)Tπ(y) is equal to xTy. Bob expresses y as the sum of M random vectors, i.e.,




  y
  =
  
    
      ∑
      
        m
        =
        1
      
      M
    
    ⁢
    
      
        v
        m
      
      .
    
  




Bob generates m random vectors ri and m random permutations πm. For each m, Alice learns πm(x+rm) without learning πm or rm, using a homomorphic encryption scheme as in Du, et al. Bob sends πm(vm) to Alice, and Alice computes πm(x+rm)tπm(vm). Finally, Alice has





  
    
      ∑
      
        m
        =
        1
      
      M
    
    ⁢
    
      (
      
        
          
            x
            t
          
          ⁢
          
            v
            m
          
        
        +
        
          
            r
            m
            t
          
          ⁢
          
            v
            m
          
        
      
      )
    
  
  ,




and Bob has





  -
  
    
      ∑
      
        m
        =
        1
      
      M
    
    ⁢
    
      (
      
        
          r
          m
          t
        
        ⁢
        
          v
          m
        
      
      )
    
  




which together form the result. Alice's chances of successfully guessing all elements in y is





  
    
      (
      
        1
        
          d
          !
        
      
      )
    
    M
  
  .




Another protocol assumes that the number of elements d in the data vector x is even, A vector x1 is defined as d/2 dimension vector including the first d/2 elements of the vector x, and the vector x2 includes the last, d/2 elements of x, and xTy=xT1y1+xT2y2. Alice and Bob jointly generate a random invertible d×d matrix M. Alice computes x′=xTM, which is partitioned into x′1 and x′2, and sends x′2 to Bob. Bob computes y′=M−1y, splits it as y′1 and y′2 and sends y′1 to Alice. Alice computes x′1y′1 and Bob computes x+2y′2 so that their sum is the required result.
Other algebraic protocols for determining dot products are also known, see I. Ioannidis, A. Grama, and M. Atallah, “A secure protocol for computing dot-products in clustered and distributed environments,” Proceedings of the Intl. Conf. on Parallel Processing, 2002; J. Vaidya and C. Clifton, “Privacy preserving association rule mining in vertically partitioned data,” Proceedings of the Intl. Conf. on Knowledge Discovery and Data Mining, 2002, and P. Ravikumar, W, W. Cohen, and S. E. Fienberg, “A secure protocol for computing string distance metrics,” Proceedings of the Workshop on Privacy and Security Aspects of Data Mining, pages 40-46, 2004, all incorporated herein by reference.
Classifiers
Data classification is well known. If the data have a multivariate distribution, then the classifier typically uses multivariate Gaussian distributions. Each class can be modeled by either a single multivariate Gaussian distribution, or a mixture of multivariate Gaussian distributions.
The classifier determines a value of a discriminant function

gi(x)=ln p(x|ω1)+ln P(ωi)

for all classes ωi and assign the data x to class ωi, if gi(x)>gj(x) for all j≠i. Here, p(x|ωi) is a class-conditional probability density function, and P(ωi) is an a priori probability of class ωi.

Single Multivariate Gaussian Distribution

The mean vector and covariance matrix of the ith class are μi and Σi, respectively. Hence, p(x|ωi) ̃(μi, Σi), and the above Equation can be expressed as:




  
    
      g
      i
    
    ⁡
    
      (
      x
      )
    
  
  =
  
    
      
        -
        
          1
          2
        
      
      ⁢
      
        
          (
          
            x
            -
            
              μ
              i
            
          
          )
        
        t
      
      ⁢
      
        
          ∑
          i
          
            -
            1
          
        
        ⁢
        
          (
          
            x
            -
            
              μ
              i
            
          
          )
        
      
    
    -
    
      
        d
        2
      
      ⁢
      ln
      ⁢
      
        
      
      ⁢
      2
      ⁢
      π
    
    -
    
      
        1
        2
      
      ⁢
      ln
      ⁢
      
        
      
      ⁢
      
        
        
          ∑
          i
        
        
      
    
    +
    
      ln
      ⁢
      
        
      
      ⁢
      
        
          P
          ⁡
          
            (
            
              ω
              i
            
            )
          
        
        .
      
    
  




If the term (d/2) ln 2π term is ignored, then this can be rewritten as:

gi(x)=x′ Wix+ w′ix+wi0,

where





  
    
      
        
          
            
              W
              _
            
            i
          
          =
          
            
              -
              
                1
                2
              
            
            ⁢
            
              ∑
              i
              
                -
                1
              
            
          
        
        ⁢
        
          
        
        ,
      
    
  
  
    
      
        
          
            
              
                w
                _
              
              i
            
            =
            
              
                ∑
                i
                
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                μ
                i
              
            
          
          ,
          and
        
        ⁢
        
          
        
      
    
  
  
    
      
        
          w
          
            i
            ⁢
            
              
            
            ⁢
            0
          
        
        =
        
          
            
              -
              
                1
                2
              
            
            ⁢
            
              μ
              i
              t
            
            ⁢
            
              
                ∑
                i
                
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                μ
                i
              
            
          
          -
          
            
              1
              2
            
            ⁢
            ln
            ⁢
            
              
              
                ∑
                i
              
              ⁢
              
                
              
              
            
          
          +
          
            ln
            ⁢
            
              
            
            ⁢
            
              
                P
                ⁡
                
                  (
                  
                    ω
                    i
                  
                  )
                
              
              .
            
          
        
      
    
  




Vectors of (d+1)-dimensions, x and wi, can be generated by appending the value 1 to the vector x, and appending an element wi0 to the vector wi. By changing the matrix Wi into a (d+1)×(d+1) matrix Wi, where the first d components of the last row are zeros and the last column is equal to wit, gi(x)=xt Wix+ witx+wi0, can be written as:

gi(x)= xtWi x. 

Expressing x as x, the above Equation becomes:

gi(x)=xtWix. 

Mixture of Distributions Gaussian

The mean vector and covariance matrix of the jth Gaussian distribution in class ωi are μij and Σij, respectively. Hence,




  
    
      p
      ⁡
      
        (
        
          x
          ❘
          
            ω
            i
          
        
        )
      
    
    =
    
      
        ∑
        
          j
          =
          1
        
        
          J
          i
        
      
      ⁢
      
        
          α
          ij
        
        ⁢
        
          א
          (
          
            
              μ
              ij
            
            ,
            
              ∑
              ij
            
          
          ⁢
          
            
          
          )
        
      
    
  
  ,




where Ji is the number of Gaussian distributions describing class ωi, and αij are the coefficients of the mixture of Gaussian distributions.

A log likelihood for the jth Gaussian distribution in the ith class is given by



  
    
      
        
          l
          ij
        
        ⁡
        
          (
          x
          )
        
      
      =
      
        
          
            x
            t
          
          ⁢
          
            
              W
              _
            
            ij
          
          ⁢
          x
        
        +
        
          
            
              w
              _
            
            ij
            t
          
          ⁢
          x
        
        +
        
          w
          ij
        
      
    
    ,
    
      

    
    ⁢
    where
  




  
    
      
        
          W
          _
        
        ij
      
      =
      
        
          -
          
            1
            2
          
        
        ⁢
        
          ∑
          ij
          
            -
            1
          
        
      
    
    ⁢
    
      
    
    ,
    
      
        
          w
          _
        
        ij
      
      =
      
        
          ∑
          ij
          
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          μ
          ij
        
      
    
    ,
    
      

    
    ⁢
    and
  




  
    
      w
      ij
    
    =
    
      
        
          -
          
            1
            2
          
        
        ⁢
        
          μ
          ij
          t
        
        ⁢
        
          
            ∑
            ij
            
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            μ
            ij
          
        
      
      -
      
        
          1
          2
        
        ⁢
        ln
        ⁢
        
          
            
            
              ∑
              ij
            
            ⁢
            
              
            
            
          
          .
        
      
    
  



Expressing x as a (d+1)-dimensional vector, and Wij, wij, wij together as the (d+1)×(d+1) matrix Wij, as described before, the above Equation becomes:

lij(x)=xtWijx. 

Hence, the discriminant function for the ith class can be written as

gi(x)=log sum(ln αi1+li1(x), . . . , ln αiJi+liJi(x))+ln P(ωi).

where




  
    
      
        
          log
          ⁢
          sum
        
        ⁡
        
          (
          
            
              x
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              x
              
                J
                i
              
            
          
          )
        
      
      =
      
        
          max
          ⁡
          
            (
            
              
                x
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                x
                
                  J
                  i
                
              
            
            )
          
        
        +
        
          ln
          ⁡
          
            (
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  J
                  i
                
              
              ⁢
              
                
              
              ⁢
              
                e
                
                  Δ
                  j
                
              
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    and
  




  
    
      Δ
      j
    
    =
    
      
        x
        j
      
      -
      
        
          max
          ⁡
          
            (
            
              
                x
                1
              
              ,
              ...
              ,
              
                x
                
                  J
                  i
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        
          
            ∀
            j
          
          ⁢
          
            ∈
            
              
                {
                
                  1
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    J
                    i
                  
                
                }
              
              .
            
          
        
      
    
  



Hereinafter, the data vector x denotes a (d+1)-dimensional vector with a last component equal to 1, unless stated otherwise.
Many conventional speech recognizer typically use hidden Markov models (HMMs) and mixtures of Gaussian distributions. It is desired to train such a speech recognizer in a secure manner. That is, the speech supplies by a client for the training remains secret, and the HMMs remain secret as well. After the recognizer is trained, it is also desired to evaluate the performance of the recognizer as it: is being trained, and to use the trained recognizer to recognize speech in a secure manner. The recognized speech is called a transcription.
SUMMARY OF THE INVENTION
The embodiments of the invention implement a system and method that enable privacy-preserving speech recognition between two parties. One party, a client or Alice, with private speech and one party, a server or Bob, with a private speech recognizer. It is a goal of the invention to enable these parties to perform a speech recognition task without revealing their private information to each other.
The protocols described herein can be used to train a speech recognition system and can be extended for arbitrary audio and speech processing.
The collaborative model according to the embodiments of the invention can be realized with no privacy leaks from any involved party. The invention provides hidden Markov models (HMM) in a secure framework that enables training and classification between multiple parties, some having private speech data and some having private HMM model for speech recognition.
The client does not have to share any information about the speech, and the server does not share any information on the HMM model. After evaluation, the transcript of the speech is revealed to the client, and not to the server that provide the HMM model, thereby providing privacy at both the data, and the semantic levels.
In one embodiment, the HMMs are trained from data provided by multiple parties, and another embodiment deals with evaluating already trained HMMs on data, from another party. These embodiments are useful for collaborative speech recognition.
One embodiment can enable model training on multiple speech data bases without requiring the disclosure of actual speech, and another embodiment can enable speech recognition as a service model to remote clients who wish to maintain privacy on their speech and their transcription from both the service provider and malicious intruders.
Theses constrains can be satisfied using a secure multi-party computation (SMC), SMC is a field of cryptography that provides means to perform arbitrary computations between multiple parties who are concerned with protecting their data. The invention provides a SMC formulation for training and evaluating HMMs as applied to speech recognition. The HMMs can be modeled by mixtures of Gaussian distributions.
It is believed that this is the first application of SMC to privacy constrained speech recognition.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block, diagram of secure speech recognition according to an embodiment of the invention;
FIG. 2 is a diagram of a hidden Markov model according to an embodiment of the invention;
FIG. 3 is a block diagram of a secure multi-party computation used to implement speech recognition according to an embodiment of the invention;
FIG. 4 is a block diagram of a secure logarithmic sum according to an embodiment of the invention;
FIG. 5 is a block diagram, of secure evaluation of the likelihood of a given data vector from a Gaussian mixture distribution according to an embodiment: of the invention;
FIG. 6 is a block diagram of secure protocol for summation, maximum likelihood element, and the argument of the maximum element, given additive shares of logarithms of combining vectors according to embodiments of the invention;
FIG. 7 is a block diagram of secure determination of a likelihood of a speech unit from a HMM according to an embodiment of the invention;
FIG. 8 is a block diagram of a secure speech recognizer according to an embodiment of the invention; and
FIG. 9 is a block diagram of steps for determining a best sequence of model states according to an embodiment of the invention.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Speech Recognition with Hidden Markov Models
As shown in FIG. 1, the embodiments of our invention implement a system and method 100 for recognizing speech securely, A client (Alice) 110 provides private speech 111. Typically, features in the acoustic speech signal are encoded as a feature vector. Any known feature can be used, e.g., mel frequency cepstral coefficients (MFCCs). Therefore, hereinafter, the term ‘speech’ generally means speech in the form of & feature vector. Linear predictive coding (LPC) can also be used.
A server (Bob) 120 provides a speech recognizer 800. The client and server are connected by a network 130, e.g., the Internet. The recognizer converts the speech 111 to a transcript 112, e.g., text. The speech recognizer 800 uses hidden Markov models (HMMs) 200, In our speech recognition, the HMMs can correspond to speech recognition units, e.g., letters, words, phonemes, syllables, word units, phrase, or other speech sounds longer than words, or several syllables.
The client and the server are conventional. Each can include a processor (P) 10, memory (M) 20, and I/O interfaces 30 connected by buses 40 as known in the art. It presumed that the I/O interface 30 can acquire speech, forward speech, and present the transcript 112 to the user.
What is unconventional about our system method is that the client 110 does not want to reveal the speech 111 nor the transcript 112, and the server 120 does not want to reveal the workings of the recognizer 120 to the client, i.e., the HMMs, However, conventional cryptographic protocols can only secure the privacy of the speech and transcript on the network 130, and not in the recognizer 120.
FIG. 2 shows an example HMM 200 with hidden states s, observable output y, transition probabilities a, and output probabilities b. In an embodiment of the invention, the transition probabilities of the HMM are modeled by mixtures of multivariate Gaussian distributions. The transition probabilities give the likelihoods that the transcript 112 corresponds to the speech 111.
HMM Design Problems
There are three fundamental problems for HMM design, namely:
1) the determination of a likelihood the observation sequence (speech) is produced by a particular HMM;
2) the determination of a best sequence of state transitions for the observation sequence; and
3) the adjustment of parameters of the HMM so as to best account for the observed sequence.
The first problem is one of determining the likelihood that a particular model matches the given observation sequence (speech). The second problem is to uncover the hidden part of the HMM. We use a secure Viterbi protocol to solve this problem. The third problem is the problem of training the HMMs.
Unsecure methods for the above three problems for conventional speech recognition are well known and described in detail by L. R, Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition,” Proceedings of the IEEE, vol. 77, no. 2, pp. 257-286, February 1989, incorporated herein by reference. However, how to solve these problems in a secure manner has not yet been considered in prior art speech recognizers.
We describe these problems using secure multi-party computations between a client and a server, named conventionally Alice 110 and Bob 120. Suppose Bob has the HMMs 200 with all the model parameters λ trained.
The model parameters λ of each HMM can be characterized as N states {S1, . . . , SN}, the state of the HMM at time t is qt, state transition probability distribution A={aij}, where

aij=P[qt+1=Sj|qt=Si], for 1≦i,j≦N.  (1)

Each state is associated with a subset of M distinct observation symbols, i.e., the HMM has a codebook with a discrete alphabet: size or vocabulary, The subset of the observation symbols correspond to the physical output of the system being modeled. The observation symbol probability distribution in state j is given by a mixture of Gaussian distributions




  
    
      
        
          
            
              b
              j
            
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              ∑
              
                m
                =
                1
              
              M
            
            ⁢
            
              
            
            ⁢
            
              
                c
                jm
              
              ⁢
              
                N
                (
                
                  
                    μ
                    jm
                  
                  ,
                  
                    ∑
                    jm
                  
                
                ⁢
                
                  
                
                )
              
            
          
        
        ,
        
          
        
        ⁢
        
          1
          ≤
          j
          ≤
          N
        
        ,
      
    
    
      
        (
        2
        )
      
    
  




where x is the variable, cjm is the mixture coefficient for the mth mixture in state j, and (.) is a Gaussian distribution with a mean vector μ, and a covariance matrix Σjm. An initial state distribution is π={πi}, where

πi=P[q1=Si], 1≦N.  (3)

We use λ to denote the entire parameter set of the HMM model. Consider the first two problems where Bob has the trained the HMM 200 with all the model parameters λ are trained.
Alice has the observation sequence X=x1x2 . . . xT, i.e., the speech feature vector 111.
We describe how Alice can securely determine the probability or likelihood P(X|λ) of the observation sequence given a particular HMM, using & forward-backward procedure. We also describe how one can securely determine the best sequence of model states using a secure Viterbi protocol. When there is a secure way of determining likelihoods, the method can be extended to applications, such as speech recognition.
Bob has trained several HMMs, which characterize various forms of speech. Each HMM corresponds to a unit of recognizable speech, e.g., a word or phoneme. Alice's observation sequence vector 111 corresponds to a small portion of speech. We assume that Alice knows the features that Bob has used to train his HMMs, and has represented her speech vector in terms of those features. Then, we describe how Alice and Bob can obtain additive shares of the likelihood of Alice's observation sequence for every speech recognition unit of Bob, and use the additive shares to determine the speech unit that corresponds to Alice's speech.
Now consider the third problem of training. The problem of security arises when Bob wants to train the HMM, or do data mining in general, on combined data from private data bases ‘owned’ by Alice and another client (Charlie), For example. Bob wants to train his recognizer for different forms of speech. We describe how Bob can securely re-estimate parameters of his HMM without gaining knowledge about the private data. The implicit assumption is that Alice and Charlie are willing to let Bob learn about: distributions of their private data,
We describe how Bob can securely re-estimate parameters of his HMMs 200 without gaining knowledge about the private data 111, The implicit assumption is that Alice allows Bob to learn about distributions of the data. It should be understood, that the training can be performed for any number of clients.
Secure Two-Party Computations
The speech recognition that we describe is a specific implementation of a secure multi-party computation (SMC). We describe the case where Alice and Bob have private data, e.g., vectors a and b, respectively, and they want to determine the result c of a function ƒ(a, b), see FIG. 3.
The SMC can be implemented, in part, in the client 110, the server 120, by a third party. In a preferred embodiment, it is assumed that the client has limited resources and is therefore relatively simple, e.g., a desktop or handheld device such as a mobile telephone, and the sever can be more complex. Therefore, the SMC is usually implemented in the server.
Consider a third-party who can take the private data, determine the result, and communicate the result to the parties. Any protocol that determines c is said to be secure only if the protocol reveals no more information about a and b than what one can gain from learning the result c from the third-party.
We assume a semi-honest model for the parties, where the parties follow the protocol but could be saving messages and intermediate results to learn more about other's private data. In other words, the parties are honest hut curious and follow the agreed-upon protocol, but try to learn as much as possible from the data flow between the parties.
In a malicious model, no such assumptions are made about the behavior of the parties. If both, parties are malicious, security can be enforced by accompanying the protocols with zero-knowledge proofs, as described above, that the protocols are indeed being followed. If only one of the parties is malicious, the other party can use conditional disclosure of secrets protocols to make sure the other party receives valid inputs from the malicious party.
The speech recognition according to the embodiments of our invention is implemented using a secure multi-party computation 300 as shown in FIG. 3. The method takes in private inputs a 301 and b 302. The method is split into steps 1-N 310. Each, step is implemented as secure primitive protocol. Intermediate results are distributed as random additive shares and feed to the following steps. The final result c 303 is obtained by Alice 110 and Bob 120, or another designated party.
We implement each step of the method securely because if one of the steps is insecurely implemented, then either party could utilize the information to work their way backwards to gain knowledge about the other's private data. In addition, we also consider the results of intermediate steps. If such results of intermediate steps are available, then there is a possibility that one could also get back to the private data.
To prevent this, we express every step of the method in terms of a handful of basic secure protocols, henceforth called primitives, for which secure implementations are provided. We distribute intermediate results randomly between the two parties, such that neither party has access to the entire result. For example, instead of obtaining the result z of a certain step, the parties obtain random additive shares z1 and z2 (z1+z2=z).
Secure protocols can be categorized as cryptographic protocols and algebraic protocols, as described above. They provide different: levels of security and efficiency. Most of the algebraic protocols leak some information but are more straightforward and efficient than their cryptographic counterparts. We use cryptographic protocols as they tend to be more secure. Below, we provide a description of the protocols we use.
Secure protocols are often analyzed for correctness, security and complexity. Correctness is measured by comparing the proposed protocol with the ideal protocol using a third party. If the results are indistinguishable, the protocol is correct. Note that we can use a secure approximation to an ideal method. All the protocols we present are exact protocols. For security, one needs to show what can and cannot be learned from the data, exchange. For complexity, one shows the computational and communication complexity of the secure method.
Based on the choice of primitive protocols used and how they are implemented, one can achieve different levels of security and computational/communication efficiency.
Secure Protocols
Below, we describe the primitive protocols that we use and their implementations, namely SIP, SMAX, SVAL, SLOG and GML.
Secure Inner Products Protocol (SIP)
One primitive protocol determines a secure inner product. If Alice has a vector x and Bob has a vector y, a secure inner product protocol produces two numbers a and b such that a+b=xTy, where T is the transpose operator. Alice obtains the result a, and Bob obtains the result b. To simplify notation, we denote a. secure inner product: computation xTy as SIP(x, y).
Secure Maximum Index Protocol (SMAX)
Alice has the vector x=[x1 . . . xd], and Bob has the vector y=[y1 . . . yd]. They would like to determine an index of a maximum of x+ y=[(x1+y1) . . . (xd+yd)]. For example, the element is a likelihood. At the end of the protocol, Alice (and/or Bob) receives the result but neither party knows the actual value of the maximum. Notice that the same protocol can be used to determine the index of the minimum.
This protocol is j=SMAX(x, y). For this primitive, we use the permute protocol, see below. The protocol enables Alice and Bob to obtain additive shares, q and s, of a random permutation of the vector x+ y, π(x+y), where the random permutation π is selected by Alice, and Bob has no knowledge of the permutation π.
Alice sends q−r to Bob, where r is a random number selected by her. Bob sends back the index of the maximum element of q+s−r to Alice. Then, Alice determines the real index using the inverse of the permutation π. Neither party learns the value of the maximum element, and Bob does not learn the index of the maximum element. If the security requirements of Alice are more strict, she can encrypt elements of q using a homomorphic encryption scheme and send them to Bob along with the public key.
Bob can make comparisons among the encrypted values of π(x+y) using Yao's millionaire problem protocol, and send back the index of the maximum element, e.g., see I. F. Blake and V. Kolesnikov, “Strong conditional oblivious transfer and determining on intervals,” Proceedings of Advances in Cryptology—ASIACRYPT'04, ser. LNCS, P. J. Lee, Ed., vol. 3329. Springer-Verlag, 2004, pp. 515-529, and H. -Y. Lin and W. -G. Tzeng, “An efficient solution to the millionaires' problem based on homomorphic encryption,” in Proc of Intl. Conf. on Applied Cryptography and Network Security, ser. LNCS, vol. 3531. Springer-Verlag, 2005, pp. 456-466, both incorporated herein by reference.
Secure Maximum Value Protocol (SVAL)
Alice has the vector x, and Bob has the vector y. They would like to determine the value of the maximum element in z=x+y. Again, as described above, the element can be a likelihood. After the protocol, Alice and Bob receive additive shares of the result, a and b, but neither party knows the index of the maximum element. Notice that the same protocol can be used to determine the value of the minimum. We denote this as a+b=SVAL(x, y). For this protocol, we can use a protocol based on the one described by M. J. Atallah, F. Kerschbaum, and W. Du, “Secure and private sequence comparisons,” in Proceedings of Workshop on Privacy in the Electronic Society, Washington, D.C., USA. Oct. 2003, incorporated herein by reference.
We first describe a naive approach. Notice that zi≧zj(xi−xj)≧(yj−yi). Alice and Bob can do such pairwise comparisons and apply any conventional maximum finding method to learn the value of the maximum. To perform the comparisons securely, they can use Yao's millionaire problem protocol.
However, if Alice and Bob follow the above naive approach, then both parties are also able to find the index of the maximum. Hence, Alice and Bob obtain two vectors whose sum is a random permutation of z. Neither Alice nor Bob know the permutation. They can then follow the above naive approach on their newly obtained vectors to determine additive shares of the maximum element. The permute protocol is described in M. J. Atallah, F. Kerschbaum, and W. Du, “Secure and private sequence comparisons,” in Proceedings of Workshop on Privacy in the Electronic Society, Washington, D.C., USA, October 2003, incorporated herein by reference.
Secure Logsum Protocol (SLOG)
FIG. 4 shows the steps for logarithmic sum (logsum) primitive protocol 400. Unlike the other protocols described above, the logsum protocol is not a cryptographic primitive. We use the logsum primitive to simplify the implementation of many of the other protocols describe herein.
Alice 110 has the vector x 401, and Bob has the vector y 402, such that

x+y−ln z=[ln z1 . . . ln zd].

They would like to determine additive shares q 405 and s 407 such that q+s=ln




  
    (
    
      
        ∑
        
          i
          =
          1
        
        d
      
      ⁢
      
        
      
      ⁢
      
        z
        i
      
    
    )
  
  ⁢
  403.




We denote this secure protocol as q+s=SLOG(x, y). One can determine the logarithm of a sum from the logarithms of individual terms 404 as follows:





  
    
      
        
          ln
          ⁡
          
            (
            
              
                ∑
                
                  i
                  =
                  1
                
                d
              
              ⁢
              
                
              
              ⁢
              
                z
                i
              
            
            )
          
        
        =
        
          
            ln
            ⁡
            
              (
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  d
                
                ⁢
                
                  
                
                ⁢
                
                  e
                  
                    
                      x
                      i
                    
                    +
                    
                      y
                      i
                    
                  
                
              
              )
            
          
          .
        
      
    
    
      
        (
        4
        )
      
    
  




This leads to the following protocol.
Alice and Bob determine the dot product between vectors ex−q and ey using SIP(ex−q, e−v) 410, where q 405 is a random number selected by Alice, Bob obtains φ 406, which is the result of the secure inner dot product.
Notice that Bob has s 407 such that




  
    s
    =
    
      
        ln
        ⁢
        
          
        
        ⁢
        φ
      
      =
      
        
          -
          q
        
        +
        
          ln
          ⁡
          
            (
            
              
                ∑
                
                  i
                  =
                  1
                
                d
              
              ⁢
              
                
              
              ⁢
              
                e
                
                  
                    x
                    j
                  
                  +
                  
                    y
                    j
                  
                
              
            
            )
          
        
      
    
  
  ,




and Alice has q 405.

Bob receives the entire result of the dot product. However, this does not reveal any information to Bob about the vector x 401 due to the presence of the random number q 405. In no other step does either party receive the complete result of an operation. Thus, the protocol is secure. In terms of efficiency, this primitive is equivalent to using the SIP primitive 410 once.
Gaussian Mixture likelihood Protocol (GML)
As shown in FIG. 5, a secure classification with Gaussian mixture models can be used to determine the likelihoods. Such as method is described in detail in U.S. patent application Ser. No. 11/219,452 filed on Sep. 2, 2005, “Secure Classifying of Data with Gaussian Distributions,” Smaragdis et al., and Shashanka et al, “Secure sound classification: Gaussian mixture models,” Acoustics, Speech and Signal Processing, 2006, ICASSP 2006 Proceedings, 2006 IEEE International Conference, Volume: 3, pp. 1088-1091 Proc, May 2006, both incorporated herein by reference.
Alice 110 has an observation sequence, i.e., a vector x 501. The observation symbol probability distribution is determined by a mixture of Gaussian distributions b(x) 502, where variable, ci is the mixture coefficient, (.) is a Gaussian distribution with a mean vector μi, and a covariance matrix Σi, all held by Bob 120. The result 503 is p+q=log b (x1), where Alice obtains p 505, and Bob obtains q 506. Additional details are described in the above referenced U.S. patent application by Smaragdis et al.
Generic Protocols
For all three HMM design problems described above, all equations for HMM design can be written as a series of steps 310 as shown in FIG. 3. Each step can be: (a) finding likelihoods from a. Gaussian mixture model, which can be accomplished securely using the secure GML protocol 500, (b), determining the index of the maximum element of the sum of two vectors, which can be accomplished using SMAX 601, (c) determining the maximum element from the sum of two vectors, which can be accomplished using SVAL 602, or (d) determining logsums, which can be accomplished using SLOG 400.
FIG. 6 show's a generic module that determines a function Φ of two vectors x and y. Alice 110 has additive shares xA, yA 604, and Bob 120 has additive shares xB, yB 605 of log x and log y, respectively, i.e.,

xA+xB=log x, and yA+yb=log y, 

If the function is Φ(xy)=argmax xiyi 610, then the module calls the primitive 601 SMAX to produce an index to the maximum element. If the function is Φ(xy)=max xiyi 620, then the module calls the primitive SVAL 602 to produce the value of the maximum element. If the function is Φ(xy)=Σxiyi 630, then the module calls the primitive SLOG 400 to produce the logarithmic sum of two elements.
Alice and Bob obtain additive results p 611, and q 612, respectively, such that

p+q=log Φ(xy) 650.

The functions used in this generic protocol module can be used to train a Gaussian mixture model from data using an EM protocol to train the HMM parameters from training speech data. The EM protocol is described in detail below. Secure training is performed by Bob using data provided by Alice following the SMAX. SVAL or SLOG primitives in a right order with appropriate inputs as described in the equations below.
Evaluating HMMs
FIG. 7 shows the secure protocol (HMM_EVAL) 700 for recognizing speech. The protocol determines the likelihood of a speech units X=x1x2 . . . xK 701, supplied by Alice 110, with respect to a HMM with parameters λ 702, supplied by Bob 120, and for the determination of the forward variable α. There are three major steps in the process as shown in FIG. 7.
Step 1—Initialization 710.
For every state i 704 of the HMM 200, the forward variable a is determined for the first vector x1 711 using the GML protocol 500, Alice and Bob obtain additive shares Q 712 and R 713 such that

Qi+Ri=log bi(x1)+ln πi=log α1(i) 703.

Step 2—Induction 720

For every state i of the HMM, the forward variable a is determined for vector xk 721, for k={2, . . . , K} using GML 500 and SLOG 400. GML 500 produces Ui 724, and Vi 725, which are summed 722, respectively, with y′ 726 and z′ 727 to produce Qi 728 and {right arrow over (R)}i 729. Finally, Alice and Bob obtain additive share vectors Q 712 and R 713 such, that Qi+Ri=log αK(i).
Step 3—Termination 730
Alice and Bob perform SLOG 400 in the final step 730 to obtain y 731 and z 732, respectively, such that y+z=ln P(X|λ) 732.
Secure computation of a backward variable β can be done in a similar way, as described in detail below.
Determination Best Sequence of Model States (Viterbi Protocol)
FIG. 9 is a block diagram of steps for determining a best sequence of model states. This protocol can be used to update the trained HMMS, i.e., to reestimate the model parameters. Alice has speech X and Bob has a trained HMM with parameters λ, as described above. Alice wants to find the best sequence of model states q*T. There are three steps:
Step 1—Initialization 901
A Viterbi score for the first speech vector is determined using GML 500 as described above. At the end of this step, Alice and Bob have Q and R such that Qi+Ri=log δ1(i).
Step 2—Recursion 902
Alice and Bob obtain vectors Q and R such that Qi+Ri=log δK(i). Alice obtains φk(i), for k={2, . . . , K} and i={1, . . . N}.
Step 3—Termination 902
Alice and Bob perform SVAL on their additive shares to obtain log P*. They engage in SMAX on their shares, and Alice obtains q*K 
In the final step, Alice backtracks to obtain the sequence of model states.
Final Step—Speech Recognition
After Alice and Bob have additive shares of the likelihood of Alice's speech for every HMM unit in Bob's vocabulary, recognition of Alice's speech unit is possible. This is analogous to assigning a class label to the speech, vector when all the class likelihoods are known. In this case, all HMM likelihoods are known and the speech corresponds to that word or speech unit for which the likelihood is the highest.
FIG. 7 describes how to evaluate the likelihood of speech data for a given HMM.
FIG. 8 shows block diagram for the final step where a label is assigned to the speech vector 801 X 801 of Alice. 120 Bob has trained parameters λi 802 for the HMM 200 corresponding to the ith speech unit in the vocabulary, i={1, . . . , M}.
The 800 speech recognizer includes the HMM_EVAL module 700, which was described for FIG. 7 above. For HMMs corresponding to every word i in the vocabulary, the likelihood of X is securely evaluated, and Alice and Bob obtain additive shares of the likelihood yi and zi, respectively. The resulting vectors 811 y and 812 z are used as inputs to SMAX protocol 601 and Alice obtains the result j. This implies that speech X 821 corresponds to the word j 822.
Secure Classification: Gaussian Mixture Models
Alice has a d-component speech vector x, and Bob has the HMMs with the multivariate Gaussian distributions of N classes ωi, for i={1, . . . , N}, that could correspond to the vector x. They engage in a protocol that lets Bob classify Alice's data but neither party wants to disclose data to the other party. We describe protocols, which enable such computations.
The idea, is to evaluate the value of a discriminant function

gi(x)=ln p(x|ωi)+ln P(ωi)  (5)

for all classes ωi, and assign x to class if ωi if gi(x)>gj(x) for all j≠i. Here, p(x|ωi) is the class-conditional probability density function, and P(ωi) is the a priori probability of the class.

We describe two cases where:
each class is modeled as a single multivariate Gaussian distribution; and
each class is modeled as a mixture of multivariate Gaussian distributions.
Case 1: Single Multivariate Gaussian Distribution
The probability distribution of data, can be represented by a multivariate Gaussian distribution i.e., p(x|ω1) ̃(μi, Σi), where μi is the mean vector and Σi is the covariance matrix of class ωi. Hence, the log-likelihood is given by:




  
    
      
        
          ln
          ⁢
          
            
          
          ⁢
          
            p
            ⁡
            
              (
              
                x
                ❘
                
                  ω
                  i
                
              
              )
            
          
        
        =
        
          
            
              -
              
                1
                2
              
            
            ⁢
            
              
                (
                
                  x
                  -
                  
                    μ
                    i
                  
                
                )
              
              t
            
            ⁢
            
              
                ∑
                i
                
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                (
                
                  x
                  -
                  
                    μ
                    i
                  
                
                )
              
            
          
          -
          
            
              d
              2
            
            ⁢
            ln
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              
            
            ⁢
            π
          
          -
          
            
              1
              2
            
            ⁢
            ln
            ⁢
            
              
              
                ∑
                i
              
              ⁢
              
                
              
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




Ignoring the constant: term (d/2) ln π, we can write Equation (5) as:




  
    
      
        
          
            
              g
              i
            
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              
                -
                
                  1
                  2
                
              
              ⁢
              
                
                  (
                  
                    x
                    -
                    
                      μ
                      i
                    
                  
                  )
                
                t
              
              ⁢
              
                
                  ∑
                  i
                  
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    x
                    -
                    
                      μ
                      i
                    
                  
                  )
                
              
            
            -
            
              
                1
                2
              
              ⁢
              ln
              ⁢
              
                
                
                  ∑
                  i
                
                ⁢
                
                  
                
                
              
            
            +
            
              ln
              ⁢
              
                
              
              ⁢
              
                P
                ⁡
                
                  (
                  
                    ω
                    i
                  
                  )
                
              
            
          
        
        ⁢
        
          
        
      
    
    
      
        (
        7
        )
      
    
  




Simplifying, we have:





  
    
      
        
          
            
              g
              i
            
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              
                x
                T
              
              ⁢
              
                
                  W
                  _
                
                i
              
              ⁢
              x
            
            +
            
              
                
                  w
                  _
                
                i
                T
              
              ⁢
              x
            
            +
            
              ω
              
                i
                ⁢
                
                  
                
                ⁢
                0
              
            
          
        
        ,
      
    
    
      
        (
        8
        )
      
    
  
  
    
      where
    
    
      
        
      
    
  
  
    
      
        
          
            
              
                W
                _
              
              i
            
            =
            
              
                -
                
                  1
                  2
                
              
              ⁢
              
                ∑
                i
                
                  -
                  1
                
              
            
          
          ⁢
          
            
          
          ,
          
            
          
          ⁢
          
            
              
                w
                _
              
              i
            
            =
            
              
            
            ⁢
            
              
                ∑
                i
                
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                μ
                i
              
            
          
          ,
          and
        
        ⁢
        
          
        
      
    
    
      
        
      
    
  
  
    
      
        
          ω
          
            i
            ⁢
            
              
            
            ⁢
            0
          
        
        =
        
          
            
              -
              
                1
                2
              
            
            ⁢
            
              μ
              i
              T
            
            ⁢
            
              
                ∑
                i
                
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                μ
                i
              
            
          
          -
          
            
              1
              2
            
            ⁢
            ln
            ⁢
            
              
              
                ∑
                i
              
              
            
          
          +
          
            ln
            ⁢
            
              
            
            ⁢
            
              P
              ⁡
              
                (
                
                  ω
                  i
                
                )
              
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




We generate the (d+1)-dimensional vectors x and wi by appending the value 1 to x, and appending wi0 to wi. By changing Wi into a (d 1)×(d 1) matrix Wi, where the first d components of the last row are zeros, and the last column is equal to wTi, we can express Equation (8) in a simplified form:

gi(x)= xTWi x, 

Expressing x as x for simplicity, we can write the above Equation as:

gi(x)=xTWix  (10)

Henceforth, we use x to denote a (d 1)-dimensional vector with the last component equal to 1, unless otherwise stated.
Single Multivariate Gaussian Protocol (SMG)
Input: Alice has vector x, Bob has a matrix Wi for i=1, . . . , N. We express the matrix Wi as [W1iW2i . . . Wd+1i], where the vector Wji is the jth column of Wi.
Output: Alice learns l such that gl(x)>gj(x) for all j≠l. Bob learns nothing about x.
For i=1, 2, . . . , N
For j=1, . . . , d+1, Alice and Bob perform SIP(x, Wji) to obtain the vectors ai=[a1i . . . ad+1i] and bi=[b1i . . . bd+1i], respectively. Alice then determines aix.
Alice and Bob perform SIP(bi,x) to obtain qi and ri respectively.
Alice has vector A=[(a1x+q1) . . . (aNx+qN)], and Bob has vector B=[r1 . . . rN].
Alice and Bob perform the secure maximum index protocol between the vectors A and B, and Alice obtains l=SMAX(A, B).
Case 2: Mixture of Multivariate Gaussian Distributions
We now describe the case where the state transition probability distribution of each class is modeled as a mixture of Gaussian distributions. The mean vector and covariance matrix of the jth Gaussian in class ωi are respectively μij and Σij. Hence, we have




  
    p
    ⁡
    
      (
      
        x
        ❘
        
          ω
          i
        
      
      )
    
  
  =
  
    
      ∑
      
        i
        =
        1
      
      
        J
        i
      
    
    ⁢
    
      
    
    ⁢
    
      
        α
        ij
      
      ⁢
      
        N
        (
        
          
            μ
            ij
          
          ,
          
            ∑
            ij
          
        
        ⁢
        
          
        
        )
      
    
  




where Ji is the number of Gaussian distributions describing class ω1, and aij are the mixture coefficients. The log likelihood for the jth Gaussian distribution in the ith class is given by:





  
    
      
        
          
            
              l
              ij
            
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              
                x
                T
              
              ⁢
              
                
                  W
                  _
                
                ij
              
              ⁢
              x
            
            +
            
              
                
                  w
                  _
                
                ij
                T
              
              ⁢
              x
            
            +
            
              ω
              ij
            
          
        
        ,
      
    
    
      
        (
        11
        )
      
    
  
  
    
      where
    
    
      
        
      
    
  
  
    
      
        
          
            
              W
              _
            
            ij
          
          =
          
            
              -
              
                1
                2
              
            
            ⁢
            
              ∑
              ij
              
                -
                1
              
            
          
        
        ⁢
        
          
        
        ,
        
          
        
        ⁢
        
          
            
              w
              _
            
            ij
          
          =
          
            
              ∑
              ij
              
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              μ
              ij
            
          
        
        ,
      
    
    
      
        
      
    
  
  
    
      and
    
    
      
        
      
    
  
  
    
      
        
          ω
          ij
        
        =
        
          
            
              -
              
                1
                2
              
            
            ⁢
            
              μ
              ij
              T
            
            ⁢
            
              
                ∑
                ij
                
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                μ
                ij
              
            
          
          -
          
            
              1
              2
            
            ⁢
            ln
            ⁢
            
              
              
                ∑
                ij
              
              
            
          
          +
          
            ln
            ⁢
            
              
            
            ⁢
            
              
                α
                ij
              
              .
            
          
        
      
    
    
      
        
      
    
  




As above, we can simplify Equation (11) as:

lij(x)=xTWijx  (12)

Hence, the discriminant function for the ith class can be written as




  
    
      
        
          
            
              
                
                  g
                  i
                
                ⁡
                
                  (
                  x
                  )
                
              
              =
              
                
                  
                    log
                    ⁢
                    sum
                  
                  ⁡
                  
                    (
                    
                      
                        
                          l
                          
                            i
                            ⁢
                            
                              
                            
                            ⁢
                            1
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      ,
                      ...
                      ⁢
                      
                        
                      
                      ,
                      
                        
                          l
                          
                            iJ
                            i
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                    )
                  
                
                +
                
                  ln
                  ⁢
                  
                    
                  
                  ⁢
                  
                    P
                    ⁡
                    
                      (
                      
                        ω
                        i
                      
                      )
                    
                  
                
              
            
          
        
        
          
            
              =
              
                
                  ln
                  ⁡
                  
                    (
                    
                      
                        ∑
                        
                          j
                          =
                          1
                        
                        
                          J
                          i
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        e
                        
                          
                            l
                            ij
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                    
                    )
                  
                
                +
                
                  ln
                  ⁢
                  
                    
                  
                  ⁢
                  
                    P
                    ⁡
                    
                      (
                      
                        ω
                        i
                      
                      )
                    
                  
                
              
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




Mixture of Gaussian Protocol (MoG)

Input: Alice has the vector x, Bob has the matrix Wij, and mixture weights P(wi) for 1, 2, . . . , N, and j=1, 2, . . . , Ji.
Output: Alice learns l such that gl(x)>gj(x), for all j≠l. Bob learns nothing about x.
For i=1, 2, . . . , N
Alice and Bob engage in steps 1 and 2 of Protocol SMG for the Ji Gaussian distributions in the ith mixture to obtain vectors Ai=[Ai1 . . . Aiji] and Bi=[Bi1 . . . Biji]. Notice that Aij+Bij=lij(x).
Alice and Bob engage in the secure logsum protocol with vectors Ai and Bi to obtain and ui and zi, i.e., ui+zi=SLOG(Ai, Bi).
Bob determines the vector v=[v1 . . . vN], where vi=zi+ln P(wi). Alice forms the vector u=[u1 . . . uN].
Alice and Bob perform the secure maximum index protocol between vectors u and v and Alice obtains l=SMAX(u, v).
Training Gaussian Mixtures from Data
We now describe a related problem. Alice has K d-component speech vectors x1, x2, . . . , xK. Alice wants to train a mixture of c Gaussian distributions with the data. She can use an iterative expectation-maximization (EM) method to estimate the parameters of the c Gaussian distributions, and their mixture weights.
Now, consider the case when Bob wants to learn the parameters but Alice does not want to disclose her speech to Bob. One solution is for Alice to estimate the parameters herself and then give the parameters to Bob. Another approach is for Alice and Bob to engage in a secure protocol, which lets Bob learn the parameters, while Alice's data remain private. The latter approach becomes necessary in a case where Bob wants to do data mining on combined data from private data bases owned by Alice and Charlie. Below, we describe a secure protocol, which lets two parties perform such computations.
Expectation-Maximization Protocol (EM)
The estimate of a particular parameter after the rth iteration is denoted by a superscript. Thus, μri,




  
    ∑
    i
    r
  
  ⁢
  
    
  




and, Pr(wi) denote the mean vector, covariance matrix and the mixture weight for the ith Gaussian distribution after the rth iteration, respectively. For convenience, we denote the entire parameter set after the rth iteration by λr. At any given iteration, Alice has access to her data and Bob has access to the parameter





  
    ∑
    i
    r
  
  .




Alice and Bob have additive shares μriA, μriB and liA, liB such that μriA+μriB=μri and liA+liB=ln Pr(wi). We can write the steps of the EM method as follows:

Estimation Step:





  
    
      
        
          P
          ⁡
          
            (
            
              
                
                  ω
                  i
                
                |
                
                  x
                  k
                
              
              ,
              
                λ
                r
              
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  
                    
                      x
                      k
                    
                    |
                    
                      ω
                      i
                    
                  
                  ,
                  
                    μ
                    i
                    r
                  
                  ,
                  
                    ∑
                    i
                    r
                  
                
                )
              
            
            ⁢
            
              
                P
                r
              
              ⁡
              
                (
                
                  ω
                  i
                
                )
              
            
          
          
            
              ∑
              
                j
                =
                1
              
              c
            
            ⁢
            
              
                p
                ⁡
                
                  (
                  
                    
                      
                        x
                        k
                      
                      |
                      
                        ω
                        j
                      
                    
                    ,
                    
                      μ
                      j
                      r
                    
                    ,
                    
                      ∑
                      j
                      r
                    
                  
                  )
                
              
              ⁢
              
                
                  P
                  r
                
                ⁡
                
                  (
                  
                    ω
                    j
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        14
        )
      
    
  




Input: Alice has xk, μriA and liA, and Bob has μriB,




  
    ∑
    i
    r
  
  .




and liB, i=1, 2, . . . , c.

Output: Alice and Bob obtain uik and vik such that uik+vik=ln P(wi|xk, λr).
Bob forms matrices Wi for i=1, . . . , c as described above, and Equation (9), using (d=2) In 2π, instead of ln P(wi) to determine wi0). With (xk−μriA) as Alice's input, and Wi for i=1, . . . , c as Bob's input, and N=c, Alice and Bob engage in steps 1 and 2 of Protocol SMG to obtain vectors A′k and B′k. The log-likelihood is given by Equation 6.
Alice and Bob obtain vectors Ak and Bk, where for each i, Aik=A′ik+liA and Bik=B′ik=liB. Notice that Aik+Bik is the logarithm of the numerator in Equation 14.
Alice and Bob engage in the secure logsum protocol with the vectors Ak and Bk to obtain yk and zk, i.e., yk+zk=SLOG(Ak, Bk). Notice that yk+zk is the logarithm of the denominator of Equation 14.
Alice forms vector uk, where uik=(Aik−yk). Bob forms the vector vk, where vik=(Bik=zk), uik+vik=ln P(wijxk; λr).
Maximization Step:




  
    
      
        
          
            μ
            i
            
              r
              +
              1
            
          
          =
          
            
              
                ∑
                
                  k
                  =
                  1
                
                K
              
              ⁢
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        
                          ω
                          i
                        
                        |
                        
                          x
                          k
                        
                      
                      ,
                      
                        λ
                        r
                      
                    
                    )
                  
                
                ⁢
                
                  x
                  k
                
              
            
            
              
                ∑
                
                  k
                  =
                  1
                
                K
              
              ⁢
              
                P
                ⁡
                
                  (
                  
                    
                      
                        ω
                        i
                      
                      |
                      
                        x
                        k
                      
                    
                    ,
                    
                      λ
                      r
                    
                  
                  )
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              P
              
                r
                +
                1
              
            
            ⁡
            
              (
              
                ω
                i
              
              )
            
          
          =
          
            
              
                ∑
                
                  k
                  =
                  1
                
                K
              
              ⁢
              
                P
                ⁡
                
                  (
                  
                    
                      
                        ω
                        i
                      
                      |
                      
                        x
                        k
                      
                    
                    ,
                    
                      λ
                      r
                    
                  
                  )
                
              
            
            K
          
        
        ⁢
        
          

        
        ⁢
        
          
            ∑
            i
            
              r
              +
              1
            
          
          ⁢
          
            =
            
              
                
                  
                    ∑
                    
                      k
                      =
                      1
                    
                    K
                  
                  ⁢
                  
                    
                      P
                      ⁡
                      
                        (
                        
                          
                            
                              ω
                              i
                            
                            |
                            
                              x
                              k
                            
                          
                          ,
                          
                            λ
                            r
                          
                        
                        )
                      
                    
                    ⁢
                    
                      (
                      
                        
                          x
                          k
                        
                        -
                        
                          μ
                          i
                          
                            r
                            +
                            1
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        (
                        
                          
                            x
                            k
                          
                          -
                          
                            μ
                            i
                            
                              r
                              +
                              1
                            
                          
                        
                        )
                      
                      T
                    
                  
                
                
                  
                    ∑
                    
                      k
                      =
                      1
                    
                    K
                  
                  ⁢
                  
                    P
                    ⁡
                    
                      (
                      
                        
                          
                            ω
                            i
                          
                          |
                          
                            x
                            k
                          
                        
                        ,
                        
                          λ
                          r
                        
                      
                      )
                    
                  
                
              
              .
            
          
        
      
    
    
      
        (
        15
        )
      
    
  




Input: Alice has xk; k=1, . . . , K. Alice and Bob have K-vectors E and F such that Ek+Fk=ln P(wi λr).
Output: Alice obtains μr+1iA, liA; Bob obtains μr+1iB, Σr+1i and liB.
Alice and Bob engage in the secure logsum protocol with vectors E and F to obtain e and f, i.e., e+f=SLOG(E, F).
Alice determines liA=e−ln K, and Bob determines liB=f.
For j=1; 2, . . . , d:
Let hj be the K-vector formed by the jth elements of x1, . . . , xK. Alice and Bob engage in the secure logsum protocol with vectors E+ln hj, and F to obtain e′ and f, i.e., e′+f=SLOG(E+In hj, F). Alice and Bob obtain the jth elements of μr+1iA and ur+1iB respectively as a result of SIP(exp(e′−e), exp( f′−f).
Consider the evaluation of σmn, the mnth element of the matrix




  
    ∑
    
      r
      +
      
        1
        ⁢
        i
      
    
  
  .




We first evaluate the mnth element of (xk−μr+1i)( xk−μr+1i)T. For k=1, . . . , K, Alice and Bob engage in the secure inner product protocol with vectors exp(γk)[ xkm xkn, − xkm, xkn, 1], and [ muin, ūim, ūimūin], where γk is a random scalar selected by Alice. Let Bob obtain the result φk.

Alice forms the K-vector γ=[γ1, . . . , γK], and Bob forms the vector φ=[φ1, . . . , φK]. Alice and Bob engage in the secure logsum protocol with vectors (E−γ) and (F+ln φ) to obtain ē and f. Alice sends (ē−e) to Bob so that he can determine σmn. At the end of all iterations, Alice sends her shares μiA and liA to Bob so that he can determine the mean and the mixture weight P(wi).
Hidden Markov Models
Forward-Backward Protocol
The forward variable αt(i) is defined as

αt(i)=P(x1x2 . . . xt, qt=Si|λ)  (16)

We can solve for αt inductively and determine P(X|λ) as follows:
Initialization:

α1(i)=πibi(x1), 1≦i≦N 

Input: Bob has the Gaussian mixture distribution that defines bi(x), and the initial state distribution π={πi}. lice has speech x1.
Output: Alice and Bob obtain vectors Q and R such that Qi+Ri=ln α1(i).
Bob forms the matrices Wij as described above. With matrices Wij and mixture weights cjm as Bob's inputs, and x1 as Alice's input, they perform steps 1 and 2 of the protocol MoG protocol. Alice and Bob obtain vectors U and V. Notice that Ui+Vi=ln bi(x1).
Alice forms the vector Q=U. Bob forms vector R, where for each i, Ri=Vi+ln πi. Thus, Qi+Ri=ln bi(x1)+ln πi=ln α1(i).
Induction:



  
    
      
        
          α
          
            t
            +
            1
          
        
        ⁡
        
          (
          j
          )
        
      
      =
      
        
          (
          
            
              ∑
              
                i
                =
                1
              
              N
            
            ⁢
            
              
                
                  α
                  t
                
                ⁡
                
                  (
                  i
                  )
                
              
              ⁢
              
                a
                ij
              
            
          
          )
        
        ⁢
        
          
            b
            j
          
          ⁡
          
            (
            
              x
              
                t
                +
                1
              
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    where
  




  
    
      1
      ≤
      t
      ≤
      
        T
        -
        1
      
    
    ,
    
      1
      ≤
      j
      ≤
      
        N
        .
      
    
  



Input: Alice and Bob have vectors Q and R such that Qi+Ri=ln αi(i). Alice and Bob have Uj and Vj such that Uj+Vj=ln bj(xi+1). Bob has the vector aj=[a1j, . . . , aNj].
Output: Alice and Bob obtain Q and R such that Q+ R=ln αt+1(j).
Alice and Bob engage in the secure logsum protocol with vectors Q and (R+ln aj) to obtain y′ and z′ i.e., y′+z′=SLOG(Q, R+ln aj).
Alice obtains Q=y′+Uj, and Bob obtains R=z′+Vj.
Termination:




  
    P
    ⁡
    
      (
      
        X
        |
        λ
      
      )
    
  
  =
  
    
      ∑
      
        i
        =
        1
      
      N
    
    ⁢
    
      
        
          α
          T
        
        ⁡
        
          (
          i
          )
        
      
      .
    
  




Input: Alice and Bob have vectors Q and R such that Qi+Ri=ln αT(i).
Output: Alice and Bob obtain y and z such that y+z=ln P(X|λ).
Alice and Bob engage in the secure logsum protocol with vectors Q and R to obtain y and z, i.e., y+z=SLOG(Q, R).
We can obtain a similar procedure for a backward variable βt(i) defined as

βt(i)=P(xt+1xt+2 . . . xT|qt=Si,λ)  (17)

We can solve for βt(i) inductively as follows:
Initialization:

βT(i)=1, 1≦i≦N 

Induction




  
    
      
        
          β
          t
        
        ⁡
        
          (
          i
          )
        
      
      =
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            a
            ij
          
          ⁢
          
            
              b
              j
            
            ⁡
            
              (
              
                x
                
                  t
                  +
                  1
                
              
              )
            
          
          ⁢
          
            
              β
              
                t
                +
                1
              
            
            ⁡
            
              (
              j
              )
            
          
        
      
    
    ,
    
      

    
    ⁢
    where
  




  
    
      t
      =
      
        T
        -
        1
      
    
    ,
    
      T
      -
      2
    
    ,
    ...
    ⁢
    
      
    
    ,
    1
    ,
    
      

    
    ⁢
    
      1
      ≤
      j
      ≤
      N
    
  



Input: Alice and Bob have vectors Y and Z such that Yj+Z=ln βt+1(j). Alice and Bob have U and V such that Uj+Vj=ln bj(xt+1). Bob has the vector a′i.
Output: Alice and Bob obtain Y and Z such that Y+ Z=ln βt(i).
Alice and Bob engage in the secure logsum protocol with vectors Y+U and (Z+V+ln a′i) to obtain Y and Z, i.e., Y and Z=SLOG(Y+U, Z+V+ln a′i).
Secure Viterbi Algorithm Protocol
The Viterbi protocol of FIG. 9 can be formally described as follows.
Consider the quantity




  
    
      
        
          
            δ
            t
          
          ⁡
          
            (
            i
            )
          
        
        =
        
          
            max
            
              
                q
                1
              
              ,
              
                
                  q
                  2
                
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                
                  q
                  
                    t
                    -
                    1
                  
                
              
            
          
          ⁢
          
            P
            ⁡
            
              [
              
                
                  
                    
                      q
                      1
                    
                    ⁢
                    
                      q
                      2
                    
                    ⁢
                    ...
                    ⁢
                    
                      
                    
                    ⁢
                    
                      q
                      t
                    
                  
                  =
                  
                    
                  
                  ⁢
                  
                    S
                    i
                  
                
                ,
                
                  
                    
                      x
                      1
                    
                    ⁢
                    
                      x
                      2
                    
                    ⁢
                    
                      
                    
                    ⁢
                    ...
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      t
                    
                  
                  ❘
                  λ
                
              
              ]
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




where δt(i) is the best score (highest probability) along a single path, at time t, which accounts for the first t observations and ends in state Si. The procedure for finding the best state sequence can be stated as follows:

Initialization:

δ1(i)=πibi(x1), Ψ1(i)=0 1≦i≦N 

The procedure evaluating δ1(i) is analogous to the initialization step of the forward backward procedure. After this step, Alice and Bob have additive shares of ln δ1(i).
Recursion:



  
    
      
        δ
        t
      
      ⁡
      
        (
        j
        )
      
    
    =
    
      
        (
        
          
            max
            
              1
              ≤
              i
              ≤
              N
            
          
          ⁢
          
            [
            
              
                
                  δ
                  
                    t
                    -
                    1
                  
                
                ⁡
                
                  (
                  i
                  )
                
              
              ⁢
              
                a
                ij
              
            
            ]
          
        
        )
      
      ⁢
      
        
          b
          j
        
        ⁡
        
          (
          
            x
            t
          
          )
        
      
    
  




  
    
      
        
          ψ
          t
        
        ⁡
        
          (
          j
          )
        
      
      =
      
        arg
        ⁢
        
          
        
        ⁢
        
          
            max
            
              1
              ≤
              i
              ≤
              N
            
          
          ⁢
          
            [
            
              
                
                  δ
                  
                    t
                    -
                    1
                  
                
                ⁡
                
                  (
                  i
                  )
                
              
              ⁢
              
                a
                ij
              
            
            ]
          
        
      
    
    ,
    
      

    
    ⁢
    where
  




  
    
      2
      ≤
      t
      ≤
      T
    
    ,
    
      1
      ≤
      j
      ≤
      
        N
        .
      
    
  



Input: Alice and Bob have vectors Q and R such that Qi+Ri=ln δt−1(i). Alice and Bob have U and V such that U+V=ln bj(xt). Bob has the vector aj.
Output: Alice and Bob obtain Q and R such that Q+ R=ln δt(j). Alice obtains φt(j).
Alice and Bob engage in the secure maximum value protocol with vectors Q and (R+ln aj) to obtain y and z. They also perform SMAX on the same vectors and Alice obtains the result which is equal to φt(j).
Alice determines Q=y+U and Bob determines R=z+V.
Termination:




  
    
      
        
          P
          *
        
        =
        
          
            max
            
              1
              ≤
              i
              ≤
              N
            
          
          ⁢
          
            [
            
              
                δ
                T
              
              ⁡
              
                (
                i
                )
              
            
            ]
          
        
      
    
    
      
        
          q
          T
          *
        
        =
        
          arg
          ⁢
          
            
          
          ⁢
          
            
              max
              
                1
                ≤
                i
                ≤
                N
              
            
            ⁢
            
              
                
                  δ
                  T
                
                ⁡
                
                  (
                  i
                  )
                
              
              .
            
          
        
      
    
  




Alice and Bob use SVAL on their additive shares of ln δT(i) for all i to evaluate ln P*. Similarly, they engage in SMAX on their shares and Alice obtains the result q*T.
Path Backtracking:

q*t=Ψt+1(q*t+1) t=T−1, T−2, . . . , 1.

Alice, who has access to qt and φt, can evaluate the path sequence. Notice that Bob could be made to obtain this result instead of Alice, if we let Bob learn the values of φt and qt in steps 2 and 3, instead of Alice.
HMM Training
In the above formulations, we assumed that Bob had already trained his HMMs, Alice has all the speech training data and Bob wants to train a HMM using her data. Below, we show how Bob can securely re-estimate parameters of his HMM. Consider the variables




  
    
      
        
          
            γ
            t
          
          ⁡
          
            (
            i
            )
          
        
        =
        
        ⁢
        
          
            P
            ⁡
            
              (
              
                
                  
                    q
                    t
                  
                  =
                  
                    
                      S
                      i
                    
                    |
                    X
                  
                
                ,
                λ
              
              )
            
          
          =
          
            
              (
              
                
                  
                    α
                    t
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
                ⁢
                
                  
                    β
                    t
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
              
              )
            
            
              P
              ⁡
              
                (
                
                  X
                  |
                  λ
                
                )
              
            
          
        
      
    
  
  
    
      
        
          
            ξ
            t
          
          ⁡
          
            (
            
              i
              ,
              j
            
            )
          
        
        =
        
        ⁢
        
          P
          ⁡
          
            (
            
              
                
                  q
                  t
                
                =
                
                  S
                  i
                
              
              ,
              
                
                  q
                  
                    t
                    +
                    1
                  
                
                =
                
                  
                    S
                    j
                  
                  |
                  X
                
              
              ,
              λ
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              
                
                  α
                  t
                
                ⁡
                
                  (
                  i
                  )
                
              
              ⁢
              
                a
                ij
              
              ⁢
              
                
                  b
                  j
                
                ⁡
                
                  (
                  
                    x
                    
                      t
                      +
                      1
                    
                  
                  )
                
              
              ⁢
              
                
                  β
                  
                    t
                    +
                    1
                  
                
                ⁡
                
                  (
                  j
                  )
                
              
            
            )
          
          
            P
            ⁡
            
              (
              
                X
                |
                λ
              
              )
            
          
        
      
    
  




We have described how Alice and Bob can obtain their additive shares. Using these shares, Alice and Bob can determine additive shares et, gt and ft, ht such that et+ft=ln ξt(i, j), and gt+ht=ln γt(i). Alice determines gt=Qi+ Y−y, and et=Qi+Uj+Yj−y. Bob determines ht=Ri+ Z and ft=Ri+ln aij+Vj+Zj−z. The variables πi and aij can then be re-estimated, as follows:



  
    
      
        π
        _
      
      i
    
    =
    
      
        γ
        1
      
      ⁡
      
        (
        i
        )
      
    
  




  
    
      
        a
        _
      
      ij
    
    =
    
      
        
          
            ∑
            
              t
              =
              1
            
            
              T
              -
              1
            
          
          ⁢
          
            
              ξ
              t
            
            ⁡
            
              (
              
                i
                ,
                j
              
              )
            
          
        
        
          
            ∑
            
              t
              =
              1
            
            
              T
              -
              1
            
          
          ⁢
          
            
              γ
              t
            
            ⁡
            
              (
              i
              )
            
          
        
      
      .
    
  



Input: Alice and Bob have (T−1)-vectors e and f such that et+ft=ln ξt(i, j). They also have vectors g and h such that gt+ht=ln γt(i).
Output: Bob obtains ln āij.
Alice and Bob engage in the secure logsum protocol with vectors e and f to obtain ē and f. They also engage in the secure logsum protocol with vectors g and h to obtain g and h respectively
Alice sends (ē− f) to Bob. Bob determines (ē− g)+( f− h) to obtain ln āij.
Notice that instead of Bob obtaining the final result, Alice and Bob can have additive shares of ln āij. The secure protocols for forward-backward and Viterbi algorithm are modified so that Alice and Bob have additive shares of the vector ln āij. As for the Gaussian mixture distributions bi(x), Bob can securely train the distributions from Alice's data as we have described above. Bob does not learn all the parameters in every iteration. He learns the mean vector for every component Gaussian distribution only after the last iteration. He does learn the covariance matrix in every iteration, but quantities used to determine the covariance matrix are additive shares which does not help him in inferring Alice's data. The example described above uses two parties but it can be generalized to the case where Bob learns from multiple parties. In that case, trained statistics are averaged and provide an additional layer of security for the data providers.
Additional Primitives Protocols
Secure Inner Product Protocol Using Homomorphic Encryption
The following protocol is based on homomorphic encryption, see Goethals et al. Let the triple (Ge, En, De) denote a public-key homomorphic cryptosystem, i.e., probabilistic polynomial time methods for key-generation, encryption and decryption,
The key generation method generates a valid pair (sk, pk) of private and public keys for a security parameter k.
The encryption method En takes as an input a plaintext m, a random value r and a public key pk, and outputs the corresponding ciphertext En(pk; m, r),
The decryption method De takes as an input a ciphertext c and a private key sk, corresponding to the public key pk, and outputs a plaintext De(sk, c). It is required that De(sk; En(pk; m; r))=m. A public-key cryptosystem is homomorphic if En(pk; m1, r1).En(pk; m2, r2)=En(pk; m1+m2, r2+r2), where ‘+’ is a group operation, and ‘.’ is a groupoid operation.
Inputs: Private vectors x and y by Bob and Alice respectively.
Outputs: Shares a and b such that a+b=xTy.
Setup phase. Bob:
generates a private and public key pair (sk, pk).
sends pk to Alice.
For i ε {1, . . . , d}, Bob:
generates a random new string ri.
sends ci=En(pk; xi, ri) to Alice.
Alice:
sets




  z
  ←
  
    
      ∏
      
        i
        =
        1
      
      d
    
    ⁢
    
      
        c
        i
        
          y
          i
        
      
      .
    
  




generates a random plaintext b and a random nonce r′.

sends z′=z.En(pk; −b, r′) to Bob.

Bob determines a=De(sk; z′)=xTy−b.
Secure inner Product Protocol from Oblivious Polynomial Evaluation
The following protocol is based on Chang et al. Let Alice represent each xi as




  
    x
    i
  
  =
  
    
      ∑
      j
    
    ⁢
    
      
        a
        ij
      
      ⁢
      
        2
        
          j
          -
          1
        
      
    
  




with aijε{0, 1}. Let vij=2j−1yi. The idea is to have Bob prepare vij and have Alice obtain those vij with aij=1 in some secure way. This is achieved as follows. Bob prepares the pair (rij, vij+rij) for randomly selected rij and Alice performs an independent oblivious transfer with Bob to obtain rij if aij=0, and vij+rij otherwise. At the end of tile protocol, Alice obtain





  
    
      ∑
      i
    
    ⁢
    
      
        ∑
        j
      
      ⁢
      
        (
        
          
            
              a
              ij
            
            ⁢
            
              v
              ij
            
          
          +
          
            r
            ij
          
        
        )
      
    
  
  =
  
    
      
        ∑
        i
      
      ⁢
      
        
          x
          i
        
        ⁢
        
          y
          i
        
      
    
    +
    
      
        ∑
        
          i
          ,
          j
        
      
      ⁢
      
        
          r
          ij
        
        .
      
    
  




Bob has





  -
  
    
      ∑
      
        i
        ,
        j
      
    
    ⁢
    
      
        r
        ij
      
      .
    
  




Thus, Alice and Bob have additive shares of the desired dot product.

Secure Inner Product Protocol Using Linear Transformation

The following protocol is based on Du et al. Define x1 as the d/2-dimensional vector including the first d=2 elements of x, and x2 as the vector including of the last d=2 elements of x. We note that xTy=xT1y1+xT2y2. Alice and Bob jointly generate a random invertible d×d matrix M. Alice determines x′=xTM, splits the matrix as x′1 and x′2, and sends x′2 to Bob. Bob determines y′=M−1y, splits it as y′1 and y′2, and sends y′1 to Alice. Alice determines x′1y′1, and Bob determines x′2y′2 so that their sum is equal to the desired result.
Secure Permute Protocol
The following protocol is based on Blake et al.
Input: Alice and Bob have d-component vectors x and y. Bob has a random permutation π.
Output; Alice and Bob obtain vectors q and s such that q+s=π(x)+π(y).
Alice generates public and private keys for a homomorphic cryptosystem and sends the public key to Bob. Let E( ) denote encryption with Alice's public key.
Alice encrypts each element of x and sends the resulting vector x to Bob.
Bob generates a random vector r and determines a new vector θ where θi= xiE(ri)=E(xi+ri), for i=1, . . . , d.
Bob permutes θ and sends π(θ) to Alice. Alice decrypts the vector to obtain q.
Bob computes y−r, and then permutes the result using ft to obtain s=π(y−r). Alice and Bob engage in the above permute protocol twice, the second time with their roles interchanged. After this is done, Alice and Bob have two vectors whose sum is a random permutation of the original sum, but neither of party knows the permutation.
EFFECT OF THE INVENTION
The embodiments of the invention provide privacy preserving hidden Markov model and Gaussian mixtures computations. We provide a privacy-preserving protocol for determining logsums. Using primitives for determining scalar products and maxima, we describe secure protocols for classification using Gaussian mixture models. We describe secure protocols for the forward-backward method, the Viterbi algorithm and HMM training,
The protocols are defined modularly in terms of primitives so that future advances in cryptography, which may provide more robust and efficient protocols, can be readily employed in our framework by straightforward replacement.
Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.

## Claims

1. A method for recognizing a speech unit stored at a client using hidden Markov models (HMMs) stored at a server, each HMM corresponds to a unit of recognizable speech, wherein the speech unit is represented as feature vectors, and wherein each feature vector is partitioned into two random additive shares such that the server receives only one random additive share from the client, the method comprising the steps of:
determining iteratively by the server, in response to receiving a random additive share of each feature vector, an additive share of a likelihood of the speech unit with respect to the each HMM using at least one secure multi-party computation protocol to produce additive shares of likelihoods of units of recognizable speech, wherein the secure multi-party computation protocol uses as inputs the two random additive shares of a corresponding feature vector, each of the two random additive shares is provided by the client and by the server respectively; and
transmitting the additive shares of the likelihoods for recognizing the speech unit.

2. The method of claim 1, wherein the secure multi-party computation protocol is selected from a group consisting of a secure inner products protocol , a secure maximum index protocol, a secure maximum value protocol , a secure logsum protocol and a Gaussian mixture likelihood protocol.

3. The method of claim 1, further comprising:
determining by the server, an additive share of an index of a maximum likelihood of the unit of speech using a secure maximum index protocol; and
transmitting the additive share of the index of the maximum likelihood to the client.

4. The method of claim 1, wherein the unit of speech includes at least some of letters, words, phonemes, syllables, and phrases, or combinations thereof.

5. The method of claim 1, wherein the likelihoods of the units of recognizable speech given a sequence of states of each HMM, is a single multivariate Gaussian distribution.

6. The method of claim 1, wherein the likelihood of the units of recognizable speech given a sequence of states of each HMM, is a mixture of multiple weighted multivariate Gaussian distributions.

7. The method of claim 1, wherein the cryptographic protocol is a secure logsum protocol (SLOG), and wherein the SLOG comprises:
determining an additive share of an inner product of exponents of the two random additive shares using a secure inner products protocol.

8. A server configured for recognizing a speech unit stored at a client using hidden Markov models (HMMs) stored at a server, each HMM corresponds to a unit of recognizable speech, wherein the speech unit is represented as feature vectors, and wherein each feature vector is partitioned into two random additive shares such that the server receives only one random additive share from the client, comprising:
means for determining iteratively by the server, in response to receiving a random additive share of each feature vector, an additive share of a likelihood of the speech unit with respect to the each HMM using at least one secure multi-party computation protocol to produce additive shares of likelihoods of units of recognizable speech, wherein the secure multi-party computation protocol uses as inputs the two random additive shares of a corresponding feature vector, each of the two random additive shares is provided by the client and by the server respectively; and
means for transmitting the additive shares of the likelihoods for recognizing the speech unit.

9. The server of claim 8, wherein the secure multi-party computation protocol is selected from a group of a secure inner products protocol (SIP), a secure maximum index protocol (SMAX), a secure maximum value protocol (SVAL), a secure logsum protocol (SLOG) and a Gaussian mixture likelihood protocol (GML).

10. The server of claim 8, further comprising:
means for determining by the server, an additive share of an index of a maximum likelihood of the unit of speech using a secure maximum index protocol (SMAX); and
means for transmitting the additive share of the index of the maximum likelihood to the client.

11. The server of claim 8, wherein the unit of speech includes at least some of letters, words, phonemes, syllables, and phrases, or combinations thereof.

12. The server of claim 8, wherein the likelihood of the unit of speech given a sequence of states of each HMM is a single multivariate Gaussian distribution.

13. The server of claim 8, wherein the likelihood of the unit of speech given a sequence of states of each HMM is a mixture of multiple weighted multivariate Gaussian distributions.

14. The server of claim 8, wherein the cryptographic protocol is a secure logsum protocol (SLOG), and wherein the SLOG comprises:
means for determining an additive share of an inner product of exponents of the two random additive shares using a secure inner products protocol (SIP).