Threshold secret sharing apparatus, threshold secret sharing scheme, secret information decryption method, and program for the same

1. A threshold secret sharing apparatus configured by a computer comprising:

a dividing means which divides inputted secret information K into same size (n p −1) divided pieces of secret information K q (n p is a prime number which is equal to or greater than a secret distribution number) according to a program loaded into the computer, the secret information K being divided according to a first expression

K=K 1 ∥K 2 ∥ . . . ∥K n p -1

whose operators and symbols are defined according to a set of definitions including

{circle around (x)}: Bitwise exclusive-or (XOR) operation

∥: Concatenation of binary sequence

n: The number of participants (nεN, 2≦n)

k: Threshold (kεN,2≦k≦n)

n p : A prime number such that (n p ≧n)

d: Data bit length in each processing (dεN)

p i : Participant (i-εN 0 , 0≦i≦n−1)

K: Secret information (Kε{0,1} d(n p −1) )

K q : A divided piece of secret information such that

K q ε{0,1} d ,qεN,1≦q≦n p −1,K 1 ∥K 2 ∥ . . . K n p -1 =K

K 0 : A dummy divided piece of secret information (K 0 ε{0} d )

R l t : A random number (R l t ε{0,1} d ,0≦t≦k−2, 0≦l≦n p −1)

S i : A share which is sent to the participant P i

S (i,m) : A piece of share S i which is sent to the participant P i ,

(S (i,0) ∥S (i,1) ∥Λ∥S (i,n p -2) =S,0≦m≦n p −2);

a dummy information generating means which generates dummy partial secret information K 0 according to a program loaded into the computer, the symbol K 0 being defined according to the set of definitions;

(k−1) random number generating means which generate respective sets of random numbers R t l which are mutually independent according to a program loaded into the computer, the symbols k and R t l being defined according to the set of definitions;

a generating means of pieces of shares, which generates pieces of shares by exclusive-OR (XOR) operations based upon the dummy partial secret information K 0 , the divided pieces of secret information K q , and the random numbers R t l according to a program loaded into the computer, the pieces of shares being generated according to a second expression

S

(

i

,

m

)

=

{

⊕

t

=

0

k

-

2

⁢

R

t

·

i

+

m

t

}

⊕

K

m

-

i

,

(

0

≤

i

≤

n

-

1

,

0

≤

m

≤

n

p

-

2

)

whose operators and symbols are defined according to the set of definitions; and

a concatenating means which concatenates the pieces of shares so as to generate n shares S i according to a program loaded into the computer, the pieces of shares being concatenated according to a third expression

S i =S (i,0) ∥S (i,1) ∥ . . . ∥S (i,n p -3) ∥S (i,n p -2)

whose operators and symbols are defined according to the set of definitions.

2. A threshold secret sharing method executed by operation of a computer comprising:

dividing inputted secret information K into same size (n p −1) divided pieces of secret information K q (n p is a prime number which is equal to or greater than a secret distribution number), the secret information K being divided according to a first expression

K=K 1 ∥K 2 ∥ . . . ∥K n p -1

whose operators and symbols are defined according to a set of definitions including

{circle around (x)}: Bitwise exclusive-or (XOR) operation

∥: Concatenation of binary sequence

n: The number of participants (nεN, 2≦n)

k: Threshold (kεN, 2≦k≦n)

n p : A prime number such that (n p ≧n)

d: Data bit length in each processing (dεN)

p i : Participant (iεN 0 , 0≦i≦n−1)

K: Secret information (Kε{0,1} d(n p −1) )

K g : A divided piece of secret information such that

K q ε{0,1} d , qεN,1≦q≦n p −1,K 1 ∥K 2 ∥ . . . K n p -1 =K

K 0 : A dummy divided piece of secret information (K 0 ε{0} d )

R l t : A random number (R l t ε{0,1} d ,0≦t≦k−2, 0<l≦n p −1)

S i : A share which is sent to the participant P i

S (i,m) : A piece of share S i which is sent to the participant P i ,

(S (i,0) ∥S (i,1) ∥Λ∥S (i,n p -2) =S,0≦m≦n p −2);

generating dummy partial secret information K 0 , the symbol K 0 being defined according to the set of definitions;

generating sets of random numbers R t l which are mutually independent, the symbol R t l being defined according to the set of definitions;

generating pieces of shares using exclusive-OR (XOR) computation based upon the dummy partial secret information K 0 , the divided pieces of secret information K q , and the random numbers R t l , the pieces of shares being generated according to a second expression

S

(

i

,

m

)

=

{

⊕

t

=

0

k

-

2

⁢

R

t

·

i

+

m

t

}

⊕

K

m

-

i

,

(

0

≤

i

≤

n

-

1

,

0

≤

m

≤

n

p

-

2

)

whose operators and symbols are defined according to the set of definitions; and

concatenating the pieces of shares so as to generate n shares S i , the pieces of shares being concatenated according to a third expression

S i =S (i,0) ∥S (i,1) ∥ . . . ∥S (i,n p -3) ∥S (i,n p -2)

whose operators and symbols are defined according to the set of definitions.

3. A computer program product comprising a computer-readable non-transitory storage medium having computer readable instructions recorded thereon, the computer readable instructions being operative, when performed by a computerized device, to cause the computerized device to:

divide inputted secret information K into same size (n p −1) divided pieces of secret information K q (n p is a prime number which is equal to or greater than a secret distribution number), the secret information K being divided according to a first expression

K=K 1 ∥K 2 ∥ . . . ∥K n p -1

whose operators and symbols are defined according to a set of definitions including

{circle around (x)}: Bitwise exclusive-or (XOR) operation

∥: Concatenation of binary sequence

n: The number of participants (nεN,2≦n)

k: Threshold (kεN,2≦k≦n)

n p : A prime number such that (n p ≧n)

d: Data bit length in each processing (dεN)

p i : Participant (iεN 0 , 0≦i≦n−1)

K: Secret information (Kε{0,1} d(n p −1) )

K q : A divided piece of secret information such that

K q ε{0,1} d ,qεN,1≦q≦n p −1,K 1 ∥K 2 ∥ . . . K n p -1 =K

K 0 : A dummy divided piece of secret information (K 0 ε{0} d )

R l t : A random number (R l t ε{0,1} d , 0≦t≦k−2,0≦n≦n p −1)

S i : A share which is sent to the participant P i

S (i,m) : A piece of share S i which is sent to the participant P i ,

(S (i,0) ∥S (i,1) ∥Λ∥S (i,n p -2) =S,0≦m≦n p −2);

generate dummy partial secret information K 0 , the symbol K 0 being defined according to the set of definitions;

generate sets of random numbers R t l which are mutually independent, the symbol R t l being defined according to the set of definitions;

generate pieces of shares using exclusive-OR (XOR) computation based upon the dummy partial secret information K 0 , the divided pieces of secret information K q , and the random numbers R t l , the pieces of shares being generated according to a second expression

S

(

i

,

m

)

=

{

⊕

t

=

0

k

-

2

⁢

R

t

·

i

+

m

t

}

⊕

K

m

-

i

,

(

0

≤

i

≤

n

-

1

,

0

≤

m

≤

n

p

-

2

)

whose operators and symbols are defined according to the set of definitions; and

concatenate the pieces of shares so as to generate n shares S i , the pieces of shares being concatenated according to a third expression

S i =s (i,0) ∥S (i,1) ∥ . . . ∥S (i,n p -3) ∥S (i,n p -2)

whose operators and symbols are defined according to the set of definitions.

4. A secret information recovery apparatus which recovers secret information from pieces of shares generated by a threshold secret sharing apparatus according to claim 1 comprising:

a dividing means which divides k shares obtained beforehand into n p (k−1) pieces of shares, the shares being divided according to a first expression

S

(

i

0

,

0

)

,

S

(

i

0

,

1

)

,

…

⁢

,

S

(

i

0

,

n

p

-

3

)

,

S

(

i

0

,

n

p

-

2

)

,

⋮

⋮

⋮

⋮

⋮

S

(

i

k

-

1

,

0

)

,

S

(

i

k

-

1

,

1

)

,

…

⁢

,

S

(

i

k

-

1

,

n

p

-

3

)

,

S

(

i

k

-

1

,

n

p

-

2

)

,

whose operators and symbols are defined according to a set of definitions including

{circle around (x)}: Bitwise exclusive-or (XOR) operation

∥: Concatenation of binary sequence

n: The number of participants (nεN,2≦n)

k: Threshold (kεN,2≦k≦n)

n p : A prime number such that (n p ≧n)

d: Data bit length in each processing (dεN)

p i : Participant (iεN 0 ,0≦i≦n−1)

K: Secret information (Kε{0,1} d(n p −1) )

K q : A divided piece of secret information such that

K q ε{0,1} d , qεN,1≦q≦n p −1,K 1 ∥K 2 ∥ . . . K n p -1 =K

K 0 : A dummy divided piece of secret information (K 0 ε{0} d )

R l t : A random number (R l t ε{0,1} d ,0≦t≦k−2,0≦l≦n p −1)

S i : A share which is sent to the participant P i

S (i,m) : A piece of share S i which is sent to the participant P i ,

(S (i,0) ∥S (i,1) ∥Λ∥S (i,n p -2) =S,0≦m≦n p −2); and

a exclusive-OR (XOR) means which outputs (n p −1) divided pieces of secret information by removing the random numbers with XOR operations, in increments of the set of random number, from each of the pieces of shares on the assumption that there are (k−1) sets of random numbers and there are the same n p random numbers for each set of random numbers, where the operators and symbols are defined according to the set of definitions; and

a concatenating means which concatenates the divided pieces of secret information so as to recover the secret information K, the divided pieces of secret information being concatenated according to a second expression

K=K 1 ∥K 2 ∥ . . . ∥K n p -1

whose operators and symbols are defined according to a the set of definitions.

5. A secret information recovery apparatus which recovers secret information from pieces of shares generated by a threshold secret sharing method according to claim 2 comprising:

dividing k shares obtained beforehand into n p (k−1) pieces of shares, the shares being divided according to a first expression

S

(

i

0

,

0

)

,

S

(

i

0

,

1

)

,

…

⁢

,

S

(

i

0

,

n

p

-

3

)

,

S

(

i

0

,

n

p

-

2

)

,

⋮

⋮

⋮

⋮

⋮

S

(

i

k

-

1

,

0

)

,

S

(

i

k

-

1

,

1

)

,

…

⁢

,

S

(

i

k

-

1

,

n

p

-

3

)

,

S

(

i

k

-

1

,

n

p

-

2

)

,

whose operators and symbols are defined according to a set of definitions including

{circle around (x)}: Bitwise exclusive-or (XOR) operation

∥: Concatenation of binary sequence

n: The number of participants (nεN,2≦n)

k: Threshold (kεN,2≦k≦n)

n p : A prime number such that (n p ≧n)

d: Data bit length in each processing (dεN)

p i : Participant (iεN 0 , 0≦i≦n−1)

K: Secret information (Kε{0,1} d(n p −1) )

K q : A divided piece of secret information such that

K q ε{0,1} d , qεN,1≦q≦n p −1,K 1 ∥K 2 ∥ . . . K n p -1 =K

K 0 : A dummy divided piece of secret information (K 0 ε{0} d )

R l t : A random number (R l t ε{0,1} d ,0≦t≦k−2,0≦l≦n p −1)

S i : A share which is sent to the participant P i

S (i,m) : A piece of share S i which is sent to the participant P i ,

(S (i,0) ∥S (i,1) ∥Λ∥S (i,n p −2) =S,0≦m≦n p −2); and

outputting (n p −1) divided pieces of secret information by removing the random numbers with XOR operations, in increments of the set of random number, from each of the pieces of shares on the assumption that there are (k−1) sets of random numbers and there are the same n p random numbers for each set of random numbers, where the operators and symbols are defined according to the set of definitions; and

concatenating the divided pieces of secret information so as to recover the secret information K, the divided pieces of secret information being concatenated according to a second expression

K=K 1 ∥K 2 ∥ . . . ∥K n p -1

whose operators and symbols are defined according to a the set of definitions.

6. A computer program product comprising a computer-readable non-transitory storage medium having computer readable instructions recorded thereon for recovering secret information from pieces of shares generated by a computer program according to claim 3 , the computer readable instructions being operative, when performed by a computerized device, to cause the computerized device to:

divide k shares obtained beforehand into n p (k−1) pieces of shares, the shares being divided according to a first expression

S

(

i

0

,

0

)

,

S

(

i

0

,

1

)

,

…

⁢

,

S

(

i

0

,

n

p

-

3

)

,

S

(

i

0

,

n

p

-

2

)

,

⋮

⋮

⋮

⋮

⋮

S

(

i

k

-

1

,

0

)

,

S

(

i

k

-

1

,

1

)

,

…

⁢

,

S

(

i

k

-

1

,

n

p

-

3

)

,

S

(

i

k

-

1

,

n

p

-

2

)

,

whose operators and symbols are defined according to a set of definitions including

{circle around (x)}: Bitwise exclusive-or (XOR) operation

∥: Concatenation of binary sequence

n: The number of participants (nεN,2≦n)

k: Threshold (kεN,2≦k≦n)

n p : A prime number such that (n p ≧n)

d: Data bit length in each processing (dεN)

d: Participant (iεN 0 ,0≦i≦n−1)

K: Secret information (Kε{0,1} d(n p −1) )

K q : A divided piece of secret information such that

K q ε{0,1} d ,qεN,1≦q≦n p −1,K 1 ∥K 2 ∥ . . . K n p -1 =K

K 0 : A dummy divided piece of secret information (K 0 ε{0} d )

R i t : A random number (R l t ε{0,1} d ,0≦t≦k−2,0≦l≦n p −1)

S i : A share which is sent to the participant P i

S (i,m ): A piece of share S i which is sent to the participant P i ,

(S (i,0) ∥S (i,1) ∥Λ∥S (i,n p -2) =S,0≦m≦n p −2); and

output (n p −1) divided pieces of secret information by removing the random numbers with XOR operations, in increments of the set of random number, from each of the pieces of shares on the assumption that there are (k−1) sets of random numbers and there are the same n p random numbers for each set of random numbers, where the operators and symbols are defined according to the set of definitions; and

concatenate the divided pieces of secret information so as to recover the secret information K, the divided pieces of secret information being concatenated according to a second expression

K=K 1 ∥K 2 ∥ . . . ∥K n p -1

whose operators and symbols are defined according to a the set of definitions.