Mã thông báo lượng tử cho chữ ký số

Mã thông báo lượng tử cho chữ ký số

Shalev Ben-David1Hoặc Sattath2

1Đại học Waterloo, Trường Khoa học Máy tính David R. Cheriton
2Đại học Ben-Gurion của Negev, Khoa Khoa học Máy tính

Tìm bài báo này thú vị hay muốn thảo luận? Scite hoặc để lại nhận xét về SciRate.

Tóm tắt

Người đánh cá đã bắt được một con cá lượng tử. “Người đánh cá, hãy để tôi đi”, con cá cầu xin, “và tôi sẽ ban cho bạn ba điều ước”. Người đánh cá đồng ý. Con cá đã đưa cho người đánh cá một chiếc máy tính lượng tử, ba mã thông báo ký lượng tử và khóa công khai cổ điển của anh ta. Con cá giải thích: “để ký ba điều ước của bạn, hãy sử dụng sơ đồ chữ ký mã hóa trên máy tính lượng tử này, sau đó đưa chữ ký hợp lệ của bạn cho nhà vua, người nợ tôi một ân huệ”.
Người đánh cá đã sử dụng một trong những thẻ ký tên để ký vào văn bản “cho tôi một lâu đài!” và lao thẳng vào cung điện. Nhà vua đã thực hiện thuật toán xác minh cổ điển bằng cách sử dụng khóa chung của con cá và vì nó hợp lệ nên nhà vua đã tuân theo.
Vợ của người đánh cá muốn ký mười điều ước bằng hai tấm thẻ ký tên còn lại của họ. Người đánh cá không muốn lừa dối nên đã bí mật chèo thuyền đến gặp cá. “Cá ơi, vợ tôi muốn ký thêm mười điều ước nữa”. Nhưng con cá không hề lo lắng: “Tôi đã học được mật mã lượng tử theo câu chuyện trước đó (Người đánh cá và vợ của anh em nhà Grimm). Mã thông báo lượng tử được tiêu thụ trong quá trình ký kết. Người vợ đa thức của bạn thậm chí không thể ký bốn điều ước bằng cách sử dụng ba biểu tượng ký hiệu mà tôi đã đưa cho bạn”.
"Làm thế nào nó hoạt động?" người đánh cá thắc mắc. “Bạn đã nghe nói về tiền lượng tử chưa? Đây là những trạng thái lượng tử có thể dễ dàng xác minh nhưng khó sao chép. Sơ đồ chữ ký lượng tử được mã hóa này mở rộng sơ đồ tiền lượng tử của Aaronson và Christiano, đó là lý do tại sao các mã thông báo ký không thể được sao chép”.
“Kế hoạch của bạn có thêm thuộc tính ưa thích nào không?” người đánh cá hỏi. “Đúng, chương trình này có các đảm bảo an ninh khác: khả năng thu hồi, khả năng kiểm tra và bảo mật vĩnh viễn. Hơn nữa, nếu bạn đang ở trên biển và điện thoại lượng tử của bạn chỉ có khả năng thu sóng cổ điển, bạn có thể sử dụng sơ đồ này để chuyển giá trị của tiền lượng tử vào bờ”, con cá nói và bơi đi.

[Nhúng nội dung]

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] S. Aaronson. Bảo vệ sao chép lượng tử và tiền lượng tử. Trong Kỷ yếu của Hội nghị thường niên lần thứ 24 của IEEE về độ phức tạp tính toán, CCC 2009, Paris, Pháp, 15-18 tháng 2009 năm 229, trang 242–2009, XNUMX.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan và L. Vaidman. Ý nghĩa của hàm sóng Vật lý. Mục sư A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson và P. Christiano. Tiền lượng tử từ các không gian con ẩn. Trong Kỷ yếu của Hội nghị chuyên đề lần thứ 44 về Lý thuyết máy tính, STOC 2012, New York, NY, Hoa Kỳ, ngày 19 – 22 tháng 2012 năm 41, trang 60–2012, XNUMX.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson và P. Christiano. Tiền lượng tử từ các không gian con ẩn. Lý thuyết máy tính, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias và M. Zhandry. Chữ ký một lần và ứng dụng để xác thực lượng tử/cổ điển lai. Trong K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath và J. Chuzhoy, các biên tập viên, Kỷ yếu của Hội nghị chuyên đề ACM SIGACT thường niên về Lý thuyết máy tính, trang 255–268. ACM, 2020, Lưu trữ ePrint mật mã: Báo cáo 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov và L. Vaidman. Đo sóng Schrödinger của một hạt đơn lẻ. Vật lý Thư A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Hy vọng, nỗi sợ hãi và sự xáo trộn phần mềm. Cộng đồng. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart và S. Wiesner. Mật mã lượng tử hoặc mã thông báo tàu điện ngầm không thể giả mạo. Trong Những tiến bộ về mật mã học, trang 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski và YT Kalai. Giảm thiểu sau lượng tử mang tính xây dựng. Trong Y. Dodis và T. Shrimpton, biên tập viên, Những tiến bộ trong mật mã học – CRYPTO 2022 – Hội nghị mật mã quốc tế thường niên lần thứ 42, CRYPTO 2022, Santa Barbara, CA, Hoa Kỳ, ngày 15-18 tháng 2022 năm 13509, Kỷ yếu, Phần III, tập 654 của Bài giảng Ghi chú trong Khoa học Máy tính, trang 683–2022. Mùa xuân, 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 và A. Rosen. Không thể làm xáo trộn với Đầu vào phụ trợ hoặc Bộ mô phỏng chung. Trong JA Garay và R. Gennaro, các biên tập viên, Những tiến bộ trong Mật mã học – CRYPTO 2014 – Hội nghị Mật mã học thường niên lần thứ 34, Santa Barbara, CA, Hoa Kỳ, ngày 17-21 tháng 2014 năm 8617, Kỷ yếu, Phần II, tập 71 của Ghi chú Bài giảng về Khoa học Máy tính, trang 89–2014. Mùa xuân, 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 và K. Yang. Về khả năng (không) làm xáo trộn các chương trình. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Cổng Clifford bằng mã biến dạng. Tạp chí Vật lý mới, 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. Đồng thau. Tìm kiếm một danh bạ điện thoại lượng tử. Khoa học, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / khoa học.275.5300.627

[14] A. Behera, O. Sattath và U. Shinar. Mã thông báo lượng tử có khả năng chịu tiếng ồn cho MAC, 2021.
https: / / doi.org/ 10.48550 / ARXIV.2105.05016

[15] D. Boneh và M. Zhandry. Mã xác thực tin nhắn bảo mật lượng tử. Trong T. Johansson và PQ Nguyen, biên tập viên, Những tiến bộ trong mật mã học – EUROCRYPT 2013, Hội nghị quốc tế thường niên lần thứ 32 về lý thuyết và ứng dụng của kỹ thuật mật mã, Athens, Hy Lạp, ngày 26-30 tháng 2013 năm 7881. Kỷ yếu, tập 592 của Ghi chú bài giảng trong máy tính Khoa học, trang 608–2013. Mùa xuân, XNUMX.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve và D. Gottesman. Tính toán hiệu quả các mã hóa để sửa lỗi lượng tử. Vật lý. Mục sư A, 56:76–82, tháng 1997 năm XNUMX.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai và V.Zikas. Mật mã với các cửa hậu dùng một lần. Cryptogr., 3(3):22, 2019, Lưu trữ ePrint mật mã: Báo cáo 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P. Christiano. Giao tiếp cá nhân, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu và M. Zhandry. Bộ đệm ẩn và ứng dụng cho mật mã không thể sao chép, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan và N. Raghunathan. Giới hạn để giảm lỗi với một số truy vấn lượng tử. Trong Xấp xỉ, Ngẫu nhiên hóa và Tối ưu hóa Tổ hợp, Thuật toán và Kỹ thuật, Hội thảo quốc tế lần thứ 8 về Thuật toán xấp xỉ cho các vấn đề tối ưu hóa tổ hợp, APPROX 2005 và RANDOM 2005, Berkeley, CA, USA, ngày 22-24 tháng 2005 năm 245, Kỷ yếu, trang 256–2005, XNUMX .
https: / / doi.org/ 10.1007 / IDIA11538462_21

[21] R. Canetti, GN Rothblum và M. Varia. Sự xáo trộn của tư cách thành viên siêu máy bay. Trong D. Micciancio, biên tập viên, Lý thuyết mật mã, Hội nghị lý thuyết mật mã lần thứ 7, TCC 2010, Zurich, Thụy Sĩ, ngày 9-11 tháng 2010 năm 5978. Kỷ yếu, tập 72 của Ghi chú bài giảng về Khoa học máy tính, trang 89–2010. Mùa xuân, XNUMX.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie và ME Hellman. Những hướng đi mới trong mật mã học. IEEE Trans. Lý thuyết Thông tin, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding và MO Rabin. Siêu mã hóa và bảo mật vĩnh viễn. Trong H. Alt và A. Ferreira, biên tập viên, STACS 2002, Hội nghị chuyên đề thường niên lần thứ 19 về các khía cạnh lý thuyết của khoa học máy tính, Antibes – Juan les Pins, Pháp, 14-16 tháng 2002 năm 2285, Kỷ yếu, tập 1 của Ghi chú Bài giảng về Khoa học Máy tính, trang 26–2002. Springer, XNUMX.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, D. Nagaj và P. Shor. Phục hồi trạng thái lượng tử và chụp cắt lớp một bản sao cho các trạng thái cơ bản của người Hamilton. Vật lý. Mục sư Lett., 105:190503, tháng 2010 năm XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski và P. Shor. Tiền lượng tử từ nút thắt. Trong Kỷ yếu của Hội nghị Khoa học Máy tính Lý thuyết về Đổi mới lần thứ 3, trang 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinsky. Tiền lượng tử với xác minh cổ điển. Trong Hội nghị thường niên lần thứ 27 của IEEE về độ phức tạp tính toán, trang 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser và YT Kalai. Về việc không thể làm xáo trộn với đầu vào phụ trợ. Trong Hội nghị chuyên đề thường niên lần thứ 46 của IEEE về Cơ sở khoa học máy tính (FOCS 2005), 23-25 ​​tháng 2005 năm 553, Pittsburgh, PA, Hoa Kỳ, Kỷ yếu, trang 562–2005, XNUMX.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou và tôi. Kerenidis. Công trình mới cho tiền lượng tử. Trong S. Beigi và R. König, biên tập viên, Hội nghị lần thứ 10 về Lý thuyết tính toán lượng tử, truyền thông và mật mã, TQC 2015, ngày 20-22 tháng 2015 năm 44, Brussels, Bỉ, tập 92 của LIPIcs, trang 110–2015. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, XNUMX.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich. Cơ sở của Mật mã học - Tập. 2, Ứng dụng cơ bản. Nhà xuất bản Đại học Cambridge, 2004.

[30] M. Grassl, M. Rötteler và T. Beth. Mạch lượng tử hiệu quả cho mã sửa lỗi lượng tử không phải Qubit. Int. J. Đã tìm thấy. Máy tính. Khoa học, 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz và Y. Lindell. Giới thiệu về Mật mã học hiện đại, Phiên bản thứ hai. Nhà xuất bản CRC, 2014.

[32] NA Lynch. Thuật toán phân tán. Morgan Kaufmann, 1996.

[33] M. Mosca và D. Stebila. Đồng tiền lượng tử, tập 523 của Contemp. Toán., trang 35–47. Amer. Toán học. Sóc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas và L. Perret. Phân tích mật mã phi lượng tử của Phiên bản ồn ào của Kế hoạch tiền lượng tử của Aaronson-Christiano. Bảo mật thông tin IET, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère và L. Perret. Phân tích mật mã đại số của một sơ đồ tiền lượng tử Trường hợp không có tiếng ồn. Trong J. Katz, biên tập viên, Mật mã khóa công khai – PKC 2015 – Hội nghị quốc tế IACR lần thứ 18 về thực hành và lý thuyết về mật mã khóa công khai, Gaithersburg, MD, Hoa Kỳ, ngày 30 tháng 1 - ngày 2015 tháng 9020 năm 194, Kỷ yếu, tập 213 của Ghi chú bài giảng trong Khoa học Máy tính, trang 2015–XNUMX. Mùa xuân, XNUMX.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Đếm các không gian con của không gian vectơ hữu hạn — 1. Cộng hưởng, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, NY Yao, L. Jiang, MD Lukin và JI Cirac. Mã thông báo lượng tử có khả năng chịu tiếng ồn không thể tha thứ. Kỷ yếu của Viện Hàn lâm Khoa học Quốc gia, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian và O. Sattath. Tiền bán lượng tử. Trong Kỷ yếu của Hội nghị ACM lần thứ nhất về những tiến bộ trong công nghệ tài chính, AFT 1, Zurich, Thụy Sĩ, ngày 2019-21 tháng 23 năm 2019, trang 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian và O. Sattath. Tiền bán lượng tử. Tạp chí Mật mã học, 35(2), tháng 2022 năm 1908.08889, arXiv: XNUMX.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[40] O. Sattath. Hợp đồng thận trọng lượng tử với các ứng dụng cho Bitcoin, năm 2022.
https: / / doi.org/ 10.48550 / ARXIV.2204.12806

[41] O. Sattath. Mật mã không thể sao chép, 2022.
https: / / doi.org/ 10.48550 / ARXIV.2210.14265

[42] O. Shmueli. Tiền lượng tử khóa công khai với một ngân hàng cổ điển. Trong S. Leonardi và A. Gupta, các biên tập viên, STOC '22: Hội nghị chuyên đề ACM SIGACT thường niên lần thứ 54 về Lý thuyết máy tính, Rome, Ý, ngày 20 – 24 tháng 2022 năm 790, trang 803–2022. ACM, XNUMX.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Chữ ký mã hóa bán lượng tử. Trong Y. Dodis và T. Shrimpton, biên tập viên, Những tiến bộ trong mật mã học – CRYPTO 2022 – Hội nghị mật mã quốc tế thường niên lần thứ 42, CRYPTO 2022, Santa Barbara, CA, Hoa Kỳ, ngày 15-18 tháng 2022 năm 13507, Kỷ yếu, Phần I, tập 296 của Bài giảng Ghi chú trong Khoa học Máy tính, trang 319–2022. Mùa xuân, XNUMX.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover và A. Patel. Một thuật toán mới cho tìm kiếm lượng tử điểm cố định Thông tin & Tính toán Lượng tử, 6(6):483–494, 2006.
http://​/​portal.acm.org/​cite.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto và N. Imoto. Tiền lượng tử ẩn danh. Trong Hội nghị ERATO về Khoa học Thông tin Lượng tử, 2003.

[46] D. Unruh. Mã hóa phát hành theo thời gian lượng tử có thể hủy bỏ. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D. Unruh. Tính toán đa bên vĩnh viễn. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[48] S. Wiesner. mã hóa liên hợp. ACM Sigact News, 15(1):78–88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[49] WK Wootters và WH Zurek. Một lượng tử đơn lẻ không thể được nhân bản. Thiên nhiên, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell và MJ Sellars. Các spin hạt nhân có thể định địa chỉ về mặt quang học trong một chất rắn có thời gian kết hợp sáu giờ. Thiên nhiên, 517(7533):177–180, tháng 2015 năm XNUMX.
https: / / doi.org/ 10.1038 / thiên nhiên14025

[51] M. Zhandry. Sét lượng tử không bao giờ tấn công cùng một trạng thái hai lần, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Sét lượng tử không bao giờ tấn công cùng một trạng thái hai lần. Hoặc: Tiền lượng tử từ các giả định về mật mã. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Trích dẫn

[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 và P. Wallden, “Những tiến bộ trong mật mã lượng tử”, Những tiến bộ trong Quang học và Quang tử 12 4, 1012 (2020).

[2] Douglas Scott, “Những trò đùa khoa học, trò đùa vật lý và trò hề thiên văn”, arXiv: 2103.17057.

[3] Thomas Vidick và Tina Zhang, "Các bằng chứng cổ điển về kiến ​​thức lượng tử", arXiv: 2005.01691.

[4] Hoặc Sattath, “Hợp đồng thận trọng lượng tử với các ứng dụng cho Bitcoin”, arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry và Ruizhe Zhang, “Các phương pháp tiếp cận mới để bảo vệ bản sao lượng tử”, arXiv: 2004.09674.

[6] Roy Radian và Or Sattath, “Tiền bán lượng tử”, arXiv: 1908.08889.

[7] Andrea Coladangelo, Shafi Goldwasser và Umesh Vazirani, “Mã hóa có thể từ chối trong thế giới lượng tử”, arXiv: 2112.14988.

[8] Prabhanjan Ananth và Rolando L. La Placa, “Cho thuê phần mềm an toàn”, arXiv: 2005.05289.

[9] Hoặc Sattath và Shai Wyborski, “Bộ giải mã không thể sao chép được từ tính năng bảo vệ bản sao lượng tử”, arXiv: 2203.05866.

[10] Andrea Coladangelo và Or Sattath, “Giải pháp tiền lượng tử cho vấn đề về khả năng mở rộng chuỗi khối”, arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery và Mark Zhandry, “Một vòng đột phá và kiếm tiền lượng tử khác: Làm thế nào để không xây dựng nó từ lưới và hơn thế nữa”, arXiv: 2211.11994.

[12] Andrea Coladangelo, Jiahui Liu, Qipeng Liu và Mark Zhandry, “Các bộ đệm ẩn và ứng dụng cho mật mã không thể nhân bản”, arXiv: 2107.05692.

[13] Hoặc Sattath, “Mật mã không thể sao chép”, arXiv: 2210.14265.

[14] Amit Behera và Or Sattath, “Tiền lượng tử gần như công khai”, arXiv: 2002.12438.

[15] Anne Broadbent, Sevag Gharibian và Hong-Sheng Zhou, “Hướng tới những ký ức lượng tử một lần từ phần cứng không trạng thái”, arXiv: 1810.05226.

[16] Niraj Kumar, “Tiền lượng tử mạnh mẽ có tính thực tế khả thi với xác minh cổ điển”, arXiv: 1908.04114.

[17] Hoặc Sattath và Uriel Shinar, “Chứng mất trí nhớ lượng tử để lại các vật lưu niệm mật mã: Một lưu ý về chủ nghĩa hoài nghi lượng tử”, arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski và Yael Tauman Kalai, “Sự giảm thiểu sau lượng tử mang tính xây dựng”, arXiv: 2203.02314.

Các trích dẫn trên là từ SAO / NASA ADS (cập nhật lần cuối thành công 2023 / 01-20 14:01:05). Danh sách có thể không đầy đủ vì không phải tất cả các nhà xuất bản đều cung cấp dữ liệu trích dẫn phù hợp và đầy đủ.

On Dịch vụ trích dẫn của Crossref không có dữ liệu về các công việc trích dẫn được tìm thấy (lần thử cuối cùng 2023 / 01-20 14:01:00).

Dấu thời gian:

Thêm từ Tạp chí lượng tử