Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties so that certain subsets can reconstruct the secret, while unauthorized subsets obtain no information. While QSS was introduced over twenty years ago, previous works focused only on existence of perfectly secure schemes, and the share size of the known schemes is exponential even for access structures computed by polynomial size monotone circuits. This stands in contrast to the classical case, where efficient computationally-secure schemes have been long known for all access structures in $\mathsf{monotone~P}$, and one can even obtain shares which are much shorter than the secret which is impossible with perfect security. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time QSS schemes under standard assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS required exponential share size. We also construct QSS schemes for which the size of the shares is significantly smaller than the size of the secret. As in the classical case, this is impossible with perfect security. We also use our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of access structures to $1.5^{n+o(n)}$, improving upon best known schemes and matching the best known result for general access structures in the classical case. Finally, we show construct efficient schemes for all access structures in $\mathsf{P}$ and $\mathsf{NP}$ when the quantum secret sharing scheme is given multiple of copies of the secret.
翻译:量子秘密共享(QSS)允许经销商将秘密量子状态分配给一组参与者,以便某些子集可以重建秘密,而未经授权的子集则无法获取信息。尽管QSS引入了20多年,但以前的作品仅关注完全安全计划的存在性,并且已知方案的共享大小对于通过多项式大小的单调电路计算的访问结构而言呈指数级增长。这与经典情况相反,在经典情况下,所有访问结构的有效计算安全方案已经为$\mathsf{monotone~P}$中的所有访问结构建立了很长时间,并且甚至可以获得比秘密短得多的份额,这在完全安全性方面是不可能的。在这项工作中,我们开始研究计算安全QSS,并表明计算假设在构建QSS方案方面有很大帮助。我们提出了一个简单的编译器并使用它来获得多种结果:我们构建了使用标准假设的多项式时间QSS方案,适用于丰富的访问结构类别。这包括许多访问结构,其中以前的QSS结果需要指数级份额大小。我们还构建了QSS方案,其份额大小明显小于秘密大小。与完全安全性相比,在经典情况下,这是不可能的。我们还使用我们的编译器获得了超出计算QSS的结果。在信息理论环境中,我们将完美QSS方案的份额大小提高为$1.5^{n+o(n)}$,为较大的访问结构类别提高了共享大小,从而优于已知的最佳方案,并与经典情况下一般访问结构的已知最佳结果相匹配。 最后,我们在给定量子秘密共享方案的多个副本时,构建了所有访问结构在$\mathsf{P}$和$\mathsf{NP}$中的有效方案。