Paper 2020/483 Original: eprint.iacr.org/2020/483 ↗
On Ideal and Weakly-Ideal Access Structures
Abstract
For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. We consider a weaker statement in this paper asking if: every ideal access structure admits an ideal perfect group-characterizable (GC) SSS. Since the class of GC SSSs is known to include the multi-linear ones (as well as several classes of non-linear schemes), it might turn out that the second statement is not only true but also easier to tackle. Unfortunately, our understanding of GC SSSs is still too basic to tackle the weaker statement. As a first attempt, it is natural to ask if every ideal perfect SSS is equivalent to some GC scheme. The main contribution of this paper is to construct counterexamples using tools from theory of Latin squares and some recent results developed by the present authors for studying GC SSSs.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2020-04-28: last updated
- 2020-04-28: published
- Short URL
- https://ia.cr/2020/483
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2020/483,
author = {Reza Kaboli and Shahram Khazaei and Maghsoud Parviz},
title = {On Ideal and Weakly-Ideal Access Structures},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/483},
year = {2020},
url = {https://eprint.iacr.org/2020/483}
}