Patent ID: 8275124

Claim:
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.