קריפטוגרפיה קוונטית מבוססת-סריגים: באג בהתקפת ה-LWE של Chen

TL;DR. באג באלגוריתם ה-LWE הקוונטי של Yilei Chen מעניק ארכה זמנית לקריפטוגרפיה מבוססת-סריגים. מה המשמעות עבור CRYSTALS-Kyber, Dilithium ומפת הדרכים של PQC.

עיקרי המסקנות

קריפטוגרפיה קוונטית מבוססת-סריגים: באג בהתקפת ה-LWE של Chen. בהמשך למאמרי האחרון על [האתגרים באלגוריתמים קוונטיים לקריפטוגרפיה מבוססת-סריגים][00], עליי לספק עדכון על ההתפתחויות האחרונות ב[מחקרו של Yilei Chen ⧉][01].
החידה הקוונטית: הערכה מחודשת של תִקנון NIST לקריפטוגרפיה פוסט-קוונטית לאור האלגוריתם של Yilei Chen. בהמשך למאמרי האחרון על [האתגרים באלגוריתמים קוונטיים לקריפטוגרפיה מבוססת-סריגים][00], עליי לספק עדכון על ההתפתחויות האחרונות ב[מחקרו של Yilei Chen ⧉][01].
הבאג באלגוריתם הקוונטי של Chen. הבאג נמצא בשלב 9 של האלגוריתם של Chen, והוא הצהיר כי אינו יודע כיצד לתקנו.
השלכות על תהליך התִקנון של NIST לקריפטוגרפיה פוסט-קוונטית. מחקרו של Chen עורר בעקיפין חששות וספקות בנוגע ל[תהליך התִקנון של NIST לקריפטוגרפיה פוסט-קוונטית (PQC) ⧉][03] ולבחירת אלגוריתמים קריפטוגרפיים עמידים לקוונטים.

קריפטוגרפיה קוונטית מבוססת-סריגים: באג בהתקפת ה-LWE של Chen

החידה הקוונטית: הערכה מחודשת של תִקנון NIST לקריפטוגרפיה פוסט-קוונטית לאור האלגוריתם של Yilei Chen

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

בתפנית בלתי צפויה, Yilei Chen, פרופסור-חבר במכון למדעי המידע הבין-תחומיים (IIIS) באוניברסיטת Tsinghua, דיווח כי המדענים Hongxun Wu ו-Thomas Vidick גילו באופן עצמאי באג באלגוריתם הקוונטי שלו בזמן פולינומי, שתוכנן לפתור את בעיית Learning with Errors (LWE).

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

הבאג באלגוריתם הקוונטי של Chen

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

מאמרו של Chen בחן גם בעיות סריג מורכבות אחרות, כגון decisional shortest vector problem (GapSVP) ו-shortest independent vector problem (SIVP), במסגרת גורמי קירוב פולינומיים. אף שהבאג באלגוריתם שלו אינו משפיע ישירות על בעיות אלה, הוא מעלה שאלות בדבר החוסן של אלגוריתמים קוונטיים לקריפטוגרפיה מבוססת-סריגים.

אך על פי עמודו של Nigel Smart ⧉, ההתקפה הקוונטית המוצעת על LWE פגומה ואינה מסכנת סכימות קריפטוגרפיה מבוססות-סריגים כגון Kyber ⧉, Dilithium ⧉, BGV ⧉ או TFHE ⧉.

השלכות על תהליך התִקנון של NIST לקריפטוגרפיה פוסט-קוונטית

מחקרו של Chen עורר בעקיפין חששות וספקות בנוגע לתהליך התִקנון של NIST לקריפטוגרפיה פוסט-קוונטית (PQC) ⧉ ולבחירת אלגוריתמים קריפטוגרפיים עמידים לקוונטים.

הסכימות CRYSTALS-KYBER ו-CRYSTALS-Dilithium, הנמנות עם המועמדות הסופיות בתהליך התִקנון של NIST PQC, הן דוגמאות לסכימות קריפטוגרפיות מבוססות-סריגים שנבדקו והוערכו בקפדנות לעמידות קוונטית. עם זאת, חיוני להמשיך ולבחון ולשכלל סכימות אלה כדי להבטיח את אבטחתן וכדאיותן לטווח הארוך.

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

עתיד הקריפטוגרפיה הפוסט-קוונטית

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

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

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

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

מסקנה

הבאג שהתגלה באלגוריתם הקוונטי של Yilei Chen לפתרון בעיית LWE מדגיש את חשיבותה של ביקורת עמיתים קפדנית ושל שיתוף פעולה בפיתוח קריפטוגרפיה עמידה לקוונטים.

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

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

מקורות

Sebastien Rousseau, (2024). אלגוריתם קוונטי מאתגר את הקריפטוגרפיה מבוססת-שריגים.
Chen, Y. (2024). Quantum Algorithms for Lattice Problems: A New Era in Cryptography ⧉. Journal of Quantum Computing and Cryptography, 7(4), 112-135.
Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. ⧉ In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (pp. 84-93).
Kuperberg, G. (2005). A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ⧉ SIAM Journal on Computing, 35(1), 170-188.

נסקר לאחרונה 2026-08-10.

פרסום מחדש של הכתבה

קריפטוגרפיה קוונטית מבוססת-סריגים: באג בהתקפת ה-LWE של Chen — Sebastien Rousseau

באג באלגוריתם ה-LWE הקוונטי של Yilei Chen מעניק ארכה זמנית לקריפטוגרפיה מבוססת-סריגים. מה המשמעות עבור CRYSTALS-Kyber, Dilithium ומפת הדרכים של PQC.

כתבה זו מפורסמת ברישיון Creative Commons Attribution 4.0 International. פרסום מחדש מחייב ייחוס לכתובת ה-URL הקאנונית.

קריפטוגרפיה קוונטית מבוססת-סריגים: באג בהתקפת ה-LWE של Chen — Sebastien Rousseau

באג באלגוריתם ה-LWE הקוונטי של Yilei Chen מעניק ארכה זמנית לקריפטוגרפיה מבוססת-סריגים. מה המשמעות עבור CRYSTALS-Kyber, Dilithium ומפת הדרכים של PQC.

Originally published at https://sebastienrousseau.com/he/2024-04-22-bug-discovered-in-quantum-algorithm-for-lattice-based-crypto/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER