Paper 2019/602

Continuously Non-Malleable Secret Sharing for General Access Structures

Gianluca Brian and Antonio Faonio and Daniele Venturi

Abstract

We study leakage-resilient continuously non-malleable secret sharing, as recently intro- duced by Faonio and Venturi (CRYPTO 2019). In this setting, an attacker can continuously tamper and leak from a target secret sharing of some message, with the goal of producing a modified set of shares that reconstructs to a message related to the originally shared value. Our contributions are two fold. - In the plain model, assuming one-to-one one-way functions, we show how to obtain noisy-leakage-resilient continuous non-malleability for arbitrary access structures, in case the attacker can continuously leak from and tamper with all of the shares inde- pendently. - In the common reference string model, we show how to obtain a new flavor of secu- rity which we dub bounded-leakage-resilient continuous non-malleability under joint k-selective partitioning. In this model, the attacker is allowed to partition the target n shares into k non-overlapping subsets, and then can continuously leak from and tamper with the shares within each subset jointly. Our construction works for arbitrary ac- cess structures, and assuming (doubly enhanced) trapdoor permutations and collision- resistant hash functions, we achieve a concrete instantiation for $k \in O(n/ \log n)$. Prior to our work, there was no secret sharing scheme achieving continuous non-malleability against joint tampering, and the only known scheme for independent tampering was tailored to threshold access structures.