Continuously non-malleable secret sharing: Joint tampering, plain model and capacity

Brian, Gianluca; Faonio, Antonio; Venturi, Daniele
TCC 2021, 19th Theory of Cryptography Conference, 8-11 November 2021, Raleigh, USA / Also on Lecture Notes in Computer Science, Vol.13043

We study non-malleable secret sharing against joint leakage and joint tampering attacks. Our main result is the first threshold secret sharing scheme in the plain model achieving resilience to noisy-leakage and continuous tampering. The above holds under (necessary) minimal computational assumptions (i.e., the existence of one-to-one one-way functions), and in a model where the adversary commits to a fixed partition of all the shares into nonoverlapping subsets of at most t − 1 shares (where t is the reconstruction threshold), and subsequently jointly leaks from and tampers with the shares within each partition. We also study the capacity (i.e., the maximum achievable asymptotic information rate) of continuously non-malleable secret sharing against joint continuous tampering attacks. In particular, we prove that whenever the attacker can tamper jointly with k > t/2 shares, the capacity is at most t − k. The rate of our construction matches this upper bound. An important corollary of our results is the first non-malleable secret sharing scheme against independent tampering attacks breaking the rate-one barrier (under the same computational assumptions as above).


DOI
Type:
Conférence
City:
Raleigh
Date:
2021-11-08
Department:
Sécurité numérique
Eurecom Ref:
6669
Copyright:
© Springer. Personal use of this material is permitted. The definitive version of this paper was published in TCC 2021, 19th Theory of Cryptography Conference, 8-11 November 2021, Raleigh, USA / Also on Lecture Notes in Computer Science, Vol.13043 and is available at : https://doi.org/10.1007/978-3-030-90453-1_12

PERMALINK : https://www.eurecom.fr/publication/6669