Short Leakage Resilient and Non-malleable Secret Sharing Schemes

Leakage resilient secret sharing (LRSS) allows a dealer to share a secret amongst n parties such that any authorized subset of the parties can recover the secret from their shares, while an adversary that obtains shares of any unauthorized subset of parties along with bounded leakage from the other shares learns no information about the secret. Non-malleable secret sharing (NMSS) provides a guarantee that even shares that are tampered by an adversary will reconstruct to either the original message or something independent of it.

The most important parameter of LRSS and NMSS schemes is the size of each share. For LRSS, in the local leakage model (i.e., when the leakage functions on each share are independent of each other and bounded), Srinivasan and Vasudevan (CRYPTO 2019), gave a scheme for threshold access structures with share size of approximately (3•message length +μ), where μ is the number of bits of leakage tolerated from every share. For the case of NMSS, the best known result (again due to the above work) has share size of (11 • message length).

In this work, we build LRSS and NMSS schemes with much improved share size. Additionally, our LRSS scheme obtains optimal share and leakage size. In particular, we get the following results:

-We build an information-theoretic LRSS scheme for threshold access structures with a share size of (message length + μ). -As an application of the above result, we obtain an NMSS with a share size of (4•message length). Further, for the special case of sharing random messages, we obtain a share size of (2 • message length).