Patent ID: 7389416

Claim:
Method for sharing a secret value (x) among n participating network devices (A, B, C) via an asynchronous network, the n participating network devices (A, B, C) comprising t faulty devices and k sub-devices capable of reconstructing the secret value (x), wherein t<n/3 and k<n, the secret value (x) being provided by a distributor (D), comprising of the following steps: deriving by the distributor (D) share values (s i ) and subshare values (s ij ) of the secret value (x) by applying a linear secret sharing scheme and deriving verification values (g s ij ) usable for verification of validity of the share values (s i ) and the subshare values (s ij ); sending to each participating network device (A, B, C) a share message comprising the corresponding subshare values (s Ai ,s iA , s Bi ,s iB , s Ci ,s iC ); broadcasting a verification message comprising the verification values (g s ij ); receiving by at least l participating network devices (A, B, C) the verification message comprising the verification values (g s ij ), wherein n−t≧l≧2t+1, and performing the steps 1) to 4) for each recipient network device (A, B, C), 1) if the share message comprising subshare values (s ij ) is received, determining the validity of the subshare values (s ij ) in dependence on the verification values (g s ij ) and 2) broadcasting in the event of positive determination an agree message comprising an agree-value (Y); 3) receiving l agree messages comprising the agree-values (Y A , Y B , Y C ); 4) in the event of l received agree messages, obtaining the share value (s i ) either from the share message sent by the distributor (D) or from subshare values (s ij ) received from participating network devices (A, B, C), and determining the validity of the subshare values (s ij ) in dependence on the verification values (g s ij ).