Patent ID: 7551740

Claim:
A method of sharing a secret, comprising: using a computer to perform the operations of: encoding the secret using a predetermined code; producing voices so that different weights are assigned to errors in an error vector according to locations of the errors in the error vector; and encrypting the encoded secret using the error vector and distributing the encrypted encoded secret to a plurality of participants N, wherein code blocks are determined by a generator polynomial of the predetermined code, and the predetermined code has a codeword which concatenates the code blocks with different lengths together, and wherein the voices are set to assign the different weights to the errors, which correspond to each code block in the error vector, so that different weights are given to errors in an error vector according to locations of the errors, the error vector e is known to the plurality of participants N, code parameters are selected to make a (K,N) threshold secret sharing scheme realizable, where N= a number of secret shares of the secret distributed to the N participants, N=wt(e) wherein a weight (wt) τ i (i=1, 2, 3. . . , N) is given to each secret share s i according to a location i in the error vector, as set forth in Equation 1 below: T = ∑ i = 1 N ⁢ ⁢ τ i , ( 1 ) (d−1) or less errors are to be corrected, wherein a number of participants required to reconstruct the secret is at least K that satisfies wt(e)−K≦(d−1)/2 or 2K≧2 wt(e)−d+1, a minimum distance is d≦deg g(x)+1 when using Goppa code, and the minimum distance is d≦2(deg g(x))+1 when using binary Goppa codewith a separable Goppa polynomial g(x), wherein for a generalized Goppa code, the minimum distance is estimated using the generalized Goppa code with a Goppa polynomial g(x) and a locator set L, and an arbitrary error set T={t 1 , t 2 , . . ., t l } that satisfies following Equation (2) with respect to the respective code blocks a 1 (l) a 2 (l) . . . a n l (l) is corrected: (deg g ( x ))/2 ≧t l τ l +t 2 τ 2 + . . . +t l τ l (2), wherein t 1 , t 2 , . . . , and t l denote numbers of errors contained in the code blocks with lengths of n 1 , n 2 , . . . , and n l , respectively, and wherein in a generalized binary Goppa code, (deg g(x))/2 presented in Equation (2) is converted into (2 deg g(x))/2.