# US 2021/0334100 A1 · Secure computation device, comparison method, comparison program recording medium, and secure computation system

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

- Number: US 2021/0334100 A1
- Document ID: US20210334100A1
- Status: Published application
- Kind: A1
- Application number: 16/613,967
- Filed: 2018-05-08
- Published: 2021-10-28
- Earliest claimed: 2017-05-18
- Assignees: NEC Corporation
- Applicants: NEC Corporation
- Inventors: Kazuhisa ISHIZAKA
- Web page: https://patentgrep.com/patent/US20210334100A1

## CPC

- G06F 9/30029: {Logical and Boolean instructions, e.g. XOR, NOT}
- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- G06F 9/3001: {Arithmetic instructions}
- G06F 9/30018: {Bit or string instructions}
- G06F 9/30134: {Register stacks; shift registers}
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/00: {Cryptographic mechanisms or cryptographic} arrangements for secret or secure communications; Network security protocols
- H04L 2209/00: Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY

## Abstract

Provided is a secure computation device for computing a comparison operation to two integers without the use of AND/XOR. The secure computation device compares a first integer a and a second integer b when the first integer a and the second integer b, which are 0 or greater and less than 2{circumflex over ( )}k (k being an integer of 1 or greater), are subjected to ring sharing. The secure computation device includes: an addition/subtraction circuitry; a bit decomposition circuitry; and a bit extraction circuitry. The addition/subtraction circuitry uses the first integer a, the second integer b, and 2{circumflex over ( )}k to carry out a predetermined addition or subtraction with ring sharing, and output an added/subtracted result. The bit decomposition circuitry converts the added/subtracted result to bit sharing, and outputs a bit shared result. The bit extraction circuitry extracts a (k+1)-th bit of the bit shared result, and outputs an extracted result.

## Claims

### Claim 1

A secure computation device for comparing, in a case where a first integer a and a second integer b, each of which is more than 0 and less than 2{circumflex over ( )}k (where k is an integer equal to or more than one), are subjected to ring sharing, the first integer a with the second integer b, wherein the secure computation device comprises:
an addition/subtraction circuitry configured to carry out a predetermined addition/subtraction using the first integer a, the second integer b, and 2{circumflex over ( )}k with the ring sharing to produce an added/subtracted result;
a bit decomposition circuitry configured to convert the added/subtracted result into bit sharing to produce a bit shared result; and
a bit extraction circuitry configured to extract a (k+1)-th bit of the bit shared result to produce an extracted result.

### Claim 2 (depends on 1)

The secure computation device as claimed in claim 1, wherein the bit extraction circuitry comprises a shifting circuitry configured to shift the bit shared result right by k bits to produce a shifted result as the extracted result.

### Claim 3 (depends on 2)

The secure computation device as claimed in claim 2, further comprising a bit composition circuitry configured to convert the shifted result into ring sharing to produce a ring shared result.

### Claim 4 (depends on 1)

The secure computation device as claimed in claim 1, wherein:
in a case of detecting whether or not the first integer a is not more than the second integer b,
the addition/subtraction circuitry is configured to calculate (b+2{circumflex over ( )}k−a) with ring sharing as the predetermined addition/subtraction to produce (b+2{circumflex over ( )}k−a) as the added/subtracted result.

### Claim 5 (depends on 1)

The secure computation device as claimed in claim 1, wherein:
in a case of detecting whether or not the first integer a is less than the second integer b,
the addition/subtraction circuitry is configured to calculate (b+2{circumflex over ( )}k−(a+1)) with ring sharing as the predetermined addition/subtraction to produce (b+2{circumflex over ( )}k−(a+1)) as the added/subtracted result.

### Claim 6 (depends on 1)

The secure computation device as claimed in claim 1, wherein:
in a case of detecting whether or not the first integer a is not less than the second integer b,
the addition/subtraction circuitry is configured to calculate (a+2{circumflex over ( )}k−b) with ring sharing as the predetermined addition/subtraction to produce (a+2{circumflex over ( )}k−b) as the added/subtracted result.

### Claim 7 (depends on 1)

The secure computation device as claimed in claim 1, wherein:
in a case of detecting whether or not the first integer a is more than the second integer b,
the addition/subtraction circuitry is configured to calculate (a+2{circumflex over ( )}k−(b+1)) with ring sharing as the predetermined addition/subtraction to produce (a+2{circumflex over ( )}k−(b+1)) as the added/subtracted result.

### Claim 8 (depends on 1)

A secure computation system comprising N secure computation devices each of which is described in claim 1, where N represents an integer which is not less three.

### Claim 9

A comparison method for comparing, in a case where a first integer a and a second integer b, each of which is more than 0 and less than 2{circumflex over ( )}k (where k is an integer equal to or more than one), are subjected to ring sharing, the first integer a with the second integer b in a secure computation device, wherein the comparison method comprises:
an addition/subtraction step of carrying out a predetermined addition/subtraction using the first integer a, the second integer b, and 2{circumflex over ( )}k with the ring sharing to produce an added/subtracted result;
a bit decomposition step of converting the added/subtracted result into bit sharing to produce a bit shared result; and
a bit extraction step of extracting a (k+1)-th bit of the bit shared result to produce an extracted result.

### Claim 10 (depends on 9)

The comparison method as claimed in claim 9, wherein the bit extraction step comprises a shifting step of shifting the bit shared result right by k bits.

### Claim 11

(canceled)

### Claim 12 (depends on 9)

The comparison method as claimed in claim 9, wherein:
in a case of detecting whether or not the first integer a is not more than the second integer b,
the addition/subtraction step calculates (b+2{circumflex over ( )}k−a) with ring sharing as the predetermined addition/subtraction to produce (b+2{circumflex over ( )}k−a) as the added/subtracted result.

### Claim 13 (depends on 9)

The comparison method as claimed in claim 9, wherein:
in a case of detecting whether or not the first integer a is less than the second integer b,
the addition/subtraction step calculates (b+2{circumflex over ( )}k−(a+1)) with ring sharing as the predetermined addition/subtraction to produce (b+2{circumflex over ( )}k−(a+1)) as the added/subtracted result.

### Claim 14 (depends on 9)

The comparison method as claimed in claim 9, wherein:
in a case of detecting whether or not the first integer a is not less than the second integer b,
the addition/subtraction step calculates (a+2{circumflex over ( )}k−b) with ring sharing as the predetermined addition/subtraction to produce (a+2{circumflex over ( )}k−b) as the added/subtracted result.

### Claim 15 (depends on 9)

The comparison method as claimed in claim 9, wherein:
in a case of detecting whether or not the first integer a is more than the second integer b,
the addition/subtraction step calculates (a+2{circumflex over ( )}k−(b+1)) with ring sharing as the predetermined addition/subtraction to produce (a+2{circumflex over ( )}k−(b+1)) as the added/subtracted result.

### Claim 16

A non-transitory comparison program recording medium storing a comparison program for causing, in a case where a first integer a and a second integer b, each of which is more than 0 and less than 2{circumflex over ( )}k (where k is an integer equal to or more than one), are subjected to ring sharing, a computer serving as a secure computation device to compare the first integer a with the second integer b, wherein the comparison program causes the computer to achieve:
an addition/subtraction function of carrying out a predetermined addition/subtraction using the first integer a, the second integer b, and 2{circumflex over ( )}k with the ring sharing to produce an added/subtracted result;
a bit decomposition function of converting the added/subtracted result into bit sharing to produce a bit shared result; and
a bit extraction function of extracting a (k+1)-th bit of the bit shared result to produce an extracted result.

### Claim 17 (depends on 16)

The non-transitory comparison program recording medium as claimed in claim 16, wherein the bit extraction function comprises a shifting function of shifting the bit shared result right by k bits.

### Claim 18

(canceled)

### Claim 19 (depends on 16)

The non-transitory comparison program recording medium as claimed in claim 16, wherein:
in a case of detecting whether or not the first integer a is not more than the second integer b,
the addition/subtraction function calculates (b+2{circumflex over ( )}k−a) with ring sharing as the predetermined addition/subtraction to produce (b+2{circumflex over ( )}k−a) as the added/subtracted result.

### Claim 20 (depends on 16)

The non-transitory comparison program recording medium as claimed in claim 16, wherein:
in a case of detecting whether or not the first integer a is less than the second integer b,
the addition/subtraction function calculates (b+2{circumflex over ( )}k−(a+1)) with ring sharing as the predetermined addition/subtraction to produce (b+2{circumflex over ( )}k−(a+1)) as the added/subtracted result.

### Claim 21 (depends on 16)

The non-transitory comparison program recording medium as claimed in claim 16, wherein:
in a case of detecting whether or not the first integer a is not less than the second integer b,
the addition/subtraction function calculates (a+2{circumflex over ( )}k−b) with ring sharing as the predetermined addition/subtraction to produce (a+2{circumflex over ( )}k−b) as the added/subtracted result.

### Claim 22 (depends on 16)

The non-transitory comparison program recording medium as claimed in claim 16, wherein:
in a case of detecting whether or not the first integer a is more than the second integer b,
the addition/subtraction function calculates (a+2{circumflex over ( )}k−(b+1)) with ring sharing as the predetermined addition/subtraction to produce (a+2{circumflex over ( )}k−(b+1)) as the added/subtracted result.
