# US 12,010,220 B2 · Secure division system, secure computation apparatus, secure division method, and program

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

- Number: US 12,010,220 B2
- Document ID: US12010220B2
- Status: Granted
- Kind: B2
- Application number: 17/615,106
- Filed: 2019-06-10
- Published: 2022-07-14
- Granted: 2024-06-11
- Earliest claimed: 2019-06-10
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Koki Hamada
- Web page: https://patentgrep.com/patent/US12010220B2

## CPC

- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- G06F 21/71: to assure secure computing or processing of information
- 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)
- G06F 7/535: Dividing only
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- 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)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY

## Abstract

Division is realized with a small number of processing stages. A secure computation apparatus (1) obtains a secret value representing a result of divided N by D using a secret value [N] of a real number N and a secret value [D] of a natural number D. An initialization unit (12) sets a secret value [PL1] of a partial remainder PL1 to 0. A parallel comparison unit (13) computes secret values [E1], . . . , [ER−1] of comparison results E1, . . . , ER−1 of comparing a secret value [n] of a partial divisor n=Pj+1R+Nj with [D]×g for each integer g not less than 1 and less than R in parallel. An update unit (14) computes a secret value [Qj] of a quotient Qj and a secret value [Pj] of a partial remainder Pj that satisfy n=DQj+Pj using the secret values [E1], . . . , [ER−1] of the comparison results E1, . . . , ER−1. An iterative control unit (15) executes the parallel comparison unit (13) and the update unit (14) for each integer j from L1−1 to −L0.

## Claims

### Claim 1

A secure division system to obtain a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L0 and L1 are non-negative integers, N is a real number not less than 0 and less than RL1, N is expressed in radix R, D is a natural number, N−L0, . . . , NL1−1 are values of respective digits from an L0th digit after the decimal point to an L1th digit of an integer part in R notation of N, and j is each integer from L1−1 to −L0, and L1 is related to the integer part of N and −L0 to L1−1 is related to the fractional part of N, the secure division system comprising:
a plurality of secure computation apparatuses connected via a network and that cooperatively compute the secret value representing the result of dividing N by D, each secure computation apparatus comprising processing circuitry that:
sets a secret value [PL1] of a partial remainder PL1 to 0;
computes secret values [E1], . . . , [ER−1] of comparison results E1, . . . , ER−1 of comparing a secret value [n] of a partial divisor n=Pj+1R+Nj with [D]×g for each integer g not less than 1 and less than R in parallel;
computes a secret value [Qj] of a quotient Qj and a secret value [Pj] of a partial remainder Pj that satisfy n=DQj+Pj using the secret values [E1], . . . , [ER−1] of the comparison results E1, . . . , ER−1; and
outputs the secret values [Q−L0] to [QL1−1] of the quotients Q−L0 to QL1−1.

### Claim 2 (depends on 1)

The secure division system according to claim 1,
wherein the processing circuitry computes a secret value [Eg] of a comparison result Eg for g by the following formula:
[
E
g
]
=
(
[
D
]
×
g
⁢
≤
?
⁢
[
n
]
)
.
[
Math
.
⁢
7
]

### Claim 3 (depends on 1)

The secure division system according to claim 1,
wherein the processing circuitry computes the secret value [Qj] of the quotient Qj by the following formula:
[
Q
j
]
:=
[
E
1
]
+
…
+
[
E
R
-
1
]
[
Math
.
⁢
8
]
and computes the secret value [Pj] of the partial remainder Pj by the following formula:
[
P
j
]
:=
[
n
]
-
[
D
]
×
[
Q
j
]
.
[
Math
.
⁢
9
]

### Claim 4

A secure computation apparatus for use in a secure division system that obtains a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L0 and L1 are non-negative integers, N is a real number not less than 0 and less than RL1, N is expressed in radix R, D is a natural number, N−L0, . . . , NL1−1 are values of respective digits from an L0th digit after the decimal point to an L1th digit of an integer part in R notation of N, j is each integer from L1−1 to −L0, and L1 is related to the integer part of N and −L0 to L1−1 is related to the fractional part of N, the secure computation apparatus comprising processing circuitry that, in cooperative computation with other secure computation apparatuses:
sets a secret value [PL1] of a partial remainder PL1 to 0;
computes secret values [E1], . . . , [ER−1] of comparison results E1, . . . , ER−1 of comparing a secret value [n] of a partial divisor n=Pj+1R+Nj with [D]×g for each integer g not less than 1 and less than R in parallel;
computes a secret value [Qj] of a quotient Qj and a secret value [Pj] of a partial remainder Pj that satisfy n=DQj+Pj using the secret values [E1], . . . , [ER−1] of the comparison results E1, . . . , ER−1; and
outputs a corresponding one of the secret values [Q−L0] to [QL1−1] of the quotients Q−L0 to QL1−1.

### Claim 5

A secure division method for execution by a secure division system comprising a plurality of secure computation apparatuses, the secure division system being used to obtain a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D by cooperation of the secure computation apparatuses, where R is an integer not less than 3, L0 and L1 are non-negative integers, N is a real number not less than 0 and less than RL1, N is expressed in radix R, D is a natural number, N−L0, . . . , NL1−1 are values of respective digits from an L0th digit after the decimal point to an L1th digit of an integer part in R notation of N, j is each integer from L1−1 to −L0, and L1 is related to the integer part of N and −L0 to L1−1 is related to the fractional part of N, the secure division method comprising:
setting a secret value [PL1] of a partial remainder PL1 to 0 with processing circuitry of each secure computation apparatus;
computing secret values [E1], . . . , [ER−1] of comparison results E1, . . . , ER−1 of comparing a secret value [n] of a partial divisor n=Pj+1R+Nj with [D]×g for each integer g not less than 1 and less than R in parallel with the processing circuitry of each secure computation apparatus;
computing a secret value [Qj] of a quotient Qj and a secret value [Pj] of a partial remainder Pj that satisfy n=DQj+Pj using the secret values [E1], . . . , [ER−1] of the comparison results E1, . . . , ER−1 with the processing circuitry of each secure computation apparatus; and
outputting the secret values [Q−L0] to [QL1−1] of the quotients Q−L0 to QL1−1 with the processing circuitry of each secure computation apparatus.

### Claim 6 (depends on 4)

A non-transitory computer-readable recording medium on which a program is recorded for causing a computer to function as the secure computation apparatus according to claim 4.

### Claim 7 (depends on 4)

The secure computation apparatus according to claim 4, wherein the secure computation apparatus is connected to the other secure computation apparatuses via a network.

### Claim 8 (depends on 7)

The secure computation apparatus according to claim 7, wherein the network includes at least one of a circuit switched network or a packet switched network.

### Claim 9 (depends on 1)

The secure division system according to claim 1, wherein the plurality of secure computation apparatuses perform cooperatively compute their respective portion of the secret value representing the result of dividing N by D in parallel.