הצפנה פוסט-קוונטית

הצפנה פּוֹסְט-קְוַנְטִית (באנגלית: Post-quantum cryptography) מתייחסת לאלגוריתמים קריפטוגרפיים (בדרך כלל של מפתח ציבורי) הנחשבים בטוחים נגד קריפטואנליזה המבוצעת עם מחשב קוונטי, בניגוד למרבית האלגוריתמים האסימטריים הפופולריים כמו אילו המבוססים על RSA ודיפי-הלמן, אותם ניתן יהיה לפרוץ בקלות עם מחשב קוונטי מעשי בקנה מידה גדול.

רקע

האלגוריתמים האסימטריים הנפוצים בשימוש מעשי כיום, מבוססים ברובם בעיקר על שתי בעיות מתורת המספרים הנחשבות "קשות" ונגזרותיהן; בעיית פירוק לגורמים ובעיית הלוגריתם הבדיד. כשהאחרונה מתחלקת לשני תחומים מתמטיים, שדה סופי ועקום אליפטי. ב-1994 הראה פיטר שור שאפשר לפרק לגורמים מספר גדול באמצעות אלגוריתם קוונטי הנקרא על שמו אלגוריתם שור בסיבוכיות זמן של , היעילה באופן דרמטי לעומת השיטות הידועות במחשב קלאסי. ב-1996 המציא לוב גרובר אלגוריתם קוונטי שנקרא אלגוריתם גרובר לחיפוש במבנה נתונים לא ממויין בזמן של . ההשלכה שלו מרחיקה לכת ויש לה השפעה עצומה על תורת ההצפנה, במיוחד על הצפנה א-סימטרית אך גם על הצפנה סימטרית. עם האלגוריתמים המנויים כאשר מחשב קוונטי גדול יהפוך למציאות, שבירת המערכות הללו יכולה להתרחש בזמן פולינומי, שזה נמוך בהרבה מהאלגוריתם הטוב ביותר הידוע כיום הנקרא נפת שדה מספרים שהוא תת-מעריכי. משמעות הדבר שפרוטוקול דיפי-הלמן, RSA וכן כל נגזרותיהם המסתמכים על בעיות דומות יצאו מכלל שימוש כליל.
בשנים האחרונות חלה התקדמות בפיתוח מחשבים קוונטיים. באוגוסט 2015 הכריזה חברת D-Wave הקנדית על מחשב קוונטי "אנלוגי" מעשי הנקרא D-Wave 2X בקנה מידה של +1000 קיוביטים. באותה עת פורסם שהמחשב הותקן בהצלחה במעבדת הבינה המלאכותית הקוונטית השייכת למיזם משותף של נאס"א וגוגל. יש לציין שמחשב קוונטי מסוג זה אינו מתאים לשימוש כללי ואינו רלוונטי לקריפטואנליזה, הוא מתאים בעיקר לפתרון בעיות מיוחדות בתחום אופטימיזציה, ביואינפורמטיקה וכדומה. אף על פי שהמחשבים הקוונטיים הדיגיטליים המיוצרים, נכון לשנת 2016, עדיין קטנים מדי מכדי לבצע עליהם התקפה מלאה נגד האלגוריתמים האסימטריים עם מפתחות באורכים המומלצים על ידי התקנים הבינלאומיים, ישנן הערכות שמחשבים קוונטיים בהיקף מלא עומדים להיות זמינים בתוך כעשור, זאת בניגוד להערכות קודמות. מסיבה זו הקהילה הקריפטוגרפית נערכת בתקופה זו למעבר לעידן קוונטי והעניין בנושא גובר מצד האקדמיה והתעשייה בעיקר דרך כנסים של PQCrypto המתקיימים אחת לשנה מאז 2006 וכן קבוצות מחקר של ארגונים כמו ETSI ו-IEEE.

הצפנה פוסט-קוונטית לעומת הצפנה קוונטית

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

הצפנה סימטרית

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

הצפנה מבוססת קוד

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

הצפנה מבוססת משוואה רבת משתנים

אלגוריתם HFE (קיצור של Hidden Fields Equations) הוא מערכת הצפנה רבת משתנים (multivariate cryptography) המבוססת על מערכת משוואות ריבועיות מרובות נעלמים, שהדיעה הרווחת שהיא תהיה עמידה נגד התקפת מחשב קוונטי. הרעיון הבסיסי העומד מאחורי הצפנה כזו הוא הקושי שבפתרון מערכת משוואות פולינומיות מרובת משתנים ממעלה שנייה או יותר, מעל שדה סופי שהיא בעיה NP-קשה או בעיית NP-שלמה. נכון להיום הניסיונות לפתח מערכת הצפנה מבוססת משוואות ריבועיות מרובות משתנים לא צלחו. ז'ק פטרין המציא ב-1997 חתימה דיגיטלית אסימטרית מעשית בשיטת Oil and Vinegar (הסתרת משוואות ריבועיות ב- נעלמים הנקראים "שמן" ו- נעלמים הנקראים "חומץ" מעל שדה סופי עם פונקציות ליניאריות סודיות, כאשר ). שמיר וקיפניס הוכיחו שהיא אינה בטוחה. וריאציה אחרת שלה הנקראת "Unbalanced Oil and Vinegar" שבה  טובה יותר וביטחונה הוא שאלה פתוחה.

הצפנה מבוססת סריג

הבעיות מרכזיות בתורת הסריגים להן ישנן שימושים בקריפטוגרפיה הן בעיית הווקטור הקצר ביותר (shortest vector problem) ובעיית הווקטור הקרוב ביותר (closest vector problem). אלגוריתם ההצפנה NTRU, אשר פותח בשנת 1996, הוא המוכר ביותר ומבוסס על בעיית הווקטור הקצר ביותר.
בשנת 2005 עודד רגב הגדיר את בעיית "למידה עם טעויות" (learning with errors) והוכיח כי בהינתן מחשב קוונטי, הבעיה שקולה אסימפטוטית למספר בעיות בתורת הסריגים, הנחשבות לבעיות קשות. הרעיון הכללי הוא לבסס מערכת הצפנת מפתח ציבורי על הקושי בהבחנה בין פונקציות ליניאריות אקראיות המוסתרות על ידי כמות מועטה של "רעש" מפונקציות אקראיות אמיתיות. רגב בנה פרוטוקול הצפנה באותו השם המבוסס על בעיה זו.
בעיית הלמידה עם טעויות ניתנת להכללה מעל מודולים, והמקרה הפרטי המעניין ביותר הוא מעל חוגים (ring learning with errors), מקרה נוסף בו ישנה הוכחה קווטנית לשקילות הבעיה לבעיות קשות בתורת הסריגים. פרוטוקולי הצפנה מעניינים במיוחד הם פרוטוקול שיתוף מפתח ring learning with errors key exchange ואלגוריתם החתימה הדיגיטלית ring learning with errors signature.
חתימה דיגיטלית BLISS שפותחה ב-2015 אף היא מבוססת על הצפנת סריגים ונחשבת אך לא מוכחת כבטוחה בהנחה שבעיית הווקטור הקרוב ביותר קשה והיא מועמדת טובה להצפנה פוסט קוונטית.

הצפנה מבוססת איזוגניה

הצפנה מבוססת איזוגניה היא נושא חדש שנמצא במחקר ועוסק במועמדים טובים להצפנת מפתח ציבורי פוסט-קוונטית המבוססת על הקושי בחישוב איזוגניה בין שני עקומים אליפטים נתונים (ובאופן כללי, בין שני עקומים הייפר-אליפטים). ישנם מספר מועמדים לפרוטוקולי שיתוף מפתח מבוססי איזוגניות. תחילה הוצע להשתמש בעקומים אליפטים רגילים (ordinary), אך הפרוטוקול איננו יעיל (מהיר) מספיק וכמו כן נמצא אלגוריתם קוונטי למציאת איזוגניות בין עקומים רגילים בעל סיבוכיות זמן תת-מעריכית. כעת המחקר מתמקד בעקומים סופר-סינגולרים, המאפשרים פרוטוקל יעיל יותר וכן זמן הריצה של האלגוריתמים הידועים לשבירת הצופן הוא מעריכי.
ב-2011 פותח אלגוריתם Supersingular isogeny Diffie–Hellman (בקיצור SIDH) הדומה לפרוטוקול העברת מפתח דיפי-הלמן הנפוץ כיום בשימוש במערכות אבטחה רבות בשתי גרסאות DHE ו-ECDHE (בעקום אליפטי). האלגוריתם פותח מתוך מטרה שיהיה מועמד ראוי להחלפת הפרוטוקולים הקודמים ובעל תכונות טובות כמו מפתח קצר וביטחון לפנים (forward secrecy). פרוטוקול נוסף הצובר עניין הוא CSIDH המוגדר מעל עקומים סופר-סינגולרים מיוחדים החולקים מספר תכונות עם עקומים רגילים. פרוטוקול זה יעיל מאוד הן בזמן ריצתו והן בגודל המפתחות.