אסימוני קוונטים עבור חתימות דיגיטליות

אסימוני קוונטים עבור חתימות דיגיטליות

חותמת זמן: 19 בינואר 2023 8:49

שלו בן דוד1 ו או סאטאת2

1אוניברסיטת ווטרלו, בית הספר למדעי המחשב דיוויד ר. צ'ריטון
2אוניברסיטת בן-גוריון בנגב, החוג למדעי המחשב

מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- SciRate.

תַקצִיר

הדייג תפס דג קוונטי. "דייג, בבקשה תן לי ללכת", התחנן הדג, "ואני אעניק לך שלוש משאלות". הדייג הסכים. הדג נתן לדייג מחשב קוונטי, שלושה אסימוני חתימה קוונטיים והמפתח הציבורי הקלאסי שלו. הדג הסביר: "כדי לחתום על שלוש המשאלות שלך, השתמש בסכימת החתימה האסימונית במחשב הקוונטי הזה, ואז הראה את החתימה התקינה שלך למלך, שחייב לי טובה".
הדייג השתמש באחד מאסימוני החתימה כדי לחתום על המסמך "תן לי טירה!" ומיהר לארמון. המלך ביצע את אלגוריתם האימות הקלאסי באמצעות המפתח הציבורי של הדג, ומכיוון שהוא תקף, המלך נענה.
אשתו של הדייג רצתה לחתום על עשר משאלות באמצעות שני אסימוני החתימה הנותרים שלהם. הדייג לא רצה לרמות, והפליג בסתר לפגוש את הדג. "דג, אשתי רוצה לחתום על עשר משאלות נוספות". אבל הדג לא היה מודאג: "למדתי הצפנה קוונטית בעקבות הסיפור הקודם (הדייג ואשתו מאת האחים גרים). האסימונים הקוונטיים נצרכים במהלך החתימה. אשתך הפולינומית לא יכולה אפילו לחתום על ארבע משאלות באמצעות שלושת אסימוני החתימה שנתתי לך".
"איך זה עובד?" תהה הדייג. "שמעת על כסף קוונטי? אלו הם מצבים קוונטיים שניתן לאמתם בקלות אך קשה להעתיקם. סכימת החתימה הקוונטית האסימונית הזו מרחיבה את סכימת הכסף הקוונטי של אהרונסון וכריסטיאנו, וזו הסיבה שלא ניתן להעתיק את אסימוני החתימה".
"האם לתוכנית שלך יש מאפיינים מפוארים נוספים?" שאל הדייג. "כן, לתוכנית יש ערובות אבטחה אחרות: ביטול, בדיקה ואבטחה נצחית. יתר על כן, אם אתה בים ולטלפון הקוונטי שלך יש רק קליטה קלאסית, אתה יכול להשתמש בתוכנית זו כדי להעביר את ערך הכסף הקוונטי לחוף", אמר הדג ושחה משם.

אסימוני קוונטים עבור חתימות דיגיטליות PlatoBlockchain Data Intelligence. חיפוש אנכי. איי.

[תוכן מוטבע]

► נתוני BibTeX

► הפניות

[1] ש' אהרונסון. הגנת העתקה קוונטית וכסף קוונטי. בהליכי הכנס השנתי ה-24 של IEEE בנושא מורכבות חישובית, CCC 2009, פריז, צרפת, 15-18 ביולי 2009, עמודים 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] י' אהרונוב, י' אננדן ול' ויידמן. משמעות פונקציית הגל. פיזי. ר' א', 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] ש' אהרונסון ופ' כריסטיאנו. כסף קוונטי מתת-חללים נסתרים. ב-Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, ניו יורק, ניו יורק, ארה"ב, 19 - 22 במאי, 2012, עמודים 41-60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] ש' אהרונסון ופ' כריסטיאנו. כסף קוונטי מתתי מרחבים נסתרים. תורת המחשוב, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] ר' עמוס, מ' ג'ורג'יו, א' קיאיאס ומ' ז'אנדרי. חתימות ויישומים חד-פעמיים לאימות קוונטי/קלאסי היברידי. ב-K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, עורכים, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, עמודים 255–268. ACM, 2020, Cryptology ePrint Archive: Report 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] י' אהרונוב ול' וידמן. מדידה של גל שרדינגר של חלקיק בודד. פיזיקה אותיות א, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] ב' ברק. תקוות, פחדים וערפול תוכנה. Commun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] C. H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner. הצפנה קוונטית, או אסימוני רכבת תחתית בלתי ניתנים לזיוף. בהתקדמות בקריפטולוגיה, עמודים 267–275. שפרינגר, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] נ' ביטנסקי, ז' ברקרסקי וי' ט' קלאי. הפחתות פוסט קוונטיות קונסטרוקטיביות. בתוך Y. Dodis and T. Shrimpton, עורכים, Advances in Cryptology – CRYPTO 2022 – 42nd Annual Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15-18 באוגוסט 2022, Proceedings, Part III, Volume 13509 of Reference הערות במדעי המחשב, עמודים 654–683. ספרינגר, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, Y. T. Kalai, O. Paneth, and A. Rosen. חוסר האפשרות של ערפול עם קלט עזר או סימולטור אוניברסלי. ב-J. A. Garay and R. Gennaro, עורכים, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, סנטה ברברה, קליפורניה, ארה"ב, 17-21 באוגוסט 2014, Proceedings, Part II, כרך 8617 של הערות הרצאה במדעי המחשב, עמודים 71–89. שפרינגר, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. על (חוסר) האפשרות לטשטש תוכניות. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] ח' בומבין. שערי קליפורד על ידי עיוות קוד. New Journal of Physics, 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. חיפוש ספר טלפונים קוונטי. מדע, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] א' בהרה, או' סאטאת, וא' שנער. אסימוני קוונטים סובלני רעש עבור MAC, 2021.
https://doi.org/​10.48550/​ARXIV.2105.05016

[15] ד' בונה ומ' ז'אנדרי. קודי אימות הודעות Quantum-Secure. ב-T. Johansson ו-P. Q. Nguyen, עורכים, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, אתונה, יוון, 26-30 במאי, 2013. Proceedings, Volume 7881 in Computer of Lecture Notes מדע, עמודים 592–608. שפרינגר, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] ר' קליב וד' גוטסמן. חישובים יעילים של קידודים לתיקון שגיאות קוונטי. פיזי. ר' א', 56:76–82, יולי 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai, and V. Zikas. קריפטוגרפיה עם דלתות אחוריות חד פעמיות. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] פ. כריסטיאנו. תקשורת אישית, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu, and M. Zhandry. Hidden Cosets ויישומים לקריפטוגרפיה בלתי ניתנת לשיבוט, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan, and N. Raghunathan. גבולות לצמצום שגיאות עם מעט שאילתות קוונטיות. בקירוב, אקראי ואופטימיזציה קומבינטורית, אלגוריתמים וטכניקות, הסדנה הבינלאומית ה-8 בנושא אלגוריתמי קירוב לבעיות אופטימיזציה קומבינטורית, APPROX 2005 ו-RANDOM 2005, ברקלי, קליפורניה, ארה"ב, 22-24 באוגוסט, 2005, 245, 256, 2005, XNUMX, Pro .
https: / doi.org/â € ‹10.1007 / 11538462_21

[21] ר' קאנטי, ג' נ' רוטבלום, ומ' וריה. ערפול של חברות ב-Hyperplane. ב-D. Micciancio, עורך, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, ציריך, שוויץ, 9-11 בפברואר, 2010. Proceedings, Volume 5978 of Lecture Notes in Science, עמודים 72–89. ספרינגר, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie ו M. E. Hellman. כיוונים חדשים בקריפטוגרפיה. IEEE טרנס. תורת המידע, 22(6):644–654, 1976.
https: / doi.org/â € ‹10.1109 / TIT.1976.1055638

[23] י"ז דינג ומ"ו רבין. היפר-הצפנה ואבטחה נצחית. ב-H. Alt ו-A. Ferreira, עורכים, STACS 2002, סימפוזיון שנתי 19 על היבטים תיאורטיים של מדעי המחשב, אנטיב – חואן לה פינס, צרפת, 14-16 במרץ, 2002, הליכים, כרך 2285 של הערות הרצאה במדעי המחשב, עמודים 1–26. שפרינגר, 2002.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] ע' פרחי, ד' גוסט, א' חסידים, א' לוטומירסקי, ד' נגאג' ופ' שור. שחזור מצב קוונטי וטומוגרפיה חד-עותק למדינות הקרקע של המילטון. פיזי. ר' לט., 105:190503, נוב' 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] ע' פרחי, ד' גוסט, א' חסידים, א' לוטומירסקי ופ' שור. כסף קוונטי מקשרים. בכנס החידושים ה-3 במדעי המחשב התיאורטיים, עמודים 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] ד' גאווינסקי. כסף קוונטי עם אימות קלאסי. בכנס השנתי ה-27 של IEEE בנושא מורכבות חישובית, עמודים 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] ש' גולדווסר וי' ט קלאי. על חוסר האפשרות של ערפול עם קלט עזר. בסימפוזיון השנתי ה-46 של IEEE על יסודות מדעי המחשב (FOCS 2005), 23-25 ​​באוקטובר 2005, פיטסבורג, הרשות הפלסטינית, ארה"ב, Proceedings, עמודים 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] מ' ג'ורג'יו ואני קרנידיס. קונסטרוקציות חדשות לכסף קוונטי. ב-S. Beigi ו-R. König, עורכים, ועידה 10 על התיאוריה של חישוב קוונטי, תקשורת וקריפטוגרפיה, TQC 2015, 20-22 במאי, 2015, בריסל, בלגיה, כרך 44 של LIPIcs, עמודים 92–110. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2015.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] או גולדרייך. יסודות הקריפטוגרפיה - כרך 2, יישומים בסיסיים. הוצאת אוניברסיטת קיימברידג', 2004.

[30] M. Grassl, M. Rötteler, and T. Beth. מעגלים קוונטיים יעילים עבור קודי תיקון שגיאות קוונטיים שאינם קוביט. Int. J. נמצא. מחשוב. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] י' כץ וי' לינדל. מבוא לקריפטוגרפיה מודרנית, מהדורה שנייה. הוצאת CRC, 2014.

[32] נ.א לינץ'. אלגוריתמים מבוזרים. מורגן קאופמן, 1996.

[33] מ' מוסקה וד' סטבילה. מטבעות קוונטיים, כרך 523 של Contemp. מתמטיקה, עמודים 35–47. עאמר. מתמטיקה. Soc., 2010.

[34] M. C. Pena, R. D. Díaz, J. Faugère, L. H. Encinas, and L. Perret. ניתוח קריפטי לא קוונטי של הגרסה הרועשת של תוכנית הכסף הקוונטי של אהרונסון-כריסטיאנו. IET Information Security, 13(4):362–366, 2019.
https:/​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] M. C. Pena, J. Faugère, ול. Perret. ניתוח קריפטי אלגברי של תוכנית כסף קוונטי המקרה ללא רעש. בתוך J. Katz, עורך, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, 30 במרץ – 1 באפריל, 2015, Proceedings, Volume 9020 of Lecture Notes במדעי המחשב, עמודים 194–213. ספרינגר, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] א פראסד. ספירת תת-מרחבים של מרחב וקטורי סופי - 1. Resonance, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, N. Y. Yao, L. Jiang, M. D. Lukin, and J. I. Cirac. אסימוני קוונטים עמידים לרעשים שלא ניתן לזייף. הליכים של האקדמיה הלאומית למדעים, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] ר' רדיאן ואו' סתת. כסף חצי קוונטי. בהליכי ועידת ACM הראשונה בנושא התקדמות בטכנולוגיות פיננסיות, AFT 1, ציריך, שוויץ, 2019-21 באוקטובר 23, עמודים 2019–132. ACM, 146, arXiv: 2019.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] ר' רדיאן ואו' סתת. כסף חצי קוונטי. Journal of Cryptology, 35(2), ינואר 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[40] O. Sattath. חוזים חכמים קוונטיים עם יישומים לביטקוין, 2022.
https://doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. קריפטוגרפיה בלתי ניתנת לשיבוט, 2022.
https://doi.org/​10.48550/​ARXIV.2210.14265

[42] או' שמואלי. כסף קוונטי במפתח ציבורי עם בנק קלאסי. ב-S. Leonardi and A. Gupta, עורכים, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, רומא, איטליה, 20 - 24 ביוני 2022, עמודים 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] או' שמואלי. חתימות סמליות למחצה קוונטיות. בתוך Y. Dodis and T. Shrimpton, עורכים, Advances in Cryptology – CRYPTO 2022 – 42nd Annual Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15-18 באוגוסט 2022, Proceedings, Part I, Volume 13507 of Reference הערות במדעי המחשב, עמודים 296–319. ספרינגר, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, L. K. Grover, and A. Patel. אלגוריתם חדש לחיפוש קוונטי בנקודה קבועה. מידע וחישוב קוונטי, 6(6):483–494, 2006.
http://​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto, and N. Imoto. מזומן קוונטי אנונימי. בכנס ERATO למדעי מידע קוונטי, 2003.

[46] ד. אונרו. הצפנה קוונטית מתוזמנת לביטול. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] ד אונרו. חישוב רב-צדדי נצחי. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[48] ש' ויזנר. קידוד מצומד. ACM Sigact News, 15(1):78–88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[49] W. K. Wootters ו W. H. Zurek. לא ניתן לשבט קוונט אחד. טבע, 299(5886):802–803, 1982.

[50] M. Zhong, M. P. Hedges, R. L. Ahlefeldt, J. G. Bartholomew, S. E. Beavan, S. M. Wittig, J. J. Longdell, and M. J. Sellars. ספינים גרעיניים הניתן לטיפול אופטי במוצק עם זמן קוהרנטיות של שש שעות. טבע, 517(7533):177–180, ינואר 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] מ' ז'אנדרי. ברק קוונטי לעולם לא מכה את אותו מצב פעמיים, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] מ' ז'אנדרי. ברק קוונטי לעולם לא מכה את אותו מצב פעמיים. או: כסף קוונטי מהנחות קריפטוגרפיות. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / doi.org/â € ‹10.1007 / s00145-020-09372-x
arXiv: 1711.02276

מצוטט על ידי

[1] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, "Advances in quantum cryptography", התקדמות באופטיקה ופוטוניקה 12 4, 1012 (2020).

[2] דאגלס סקוט, "זיופים מדעיים, מתיחות פיזיקה ותעלולים אסטרונומיים", arXiv: 2103.17057.

[3] תומאס וידיק וטינה ג'אנג, "הוכחות קלאסיות לידע קוונטי", arXiv: 2005.01691.

[4] Or Sattath, "חוזים נבונים בקוונטים עם יישומים לביטקוין", arXiv: 2204.12806.

[5] סקוט אהרונסון, Jiahui Liu, Qipeng Liu, Mark Zhandry ו- Ruizhe Zhang, "גישות חדשות להגנה על העתקה קוונטית", arXiv: 2004.09674.

[6] רוי רדיאן ואור סאטאת, "כסף קוונטי למחצה", arXiv: 1908.08889.

[7] אנדריאה קולדאנג'לו, שאפי גולדווסר ואומש וזיראני, "הצפנה ניתנת להכחשה בעולם קוונטי", arXiv: 2112.14988.

[8] Prabhanjan Ananth ורולנדו L. La Placa, "השכרת תוכנה מאובטחת", arXiv: 2005.05289.

[9] אור סאטאת ושי וויבורסקי, "מפענחים בלתי ניתנים לשיבוט מהגנה קוונטית להעתקה", arXiv: 2203.05866.

[10] אנדריאה קולדג'לו ואור סאטאת, "פתרון כסף קוונטי לבעיית מדרגיות הבלוקצ'יין", arXiv: 2002.11998.

[11] ג'יאהוי ליו, הארט מונטגומרי ומארק ז'אנדרי, "עוד סיבוב של שבירה ועשיית כסף קוונטי: איך לא לבנות אותו מסריג ועוד", arXiv: 2211.11994.

[12] אנדריאה קולדאנג'לו, Jiahui Liu, Qipeng Liu ומארק ז'אנדרי, "חבילות נסתרות ויישומים לקריפטוגרפיה בלתי ניתנת לשיבוט", arXiv: 2107.05692.

[13] Or Sattath, "קריפטוגרפיה בלתי ניתנת לשיבוט", arXiv: 2210.14265.

[14] עמית בהרה ואור סתת, "מטבעות קוונטיים כמעט ציבוריים", arXiv: 2002.12438.

[15] אן ברודבנט, סבג גריביאן והונג-שנג ג'ואו, "לקראת זיכרונות חד-פעמיים קוונטיים מחומרה חסרת מדינה", arXiv: 1810.05226.

[16] ניראג' קומאר, "כסף קוונטי חזק בר-ביצוע מעשי עם אימות קלאסי", arXiv: 1908.04114.

[17] אור סתת ואוריאל שנער, "אמנזיה קוונטית משאירה מזכרות קריפטוגרפיות: הערה על ספקנות קוונטית", arXiv: 2212.08750.

[18] ניר ביטנסקי, צביקה ברקרסקי ויעל טאומן קלאי, "צמצומים פוסט-קוונטיים בונים", arXiv: 2203.02314.

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2023-01-20 14:01:05). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2023-01-20 14:01:00)

מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.

בול זמן:

עוד מ יומן קוונטים