Token Kuantum untuk Tanda Tangan Digital

Token Kuantum untuk Tanda Tangan Digital

Stempel Waktu: 19 Januari 2023 8

Shalev Ben-David1 dan Atau Sattath2

1Universitas Waterloo, Sekolah Ilmu Komputer David R. Cheriton
2Universitas Ben-Gurion Negev, Departemen Ilmu Komputer

Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.

Abstrak

Nelayan menangkap ikan kuantum. “Nelayan, tolong lepaskan aku”, pinta ikan itu, “dan aku akan mengabulkan tiga permintaanmu”. Nelayan itu setuju. Ikan itu memberi nelayan itu komputer kuantum, tiga token penandatanganan kuantum, dan kunci publik klasiknya. Ikan itu menjelaskan: “untuk menandatangani tiga permintaan Anda, gunakan skema tanda tangan yang diberi token pada komputer kuantum ini, lalu tunjukkan tanda tangan Anda yang sah kepada raja, yang berhutang budi kepada saya”.
Nelayan menggunakan salah satu token penandatanganan untuk menandatangani dokumen “berikan aku sebuah kastil!” dan bergegas ke istana. Raja mengeksekusi algoritma verifikasi klasik menggunakan kunci publik ikan, dan karena valid, raja mematuhinya.
Istri nelayan ingin menandatangani sepuluh permintaan dengan menggunakan dua tanda tanda tangan mereka yang tersisa. Nelayan tidak mau berbuat curang, dan diam-diam berlayar menemui ikan tersebut. “Ikan, istriku ingin menandatangani sepuluh permintaan lagi”. Namun ikan itu tidak khawatir: “Saya telah mempelajari kriptografi kuantum mengikuti cerita sebelumnya (Nelayan dan Istrinya oleh Grimm bersaudara). Token kuantum dikonsumsi selama penandatanganan. Istri polinomialmu bahkan tidak bisa menandatangani empat permintaan menggunakan tiga token penandatanganan yang kuberikan padamu”.
"Bagaimana cara kerjanya?" tanya si nelayan. “Pernahkah Anda mendengar tentang uang kuantum? Ini adalah keadaan kuantum yang dapat diverifikasi dengan mudah tetapi sulit untuk ditiru. Skema tanda tangan kuantum yang diberi token ini memperluas skema uang kuantum Aaronson dan Christiano, itulah sebabnya token penandatanganan tidak dapat disalin”.
“Apakah skema Anda memiliki properti tambahan yang mewah?” tanya nelayan itu. “Ya, skema ini memiliki jaminan keamanan lainnya: dapat dibatalkan, dapat diuji, dan keamanan abadi. Terlebih lagi, jika Anda berada di laut dan telepon kuantum Anda hanya memiliki penerimaan klasik, Anda dapat menggunakan skema ini untuk mentransfer nilai uang kuantum ke darat”, kata ikan tersebut, dan berenang menjauh.

Token Kuantum untuk Tanda Tangan Digital Kecerdasan Data PlatoBlockchain. Pencarian Vertikal. Ai.

[Embedded content]

► data BibTeX

► Referensi

[1] S.Aaronson. Perlindungan Penyalinan Kuantum dan Uang Kuantum. Dalam Prosiding Konferensi IEEE Tahunan ke-24 tentang Kompleksitas Komputasi, CCC 2009, Paris, Prancis, 15-18 Juli 2009, halaman 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan, dan L. Vaidman. Arti fungsi gelombang. Fis. Pendeta A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson dan P. Christiano. Uang kuantum dari subruang tersembunyi. Dalam Prosiding Konferensi Simposium Teori Komputasi ke-44, STOC 2012, New York, NY, AS, 19 – 22 Mei 2012, halaman 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson dan P. Christiano. Uang Kuantum dari Subruang Tersembunyi. Teori Komputasi, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias, dan M. Zhandry. Tanda tangan sekali pakai dan aplikasi untuk autentikasi kuantum/klasik hibrid. Dalam K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, dan J. Chuzhoy, editor, Prosiding Simposium Tahunan ACM SIGACT tentang Teori Komputasi,, halaman 255–268. ACM, 2020, Arsip Kriptologi ePrint: Laporan 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov dan L. Vaidman. Pengukuran gelombang Schrödinger dari satu partikel. Fisika Huruf A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B.Barak. Harapan, ketakutan, dan kebingungan perangkat lunak. Komunitas. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart, dan S. Wiesner. Kriptografi kuantum, atau token kereta bawah tanah yang tidak dapat dipalsukan. Dalam Kemajuan dalam Kriptologi, halaman 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski, dan YT Kalai. Reduksi Pasca-Quantum yang Konstruktif. Dalam Y. Dodis dan T. Shrimpton, editor, Kemajuan dalam Kriptologi – CRYPTO 2022 – Konferensi Kriptologi Internasional Tahunan ke-42, CRYPTO 2022, Santa Barbara, CA, AS, 15-18 Agustus 2022, Prosiding, Bagian III, volume 13509 Kuliah Catatan dalam Ilmu Komputer, halaman 654–683. Pegas, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, YT Kalai, O. Paneth, dan A. Rosen. Ketidakmungkinan Kebingungan dengan Input Tambahan atau Simulator Universal. Dalam JA Garay dan R. Gennaro, editor, Kemajuan dalam Kriptologi – CRYPTO 2014 – Konferensi Kriptologi Tahunan ke-34, Santa Barbara, CA, AS, 17-21 Agustus 2014, Prosiding, Bagian II, volume 8617 Catatan Kuliah Ilmu Komputer, halaman 71–89. Pegas, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, SP Vadhan, dan K. Yang. Tentang kemungkinan (im)kemungkinan mengaburkan program. J.ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H.Bombin. Gerbang Clifford dengan deformasi kode. Jurnal Fisika Baru, 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.Brassard. Mencari Buku Telepon Quantum. Sains, 275(5300):627–628, 1997.
https://​/​doi.org/​10.1126/​science.275.5300.627

[14] A. Behera, O. Sattath, dan U. Shinar. Token Quantum Toleransi Kebisingan untuk MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh dan M. Zhandry. Kode Otentikasi Pesan Quantum-Secure. Dalam T. Johansson dan PQ Nguyen, editor, Kemajuan dalam Kriptologi – EUROCRYPT 2013, Konferensi Internasional Tahunan ke-32 tentang Teori dan Penerapan Teknik Kriptografi, Athena, Yunani, 26-30 Mei 2013. Prosiding, volume 7881 dari Catatan Kuliah di Komputer Sains, halaman 592–608. Pegas, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve dan D. Gottesman. Perhitungan pengkodean yang efisien untuk koreksi kesalahan kuantum. Fis. Pendeta A, 56:76–82, Juli 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai, dan V. Zikas. Kriptografi dengan Pintu Belakang Sekali Pakai. Cryptogr., 3(3):22, 2019, Arsip Kriptologi ePrint: Laporan 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P.Christiano. Komunikasi pribadi, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu, dan M. Zhandry. Koset Tersembunyi dan Penerapan pada Kriptografi yang Tidak Dapat Dikloning, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan, dan N. Raghunathan. Batasan Pengurangan Kesalahan dengan Beberapa Kueri Kuantum. Dalam Pendekatan, Pengacakan dan Optimasi Kombinatorial, Algoritma dan Teknik, Lokakarya Internasional ke-8 tentang Algoritma Pendekatan untuk Masalah Optimasi Kombinatorial, APPROX 2005 dan RANDOM 2005, Berkeley, CA, AS, 22-24 Agustus 2005, Prosiding, halaman 245–256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum, dan M. Varia. Kebingungan Keanggotaan Hyperplane. Dalam D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Swiss, 9-11 Februari 2010. Proceedings, volume 5978 dari Lecture Notes in Computer Science, halaman 72–89. Pegas, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie dan AKU Hellman. Arah baru dalam kriptografi. IEEE Trans. Teori Informasi, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding dan MO Rabin. Enkripsi Hiper dan Keamanan Abadi. Dalam H. Alt dan A. Ferreira, editor, STACS 2002, Simposium Tahunan ke-19 tentang Aspek Teoritis Ilmu Komputer, Antibes – Juan les Pins, Prancis, 14-16 Maret 2002, Prosiding, volume 2285 dari Catatan Kuliah Ilmu Komputer, halaman 1–26. Springer, 2002.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, D. Nagaj, dan P. Shor. Restorasi Keadaan Kuantum dan Tomografi Salinan Tunggal untuk Keadaan Dasar Hamiltonian. Fis. Pendeta Lett., 105:190503, November 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, dan P. Shor. Uang kuantum dari simpul. Dalam Prosiding Konferensi Inovasi ke-3 dalam Ilmu Komputer Teoritis, halaman 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D.Gavinsky. Uang kuantum dengan verifikasi klasik. Dalam Konferensi Tahunan IEEE ke-27 tentang Kompleksitas Komputasi, halaman 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser dan YT Kalai. Tentang Ketidakmungkinan Kebingungan dengan Input Tambahan. Dalam Simposium IEEE Tahunan ke-46 tentang Yayasan Ilmu Komputer (FOCS 2005), 23-25 ​​Oktober 2005, Pittsburgh, PA, AS, Proceedings, halaman 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou dan I. Kerenidis. Konstruksi Baru untuk Uang Kuantum. Dalam S. Beigi dan R. König, editor, Konferensi ke-10 Teori Komputasi Kuantum, Komunikasi dan Kriptografi, TQC 2015, 20-22 Mei 2015, Brussels, Belgia, LIPIcs volume 44, halaman 92–110. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2015.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich. Dasar-dasar Kriptografi - Vol. 2, Aplikasi Dasar. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler, dan T. Beth. Sirkuit Kuantum Efisien Untuk Kode Koreksi Kesalahan Kuantum Non-Qubit. Int. J.Ditemukan. Hitung. Sains, 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz dan Y. Lindell. Pengantar Kriptografi Modern, Edisi Kedua. CRC Press, 2014.

[32] NA Lynch. Algoritma Terdistribusi. Morgan Kaufmann, 1996.

[33] M.Mosca dan D.Stebila. Koin kuantum, volume 523 dari Contemp. Matematika., halaman 35–47. Amer. Matematika. Sosial, 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas, dan L. Perret. Kriptanalisis Non-kuantum dari Skema Uang Kuantum Aaronson-Christiano Versi Bising. Keamanan Informasi IET, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère, dan L. Perret. Kriptanalisis Aljabar dari Skema Uang Kuantum Kasus Bebas Kebisingan. Dalam J. Katz, editor, Kriptografi Kunci Publik – PKC 2015 – Konferensi Internasional IACR ke-18 tentang Praktek dan Teori dalam Kriptografi Kunci Publik, Gaithersburg, MD, AS, 30 Maret – 1 April 2015, Prosiding, volume 9020 dari Catatan Kuliah dalam Ilmu Komputer, halaman 194–213. Pegas, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A.Prasad. Menghitung subruang dari ruang vektor berhingga — 1. Resonansi, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, NY Yao, L. Jiang, MD Lukin, dan JI Cirac. Token kuantum yang tahan terhadap kebisingan yang tidak dapat dipalsukan. Prosiding National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian dan O. Sattath. Uang Semi-Kuantum. Dalam Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Swiss, 21-23 Oktober 2019, halaman 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian dan O. Sattath. Uang Semi-kuantum. Jurnal Kriptologi, 35(2), Januari 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[40] O. Sattath. Kontrak Quantum Prudent dengan Penerapan pada Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Kriptografi yang Tidak Dapat Dikloning, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O.Shmueli. Uang kuantum kunci publik dengan bank klasik. Dalam S. Leonardi dan A. Gupta, editor, STOC '22: Simposium ACM SIGACT Tahunan ke-54 tentang Teori Komputasi, Roma, Italia, 20 – 24 Juni 2022, halaman 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O.Shmueli. Tanda Tangan Tokenisasi Semi-kuantum. Dalam Y. Dodis dan T. Shrimpton, editor, Kemajuan dalam Kriptologi – CRYPTO 2022 – Konferensi Kriptologi Internasional Tahunan ke-42, CRYPTO 2022, Santa Barbara, CA, AS, 15-18 Agustus 2022, Prosiding, Bagian I, volume 13507 Kuliah Catatan dalam Ilmu Komputer, halaman 296–319. Pegas, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover, dan A. Patel. Algoritma baru untuk pencarian kuantum titik tetap. Informasi & Komputasi Kuantum, 6(6):483–494, 2006.
http://​/​portal.acm.org/​itation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto, dan N. Imoto. Uang tunai kuantum anonim. Dalam Konferensi ERATO tentang Ilmu Informasi Kuantum, 2003.

[46] D.Unruh. Enkripsi Rilis Berwaktu Kuantum yang Dapat Dicabut. J.ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D.Unruh. Perhitungan Multi-pihak yang Abadi. J.Kriptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[48] S. Wiesner. Konjugasi coding. ACM Sigact News, 15 (1): 78–88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[49] WK Wootters dan WH Zurek. Sebuah kuantum tunggal tidak dapat dikloning. Alam, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell, dan MJ Sellars. Nuklir yang dapat dialamatkan secara optik berputar dalam benda padat dengan waktu koherensi enam jam. Alam, 517(7533):177–180, Januari 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M.Zandry. Petir Kuantum Tidak Pernah Menyerang Keadaan yang Sama Dua Kali, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M.Zandry. Petir Kuantum Tidak Pernah Menerjang Keadaan yang Sama Dua Kali. Atau: Uang Kuantum dari Asumsi Kriptografi. J.Kriptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Dikutip oleh

[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, dan P. Wallden, “Kemajuan dalam kriptografi kuantum”, Kemajuan dalam Optik dan Fotonik 12 4, 1012 (2020).

[2] Douglas Scott, “Spoof Sains, Lelucon Fisika, dan Kejenakaan Astronomi”, arXiv: 2103.17057.

[3] Thomas Vidick dan Tina Zhang, "Bukti klasik dari pengetahuan kuantum", arXiv: 2005.01691.

[4] Atau Sattath, “Kontrak Bijaksana Quantum dengan Penerapan pada Bitcoin”, arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, dan Ruizhe Zhang, “Pendekatan Baru untuk Perlindungan Salinan Kuantum”, arXiv: 2004.09674.

[6] Roy Radian dan Or Sattath, “Uang Semi-Kuantum”, arXiv: 1908.08889.

[7] Andrea Coladangelo, Shafi Goldwasser, dan Umesh Vazirani, “Enkripsi yang Dapat Ditolak di Dunia Kuantum”, arXiv: 2112.14988.

[8] Prabhanjan Ananth dan Rolando L. La Placa, “Penyewaan Perangkat Lunak Aman”, arXiv: 2005.05289.

[9] Atau Sattath dan Shai Wyborski, “Decryptors yang Tidak Dapat Dikloning dari Quantum Copy-Protection”, arXiv: 2203.05866.

[10] Andrea Coladangelo dan Or Sattath, “Solusi Uang Kuantum untuk Masalah Skalabilitas Blockchain”, arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery, dan Mark Zhandry, “Putaran Lain dalam Menghancurkan dan Menghasilkan Uang Kuantum: Bagaimana Tidak Membangunnya dari Kisi-kisi, dan Banyak Lagi”, arXiv: 2211.11994.

[12] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, dan Mark Zhandry, “Koset dan Aplikasi Tersembunyi untuk Kriptografi yang Tidak Dapat Dikloning”, arXiv: 2107.05692.

[13] Atau Sattath, “Kriptografi yang Tidak Dapat Dikloning”, arXiv: 2210.14265.

[14] Amit Behera dan Or Sattath, “Koin Kuantum Hampir Publik”, arXiv: 2002.12438.

[15] Anne Broadbent, Sevag Gharibian, dan Hong-Sheng Zhou, “Menuju Kenangan Satu Kali Kuantum dari Perangkat Keras Tanpa Negara”, arXiv: 1810.05226.

[16] Niraj Kumar, “Uang kuantum kuat yang layak secara praktis dengan verifikasi klasik”, arXiv: 1908.04114.

[17] Atau Sattath dan Uriel Shinar, “Quantum Amnesia Meninggalkan Kenang-kenangan Kriptografis: Catatan Tentang Skeptisisme Quantum”, arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski, dan Yael Tauman Kalai, “Reduksi Pasca-Quantum yang Konstruktif”, arXiv: 2203.02314.

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2023-01-20 14:01:05). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.

On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2023-01-20 14:01:00).

Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.

Stempel Waktu:

Lebih dari Jurnal Kuantum