SHARE RECOVERY SYSTEM, SHARE RECOVERY APPARATUS, SHARE RECOVERY METHOD, AND PROGRAM

摘要

An efficient share recovery technique for Shamir's secret sharing is provided. n share recovery apparatuses p 0 , ..., p n-1 generate a share [r] i of a secretly shared value shared through Shamir's secret sharing, which becomes a random number r when restored. k share recovery apparatuses à 0 , ..., à k-1 calculate a share [b] i by subtracting the share [r] i from a share [a] i . The share recovery apparatus Ä k receives the shares [b] 0 , ..., [b] k-1 from the share recovery apparatuses à 0 , ..., à k-1 . The share recovery apparatus Ä k recovers shares [b] k , ..., [b] k+m-1 using the shares [b] 0 , ..., [b] k-1 . m-1 share recovery apparatuses Ä k+1 , ..., Ä k+m-1 receive a share [b] j from the share recovery apparatus Ä k . m share recovery apparatuses Ä k , ..., Ä k+m-1 calculate the share [a] j by adding the share [r] j to the share [b] j .