Back to Search
Start Over
The Size of a Share Must Be Large
- Source :
- Journal of Cryptology. 10:223-231
- Publication Year :
- 1997
- Publisher :
- Springer Science and Business Media LLC, 1997.
-
Abstract
- A secret sharing scheme permits a secret to be shared among participants of an n-element group in such a way that only qualified subsets of participants can recover the secret. If any nonqualified subset has absolutely no information on the secret, then the scheme is called perfect. The share in a scheme is the information that a participant must remember. In [3] it was proved that for a certain access structure any perfect secret sharing scheme must give some participant a share which is at least 50\percent larger than the secret size. We prove that for each n there exists an access structure on n participants so that any perfect sharing scheme must give some participant a share which is at least about $n/\log n$ times the secret size.^1 We also show that the best possible result achievable by the information-theoretic method used here is n times the secret size. ^1 All logarithms in this paper are of base 2.
- Subjects :
- TheoryofComputation_MISCELLANEOUS
Discrete mathematics
Homomorphic secret sharing
Theoretical computer science
Applied Mathematics
Key distribution
Shared secret
Secret sharing
Computer Science Applications
Shamir's Secret Sharing
Secure multi-party computation
Verifiable secret sharing
Software
Mathematics
Access structure
Subjects
Details
- ISSN :
- 14321378 and 09332790
- Volume :
- 10
- Database :
- OpenAIRE
- Journal :
- Journal of Cryptology
- Accession number :
- edsair.doi...........255c556b8038d574e2129e09bf444f66