Secret Sharing with Binary Shares
Secret Sharing with Binary Shares
复制标题
与二进制共享的秘密共享
DOI：
10.4230/lipics.itcs.2019.53
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Huaxiong Wang
中科院分区：
文献类型：
--
作者：
Fuchun Lin;Mahdi Cheraghchi;V. Guruswami;R. Safavi;Huaxiong Wang
Shamir的著名的秘密共享方案提供了一种有效的方法编码的秘密任意长度$\ell$之间的任何$N \leq 2 ^\ell $的球员，这样的阈值参数$t$，（i）的知识任何$t$份额不透露任何信息的秘密，（ii）任何选择的$t+1$份额完全揭示了秘密。众所周知，任何这样的门限秘密共享方案都需要长度为$\ell$的份额，在这个意义上，Shamir的方案是最优的。更一般的概念斜坡计划需要重建的秘密从任何$t+g$份额，为一个正整数的间隙参数$g$。斜坡秘密共享方案需要长度为$\ell/g$的份额。除了与秘密长度$\ell$相关的上界之外，Ramp方案的共享长度不能低于仅取决于差距比$g/N$的量。在这项工作中，我们研究的极端情况下的比特长的股份和任意小的间隙比$g/N$，标准的斜坡秘密共享变得不可能的秘密共享。然而，我们发现，一个稍微放松，但同样有效的概念的秘密，和可忽略不计的重建错误概率的语义安全，消除了不可能性。此外，我们提供了明确的结构，这样的计划。我们放松的后果之一是，与具有完美保密性的标准斜坡方案不同，自适应和非自适应对手需要不同的分析和构造。对于非自适应的对手，我们明确地构建秘密共享方案，提供对任何$\tau$分数的观察到的份额，并从任何$\rho$分数的份额重建，为任何选择0\leq \tau < \rho \leq 1$。我们的构造达到了秘密长度$N（\rho-\tau-o（1））$，我们证明了这是最优的。对于自适应对手，我们构建显式的计划达到秘密长度$\Omega（N（\rho-\tau））$。
Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length $\ell$ among any $N \leq 2^\ell$ players such that for a threshold parameter $t$, (i) the knowledge of any $t$ shares does not reveal any information about the secret and, (ii) any choice of $t+1$ shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length $\ell$, and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any $t+g$ shares, for a positive integer gap parameter $g$. Ramp secret sharing scheme necessarily requires shares of length $\ell/g$. Other than the bound related to secret length $\ell$, the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio $g/N$. In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio $g/N$, where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any $\tau$ fraction of observed shares, and reconstruction from any $\rho$ fraction of shares, for any choices of $0 \leq \tau < \rho \leq 1$. Our construction achieves secret length $N(\rho-\tau-o(1))$, which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length $\Omega(N(\rho-\tau))$.
影响因子：
2.5
作者：
Guruswami, Venkatesan;Smith, Adam
通讯作者：
Smith, Adam