Systematic methods reveal secrets leaked by partial data in secret sharing
Systematic Derivation of Leakage in Massey Secret Sharing Schemes
Cryptography and Security
Summary
Secret sharing splits a secret into parts to keep it safe, but sometimes small bits of information about these parts can reveal the secret. The authors study ways to recover the secret from limited information using mathematical methods called linear exact repair schemes (LERSs). They build on earlier work and create new methods to find and understand these partial-leakage patterns, especially in certain types of codes used for secret sharing. Their systematic computational approach finds new examples of these schemes beyond what was known before.
What this means in practice
- •For cryptographic system designers: Identify vulnerabilities in secret sharing schemes by analyzing possible partial information leaks using new computational methods.
- •For data storage architects: Design storage and repair systems that avoid weak points where partial data could reveal stored secrets.
Authors
Nadja Aoutouf, Daniel Augot
Abstract
Leakage attacks on secret sharing schemes can be based on the exploitation of partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) allow the recovery of a codeword symbol from limited information obtained from the remaining symbols. When applied to code-based secret sharing schemes, such repair schemes can be interpreted as recovering the secret from partial information about the shares, expressed in terms of subfield symbols. Guruswami and Wootters introduced the first explicit constructions of LERSs for low-rate Reed--Solomon codes that is optimal in terms of bandwidth. In this work, we first investigate the construction and algebraic properties of LERSs, building on the Guruswami-Wootters construction. We derive new explicit repair schemes from their construction and establish structural properties of the resulting schemes. Second, we further develop a systematic computational approach based on a Gr{ö}bner bases approach to identify leakage functions associated with LERSs for arbitrary linear codes. This approach enables us to investigate the existence and structural properties of LERSs across different code families and parameter ranges. We first applied our method to Reed-Solomon codes, which gave as further insights into the algebraic structure of LERSs. Moreover, by applying our method to generalized Reed-Muller and Tamo-Barg codes, we identify several LERSs that, to the best of our knowledge, have not previously been described in the literature.