10th WorldS4 2026

Authors - Hiep. L. Thi
Abstract - Secret-sharing is a fundamental cryptographic primitive that enables the secure distribution of sensitive information among multiple participants while guaranteeing correctness and privacy. In this paper, we present a comprehensive study of secret-sharing schemes from both information-theoretic and computational perspectives. We begin by reviewing classical threshold constructions, including Shamir’s polynomial-based scheme and its algebraic interpretation via linear codes. The notions of correctness and perfect secrecy are formalized using entropy, and the role of access structures in characterizing authorized subsets is emphasized. We then examine ideal secret-sharing schemes, where each share has the same size as the secret, and highlight their deep connection with representable matroids. In particular, we discuss how matroid representability over finite fields characterizes the existence of ideal linear secret-sharing schemes, thereby linking combinatorial independence with cryptographic access control. Additional structural results concerning field dependence, minimal non-ideal access structures, and connections to linear codes are also addressed. The paper further explores computational secret-sharing, which relaxes perfect privacy to computational indistinguishability under standard cryptographic assumptions. We describe constructions based on encryption and threshold key sharing, as well as realizations derived from monotone circuits. A central theme is the separation between information-theoretic and computational models: while certain access structures require exponential share size in the information-theoretic setting, they admit polynomial-size shares under computational assumptions. Finally, we discuss algebraic methods underlying secret-sharing, including polynomial interpolation and linear coding techniques, and illustrate how these tools support efficient distributed protocols such as secure multiparty computation and threshold cryptography. Overall, the paper provides a unified treatment of structural, algebraic, and computational aspects of secret-sharing, highlighting its foundational role in modern distributed cryptographic systems.