Method of verifiably sharing a secret in potentially asynchronous networks

Abstract

In accordance with the present invention, there is provided a method for sharing a secret value x among n participating network devices via an asynchronous network. The n participating network devices comprises 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. The method comprising of deriving by the distributor share values sand subshare values sof the secret value x by applying a linear secret sharing scheme and deriving verification values gusable for verification of validity of the share values sand the subshare values s; sending to each participating network device a share message comprising the corresponding subshare values s,s, s,s, s,s; broadcasting a verification message comprising the verification values g; receiving by at least l participating network devices the verification message comprising the verification values g, wherein n−t≧l≧2t+1, and performing the following steps 1) to 4) for each recipient network device, 1) if a share message comprising subshare values sis received, determining the validity of the subshare values sin dependence on the verification values gand 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, Y, Y; 4) in the event of l received agree messages, obtaining the share value seither from the share message sent by the distributor D or from subshare values sreceived from participating network devices and determining the validity of the subshare values sin dependence on the verification values g. In a second aspect of the present invention a method without broadcast is disclosed.