Visible to the public Secret Sharing Schemes with Hidden Sets

TitleSecret Sharing Schemes with Hidden Sets
Publication TypeConference Paper
Year of Publication2018
Authorsde Souza, Rick Lopes, Vigil, Martín, Custódio, Ricardo, Caullery, Florian, Moura, Lucia, Panario, Daniel
Conference Name2018 IEEE Symposium on Computers and Communications (ISCC)
Date Publishedjun
KeywordsAnalytical models, cloud providers, Computational modeling, Computers, cryptographic keys, cryptographic protocols, cryptography, detect hidden sets, Human Behavior, human factors, interpolation, malicious dealer, Metrics, multifactor authentication, polynomial, polynomials, Protocols, pubcrawl, resilience, Resiliency, set theory, Shamirs secret sharing scheme, telecommunication security, uniform distribution
AbstractShamir's Secret Sharing Scheme is well established and widely used. It allows a so-called Dealer to split and share a secret k among n Participants such that at least t shares are needed to reconstruct k, where 0 \textbackslashtextbackslashtextless; t ≤ n. Nothing about the secret can be learned from less than t shares. To split secret k, the Dealer generates a polynomial f, whose independent term is k and the coefficients are randomly selected using a uniform distribution. A share is a pair (x, f(x)) where x is also chosen randomly using a uniform distribution. This scheme is useful, for example, to distribute cryptographic keys among different cloud providers and to create multi-factor authentication. The security of Shamir's Secret Sharing Scheme is usually analyzed using a threat model where the Dealer is trusted to split and share secrets as described above. In this paper, we demonstrate that there exists a different threat model where a malicious Dealer can compute shares such that a subset of less than t shares is allowed to reconstruct the secret. We refer to such subsets as hidden sets. We formally define hidden sets and prove lower bounds on the number of possible hidden sets for polynomials of degree t - 1. Yet, we show how to detect hidden sets given a set of n shares and describe how to create hidden sets while sharing a secret using a modification of Shamir's scheme.
Citation Keyde_souza_secret_2018