# US 2018/0025670 A1 · Inconsistency detecting method, inconsistency detecting system, inconsistency detecting device, and program

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

- Number: US 2018/0025670 A1
- Document ID: US20180025670A1
- Status: Published application
- Kind: A1
- Application number: 15/541,410
- Filed: 2016-02-01
- Published: 2018-01-25
- Earliest claimed: 2015-02-06
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Dai IKARASHI; Ryo KIKUCHI; Koki HAMADA; Koji CHIDA
- Web page: https://patentgrep.com/patent/US20180025670A1

## CPC

- 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 21/64: Protecting data integrity, e.g. using checksums, certificates or signatures
- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
- 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)

## Abstract

An inconsistency in shares is detected with a small volume of communications traffic. n inconsistency detecting devices generate random numbers si and make the random numbers si public. The n inconsistency detecting devices generate a common random number s which is the sum total of the random numbers s0, . . . , sn−1. The n inconsistency detecting devices calculate shares [c]i. The n inconsistency detecting devices generate shares [r]i, each of which would become a random number r by reconstruction. The n inconsistency detecting devices calculate shares [d]i, each of which would become a judgment value d by reconstruction. One inconsistency detecting device receives shares [d]1, . . . , [d]n−1 from n−1 inconsistency detecting devices. The one inconsistency detecting device restores n−k shares [d]′k, . . . , [d]′n−1 from k shares [d]0, . . . , [d]k−1. The one inconsistency detecting device judges, for j=k, . . . , n−1, whether or not a share [d]j and a share [d]′j coincide with each other.

## Claims

### Claim 1

An inconsistency detecting method, wherein
n and k are assumed to be integers that satisfy n≧2k−1, m is assumed to be an integer greater than or equal to 1, and i is assumed to be each of integers greater than or equal to 0 but smaller than n,
the inconsistency detecting method comprising:
storing shares [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in storages of n inconsistency detecting devices pi,
generating, by circuitry of the n inconsistency detecting devices pi, random numbers si and making the random numbers si public;
generating, by circuitry of the n inconsistency detecting devices pi a common random number s which is a sum total of the random numbers s0, . . . , sn−1;
calculating, by circuitry of the n inconsistency detecting devices pi shares [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]1, . . . , [am−1]i;
generating, by circuitry of then inconsistency detecting device3s pi shares [r]i, each of which would become a random number r by reconstruction;
calculating, by circuitry of then inconsistency detecting devices pi shares [d]i=[c−r]i, each of which would become a judgment value d by reconstruction;
receiving, by circuitry of one inconsistency detecting device p0 n−1 shares [d]1, . . . , [d]n−1 from circuitry of n−1 inconsistency detecting devices p1, . . . , pn−1;
restoring, by circuitry of the inconsistency detecting device p0 n−k shares [d]′k, . . . , [d]′n−1 from k shares [d]0, . . . , [d]k−1; and
judging, by circuitry of the inconsistency detecting device p0 for j=k, . . . , n−1, whether or not the share [d]j and the share [d]′j coincide with each other.

### Claim 2 (depends on 1)

The inconsistency detecting method according to claim 1, wherein
m is assumed to be an integer greater than or equal to 2 and j is assumed to be an integer greater than or equal to 0 but smaller than m, and
the shares [a0]i, . . . , [am−1]i are divided into a plurality of groups, a presence or absence of an inconsistency in each group is detected by the inconsistency detecting method according to claim 1, a group on which a judgment that an inconsistency has occurred therein is made is further divided into a plurality of groups, and processing is repeated until a number of shares included in a group becomes one to identify a share [aj]i in which an inconsistency has occurred.

### Claim 3 (depends on 1, 2)

The inconsistency detecting method according to claim 1 or 2, wherein
n, n′, and k are assumed to be integers that satisfy n>n′=2k−1, and
for all combinations of n′ inconsistency detecting devices selected from among the n inconsistency detecting devices, a presence or absence of an inconsistency is detected by the inconsistency detecting method according to claim 1 or 2 and the shares [a0]i, . . . , [am−1]i which are stored in the inconsistency detecting device that is included in all combinations on which a judgment that an inconsistency has occurred therein is made are identified as shares in which an inconsistency has occurred.

### Claim 4

An inconsistency detecting system that includes n inconsistency detecting devices p0, . . . pn−1, wherein
n and k are assumed to be integers that satisfy n≧2k−1, m is assumed to be an integer greater than or equal to 1, i is assumed to be each of integers greater than or equal to 0 but smaller than n, and i′ is assumed to be each of integers that satisfy i≠i′ and are greater than or equal to 0 but smaller than n, and
each of the inconsistency detecting devices pi comprising:
circuitry configured to:
store shares [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in a storage;
generate a random number si and make the random number si public;
generate a common random number s which is a sum total of the random numbers s0, . . . , sn−1;
calculate a share [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]i, . . . , [am−1]i;
generate a share [r]i which would become a random number r by reconstruction;
calculate a share [d]i=[c−r]i which would become a judgment value d by reconstruction;
receive n−1 shares [d]i′ from other n−1 inconsistency detecting devices pi′;
restore n−k shares [d]′k, . . . , [d]′n−1 from k shares [d]0, . . . , [d]k−1; and
judge, for j=k, . . . , n−1, whether or not the share [d]j and the share [d]′j coincide with each other.

### Claim 5

An inconsistency detecting device, wherein
n and k are assumed to be integers that satisfy n≧2k−1, in is assumed to be an integer greater than or equal to 1, i is assumed to be an integer greater than or equal to 0 but smaller than n, and i′ is assumed to be each of integers that satisfy i≠i′ and are greater than or equal to 0 but smaller than n, and
the inconsistency detecting device comprising:
circuitry configured to:
store shares [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in a storage;
generate a random number si and makes the random number si public;
generate a common random numbers which is a sum total of the random numbers s0, . . . , sn−1;
calculate a share [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]i, . . . , [am−1]i;
generate a share [r]i which would become a random number r by reconstruction;
calculate a share [d]i=[c−r]i which would become a judgment value d by reconstruction;
receive n−1 shares [d]i′ from circuitry of other n−1 inconsistency detecting devices pi′;
restore n−k shares [d]′k, . . . , [d]′n−1 from k shares [d]0, . . . , [d]k−1; and
judge, for j=k, . . . , n−1, whether or not the share [d]j and the share [d]′j coincide with each other.

### Claim 6

(canceled)

### Claim 7

A non-transitory computer readable medium including computer executable instructions that make an inconsistency detecting device, wherein
n and k are assumed to be integers that satisfy n≧2k−1, m is assumed to be an integer greater than or equal to 1, i is assumed to be an integer greater than or equal to 0 but smaller than n, and i′ is assumed to be each of integers that satisfy i≠i′ and are greater than or equal to 0 but smaller than n,
perform a method comprising:
storing shares [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in a storage;
generating a random number si and making the random number si public;
generating a common random numbers which is a sum total of the random numbers s0, . . . , sn−1;
calculating a share [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]i, . . . , [am−1]i;
generating a share which would become a random number r by reconstruction;
calculating a share [d]i=[c−r]i which would become a judgment value d by reconstruction;
receiving n−1 shares [d]i′ from circuitry of other n−1 inconsistency detecting devices pi′;
restoring n−k shares [d]′k, . . . , [d]′n−1 from k shares [d]0, . . . , [d]k−1; and
judging, for j=k, . . . , n−1, whether or not the share [d]j and the share [d]′j coincide with each other.