הצגת המקור של הדף "הצפנה פוסט-קוונטית"

'''הצפנה פּוֹסְט-קְוַנְטִית''' (ב[[אנגלית]]: '''Post-quantum cryptography''') היא פיתוח של [[אלגוריתם|אלגוריתמים]] [[קריפטוגרפיה|קריפטוגרפיים]] חסינים בפני פיצוח על ידי מחשבים קוואנטיים. שיטות ההצפנה הא-סימטריות (שבהן יש [[מפתח ציבורי]] גלוי ומפתח אישי סודי), כדוגמת הצפנה [[RSA]] והצפנת-[[ECC (הצפנה)|ECC]], מתבססות על הקושי של מחשב לפצח אותן בזמן סביר. אלה השיטות המקובלות אבל מחשב קוואנטי עתידי יוכל לפצח אותן בשבריר מהזמן הזה. האלגוריתמים הסימטריים להצפנה שנהוגים נחשבים חסינים גם בפני מחשב קוואנטי. חברות וארגונים מתכוננים ליום תאורטי - המכונה QDay - שבו יהיו מחשבים קוואנטיים גדולים מספיק שיוכלו לפצח את ההצפנות הנהוגות.{{הערה|Daniel J. Bernstein (2009). "[http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf Introduction to post-quantum cryptography]". (Introductory chapter to book "Post-quantum cryptography").}}{{הערה|שם=:0|{{ynet|טל שחף|ארה"ב פיתחה שיטה לפתרון אחת הסכנות הגדולות על ביטחון העולם|digital/technology/article/rklqiemcc|8 באוגוסט 2024}}}}

==רקע==
האלגוריתמים האסימטריים הנפוצים בשימוש מעשי כיום, מבוססים ברובם בעיקר על שתי [[בעיה פתוחה במתמטיקה|בעיות]] מ[[תורת המספרים]] הנחשבות "קשות" ונגזרותיהן; [[פירוק לגורמים של מספר שלם|בעיית פירוק לגורמים]] ו[[בעיית הלוגריתם הבדיד]]. כשהאחרונה מתחלקת לשני תחומים מתמטיים, [[שדה סופי]] ו[[הצפנה מבוססת עקום אליפטי|עקום אליפטי]]. ב-1994 הראה [[פיטר שור]]{{הערה|Peter W. Shor (1995-08-30). "[http://arxiv.org/abs/quant-ph/9508027 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer]"}} שאפשר לפרק לגורמים מספר גדול באמצעות אלגוריתם קוונטי, הנקרא על שמו [[אלגוריתם שור]], ב[[סיבוכיות זמן]] של <math>O(\log^3(n))</math>, היעילה באופן דרמטי לעומת השיטות הידועות במחשב קלאסי. ב-1996 המציא [[לוב גרובר]]{{הערה|Grover L.K.: [http://arxiv.org/abs/quant-ph/9605043 A fast quantum mechanical algorithm for database search], Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212}} אלגוריתם קוונטי שנקרא [[אלגוריתם גרובר]] לחיפוש ב[[מבנה נתונים]] לא ממויין בזמן של <math>O(\sqrt{N})</math>. ההשלכה שלו מרחיקה לכת ויש לה השפעה עצומה על תורת ההצפנה, במיוחד על הצפנה א-סימטרית אך גם על [[הצפנה סימטרית]]. כאשר מחשב קוונטי גדול יהפוך למציאות, וישתמשו בו עם האלגוריתמים המנויים, שבירת המערכות הללו יכולה להתרחש ב[[זמן פולינומי]], שזה נמוך בהרבה מהאלגוריתם הטוב ביותר הידוע כיום הנקרא [[נפת שדה מספרים]] שהוא תת-מעריכי. משמעות הדבר שפרוטוקול דיפי-הלמן, RSA וכן כל נגזרותיהם המסתמכים על בעיות דומות יצאו מכלל שימוש<ref name=":0" />.

בשנים האחרונות חלה התקדמות בפיתוח מחשבים קוונטיים. באוגוסט [[2015]] הכריזה חברת [[D-Wave]] הקנדית על מחשב קוונטי "אנלוגי" מעשי הנקרא D-Wave 2X בקנה מידה של +1000 [[קיוביט]]ים. באותה עת פורסם שהמחשב הותקן בהצלחה ב[[מעבדת הבינה המלאכותית הקוונטית]] השייכת ל[[מיזם משותף]] של [[נאס"א]] ו[[גוגל (חברה)|גוגל]]. מחשב קוונטי מסוג זה אינו מתאים לשימוש כללי ואינו רלוונטי לקריפטואנליזה, הוא מתאים בעיקר לפתרון בעיות מיוחדות בתחום [[אופטימיזציה (מתמטיקה)|אופטימיזציה]], [[ביואינפורמטיקה]] וכדומה. אף על פי שהמחשבים הקוונטיים הדיגיטליים המיוצרים, נכון לשנת [[2016]], עדיין קטנים מדי מכדי לבצע באמצעותם התקפה מלאה נגד האלגוריתמים האסימטריים עם מפתחות באורכים המומלצים על ידי התקנים הבינלאומיים, ישנן הערכות שמחשבים קוונטיים בהיקף מלא עומדים להיות זמינים בתוך כעשור, זאת בניגוד להערכות קודמות. מסיבה זו הקהילה הקריפטוגרפית נערכת בתקופה זו למעבר לעידן קוונטי והעניין בנושא גובר מצד האקדמיה והתעשייה בעיקר דרך כנסים של PQCrypto{{הערה|[http://spectrum.ieee.org/computing/software/cryptographers-take-on-quantum-computers Cryptographers Take On Quantum Computers]}} המתקיימים אחת לשנה מאז 2006 וכן קבוצות מחקר של ארגונים כמו [[ETSI]] ו-[[IEEE]]{{הערה|1=[http://www.etsi.org/news-events/events/770-etsi-crypto-workshop-2014?highlight=YTozOntpOjA7czo3OiJxdWFudHVtIjtpOjE7czo0OiJzYWZlIjtpOjI7czoxMjoicXVhbnR1bSBzYWZlIjt9 ETSI 2nd Quantum-Safe Crypto Workshop in partnership with the IQC]}}.

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

לאור זאת יש מי שחושש שבעידן הפוסט-קוונטי יחזרו לשיטות הישנות של הסתרת מידע באמצעות [[כספת|כספות]], תיקים נעולים אזוקים בשלשלאות לזרוע או מפגשים אישיים חשאיים. אולי מכיוון שקל לטעות בין הצפנה פוסט-קוונטית לבין הצפנה קוונטית. המציאות היא שכנראה הקריפטוגרפיה לא תשתנה במידה ניכרת והמעבר יהיה די חלק<ref name=":0" />.

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

==אלגוריתמים פוסט קוונטיים==
אלגוריתמים אחדים ישרדו את העידן הפוסט-קוונטי ואחרים לא. [[RSA]], [[Digital Signature Algorithm|DSA]], [[הצפנה מבוססת עקום אליפטי|ECC]] ודומיהם לא ישרדו. לעומתם קיימים מזה שנים רבות אלגוריתמים טובים הבטוחים הן בפני איום קלאסי והן בפני איום קוונטי. הסיבה שלא משתמשים בהם כיום נובעת אך ורק משקולי יעילות. המעבר לעידן הפוסט-קוונטי מחייב שימוש באלגוריתמים שכיום אינם יעילים במונחי מחשוב ואינם מתאימים לשימוש מאסיבי, אם כי המחקר עדיין בעיצומו וייתכנו שיפורים מרחיקי לכת<ref name=":0" />. אלגוריתמים פוסט-קוונטיים שהדיעה הרווחת לגביהם שהם עמידים נגד [[קריפטואנליזה]] קוונטית קיימים אך חלקם לא יעילים, חלקם ללא הוכחה מתמטית מוצקה וחלקם צעירים מאוד. אפשר לבסס הצפנה פוסט-קוונטית על מספר בעיות מתמטיות קשות שמהן ניתן להכין [[פונקציה חד-כיוונית]] המתאימה לצורך קריפטוגרפי ואשר הדעה הרווחת לגביהן שהן יוותרו בטוחות גם נוכח איום מחשב קוונטי, מהן ניתן למנות את:
*'''הצפנה מבוססת גיבוב''': הדוגמה הקלאסית למערכת כזו היא [[עץ מרקל|חתימה דיגיטלית מבוססת עץ גיבוב]] משנת 1979 של [[רלף מרקל]] מחלוצי הצפנת מפתח ציבורי, המבוססת על [[חתימת למפורט]].
*'''הצפנה מבוססת קוד''': הדוגמה הטובה ביותר היא [[הצפנת מקאליס]] משנת 1978 של [[רוברט מקאליס]] המבוססת על [[תורת הקודים]].
*'''הצפנה מבוססת משוואה רבת משתנים''': הדוגמה המבטיחה ביותר היא גרסאות של אלגוריתם [[חתימה דיגיטלית]] [[HFE]] של [[Jacques Patarin]] משנת 1996{{הערה|[http://www.cryptosystem.net/hfe.pdf Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms]}}.
*'''[[הצפנה מבוססת סריג]]''': סריגים נחקרו במשך שנים לטובת הצפנה, הדוגמה הידועה והמעשית ביותר היא אלגוריתם [[NTRU]] משנת 1996 של Jeffrey Hoffstein, Jill Pipher ו-Joseph Silverman{{הערה|1=[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.8422&rep=rep1&type=pdf NTRU: A Ring-Based Public Key Cryptosystem]|שם=NTRU}}.
*'''הצפנה מבוססת איזוגניה''': שיטת הצפנה חדשה יחסית המבוססת על [[איזוגניות]] בין [[יריעה אלגברית|יריעות אלגבריות]] ובפרט בין [[עקום אליפטי|עקומים אליפטים]], לדוגמה [[פרוטוקול שיתוף מפתח|פרוטוקול שיתוף המפתח]] SIDH משנת 2011{{הערה|שם=ISOGENIES|[https://eprint.iacr.org/2011/506 Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies]}}.
*'''הצפנה סימטרית''' או הצפנת מפתח סודי: הדוגמה הטובה ביותר היא תקן [[AES]] אך קיים מאגר עשיר של אלגוריתמים יעילים ובדוקים כמו [[Salsa20]] או [[SNOW#SNOW 3G|SNOW 3G]] ועוד רבים שנבחנו במשך שנים ולא נמצאו בהם חולשות משמעותיות. חלקם בטוחים יותר וחלקם פחות, כל אחד מהם מתאים לשימוש בהתאם לסיטואציה, חשיבות היעילות, פוטנציאל האיום, קונפיגורציה וכדומה. נכון להיום מרבית האלגוריתמים הבטוחים יעמדו במבחן האיום הקוונטי עם מפתחות באורך כפול מהאורך הנוכחי בלבד. עובדה זו מאפשרת מציאת חלופות להצפנה אסימטרית כמו העברת מפתח מבוססת הצפנה סימטרית של [[קרברוס (פרוטוקול)|קרברוס]].

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

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

===הצפנה מבוססת קוד===
{{ערך מורחב|הצפנה מבוססת קודים}}
הרעיון מאחורי [[הצפנה מבוססת קודים|הצפנה מבוססת קוד]] הוא בעיית [[קוד ליניארי#פענוח סינדרומי|פענוח סינדרומי]], אם נתונה מטריצה <math>K</math> מסדר <math>dt\times n</math> (כאשר <math>n</math> הוא [[פרמטר]] ביטחון, <math>d=\left\lceil\lg n\right\rceil </math> ו-<math>t=\left\lfloor 0.5n/d\right\rfloor</math>) עם מקדמים מ-<math>\mathbb{F}_2 </math> ומסר <math>m</math>, ההצפנה היא [[כפל מטריצות|הכפלת]] המסר במטריצה <math>K</math>. כדי לשחזר את המסר יש צורך להפוך את הפעולה כלומר באמצעות [[אלגברה ליניארית]] למצוא וקטור <math>v</math> המקיים <math>Kv=Km</math>, הבעיה היא שקיים מספר עצום של וקטורים מתוכם אפשר לבחור את <math>v</math> ומציאת וקטור כזה בעל משקל <math>t</math> היא בעיה קשה מאוד. המקבל יכול לפענח את המסר או לשחזר את הקוד על ידי הסתרה של מטריצת בדיקת [[סיבית זוגיות|זוגיות]] סודית כמו [[קודי גופה|קוד גופה]] או קוד אחר בתוך המטריצה כך שיהיה פתרון פולינומי לבעיה על ידי אלגוריתם כמו [[אלגוריתם פטרסון]]. האלגוריתם המתואר הוא וריאציה של [[הצפנת מקאליס]] והמטריצה <math>K</math> היא בעצם כפולה של שלוש מטריצות שונות <math>K=SHP</math>, כאשר <math>H</math> היא מטריצת זוגיות של "גופה" וכדי להסתירה מעיני היריב מכפילים אותה ב-<math>S</math> שהיא [[מטריצה]] אקראית הפיכה ו-<math>P</math> פרמוטציה כלשהי. הפענוח מתבצע על ידי חישוב <math>HPm=KmS^{-1}</math> ופענוח <math>H</math> כדי לקבל את <math>Pm</math> ואז <math>m=PmP^{-1}</math>. אף על פי שהומצאה לפני כשלושים שנה, נותרה מערכת מקאליס בטוחה והיא יעילה מאוד, אך סובלת מבעיה מהותית והיא מפתחות עצומים (תקציר אורכי המפתחות של האלגוריתמים השונים מובא בטבלה להלן).

===הצפנה מבוססת משוואה רבת משתנים===
{{ערך מורחב|הצפנה מרובת משתנים}}
אלגוריתם [[HFE]] (קיצור של Hidden Fields Equations) הוא מערכת [[הצפנה מרובת משתנים|הצפנה רבת משתנים]] (multivariate cryptography) המבוססת על מערכת [[משוואה ממעלה שנייה|משוואות ריבועיות]] מרובות נעלמים, שהדיעה הרווחת שהיא תהיה עמידה נגד התקפת מחשב קוונטי. הרעיון הבסיסי העומד מאחורי הצפנה כזו הוא הקושי שבפתרון מערכת משוואות פולינומיות מרובת משתנים ממעלה שנייה או יותר, מעל שדה סופי שהיא בעיה [[NP-קשה]] או בעיית [[NP-שלמה]]. נכון להיום הניסיונות לפתח מערכת הצפנה מבוססת משוואות ריבועיות מרובות משתנים לא צלחו. ז'ק פטרין המציא ב-1997 חתימה דיגיטלית אסימטרית מעשית בשיטת Oil and Vinegar (הסתרת משוואות ריבועיות ב-<math>n</math> נעלמים הנקראים "שמן" ו-<math>v</math> נעלמים הנקראים "חומץ" מעל [[שדה סופי]] עם [[פונקציה ליניארית|פונקציות ליניאריות]] סודיות, כאשר <math>v=n</math>). שמיר וקיפניס הוכיחו{{הערה|A. Kipnis, A. Shamir, Cryptanalysis of the Oil and Vinegar Signature Scheme, Proceedings of CRYPTO’98, Springer, LNCS no1462, pp. 257-266}} שהיא אינה בטוחה. וריאציה אחרת שלה הנקראת "Unbalanced Oil and Vinegar"{{הערה|[http://link.springer.com/chapter/10.1007%2F3-540-48910-X_15 Unbalanced Oil and Vinegar Signature Schemes]}} שבה <math>v>n</math> טובה יותר וביטחונה הוא שאלה פתוחה{{הערה|Bulygin, Stanislav; Petzoldt; Buchmann (2010). "[http://link.springer.com/chapter/10.1007%2F978-3-642-17401-8_3 Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks]". Progress in Cryptology – INDOCRYPT 2010. Lecture Notes in Computer Science (Springer) 6498: 17–32.}}.

=== הצפנה מבוססת סריג ===
{{ערך מורחב|הצפנה מרובת משתנים}}
הבעיות מרכזיות בתורת הסריגים להן ישנן שימושים בקריפטוגרפיה הן בעיית הווקטור הקצר ביותר (shortest vector problem) ו[[בעיית הווקטור הקרוב ביותר]] (closest vector problem). אלגוריתם ההצפנה NTRU{{הערה|1=|שם=NTRU}}, אשר פותח בשנת 1996, הוא המוכר ביותר ומבוסס על בעיית הווקטור הקצר ביותר.

בשנת 2005 עודד רגב הגדיר את בעיית "למידה עם טעויות" (learning with errors) והוכיח כי בהינתן מחשב קוונטי, הבעיה שקולה אסימפטוטית למספר בעיות בתורת הסריגים, הנחשבות לבעיות קשות{{הערה|1=Regev, Oded (2005-01-01). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776. doi:10.1145/1060590.1060603. {{ISBN|978-1581139600}}.|שם=}}. הרעיון הכללי הוא לבסס מערכת הצפנת מפתח ציבורי על הקושי בהבחנה בין פונקציות ליניאריות אקראיות המוסתרות על ידי כמות מועטה של "רעש" מפונקציות אקראיות אמיתיות. רגב בנה פרוטוקול הצפנה באותו השם המבוסס על בעיה זו.

בעיית הלמידה עם טעויות ניתנת להכללה מעל [[מודול (מבנה אלגברי)|מודולים]], והמקרה הפרטי המעניין ביותר הוא מעל [[חוג (מבנה אלגברי)|חוגים]] (ring learning with errors), מקרה נוסף בו ישנה הוכחה קוונטית לשקילות הבעיה לבעיות קשות בתורת הסריגים. פרוטוקולי הצפנה מעניינים במיוחד הם [[פרוטוקול שיתוף מפתח]] ring learning with errors key exchange ואלגוריתם ה[[חתימה דיגיטלית|חתימה הדיגיטלית]] ring learning with errors signature.

חתימה דיגיטלית [[BLISS]]{{הערה|[https://eprint.iacr.org/2013/383.pdf Lattice Signatures and Bimodal Gaussians], Leo Ducas and Alain Durmus and Tancrede Lepoint and Vadim Lyubashevsky}} שפותחה ב-2015 אף היא מבוססת על הצפנת סריגים ונחשבת אך לא מוכחת כבטוחה בהנחה שבעיית הווקטור הקרוב ביותר קשה והיא מועמדת טובה להצפנה פוסט קוונטית.

=== הצפנה מבוססת איזוגניה ===
{{ערך מורחב|הצפנה מרובת משתנים}}
הצפנה מבוססת איזוגניה היא נושא חדש שנמצא במחקר ועוסק במועמדים טובים להצפנת מפתח ציבורי פוסט-קוונטית המבוססת על הקושי בחישוב [[איזוגניה]] בין שני עקומים אליפטיים נתונים (ובאופן כללי, בין שני [[עקום הייפר-אליפטי|עקומים הייפר-אליפטים]]). ישנם מספר מועמדים לפרוטוקולי שיתוף מפתח מבוססי איזוגניות. תחילה הוצע להשתמש בעקומים אליפטיים רגילים (ordinary), אך הפרוטוקול איננו יעיל (מהיר) מספיק וכמו כן נמצא אלגוריתם קוונטי למציאת איזוגניות בין עקומים רגילים בעל [[סיבוכיות זמן]] תת-מעריכית. כעת המחקר מתמקד בעקומים סופר-סינגולרים, המאפשרים פרוטוקל יעיל יותר וכן זמן הריצה של האלגוריתמים הידועים לשבירת הצופן הוא מעריכי.

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

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

{| class="wikitable"
|-
! אלגוריתם !! אורך מפתח ציבורי בסיביות !! אורך מפתח פרטי בסיביות
|-
| [[Ring-LWE]]{{הערה|[http://eprint.iacr.org/2015/138 A Practical Key Exchange for the Internet using Lattice Cryptography]}} || 6,595 || 14,000
|-
| [[NTRU]]{{הערה|1=Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.8422&rep=rep1&type=pdf NTRU: A Ring Based Public Key Cryptosystem]. In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.}} || 6,130 || 6,743
|-
| [[Rainbow (הצפנה)|Rainbow]]{{הערה|Ding J., Schmidt D.: [http://link.springer.com/chapter/10.1007%2F11496137_12 Rainbow, a new multivariate polynomial signature scheme]. In Ioannidis, J.,Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS vol. 3531, pp. 164–175 Springer, Heidelberg (2005)}}{{הערה|[https://eprint.iacr.org/2010/437.pdf Selecting Parameters for the Rainbow Signature Scheme]}} || 991,000 || 740,000
|-
| הצפנה מבוססת גיבוב{{הערה|1=[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.146.5251&rep=rep1&type=pdf One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal]}} || 36,000 || 36,000
|-
| [[הצפנת מקאליס|McEliece]]{{הערה|שם=pqcrypto|[http://pqcrypto.eu.org/docs/initial-recommendations.pdf Post-Quantum Cryptography for Long-Term Security]}} || 8,373,911 || 92,027
|-
| [[MDPC McEliece]]{{הערה|שם=pqcrypto|}}{{הערה|[https://eprint.iacr.org/2012/409.pdf MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes]}} || 65,542 || 4,384
|-
| [[SIDH]]{{הערה|שם=ISOGENIES|}} || 6,144 || 6,144
|}

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

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

==ראו גם==
*[[הצפנה קוונטית]]

==קישורים חיצוניים==
*[https://www.gov.il/he/departments/general/quantum_computing היערכות ארגונית בסייבר לעידן הפוסט-קוונטי], [[מערך הסייבר הלאומי]], ינואר 2022
<div class="mw-content-ltr">
* [[מצו"ב|MATZOV]], [https://zenodo.org/record/6493704#.Ym1s6trP3cs Report on the Security of LWE: Improved Dual Lattice Attack], Zenodo, April 4, 2022
</div>

* {{TheMarker|רן בר-זיק|גוגל תשלב אלגוריתם פוסט קוונטי במוצריה. אתם עוד לא יודעים זאת - אך מדובר ברעידת אדמה|0000018a-1da6-df73-a5eb-5dbf2dfb0000|27 באוגוסט 2023}}

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}
[[קטגוריה:הצפנה]]
[[קטגוריה:חישוב קוונטי]]