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}$中的有效方案。

0
下载
关闭预览

相关内容

【Nature machine intelligence】闭型连续时间神经网络
专知会员服务
29+阅读 · 2022年11月17日
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
76+阅读 · 2021年3月16日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】用TensorFlow实现LSTM社交对话股市情感分析
机器学习研究会
11+阅读 · 2018年1月14日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年6月13日
Competitive Channel-Capacity
Arxiv
0+阅读 · 2023年6月13日
Arxiv
0+阅读 · 2023年6月13日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】用TensorFlow实现LSTM社交对话股市情感分析
机器学习研究会
11+阅读 · 2018年1月14日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员