פיתוח בטכניון: פרוטוקול הצפנה קוונטית למחצה

בהצפנה קוונטית קונוונציונלית יש צורך במכונות הצפנה קוונטיות בשני הצדדים. בשיטה שפותחה בפקולטה למדעי המחשב בטכניון, ניתן להסתפק בצד אחד קוונטי, ואילו לצד השני ניתנות יכולות קידוד של מידע קלאסי בלבד. למרות שהשיטה הינה קלאסית למחצה, אם מישהו מצותת, הציתות מייצר רעש רב, המורגש על ידי המשתמשים החוקיים

דן קניגסברג, הטכניון
דן קניגסברג, הטכניון

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

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

בשיחה עם אתר הידען מסביר פרופ' מור כי "שיטת העברת המפתח המקובלת כיום היא שיטת RSA המסתמכת על מספר ארוך מאוד – בעל מאות ספרות – ועל מרכיביו הראשוניים. ההנחה היא שלהכפיל מספרים ראשוניים זו פעולה קלה לביצוע ואילו הניסיון לפרק מספר גדול למרכיבו הראשוניים זו פעולה קשה הדורשת כוח מחשוב רב. לכן תמיד ניתן יהיה למצוא מפתחות מספיק ארוכים, שכוח החישוב שיידרש לפענחם יהיה כה רב, עד כדי הפיכת הפענוח לבלתי אפשרית. ואולם אין הוכחת בטיחות לשיטה זו ולשיטות הדומות לה, ויתכן שסוכנות ביון גדולה כבר יודעת לפצחן, אך שומרת עובדה זאת בסוד. אפילו ייתכן (אם כי הרבה פחות סביר) שהאקר גאון יצליח לפתח את RSA בשנים הקרובות. במיוחד מעניין לציין שתיאורטית, שיטת RSA כבר נשברה, אך לא על-ידי אלגוריתם רגיל אלא על מחשבים קוונטיים. אבל מעשית, פיצוח זה עדיין רחוק מאד – זה יקרה אם וכאשר מחשבים קוונטיים יהיו ניתנים לבנייה. הם יוכלו לפענח כל צופן מסוג RSA ודומיו, בכל אורך. לאור הסכנות הנ"ל, חשוב לדעת שקיימת גם שיטה אחרת לחלוטין, המתבססת על תורת הקוונטים.”

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

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

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

כשפוטון של אליס מגיע לבוב, הוא בוחר באחד הבסיסים – "חישובי" או "אלכסוני" ואומר לאליס באיזה בסיס הוא משתמש. בכל פעם שהוא משתמש בבסיס הלא נכון, הוא מקבל תשובה אקראית, ואליס אומרת לו להיפטר מה"ביט" הזה, כלומר להתעלם מהפוטון. "ביטים" אלו מסולקים, ומהנותרים מיוצר המפתח הסודי. אם יש מצותת כלשהו, כשהוא מקבל את הפוטונים הוא צריך לנחש באיזה בסיס להשתמש כדי לקרוא אותם. כתוצאה מכך, ובהתאם לחוקי המכניקה הקוונטית, הוא למעשה פוגם בקיטוב בכל פעם שאינו מנחש נכון, מכניס רעש, וגוזל מיכולתו של בוב לקרוא נכון חלק מהפוטונים שהוא היה עשוי לקרוא נכון. הרעש בו מבחין בוב מגלה לבוב שערוץ התקשורת משובש על-ידי מצותת."

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

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

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

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

בפרוטוקול החדש הראינו שאכן יכולות אלו מספיקות על מנת להגדיר פרוטוקול קוונטי-למחצה, ובכל זאת בטוח כנגד ציתות.

שיתוף ב print
שיתוף ב email
שיתוף ב whatsapp
שיתוף ב linkedin
שיתוף ב twitter
שיתוף ב facebook

17 תגובות

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

    עוד שאלה הקשורה לכך – בתהליך האבולוציה, החל מאיזה שלב ניתן לאמר שהמוח של בעל החיים פותר את הבעייה הקשה? האם קבוצת נוירונים שבמוח תולעת כבר עושה זאת? האם זה מצריך CNS כלומר מערכת עצבים מרכזית? האם זה מצריך משהו נוסף, מעבר ל CNS של חרק או דג או חתול?

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

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

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

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

  6. מי שרוצה לקרוא דעה מעניינת על הקשר בין המוח לתורת הקוונטים מוזמן לקרוא את ספרו של פנרוז The Emperor's New Mind
    כמובן שהוא אינו מדבר על הצפנה קוואנטית אלא על תהליך קוואנטי של עיבוד מידע, תהליך שמזכיר יותר מחשב קוואנטי.

  7. ל-8 אכן תשובתך ל-6 מדויקת יותר מתשובתי!
    ל-9 שאלה מעניינית כמובן, ששואלים כולם, אך למה לחשוב כך? יש סיבה?
    אגב, למי שרוצה לראות בדיוק מה כתבו מישל בויר דן קניגסברג וטל מור, המאמר נמצא ב-
    Physical Review Letters, vol. 99,
    Issue 14, id. 140501 וניתן לראות גירסה (אולי לא לגמרי זהה) ב-
    arXiv:quant-ph/0703107

  8. ל 6 ולתשובה שניתנה ב 7:
    שאלתך, איש הקש, אינה על מלחמה בצופן אלא על מלחמה בתשדורת.
    כך גם תשובתו של טל בקשר לשיבוש.
    מלחמה בצופן היא תהליך המאפשר למאזין שהשדר אינו מכוון אליו לפענח את תוכנו. שיבוש אינו מאפשר לעשות זאת.

  9. ל-3 לימוד המיקום פוגע בתנע ולהיפך – לימוד התנע פוגע במיקום.

    ל-6 או משבשים, או מחפשים באג במימוש (בטיחות של פרוטוקול "אידיאלי" ובטיחות של המימוש של הפרוטוקול אינן בהכרח זהות). מימוש מושלם לרוב בלתי אפשרי טכנית, ומימוש פשטני עלול לכלול באגים. הדבר נכון גם להצפנה הקוונטית הרגילה, וגם ל RSA וכדומה. לפעמים קוראים להתקפות כאלו side-channel attacks

  10. אבדתם אותי בפיסקה השמינית ואני עוד מחוזק בידע מספר על תורת ההצפנה. אבל עדיין אספסוף.

    אז איך נלחמים בצופן כזה? פשוט משבשים אותו?

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

  12. עיקרון אי הודאות קובע שידיעת המיקום פוגע במהירות או פוגע בידיעת המהירות?

  13. כל הכבוד לחוקרים!
    למה זה כל כך משנה אם משתמשים באלכסוניות או באנכיות? לא הבנתי מה ההבדל..

  14. מעניין ונחמד לראות ולקרוא על מדע תאורתי שהופך למעשי.
    עד היישום של השיטה כל שנשאר לי זה לשאול:
    כמה עולה לשלוח בפדקס חבילה עם חלקיק אחד?
    ויותר מכך: האם זה שאני יודע את מיקום החבילה פוגע במהירות שלה?

    את התשובה לשאלה השניה אני כבר יכול לתת: כן!

כתיבת תגובה

האימייל לא יוצג באתר.

דילוג לתוכן