用于数字签名的量子令牌

用于数字签名的量子令牌

沙莱夫本大卫1或萨塔斯2

1滑铁卢大学 David R. Cheriton 计算机科学学院
2内盖夫本古里安大学计算机科学系

觉得本文有趣或想讨论? 在SciRate上发表评论或发表评论.

抽象

渔夫钓到一条量子鱼。 “渔夫,放过我吧”,鱼央求道,“我可以满足你三个愿望”。 渔夫同意了。 这条鱼给了渔夫一台量子计算机、三个量子签名令牌和他的经典公钥。 鱼解释说:“要签署你的三个愿望,使用这台量子计算机上的令牌化签名方案,然后向欠我一个人情的国王出示你的有效签名”。
渔夫使用其中一个签名标记在文件“给我一座城堡!”上签名。 并赶往宫殿。 国王使用鱼的公钥执行经典验证算法,由于它是有效的,国王照办了。
渔夫的妻子想用剩下的两个签名信物在十个愿望上签名。 渔夫不想作弊,偷偷开船去见鱼。 “鱼儿,老婆要再签十个心愿”。 但鱼并不担心:“我是跟着前面的故事(格林兄弟的渔夫和他的妻子)学的量子密码学的。” 量子令牌在签名期间被消耗。 你的多项式妻子甚至不能用我给你的三个签名令牌来签署四个愿望。”
“它是如何工作的?” 渔夫想知道。 “你听说过量子货币吗? 这些是可以轻松验证但难以复制的量子态。 这种代币化的量子签名方案扩展了 Aaronson 和 Christiano 的量子货币方案,这就是签名代币不能被复制的原因”。
“你的方案有额外的花哨属性吗?” 渔夫问道。 “是的,该方案还有其他安全保证:可撤销性、可测试性和永久安全性。 此外,如果你在海上并且你的量子电话只有经典接收,你可以使用这个方案将量子货币的价值转移到岸上”,鱼说着游走了。

[嵌入的内容]

►BibTeX数据

►参考

[1] S. 亚伦森。 量子复制保护和量子货币。 在第 24 届 IEEE 计算复杂性年会会议记录中,CCC 2009,法国巴黎,15 年 18 月 2009 日至 229 日,第 242-2009 页,XNUMX 年。
https:///doi.org/10.1109/CCC.2009.42

[2] Y. Aharonov、J. Anandan 和 L. Vaidman。 波函数的意义。 物理。 修订版 A,47:4616–4626,1993 年。
https:/ / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson 和 P. Christiano。 来自隐藏子空间的量子货币。 在第 44 届计算理论研讨会论文集中,STOC 2012,美国纽约州纽约市,19 年 22 月 2012 日至 41 日,第 60-2012 页,XNUMX 年。
https:/ / doi.org/10.1145/ 2213977.2213983

[4] S. Aaronson 和 P. Christiano。 来自隐藏子空间的量子货币。 计算理论,9:349–401, 2013。
https:///doi.org/10.4086/toc.2013.v009a009

[5] R. Amos、M. Georgiou、A. Kiayias 和 M. Zhandry。 混合量子/经典认证的一次性签名和应用。 K. Makarychev、Y. Makarychev、M. Tulsiani、G. Kamath 和 J. Chuzhoy,编辑,年度 ACM SIGACT 计算理论研讨会论文集,第 255-268 页。 ACM,2020,Cryptology ePrint Archive:报告 2020/ 107。
https:/ / doi.org/10.1145/ 3357713.3384304

[6] Y. Aharonov 和 L. Vaidman。 测量单个粒子的薛定谔波。 物理快报 A, 178(1):38 – 42, 1993。
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B.巴拉克。 希望、恐惧和软件混淆。 公社。 美国计算机学会,59(3):88–96, 2016。
https:/ / doi.org/10.1145/ 2757276

[8] CH Bennett、G. Brassard、S. Breidbart 和 S. Wiesner。 量子密码学,或不可伪造的地铁令牌。 在密码学进展中,第 267-275 页。 斯普林格,1983 年。
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky、Z. Brakerski 和 YT Kalai。 建设性的后量子减少。 Y. Dodis 和 T. Shrimpton,编辑,密码学进展 – CRYPTO 2022 – 第 42 届年度国际密码学会议,CRYPTO 2022,美国加利福尼亚州圣巴巴拉,15 年 18 月 2022 日至 13509 日,会议记录,第三部分,讲座第 654 卷计算机科学笔记,第 683-2022 页。 施普林格,XNUMX 年。
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky、R. Canetti、H. Cohn、S. Goldwasser、YT Kalai、O. Paneth 和 A. Rosen。 不可能使用辅助输入或通用模拟器进行混淆。 JA Garay 和 R. Gennaro,编辑,密码学进展 – CRYPTO 2014 – 第 34 届密码学年度会议,美国加利福尼亚州圣巴巴拉,17 年 21 月 2014 日至 8617 日,会议记录,第二部分,计算机科学讲义第 71 卷,第 89-2014 页。 施普林格,XNUMX 年。
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak、O. Goldreich、R. Impagliazzo、S. Rudich、A. Sahai、SP Vadhan 和 K. Yang。 关于混淆程序的(不)可能性。 美国计算机学会杂志,59(2):6,2012 年。
https:/ / doi.org/10.1145/ 2160158.2160159

[12] H. 邦宾。 克利福德盖茨通过代码变形。 新物理学杂志,13(4):043005, 2011。
https:/​/​doi.org/​10.1088/​1367-2630/​13/​4/​043005
http:/​/​stacks.iop.org/​1367-2630/​13/​i=4/​a=043005

[13] G.布拉萨德。 搜索 Quantum 电话簿。 科学, 275(5300):627–628, 1997。
https:/ / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera、O. Sattath 和 U. Shinar。 MAC 的抗噪声量子代币,2021 年。
https:///doi.org/10.48550/ARXIV.2105.05016

[15] D. Boneh 和 M. Zhandry。 量子安全消息验证代码。 由 T. Johansson 和 PQ Nguyen 编辑,Advances in Cryptology – EUROCRYPT 2013,第 32 届密码技术理论和应用国际会议,希腊雅典,26 年 30 月 2013 日至 7881 日。会议记录,计算机讲义第 592 卷科学,第 608-2013 页。 施普林格,XNUMX 年。
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve 和 D. Gottesman。 量子纠错编码的高效计算。 物理。 修订版 A,56:76–82,1997 年 XNUMX 月。
https:/ / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung、M. Georgiou、C. Lai 和 V. Zikas。 带有一次性后门的密码学。 Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/ 352.
https:/ / doi.org/ 10.3390 / cryptography3030022

[18] P.克里斯蒂亚诺。 个人通讯,2015 年。

[19] A. Colagangelo、J. Liu、Q. Liu 和 M. Zhandry。 隐藏的陪集和不可克隆密码学的应用,2021,arXiv:2107.05692。
的arXiv:2107.05692

[20] S. Chakraborty、J. Radhakrishnan 和 N. Raghunathan。 使用少量量子查询减少错误的界限。 在 Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 和 RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, pages 245–256, 2005 会议论文集, pages XNUMX–XNUMX, XNUMX .
https:/ / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti、GN Rothblum 和 M. Varia。 超平面成员的混淆。 载于 D. Micciancio,编辑,密码学理论,第七届密码学理论会议,TCC 7,瑞士苏黎世,2010 年 9 月 11 日至 2010 日。会议记录,计算机科学讲义第 5978 卷,第 72-89 页。 施普林格,2010 年。
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie 和 ME Hellman。 密码学的新方向。 IEEE 跨。 信息论,22(6):644–654, 1976。
https:///doi.org/10.1109/TIT.1976.1055638

[23] YZ Ding 和 MO Rabin。 超级加密和永久安全。 在 H. Alt 和 A. Ferreira,编辑,STACS 2002,第 19 届计算机科学理论方面年度研讨会,安提比斯 - 胡安莱宾,法国,14 年 16 月 2002 日至 2285 日,会议记录,计算机科学讲义第 1 卷,第 26-2002 页。 施普林格,XNUMX 年。
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] E. Farhi、D. Gosset、A. Hassidim、A. Lutomirski、D. Nagaj 和 P. Shor。 哈密​​顿量基态的量子态恢复和单拷贝层析成像。 物理。 Rev. Lett.,105:190503,2010 年 XNUMX 月。
https:/ / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi、D. Gosset、A. Hassidim、A. Lutomirski 和 P. Shor。 来自结的量子货币。 在第三届理论计算机科学会议创新会议记录中,第 3-276 页。 美国计算机学会,289 年。
https:/ / doi.org/10.1145/ 2090236.2090260

[26] D. 加文斯基。 具有经典验证的量子货币。 在 IEEE 第 27 届计算复杂性年会上,第 42-52 页。 IEEE,2012 年。
https:///doi.org/10.1109/CCC.2012.10

[27] S. Goldwasser 和 YT Kalai。 关于使用辅助输入进行混淆的不可能性。 第 46 届年度 IEEE 计算机科学基础研讨会 (FOCS 2005),23 年 25 月 2005 日至 553 日,美国宾夕法尼亚州匹兹堡,会议记录,第 562-2005 页,XNUMX 年。
https:///doi.org/10.1109/SFCS.2005.60

[28] M. Georgiou 和 I. Kerenidis。 量子货币的新结构。 载于 S. Beigi 和 R. König,编辑,第 10 届量子计算、通信和密码学理论会议,TQC 2015,20 年 22 月 2015-44 日,比利时布鲁塞尔,LIPIcs 第 92 卷,第 110-2015 页。 Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik,XNUMX 年。
https:/ / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich。 密码学的基础-卷。 2,基本应用。 剑桥大学出版社,2004年。

[30] M. Grassl、M. Rötteler 和 T. Beth。 用于非量子位量子纠错码的高效量子电路。 诠释。 J. 发现。 电脑。 科学, 14(5):757–776, 2003。
https:/ / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz和Y. Lindell。 《现代密码学简介》,第二版。 CRC出版社,2014年。

[32] NA林奇。 分布式算法。 摩根考夫曼,1996 年。

[33] M. Mosca 和 D. Stebila。 量子硬币,Contemp 第 523 卷。 数学,第 35-47 页。 阿米尔。 数学。 社会科学杂志,2010 年。

[34] MC Pena、RD Díaz、J. Faugère、LH Encinas 和 L. Perret。 Aaronson-Christiano 的量子货币计划的嘈杂版本的非量子密码分析。 IET 信息安全,13(4):362–366, 2019。
https:// / doi.org/ 10.1049/ iet-ifs.2018.5307

[35] MC Pena、J. Faugère 和 L. Perret。 量子货币方案的代数密码分析无噪声案例。 J. Katz,编辑,公钥密码学 – PKC 2015 – 第 18 届 IACR 国际公钥密码学实践和理论会议,美国马里兰州盖瑟斯堡,30 年 1 月 2015 日至 9020 月 194 日,会议记录,第 213 卷讲义在计算机科学中,第 2015-XNUMX 页。 施普林格,XNUMX 年。
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A.普拉萨德。 有限向量空间的子空间计数 — 1. Resonance, 15(11):977–987, 2010。
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski、NY Yao、L. Jiang、MD Lukin 和 JI Cirac。 不可伪造的抗噪声量子令牌。 美国国家科学院院刊,109(40):16079–16082, 2012。
https:/ / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian 和 O. Sattath。 半量子货币。 在第一届 ACM 金融技术进展会议记录中,AFT 1,瑞士苏黎世,2019 年 21 月 23 日至 2019 日,第 132-146 页。 美国计算机学会,2019 年,arXiv:1908.08889。
https:/ / doi.org/10.1145/ 3318041.3355462
的arXiv:1908.08889

[39] R. Radian 和 O. Sattath。 半量子货币。 密码学杂志,35(2),2022 年 1908.08889 月,arXiv:XNUMX。
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
的arXiv:1908.08889

[40] O. 萨塔。 Quantum Prudent Contracts with Applications to Bitcoin, 2022。
https:///doi.org/10.48550/ARXIV.2204.12806

[41] O. 萨塔。 不可克隆的密码学,2022 年。
https:///doi.org/10.48550/ARXIV.2210.14265

[42] O. Shmueli。 经典银行的公钥量子货币。 S. Leonardi 和 A. Gupta 编辑,STOC '22:第 54 届年度 ACM SIGACT 计算理论研讨会,意大利罗马,20 年 24 月 2022 日至 790 日,第 803-2022 页。 美国计算机学会,XNUMX 年。
https:/ / doi.org/10.1145/ 3519935.3519952

[43] O. Shmueli。 半量子标记化签名。 Y. Dodis 和 T. Shrimpton,编辑,密码学进展 – CRYPTO 2022 – 第 42 届年度国际密码学会议,CRYPTO 2022,美国加利福尼亚州圣巴巴拉,15 年 18 月 2022 日至 13507 日,会议记录,第一部分,第 296 卷讲座计算机科学笔记,第 319-2022 页。 施普林格,XNUMX 年。
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi、LK Grover 和 A. Patel。 一种新的定点量子搜索算法。 量子信息与计算,6(6):483–494, 2006。
http://portal.acm.org/citation.cfm?id=2011693

[45] Y. Tokunaga、T. Okamoto 和 N. Imoto。 匿名量子现金。 在 ERATO 量子信息科学会议上,2003 年。

[46] D. 不鲁。 可撤销的量子定时释放加密。 美国计算机学会杂志,62(6):49:1–49:76,2015 年。
https:/ / doi.org/10.1145/ 2817206

[47] D. 不鲁。 永恒的多方计算。 J. Cryptol., 31(4):965–1011, 2018。
https:/ / doi.org/ 10.1007 / s00145-018-9278-z

[48] S.维斯纳。 共轭编码。 ACM Sigact新闻,15(1):78-88,1983年。
https:/ / doi.org/10.1145/ 1008908.1008920

[49] WK Wootters 和 WH Zurek。 无法克隆单个量子。 自然,299(5886):802–803, 1982。

[50] M. Zhong、MP Hedges、RL Ahlefeldt、JG Bartholomew、SE Beavan、SM Wittig、JJ Longdell 和 MJ Sellars。 具有 517 小时相干时间的固体中可光学寻址的核自旋。 自然,7533(177):180–2015,XNUMX 年 XNUMX 月。
https:/ / doi.org/10.1038/nature14025

[51] M. 赞德里。 量子闪电永远不会两次袭击同一个州,2017 年,arXiv:1711.02276。
的arXiv:1711.02276

[52] M. 赞德里。 量子闪电永远不会两次袭击同一个州。 或者:来自加密假设的量子货币。 J. Crypto., 34(1):6, 2021, arXiv: 1711.02276。
https:///doi.org/10.1007/s00145-020-09372-x
的arXiv:1711.02276

被引用

[1] S. Pirandola、UL Andersen、L. Banchi、M. Berta、D. Bunandar、R. Colbeck、D. Englund、T. Gehring、C. Lupo、C. Ottaviani、JL Pereira、M. Razavi、J . Shamsul Shaari、M. Tomamichel、VC Usenko、G. Vallone、P. Villoresi 和 P. Wallden,“量子密码学的进展”, 光学与光子学进展 12 4, 1012 (2020).

[2] Douglas Scott,“科学恶搞、物理恶作剧和天文滑稽动作”, 的arXiv:2103.17057.

[3] Thomas Vidick和Tina Zhang,“量子知识的经典证明”, 的arXiv:2005.01691.

[4] 或 Sattath,“Quantum Prudent Contracts with Applications to Bitcoin”, 的arXiv:2204.12806.

[5] Scott Aaronson、Jiahui Liu、Qipeng Liu、Mark Zhandry 和 Ruizhe Zhang,“量子拷贝保护的新方法”, 的arXiv:2004.09674.

[6] Roy Radian 和 Or Sattath,“半量子货币”, 的arXiv:1908.08889.

[7] Andrea Coladangelo、Shafi Goldwasser 和 Umesh Vazirani,“量子世界中的可否认加密”, 的arXiv:2112.14988.

[8] Prabhanjan Ananth 和 Rolando L. La Placa,“安全软件租赁”, 的arXiv:2005.05289.

[9] Or Sattath 和 Shai Wyborski,“来自量子复制保护的不可克隆的解密器”, 的arXiv:2203.05866.

[10] Andrea Colagangelo 和 Or Sattath,“区块链可扩展性问题的量子货币解决方案”, 的arXiv:2002.11998.

[11] Jiahui Liu、Hart Montgomery 和 Mark Zhandry,“另一轮突破和制造量子货币:如何不从格子等构建它”, 的arXiv:2211.11994.

[12] Andrea Coladangelo、Jiahui Liu、Qipeng Liu 和 Mark Zhandry,“隐藏陪集及其在不可克隆密码学中的应用”, 的arXiv:2107.05692.

[13] 或 Sattath,“不可克隆的密码学”, 的arXiv:2210.14265.

[14] Amit Behera 和 Or Sattath,“Almost Public Quantum Coins”, 的arXiv:2002.12438.

[15] Anne Broadbent、Sevag Gharibian 和 Hong-Sheng Zhou,“从无状态硬件走向量子一次性存储器”, 的arXiv:1810.05226.

[16] Niraj Kumar,“具有经典验证的实际可行的稳健量子货币”, 的arXiv:1908.04114.

[17] Or Sattath 和 Uriel Shinar,“量子健忘症留下密码学纪念品:关于量子怀疑主义的注释”, 的arXiv:2212.08750.

[18] Nir ​​Bitansky、Zvika Brakerski 和 Yael Tauman Kalai,“建设性后量子缩减”, 的arXiv:2203.02314.

以上引用来自 SAO / NASA广告 (最近成功更新为2023-01-20 14:01:05)。 该列表可能不完整,因为并非所有发布者都提供合适且完整的引用数据。

On Crossref的引用服务 找不到有关引用作品的数据(上一次尝试2023-01-20 14:01:00)。

时间戳记:

更多来自 量子杂志