ניתוב קוד: התקפה חדשה על אימות מיקום

ניתוב קוד: התקפה חדשה על אימות מיקום

חותמת זמן: 9 באוגוסט, 2023 11:18
ניתוב קוד: מתקפה חדשה על אימות מיקום PlatoBlockchain Data Intelligence. חיפוש אנכי. איי.

ג'וי קרי ו אלכס מאי

אוניברסיטת סטנפורד

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

תַקצִיר

המשימה ההצפנה של אימות מיקום מנסה לאמת מיקומו של צד אחד במרחב-זמן על-ידי ניצול אילוצים על מידע קוונטי וסיבתיות רלטיבית. סכימת אימות פופולרית הידועה בשם $f$-ניתוב כוללת דרישה מהמוכיח לנתב מחדש מערכת קוונטית על סמך הערך של פונקציה בוליאנית $f$. אסטרטגיות רמאות עבור סכמת הניתוב $f$ מחייבות את המוכיח להשתמש בהסתבכות משותפת מראש, ואבטחת הסכימה נשענת על הנחות לגבי כמה הסתבכות מוכיח יכול לתמרן. כאן, אנו נותנים אסטרטגיית רמאות חדשה שבה המערכת הקוונטית מקודדת לסכמת שיתוף סודות, ומבנה ההרשאות של סכימת שיתוף הסוד מנוצל כדי לכוון את המערכת כראוי. אסטרטגיה זו משלימה את משימת הניתוב $f$ באמצעות $O(SP_p(f))$ צמדי EPR, כאשר $SP_p(f)$ הוא הגודל המינימלי של תוכנית span על פני השדה $mathbb{Z}_p$ המחשוב $ f$. זה מראה שאנחנו יכולים לתקוף ביעילות סכימות ניתוב של $f$ בכל פעם ש$f$ נמצא במחלקת המורכבות $text{Mod}_ptext{L}$, לאחר שמאפשרים עיבוד מקדים מקומי. הבנייה הקודמת הטובה ביותר השיגה את המחלקה L, אשר מאמינים שהיא אך ורק בתוך $text{Mod}_ptext{L}$. אנו מראים גם שהגודל של סכימת שיתוף סודות קוונטית עם פונקציית אינדיקטור $f_I$ מגביל את עלות ההסתבכות של $f$-ניתוב על הפונקציה $f_I$.

► נתוני BibTeX

► הפניות

[1] נישאנת' צ'נדרן, ויפול גויאל, ריאן מוריארטי ורפאיל אוסטרובסקי. קריפטוגרפיה מבוססת מיקום. בכנס השנתי הבינלאומי לקריפטולוגיה, עמודים 391–407. ספרינגר, 2009. https://doi.org/​10.1007/​978-3-642-03356-8_23.
https:/​/​doi.org/​10.1007/​978-3-642-03356-8_23

[2] אדריאן קנט, וויליאם ג'יי מונרו וטימותי פי ספילר. תיוג קוונטי: אימות מיקום באמצעות מידע קוונטי ומגבלות איתות רלטיביסטיות. Physical Review A, 84 (1): 012326, 2011. https:/​/​doi.org/​10.1103/​PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] אדריאן קנט. משימות קוונטיות בחלל מינקובסקי. כבידה קלאסית וקוונטית, 29 (22): 224013, 2012. 10.1088/​0264-9381/​29/​22/​224013.
https:/​/​doi.org/​10.1088/​0264-9381/​29/​22/​224013

[4] וויליאם ק ווטרס וויצ'ך ה' זורק. לא ניתן לשבט קוונט אחד. Nature, 299 (5886): 802–803, 1982. https://doi.org/​10.1038/​299802a0.
https: / / doi.org/ 10.1038 / 299802a0

[5] אדריאן פ קנט, וויליאם ג'יי מונרו, טימותי פי ספילר וריימונד ג'י בוזולי. מערכות תיוג, 11 ביולי 2006. פטנט אמריקאי 7,075,438.

[6] רוברט א' מלאני. תקשורת תלוית מיקום באמצעות הסתבכות קוונטית. Physical Review A, 81 (4): 042319, 2010. https:/​/​doi.org/​10.1103/​PhysRevA.81.042319.
https: / / doi.org/ 10.1103 / PhysRevA.81.042319

[7] הארי בוהרמן, נישאנת' צ'נדרן, סרג' פהר, רן גלס, ויפול גויאל, רפאיל אוסטרובסקי וכריסטיאן שפנר. הצפנה קוונטית מבוססת מיקום: חוסר אפשרות וקונסטרוקציות. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] סלמאן בייגי ורוברט קוניג. חישוב קוונטי מיידי לא מקומי פשוט עם יישומים לקריפטוגרפיה מבוססת מיקום. New Journal of Physics, 13 (9): 093036, 2011. 10.1088/​1367-2630/​13/​9/​093036.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​9/​093036

[9] אנדראס בלוהם, מתיאס קריסטנדל ופלוריאן ספלמן. פרוטוקול אימות מיקום יחיד המאובטח מפני התקפות ריבוי קיוביטים. פיסיקת הטבע, עמודים 1–4, 2022. https://doi.org/​10.1038/​s41567-022-01577-0.
https:/​/​doi.org/​10.1038/​s41567-022-01577-0

[10] הארי בוהרמן, סרג' פהר, כריסטיאן שפנר ופלוריאן ספלמן. דגם צינור הגינה. ב-Proceedings of the 4th conference on Innovations in Theoretical Computer Science, עמודים 145–158, 2013. https://​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] הרטמוט קלאק וסופרתה פודר. גבולות חדשים לדגם צינור הגינה. ביסודות טכנולוגיית תוכנה ומדעי המחשב תיאורטיים, 2014. 10.4230/​LIPIcs.FSTTCS.2014.481.
https:/​/​doi.org/​10.4230/​LIPIcs.FSTTCS.2014.481

[12] Srinivasan Arunachalam ו-Supartha Podder. מזכרת תקשורת: מורכבות תקשורת חסרת זיכרון. בכנס חידושים במדעי המחשב התיאורטיים (ITCS 12). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. 2021/​LIPIcs.ITCS.10.4230.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.61

[13] אלכס מאי. משימות קוונטיות בהולוגרפיה. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https:/​/​doi.org/​10.1007/​JHEP10(2019)233.
https: / / doi.org/ 10.1007 / JHEP10 (2019) 233

[14] אלכס מאי, ג'וף פינגטון וג'ונתן סורס. פיזור הולוגרפי דורש טריז הסתבכות מחובר. Journal of High Energy Physics, 2020 (8): 1–34, 2020. https:/​/​doi.org/​10.1007/​JHEP08(2020)132.
https: / / doi.org/ 10.1007 / JHEP08 (2020) 132

[15] אלכס מאי. מורכבות והסתבכות בחישוב והולוגרפיה לא מקומיים. Quantum, 6: 864, נובמבר 2022. ISSN 2521-327X. 10.22331/​q-2022-11-28-864. כתובת האתר https://doi.org/​10.22331/​q-2022-11-28-864.
https:/​/​doi.org/​10.22331/​q-2022-11-28-864

[16] אדם די סמית'. שיתוף סודי קוונטי עבור מבני גישה כלליים. arXiv preprint quant-ph/​0001087, 2000. https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0001087.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0001087
arXiv: quant-ph / 0001087

[17] חואן מלדצ'נה. הגבול הגדול-N של תיאוריות שדות על-קונפורמיות וסופר-כבידה. כתב העת הבינלאומי לפיזיקה תיאורטית, 38 (4): 1113–1133, 1999. https://doi.org/​10.1023/​A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[18] אדוארד ויטן. חלל אנטי-די סיטר והולוגרפיה. Advances in Theoretical and Mathematical Physics, 2: 253–291, 1998. 10.4310/​ATMP.1998.v2.n2.a2.
https:/​/​doi.org/​10.4310/​ATMP.1998.v2.n2.a2

[19] דניאל גוטסמן. תיאוריה של שיתוף סודי קוונטי. סקירה גופנית א ', 61 (4): 042311, 2000. https: / / doi.org/ 10.1103 / PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] בנג'מין שומאכר ומייקל א נילסן. עיבוד נתונים קוונטי ותיקון שגיאות. Physical Review A, 54 (4): 2629, 1996. https:/​/​doi.org/​10.1103/​PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[21] בנג'מין שומאכר ומייקל ד' ווסטמורלנד. תיקון שגיאות קוונטי משוער. Quantum Information Processing, 1 (1): 5–12, 2002. https://doi.org/​10.1023/​A:1019653202562.
https: / / doi.org/ 10.1023 / A: 1019653202562

[22] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, וכריסטוף מיינל. מבנה וחשיבות של מחלקת logspace-mod. תורת המערכות המתמטית, 25 (3): 223–237, 1992. https://doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] מאוריסיו קרצ'מר ואבי וידרסון. על תוכניות span. בשנת [1993] כנס הליכים של המבנה השנתי השמיני בתורת המורכבות, עמודים 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] ניל די ג'ונס, י אדמונד ליאן, וויליאם טי לאזר. בעיות חדשות הושלמו עבור שטח יומן לא דטרמיניסטי. תורת המערכות המתמטית, 10 (1): 1–17, 1976. https://doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] קלאוס ריינהרדט ואריק אלנדר. הפיכת הבלתי דטרמיניזם לחד משמעי. SIAM Journal on Computing, 29 (4): 1118–1131, 2000. https://doi.org/​10.1137/​S0097539798339041.
https: / / doi.org/ 10.1137 / S0097539798339041

[26] אריק אלנדר, קלאוס ריינהרדט ושייו ג'ואו. בידוד, התאמה וספירה של גבולות עליונים אחידים ולא אחידים. Journal of Computer and System Sciences, 59 (2): 164–181, 1999. https://doi.org/​10.1006/​jcss.1999.1646.
https: / / doi.org/ 10.1006 / jcss.1999.1646

[27] אייל קושילוביץ. מורכבות תקשורת. בהתקדמות במחשבים, כרך 44, עמודים 331–360. Elsevier, 1997. https://doi.org/​10.1016/​S0065-2458(08)60342-3.
https:/​/​doi.org/​10.1016/​S0065-2458(08)60342-3

[28] נועם ניסן. מורכבות התקשורת של שערי סף. קומבינטוריקה, פול ארדוס בן שמונים, 1: 301–315, 1993.

[29] רוברט רובר, טוניאן פיטסי, בנג'מין רוסמן וסטיבן א קוק. גבול תחתון אקספוננציאלי עבור תוכניות טווח מונוטוני. בשנת 2016 IEEE 57th Annual Symposium on Foundations of Science (FOCS), עמודים 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] פלוריאן ספלמן. חישוב מיידי לא מקומי של מעגלים קוונטיים בעומק T נמוך. בכנס ה-11 על התיאוריה של חישוב קוונטי, תקשורת וקריפטוגרפיה (TQC 2016), כרך 61 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 9:1–9:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230/​LIPIcs.TQC.2016.9.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2016.9

מצוטט על ידי

[1] אלכס מאי, "מורכבות והסתבכות בחישוב והולוגרפיה לא מקומיים", קוונטום 6, 864 (2022).

[2] אלכס מאי, ג'ונתן סורס ובני יושידה, "משפט הטריז המחובר והשלכותיו", כתב העת לפיסיקה של אנרגיה גבוהה 2022 11, 153 (2022).

[3] כפיר דולב וסם קרי, "הולוגרפיה כמשאב לחישוב קוונטי לא מקומי", arXiv: 2210.13500, (2022).

[4] כפיר דולב וסם קרי, "חישוב לא מקומי של מעגלים קוונטיים עם חרוטי אור קטנים", arXiv: 2203.10106, (2022).

[5] רנה אלרסטורפר, הארי בוהרמן, אלכס מיי, פלוריאן ספלמן ופיליפ ורדיין לונאל, "קישור חישוב קוונטי לא מקומי להצפנה תיאורטית של מידע", arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs ופלוריאן ספלמן, "פרוטוקול אימות מיקום קוונטי קוונטי סובלני לאובדן יחיד מאובטח מפני תוקפים מסובכים", arXiv: 2212.03674, (2022).

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2023-08-10 03:31:42). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2023-08-10 03:31:41)

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

בול זמן:

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