Cryptology ePrint Archive: Report 2020/483

On Ideal and Weakly-Ideal Access Structures

Reza Kaboli and Shahram Khazaei and Maghsoud Parviz

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.

Category / Keywords: foundations / ideal secret sharing schemes, linear secret sharing, group-characterizable secret sharing, ideal access structure

Date: received 24 Apr 2020

Contact author: shahram khazaei at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200428:121348 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]