Paper 2026/2008

New Imperfect High Threshold and Slice Secret Sharing Schemes

Abstract

We present new constructions of (n - t + 1)-out-of-n threshold and slice secret sharing schemes for short secrets with imperfect secrecy for constant t and growing n. Our main results are 1. an ε-differentially secret, (n - t + 1)-out-of-n bit secret sharing scheme with share alphabet size Õ_t(1/ε^2). In contrast, perfect secrecy requires share alphabet size n - t + 1 (Bogdanov, Guo, and Komargodski, ToC 2020). For t > 3, the security of our scheme relies on a conjecture about factorizations of univariate polynomials in finite fields. 2. an ε-statistically secret bit secret sharing scheme for every (n-2)-out-of-n slice with share size O(log n log 1/ε). Previous constructions with comparable parameters achieved only computational security (Beimel, Farràs, Lasri, and Nir, TCC 2024). Variants of our first construction produce plain and anonymous (n-1)-out-of-n weak bit secret sharing schemes with optimal share size. We discuss the relevance of these schemes to secret sharing duality.