Perfect secrecy of Shamir's threshold scheme
ID: perfect-secrecy-of-shamir-s-threshold-scheme
In Shamir's secret sharing, observing any shares leaves the secret's prior distribution unchanged. In particular, the posterior distribution is uniform if the prior distribution was uniform; uniformity of the secret is not required for perfect secrecy.
To prove this, fix distinct nonzero evaluation points and a candidate secret . The evaluations impose independent linear equations on the random coefficients. The evaluation matrix has rank : its first columns form a Vandermonde matrix multiplied by a nonsingular diagonal matrix of nonzero evaluation points. Every observed share tuple therefore has exactly compatible coefficient tuples. Since the coefficients were independently uniform, its conditional probability isindependent of . Thus the shares and the secret are independent random variables, which proves perfect secrecy.[ref]
How to Share a Secret by Adi Shamir. Pages 612–613: interpolation argument for fewer than the threshold number of shares
New to topics? Read the docs here!