כיצד מנסים ארגוני התקינה בעולם להתאים עצמם ליום שבו מחשבים קוונטיים יתפסו מקום חשוב בחיינו? ולמה זה קשה בהרבה משנדמה לנו?

איורים: Dall-E

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

אוניברסיטאות וחברות רבות משקיעות כסף ומשאבים בפיתוח מחשבים ואלגוריתמים קוונטיים. לשם הדוגמה נתמקד ב-IBM .IBM מתכננת להוציא לשוק ב-2022 מחשב קוונטי של 433 קיוביט [3]. למה זה מעניין? IBM מוציאה מחשב קוונטי חזק וגדול יותר כאחת לשנה מאז 2019, ובכל שנה מכפילה בערך פי 2 את גודל המחשב הקוונטי שלה. ב-2025 הם מכוונים להגיע ל-4000 קיוביטים, וזה כבר צריך לעניין אתכם. 4000 קיוביטים מקרבים אותנו למצב שבו מחשבים קוונטיים יוכלו לסכן את ההצפנות הקלאסיות שהאינטרנט ותעשיות רבות מתבססים עליהן. 

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

בשנת 2017 פרסם ארגון התקנים האמריקאי NIST (National Institute of Standards and Technology) קריאה להצעות לאלגוריתמים כאלו בדיוק, להצפנה ולחתימה על קבצים והודעות, תחת הכותרת "שיטות הצפנה פוסט-קוונטיות" - כהכנה לכך שבשנים הקרובות יהפכו מחשבים קוונטיים לעובדה מוגמרת. שיטות אלו עמידות למול אלגוריתם שור, אך אינן יעילות כמו השיטות הקלאסיות - הן דורשות יותר זמן ומשאבי חישוב. בצירוף עם הדרישה שהאלגוריתמים יוכלו לרוץ ביעילות יחסית על מחשבים קלאסיים - מדובר באתגר משמעותי. מפתחות ההצפנה הפוסט-קוונטית ארוכים משמעותית ביחס לאלו הקלאסיים: לעומת כמה מאות ביטים או אלפי ביטים בודדים בהצפנות קלאסיות, הצפנות קוונטיות משתמשות במפתחות באורך מאות אלפי ביטים ואף מיליונים. כתוצאה מכך יעילות ההצפנה של השיטות הפוסט-קוונטיות נמוכה יחסית. ההנחה היא שברגע שייקבעו האלגוריתמים ושיטות ההצפנה של העידן הפוסט-קוונטי, נוכל לפתח מחשבים וכלים מתאימים לייעול תהליך ההצפנה, בתקווה שנוכל להגיע לביצועים דומים לביצועים היום. גם אם נצליח למצוא אלגוריתם יעיל וחסין מול אלגוריתם שור וכוח המחשוב הקלאסי הקיים כיום, לא נוכל להבטיח שלא יפרוץ אותו אף אלגוריתם קוונטי או קלאסי אחר שעדיין לא התגלה. גיבוש תקינת האלגוריתמים היא תהליך מתמשך: קהילת הקריפטוגרפיה מציעה שיטות וארגון התקנים בוחר את המבטיחים ביותר. כאשר חלק מהאלגוריתמים המוצעים נפרצים באופן מלא או חלקי, התקינה מתעדכנת. 

בתחילת השנה (ינואר 2022) הכריז NIST על רשימת האלגוריתמים הפיינליסטים, המבוססים על בעיות מתמטיות מעולם הפיזיקה וכן על הרחבות של בעיות מתמטיות אחרות מעולם הקריפטוגרפיה. האלגוריתמים החדשים מסתמכים על שיטות ועל טריקים אחרים משל השיטות הקלאסיות. בפברואר השנה נפרץ אחד האלגוריתמים האלו - Rainbow Signature Scheme המשמש לחתימה על הודעות קבצים - באמצעות מחשב קלאסי ובמהלך סוף שבוע אחד [5]. בסוף יולי האחרון יצאה הודעה שנייה ודרמטית עוד יותר על אלגוריתם SIKE, שנתמך על ידי מיקרוסופט ונפרץ לגמרי בפרק זמן של שעה [6].

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

ליווי מדעי: דוד קייסר

עריכה: שיר רוזנבלום-מן

מקורות לקריאה נוספת:

[1] פוסט על מחשוב קוונטי

[2] פוסט על אלגוריתם שור למחשב קוונטי 

[3] מפת הדרכים של IBM לעידן המחשוב הקוונטי 

[4] פוסט על הקסם בהצפנה קוונטית 

[5] מאמר על שבירת חתימת Rainbow Signature Scheme 

[6] מאמר על שבירת SIDH