Inequalities
Inequalities
复制标题
DOI：
10.1090/chel/351/04
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Guozhen Lu;Qiaohua Yang
中科院分区：
文献类型：
--
作者：
Guozhen Lu;Qiaohua Yang
对于大多数访问结构而言，已知的秘密共享方案效率不高；即使是对于一位的秘密，这些方案中份额的长度也是\(2^{O(n)}\)，其中\(n\)是访问结构中的参与者数量。改进这些方案或者证明它们无法被改进是一个长期未解决的问题。已知的最佳下界是由齐尔马兹（Csirmaz，《密码学杂志》97年）给出的，他证明了存在具有\(n\)个参与者的访问结构，使得至少一方的份额大小是秘密大小的\(n / \log n\)倍。齐尔马兹的证明使用了香农信息不等式，在齐尔马兹发表其结果时，这是已知的唯一信息不等式。从负面来看，齐尔马兹证明了仅使用香农信息不等式无法证明份额大小的\(\omega(n)\)下界。在过去十年中，一系列非香农信息不等式被发现。这带来了一种希望，即这些不等式有助于将下界改进到超过\(n\)。然而，在本文中我们表明，迄今为止所有已知的不等式都无法证明份额大小的\(\omega(n)\)下界。
. The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2 O ( n ) , where n is the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz (J. Cryptology 97), who proved that there exist access structures with n participants such that the size of the share of at least one party is n/ log n times the secret size. Csirmaz’s proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω ( n ) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. This raises the hope that these inequalities can help in improving the lower bounds beyond n . However, in this paper we show that all the inequalities known to date cannot prove a lower bound of ω ( n ) on the share size.