# US 2009/0268908 A1 · Methods and Apparatus for Securely Classifying Data

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

- Number: US 2009/0268908 A1
- Document ID: US20090268908A1
- Status: Published application
- Kind: A1
- Application number: 12/111,538
- Filed: 2008-04-29
- Published: 2009-10-29
- Earliest claimed: 2008-04-29
- Assignees: International Business Machines Corporation
- Inventors: Daniel Martin Bikel; Jeffrey Scott Sorensen
- Web page: https://patentgrep.com/patent/US20090268908A1

## CPC

- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- H04L 2209/16: Obfuscation or hiding, e.g. involving white box
- H04L 2209/50: Oblivious transfer
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques are disclosed for securely classifying or decoding data. By way of example, a method of determining a most likely sequence for a given data set comprises a computer system associated with a first party performing the following steps. An encrypted model is obtained from a second party. The encrypted model is utilized to determine cost values associated with a particular sequence of observed outputs associated with the given data set. The cost values are sent to the second party. At least one index of a minimum cost value determined by the second party from the cost values sent thereto is obtained from the second party. A minimum cost sequence resulting from the at least one index is determined as the most likely sequence.

## Claims

### Claim 1

A method of determining a most likely sequence for a given data set, the method comprising a computer system associated with a first party performing steps of:
obtaining from a second party an encrypted model;
utilizing the encrypted model to determine cost values associated with a particular sequence of observed outputs associated with the given data set, sending to the second party the cost values;
obtaining from the second party at least one index of a minimum cost value determined by the second party from the cost values sent thereto; and
determining, as the most likely sequence, a minimum cost sequence resulting from the at least one index.

### Claim 2 (depends on 1)

The method of claim 1, wherein the encrypted model further comprises a plurality of encrypted state transition costs.

### Claim 3 (depends on 1)

The method of claim 1, wherein the encrypted model further comprises a plurality of encrypted costs associated with observable outputs.

### Claim 4 (depends on 1)

The method of claim 1, wherein the encrypted model further comprises a plurality of initial state costs.

### Claim 5 (depends on 1)

The method of claim 1, wherein the model is encrypted by a Paillier cryptographic method.

### Claim 6 (depends on 1)

The method of claim 1, wherein the model is encrypted by an ElGamal cryptographic method.

### Claim 7 (depends on 1)

The method of claim 1, wherein the model is encrypted by a Rivest-Shamir-Adleman cryptographic method.

### Claim 8 (depends on 1)

The method of claim 1, wherein the cost values comprise a set of total partial costs which are combined with a randomly chosen bias value before sending.

### Claim 9 (depends on 1)

The method of claim 1, wherein the obtaining step further comprises obtaining from the second party indices of the two smallest cost values, such the most likely state sequence and the second most likely state sequence are determined.

### Claim 10 (depends on 1)

The method of claim 1, wherein the most likely sequence represents a decoding result such that the second party is not permitted to learn the sequence of observed outputs and the first party is not permitted to learn one or more parameters of the model that generated the sequence.

### Claim 11

A method of determining a most likely sequence for a given data set, the method comprising a computer system associated with a first party performing steps of:
encrypting a model;
sending the encrypted model to a second party such that the second party utilizes the encrypted model to determine cost values associated with a particular sequence of observed outputs associated with the given data set, obtaining from the second party the cost values;
determining at least one index of a minimum cost value from the cost values obtained from the second party;
sending the at least one index of the minimum cost value to the second party such that the second party determines, as the most likely sequence, a minimum cost sequence resulting from the at least one index.

### Claim 12

A method of securely determining a minimum data value of a set of asymmetrically encrypted data values, the method comprising a computer system performing steps of:
decrypting the values in the set of asymmetrically encrypted data values;
comparing the values in the set of asymmetrically encrypted data values; and
outputting an index of the minimum data value of the set of asymmetrically encrypted data values;
wherein the set of asymmetrically encrypted data values comprises a public and private key pair, and numeric data values encrypted using the public key and transmitted to a holder of the private key.

### Claim 13 (depends on 12)

The method of claim 12, wherein the set of asymmetrically encrypted data values is permuted randomly before transmission to another party, and a resulting returned index is mapped back to an original position before permutation.

### Claim 14 (depends on 12)

The method of claim 12, wherein the set of asymmetrically encrypted data values is expanded to include additional values with total costs larger then the minimum cost.

### Claim 15 (depends on 1)

An article of manufacture for determining a most likely sequence for a given data set, the article comprising a computer readable storage medium including one or more programs which when executed by a computer system associated with a first party perform the steps of claim 1.

### Claim 16

Apparatus for determining a most likely sequence for a given data set, the apparatus being associated with a first party and comprising:
a memory; and
a processor coupled to the memory and configured to: obtain from a second party an encrypted model; utilize the encrypted model to determine cost values associated with a particular sequence of observed outputs associated with the given data set, send to the second party the cost values; obtain from the second party at least one index of a minimum cost value determined by the second party from the cost values sent thereto;
and determine, as the most likely sequence, a minimum cost sequence resulting from the at least one index.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the encrypted model further comprises a plurality of encrypted state transition costs.

### Claim 18 (depends on 16)

The apparatus of claim 16, wherein the encrypted model further comprises a plurality of encrypted costs associated with observable outputs.

### Claim 19 (depends on 16)

The apparatus of claim 16, wherein the encrypted model further comprises a plurality of initial state costs.

### Claim 20 (depends on 16)

The apparatus of claim 16, wherein the cost values comprise a set of total partial costs which are combined with a randomly chosen bias value before sending.
