Non-malleable secret sharing
February 20, 2019 (GHC 8102)

Secret sharing is typically concerned with hiding the secret. However, what if the goal of the adversary is to tamper with the secret instead? In this work, we initiate a systematic study of what we call non-malleable secret sharing. Very roughly, the guarantee we seek is the following: the adversary may potentially tamper with all of the shares, and still, either the reconstruction procedure outputs the original secret, or, the original secret is ''destroyed'' and the reconstruction outputs a string which is completely ''unrelated'' to the original secret. This notion is inspired by the beautiful line of works on non-malleable codes.

We will present a construction of a t-out-of-n non-malleable secret sharing scheme against an adversary who arbitrarily tampers each of the shares independently. Going further, we also present t-out-of-n non-malleable secret sharing scheme in a stronger adversarial model where an adversary may jointly tamper multiple shares. Our constructions are unconditional and the adversary is allowed to jointly-tamper subsets of up to (t-1) shares. No cryptography is used.