# US 2008/0304657 A1 · Secure Threshold Decryption Protocol Computation

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

- Number: US 2008/0304657 A1
- Document ID: US20080304657A1
- Status: Published application
- Kind: A1
- Application number: 12/096,802
- Filed: 2006-12-07
- Published: 2008-12-11
- Earliest claimed: 2005-12-13
- Assignees: Koninklijke Philips Electronics N.V.
- Inventors: Pim Theo Tuyls; Berry Schoenmakers
- Web page: https://patentgrep.com/patent/US20080304657A1

## CPC

- H04L 9/0869: {involving random numbers or seeds}
- G06F 7/588: {Random number generators, i.e. based on natural stochastic processes}
- H04L 9/008: {involving homomorphic encryption}
- H04L 9/3231: {Biological data, e.g. fingerprint, voice or retina (network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861)}
- H04L 2209/24: Key scheduling, i.e. generating round keys or sub-keys for block encryption
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L 2209/805: Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention relates to a method of converting an encrypted data set into an encryption of individual bits representing the data set. Further, the invention relates to a system for converting an encrypted data set into an encryption of individual bits representing the data set. A basic idea of the present invention is to provide a protocol in which it is possible to divide an encryption of a data set in the form of e.g. a biometric feature, such as a number x, where xε{0, 1, . . . , n−1}, into an encryption of respective bits x0, x1, . . . , xt−1 forming the number x, where t is the number of bits of the number n−1, without leaking any information about x or its bits x0, x1, . . . , xt−1 Hence, the present invention enables splitting of the encryption [[x]] into the respective encrypted bits [[x0]], [[x1]], . . . , [[xt−1]] forming the encrypted number x=ΣI=1n xi 2i.

## Claims

### Claim 1

A method of converting an encrypted data set into an encryption of individual bits representing the data set, the method comprising the steps of:
generating a random number and computing a bitwise encryption of the random number;
securely computing an encrypted sum based on the encrypted data set and the encrypted random number;
performing a decryption of the encrypted sum and determining a bit representation of the sum; and
creating the encryption of said individual bits representing the encrypted data set by processing the sum with the encrypted random number.

### Claim 2 (depends on 1)

The method according to claim 1, further comprising the step of acquiring the encrypted data set.

### Claim 3 (depends on 1)

The method according to claim 1, further comprising the step of providing a publicly verifiable proof that the encryptions of the random number have been correctly computed.

### Claim 4 (depends on 1)

The method according to claim 1, wherein said step of computing an encrypted sum is performed by multiplying the encrypted data set and the encrypted random number using a secure multiplication gate.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the step of decrypting said encrypted sum is performed by using a threshold decryption protocol.

### Claim 6 (depends on 1)

The method according to claim 1, wherein the step of creating the encryption of said individual bits representing the encrypted data set is performed by subtracting the encrypted random number from the bit representation of the sum.

### Claim 7 (depends on 6)

The method according to claim 6, wherein the subtraction is performed using a secure subtraction gate.

### Claim 8 (depends on 6)

The method according to claim 6, wherein the step of creating the encryption of said individual bits further comprises the step of adding a sign bit to the bit representation of the sum.

### Claim 9 (depends on 1)

The method according to claim 1, wherein the step of creating the encryption of said individual bits representing the encrypted data set is performed by adding the encrypted random number to the bit representation of the sum.

### Claim 10 (depends on 1)

The method according to claim 1, wherein the data set that is encrypted is extracted from a biometric feature of an individual.

### Claim 11

A system for converting an encrypted data set into an encryption of individual bits representing the data set, the system comprising:
at least a first and a second computing device (212,213) being arranged to jointly generate a random number and compute a bitwise encryption of the random number; wherein
at least one of the computing devices is arranged to compute an encrypted sum based on the encrypted data set and the encrypted random number;
said first and second computing device are arranged to jointly perform decryption of the encrypted sum and determine a bit representation of the sum, and
said first and second computing device are arranged to jointly create the encryption of said individual bits representing the encrypted data set by processing the sum with the encrypted random number.

### Claim 12 (depends on 11)

The system according to claim 11, wherein said first and second computing device (212, 213) further are arranged to compute a publicly verifiable proof that the encryptions of the random number have been correctly computed.

### Claim 13 (depends on 11)

The system according to claim 11, wherein said first and second computing device (212, 213) are arranged to decrypt the encrypted sum by jointly running a threshold decryption protocol.

### Claim 14 (depends on 11)

The system according to claim 11, wherein said first and second computing device (212, 213) are arranged to create the encryption of said individual bits representing the encrypted data set by subtracting the encrypted random number from the bit representation of the sum.

### Claim 15 (depends on 11)

The system according to claim 11, wherein said first and second computing device (212, 213) are arranged to create the encryption of said individual bits representing the encrypted data set by adding the encrypted random number to the bit representation of the sum.

### Claim 16 (depends on 11)

The system according to claim 11, wherein said first and second computing device (212, 213) are arranged to jointly generate a random number and compute a bitwise encryption of the random number by:
generating a respective bit for each bit of the random number and XORing said respective bits to create said each bit of the random number; and
securely encrypting each bit of the random number.

### Claim 17 (depends on 1)

A computer program comprising computer-executable components for causing a device to perform the steps recited in claim 1 when the computer-executable components are run on a processing unit included in the device.
