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

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

רקע

האלגוריתמים האסימטריים הנפוצים בשימוש מעשי כיום, מבוססים ברובם בעיקר על שתי בעיות מתורת המספרים הנחשבות "קשות" ונגזרותיהן; בעיית פירוק לגורמים ובעיית הלוגריתם הבדיד. כשהאחרונה מתחלקת לשני תחומים מתמטיים, שדה סופי ועקום אליפטי. ב-1994 הראה פיטר שורתבנית:הערה שאפשר לפרק לגורמים מספר גדול באמצעות אלגוריתם קוונטי, הנקרא על שמו אלגוריתם שור, בסיבוכיות זמן של $O({\log }^3(n))$, היעילה באופן דרמטי לעומת השיטות הידועות במחשב קלאסי. ב-1996 המציא לוב גרוברתבנית:הערה אלגוריתם קוונטי שנקרא אלגוריתם גרובר לחיפוש במבנה נתונים לא ממויין בזמן של $O(\sqrt{N})$. ההשלכה שלו מרחיקה לכת ויש לה השפעה עצומה על תורת ההצפנה, במיוחד על הצפנה א-סימטרית אך גם על הצפנה סימטרית. כאשר מחשב קוונטי גדול יהפוך למציאות, וישתמשו בו עם האלגוריתמים המנויים, שבירת המערכות הללו יכולה להתרחש בזמן פולינומי, שזה נמוך בהרבה מהאלגוריתם הטוב ביותר הידוע כיום הנקרא נפת שדה מספרים שהוא תת-מעריכי. משמעות הדבר שפרוטוקול דיפי-הלמן, RSA וכן כל נגזרותיהם המסתמכים על בעיות דומות יצאו מכלל שימוש.

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

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

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

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

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

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

אלגוריתמים פוסט קוונטיים

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

• הצפנה מבוססת גיבוב: הדוגמה הקלאסית למערכת כזו היא חתימה דיגיטלית מבוססת עץ גיבוב משנת 1979 של רלף מרקל מחלוצי הצפנת מפתח ציבורי, המבוססת על חתימת למפורט.
• הצפנה מבוססת קוד: הדוגמה הטובה ביותר היא הצפנת מקאליס משנת 1978 של רוברט מקאליס המבוססת על תורת הקודים.
• הצפנה מבוססת משוואה רבת משתנים: הדוגמה המבטיחה ביותר היא גרסאות של אלגוריתם חתימה דיגיטלית HFE של Jacques Patarin משנת 1996תבנית:הערה.
• הצפנה מבוססת סריג: סריגים נחקרו במשך שנים לטובת הצפנה, הדוגמה הידועה והמעשית ביותר היא אלגוריתם NTRU משנת 1996 של Jeffrey Hoffstein, Jill Pipher ו-Joseph Silvermanתבנית:הערה.
• הצפנה מבוססת איזוגניה: שיטת הצפנה חדשה יחסית המבוססת על איזוגניות בין יריעות אלגבריות ובפרט בין עקומים אליפטים, לדוגמה פרוטוקול שיתוף המפתח SIDH משנת 2011תבנית:הערה.
• הצפנה סימטרית או הצפנת מפתח סודי: הדוגמה הטובה ביותר היא תקן AES אך קיים מאגר עשיר של אלגוריתמים יעילים ובדוקים כמו Salsa20 או SNOW 3G ועוד רבים שנבחנו במשך שנים ולא נמצאו בהם חולשות משמעותיות. חלקם בטוחים יותר וחלקם פחות, כל אחד מהם מתאים לשימוש בהתאם לסיטואציה, חשיבות היעילות, פוטנציאל האיום, קונפיגורציה וכדומה. נכון להיום מרבית האלגוריתמים הבטוחים יעמדו במבחן האיום הקוונטי עם מפתחות באורך כפול מהאורך הנוכחי בלבד. עובדה זו מאפשרת מציאת חלופות להצפנה אסימטרית כמו העברת מפתח מבוססת הצפנה סימטרית של קרברוס.

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

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

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

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

תבנית:ערך מורחב הרעיון מאחורי הצפנה מבוססת קוד הוא בעיית פענוח סינדרומי, אם נתונה מטריצה $K$ מסדר $dt\times n$ (כאשר $n$ הוא פרמטר ביטחון, $d=\lceil \lg n\rceil$ ו-$t=\lfloor 0.5n/d\rfloor$) עם מקדמים מ-${𝔽}_2$ ומסר $m$, ההצפנה היא הכפלת המסר במטריצה $K$. כדי לשחזר את המסר יש צורך להפוך את הפעולה כלומר באמצעות אלגברה ליניארית למצוא וקטור $v$ המקיים $Kv=Km$, הבעיה היא שקיים מספר עצום של וקטורים מתוכם אפשר לבחור את $v$ ומציאת וקטור כזה בעל משקל $t$ היא בעיה קשה מאוד. המקבל יכול לפענח את המסר או לשחזר את הקוד על ידי הסתרה של מטריצת בדיקת זוגיות סודית כמו קוד גופה או קוד אחר בתוך המטריצה כך שיהיה פתרון פולינומי לבעיה על ידי אלגוריתם כמו אלגוריתם פטרסון. האלגוריתם המתואר הוא וריאציה של הצפנת מקאליס והמטריצה $K$ היא בעצם כפולה של שלוש מטריצות שונות $K=SHP$, כאשר $H$ היא מטריצת זוגיות של "גופה" וכדי להסתירה מעיני היריב מכפילים אותה ב-$S$ שהיא מטריצה אקראית הפיכה ו-$P$ פרמוטציה כלשהי. הפענוח מתבצע על ידי חישוב $HPm=Km{S}^{-1}$ ופענוח $H$ כדי לקבל את $Pm$ ואז $m=Pm{P}^{-1}$. אף על פי שהומצאה לפני כשלושים שנה, נותרה מערכת מקאליס בטוחה והיא יעילה מאוד, אך סובלת מבעיה מהותית והיא מפתחות עצומים (תקציר אורכי המפתחות של האלגוריתמים השונים מובא בטבלה להלן).

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

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

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

תבנית:ערך מורחב הבעיות מרכזיות בתורת הסריגים להן ישנן שימושים בקריפטוגרפיה הן בעיית הווקטור הקצר ביותר (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 המוגדר מעל עקומים סופר-סינגולרים מיוחדים החולקים מספר תכונות עם עקומים רגילים. פרוטוקול זה יעיל מאוד הן בזמן ריצתו והן בגודל המפתחות.

אורך מפתחות

בטבלה הבאה מובאים אורכי מפתחות ציבוריים ופרטיים של מספר אלגוריתמים פוסט-קוונטיים:

אלגוריתם	אורך מפתח ציבורי בסיביות	אורך מפתח פרטי בסיביות
Ring-LWEתבנית:הערה	6,595	14,000
NTRUתבנית:הערה	6,130	6,743
Rainbowתבנית:הערהתבנית:הערה	991,000	740,000
הצפנה מבוססת גיבובתבנית:הערה	36,000	36,000
McElieceתבנית:הערה	8,373,911	92,027
MDPC McElieceתבנית:הערהתבנית:הערה	65,542	4,384
SIDHתבנית:הערה	6,144	6,144

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

אתגרים

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

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

ראו גם

• הצפנה קוונטית

קישורים חיצוניים

• היערכות ארגונית בסייבר לעידן הפוסט-קוונטי, מערך הסייבר הלאומי, ינואר 2022

• MATZOV, Report on the Security of LWE: Improved Dual Lattice Attack, Zenodo, April 4, 2022

• תבנית:TheMarker