Inconsistency detecting method, inconsistency detecting system, inconsistency detecting device, and program

• US 10,665,137 B2
• Filed: 02/01/2016
• Issued: 05/26/2020
• Est. Priority Date: 02/06/2015
• Status: Active Grant

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Ikarashi, Dai, Kikuchi, Ryo, Hamada, Koki, Chida, Koji
• Primary Examiner(s): Gelagay, Shewaye
• Assistant Examiner(s): Ayala, Kevin
• Application Number:
  US15/541,410
• Publication Number:
  US 20180025670A1
• Time in Patent Office: 1,576 Days
• Field of Search: 380 28
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: 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
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

An inconsistency in shares is detected with a small volume of communications traffic. n inconsistency detecting devices generate random numbers s_i and make the random numbers s_i public. The n inconsistency detecting devices generate a common random number s which is the sum total of the random numbers s₀, . . . , s_n−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]₁, . . . , [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]₀, . . . , [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

1. An inconsistency detecting method, implemented by an inconsistency detecting system that includes n inconsistency detecting devices, 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 [a₀]_i, . . . , [a<sub>m−

1</sub>]_i obtained by dividing m electronic plain text values a₀, . . . , a<sub>m−

1</sub> by (k, n)-secret sharing in storages of the n inconsistency detecting devices p_i which are connected to each other via a communications network, where an original plain text value based on a combination of the values a₀, . . . , a<sub>m−

1</sub> is only reconstructed when at least arbitrary k shares of the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i are provided by the inconsistency detecting devices p_i,

generating, by circuitry of the n inconsistency detecting devices p_i, random numbers s_i and making the random numbers s_i public;

generating, by circuitry of the n inconsistency detecting devices p_i a common random number s which is a sum total of the random numbers s₀, . . . , s<sub>n−

1</sub>;

calculating, by circuitry of the n inconsistency detecting devices p_i shares [c]_i=Σ

<sub>j<

m−

1</sub>s^j+1[a_j]_i+s^m+1[a<sub>m−

1</sub>]_i by using the common random number s and the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

generating, by circuitry of the n inconsistency detecting devices p_i shares [r]_i, each of which becomes a random number r by reconstruction when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p₀, . . . , p<sub>n−

1</sub>;

calculating, by circuitry of the n inconsistency detecting devices p_i shares [d]_i=[c−

r]_i, each of which becomes a judgment value d by reconstruction when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

receiving, by circuitry of one inconsistency detecting device p₀ n−

1 shares [d]₁, . . . , [d]<sub>n−

1</sub> from circuitry of n−

1 inconsistency detecting devices p₁, . . . , p<sub>n−

1</sub>;

restoring, by circuitry of the inconsistency detecting device p₀ n−

k shares [d]′

_k, . . . , [d]′

<sub>n−

1</sub> from k shares [d]₀, . . . , [d]<sub>k−

1</sub>; and

judging, by circuitry of the inconsistency detecting device p₀ for j=k, . . . , n−

1, whether or not the share [d]_j and the share [d]′

_j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i for i=0, . . . , n are consistent while concealing the electronic plain text values a₀, . . . , a<sub>m−

1</sub> from all of the n inconsistency detecting devices by secret sharing.

2. The inconsistency detecting method according to claim 1, wherein

j is assumed to be an integer greater than or equal to 0 but smaller than m,

the inconsistency detecting method further includes:

dividing the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i into a plurality of groups;

performing a processing which includes;

detecting a presence or absence of an inconsistency in each group; and

dividing a group on which a judgment that an inconsistency has occurred therein is made into a plurality of groups; and

repeating the processing until a number of shares included in a group becomes one to identify a share [a_j]_i in which an inconsistency has occurred.

3. An inconsistency detecting system that includes n inconsistency detecting devices p₀, . . . , p_n−

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 p_i comprising;

circuitry configured to;

store shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i obtained by dividing m electronic plain text values a₀, . . . , a<sub>m−

1</sub> by (k, n)-secret sharing in a storage, the n inconsistency detecting devices being connected to each other via a communications network, where an original plain text value based on a combination of the values a₀, . . . , a<sub>m−

1</sub> is only reconstructed if at least arbitrary k shares of the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i are provided by the inconsistency detecting devices p_i;

generate a random number s_i and make the random number s_i public;

generate a common random number s which is a sum total of the random numbers s₀, . . . , s<sub>n−

1</sub>;

calculate a share [c]_i=Σ

<sub>j<

m−

1</sub>s^j+1[a_j]_i+s^m+1[a<sub>m−

1</sub>]_i by using the common random number s and the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

generate a share [r]_i which becomes a random number r when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p₀, . . . , p<sub>n−

1</sub>;

calculate a share [d]_i=[c−

r]_i which becomes a judgment value d

when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

receive n−

1 shares [d]_i′

from other n−

1 inconsistency detecting devices p_i;

restore n−

k shares [d]′

_k, . . . , [d]′

<sub>n−

1</sub> from k shares [d]₀, . . . , [d]<sub>k−

1</sub>; and

judge, for j=k, . . . , n−

1, whether or not the share [d]_j and the share [d]′

_j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i for i=0, . . . , n are consistent while concealing the electronic plain text values a₀, . . . , a<sub>m−

1</sub> from all of the n inconsistency detecting devices by secret sharing.

4. An inconsistency detecting device in an inconsistency detecting system that includes n inconsistency detecting devices, 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, and

the inconsistency detecting device comprising;

circuitry configured to;

store shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i obtained by dividing electronic plain text values a₀, . . . , a<sub>m−

1</sub> by (k, n)-secret sharing in a storage, the n inconsistency detecting devices being connected to each other via a communications network, where an original plain text value based on a combination of the values a₀, . . . , a<sub>m−

1</sub> is only reconstructed if at least arbitrary k shares of the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i are provided by the inconsistency detecting devices p_i;

generate a random number s_i and makes the random number s_i public;

generate a common random number s which is a sum total of the random numbers s₀, . . . , s<sub>n−

1</sub>;

calculate a share [c]_i=Σ

<sub>j<

m−

1</sub>s^j+1[a_j]_i+s^m+1[a<sub>m−

1</sub>]_i by using the common random number s and the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

generate a share [r]_i which becomes a random number r when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p₀, . . . , p<sub>n−

1</sub>;

calculate a share [d]_i=[c−

r]_i which becomes a judgment value d when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

receive n−

1 shares [d]_i′

from circuitry of other n−

1 inconsistency detecting devices p_i′

;

restore n−

k shares [d]′

_k, . . . , [d]′

<sub>n−

1</sub> from k shares [d]₀, . . . , [d]<sub>k−

1</sub>; and

judge, for j=k, . . . , n−

1, whether or not the share [d]_j and the share [d]′

_j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i for i=0, . . . , n are consistent while concealing the electronic plain text values a₀, . . . , a<sub>m−

1</sub> from all of the n inconsistency detecting devices by secret sharing computation.

5. A non-transitory computer readable medium including computer executable instructions that make an inconsistency detecting device in an inconsistency detecting system that includes n inconsistency detecting devices, 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 [a₀]_i, . . . , [a<sub>m−

1</sub>]_i obtained by dividing m electronic plain text values a₀, . . . , a<sub>m−

1</sub> by (k, n)-secret sharing in a storage, the n inconsistency detecting devices being connected to each other via a communications network, where an original plain text value based on a combination of the values a₀, . . . , a<sub>m−

1</sub> is only reconstructed if at least arbitrary k shares of the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i are provided by the inconsistency detecting devices p_i;

generating a random number s_i and making the random number s_i public;

generating a common random number s which is a sum total of the random numbers s₀, . . . , s<sub>n−

1</sub>;

calculating a share [c]_i=Σ

<sub>j<

m−

1</sub>s^j+1[a_j]_i+s^m+1[a<sub>m−

1</sub>]_i by using the common random number s and the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

generating a share [r]_i which becomes a random number r when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p₀, . . . , p<sub>n−

1</sub>;

calculating a share [d]_i=[c−

r]_i which becomes a judgment value d when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i;

receiving n−

1 shares [d]_i′

from circuitry of other n−

1 inconsistency detecting devices p_i′

;

restoring n−

k shares [d]′

_k, . . . , [d]′

<sub>n−

1</sub> from k shares [d]₀, . . . , [d]<sub>k−

1</sub>; and

judging, for j=k, . . . , n−

1, whether or not the share [d]_j and the share [d]′

_j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a₀]_i, . . . , [a<sub>m−

1</sub>]_i for i=0, . . . , n are consistent while concealing the electronic plain text values a₀, . . . , a<sub>m−

1</sub> from all of the n inconsistency detecting devices by secret sharing.