GGH

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

פונקציה חד-כיוונית עם דלת מלכודת

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

סריג ובעיית הווקטור הקרוב ביותר

ערך מורחב – הצפנה מבוססת סריג

בהינתן קבוצה של $n$ וקטורים בלתי תלויים מעל $\mathbb {R} ^{n}$, הסריג (Lattice) $L$ הנפרש על ידי $B=\{\mathbf {b} _{1},\mathbf {b} _{2},...,\mathbf {b} _{n}\}$ הוא קבוצת כל הצירופים הליניאריים האפשריים של הווקטורים $\mathbf {b} _{i}$ עם מקדמים שלמים, כלומר:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(B)\ \overset{\underset{\mathrm{def}}{}}{=}\ \left \{ \sum_i k_i\mathbf{b}_i : k_i\in\mathbb{Z} \text{ for all }i \right \}}

כל וקטור נקרא "נקודה" בסריג. נוח לייצג את הסריג באמצעות מטריצה לא סינגולרית (הפיכה) מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\times n} שרכיביה הם מספרים ממשיים ועמודותיה הם וקטורי הבסיס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . פרט חשוב בנוגע לסריגים הוא שלכל סריג בסיסים רבים שלהם אותה דטרמיננטה. למעשה, על ידי צירוף ליניארי (שלם) כלשהו של וקטורי הבסיס אפשר להגיע לבסיס אחר של אותו סריג. מזה נובע שבהינתן מטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} (שרכיביה שלמים) כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle BT=C} קיימת מטריצה אחרת הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle T^{-1}} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle CT^{-1}=B} . תכונה נוספת וחשובה המשמשת בהצפנת GGH היא orthogonality defect (פונקציית אורתוגונליות פגומה) שהיא פונקציה המוגדרת כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \text{orth-defect}(B)\ \overset{\underset{\mathrm{def}}{}}{=}\ \frac{\prod_i||\mathbf{b}_i||}{|\text{det}(B)|}}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||\mathbf{b}_i||} הוא הנורמה האוקלידית של העמודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . והיא מספקת כלי מדידה להערכה כמה קרובות עמודות B להיות אורתוגונליות (ניצבות) זו לזו. כאשר עמודות $B$ אורתוגונליות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{orth-defect}(B)=1} . בסיס של סריג נחשב לבסיס "טוב" אם פונקציית פגם האורתוגונליות נמוכה, כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} אורתוגונלית או "כמעט" אורתוגונלית, כך שהפונקציה האמורה לא גדולה בהרבה מ-1.

בעיית הווקטור הקרוב ביותר היא בעיה קשה בתורת הסריגים שלה השלכות על תורת הקריפטוגרפיה. בהינתן בסיס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} של סריג כמתואר לעיל ווקטור כלשהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} , הבעיה היא למצוא וקטור אחר ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(B)} שהוא הקרוב ביותר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} בנורמה מסוימת. בעיה זו הוכחה כבעיית NP-קשה. לא ידוע על אלגוריתם שיכול אף למצוא קירוב טוב בפקטור פולינומי ב-$n$ שהוא הממד. בעיה קשורה נוספת היא מציאת בסיס מינימלי (SBP), שגם היא קשה, אם ניתן למצוא בסיס כזה בזמן פולינומי אז אפשר גם לפתור את בעיית הווקטור הקצר ביותר. האלגוריתם הטוב ביותר הידוע כיום הוא LLL אלגוריתם לצמצום בסיס הסריג (lattice basis reduction) והוא אינו יעיל כאשר הסריג בעל ממד גדול. חישוב המפתח הפרטי מתוך המפתח הציבורי שקול לפתרון בעיה זו.

תיאור הצופן

האלגוריתם מורכב משלושה חלקים; הכנה, הצפנה ופענוח כדלהלן: להכנה המקבל בוחר שני בסיסים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} המיוצגים כמטריצות מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\times n} כאמור, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} הוא פרמטר ביטחון (למשל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\ge 200} ). הבסיס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} נבחר באופן אקראי באופן שיהיה בסיס "טוב" כלומר שהפונקציה ${\text{dual-orth-defect}}$ שלו נמוכה והוא משמש כמפתח פרטי ונשמר בסוד. המקבל מפרסם את המפתח הציבורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} שהוא גרסה "מסווית" של המפתח הפרטי. השיטה הישירה להסוות את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} היא ערבוב של כל וקטורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} עם צירוף ליניארי של וקטורים אחרים, עם מקדמים בטווח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{-1,0,1\}} . נוח לממש זאת באמצעות המכפלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=TR} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} הוא מטריצה אונימודולרית (unimodular) אקראית, כלומר מטריצה ריבועית במספרים שלמים שהדטרמיננטה שלה היא $\pm 1$. והמקבל שומר גם את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} בסוד.

להצפנת המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\in \mathbb{Z}^n} תחילה השולח ממיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} בשיטה מוסכמת ובטוחה לנקודה בסריג, נניח הווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} . לאחר מכן השולח מחשב את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=\mathbf{v}B+\mathbf{e}} ושולח למקבל את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} .

כאשר $\mathbf {e}$ הוא "וקטור שגיאה" אקראי קצר, כלומר שמקדמיו הם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{\sigma,-\sigma\}} בהסתברות שווה, עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} ממשי (כגון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma=3} ). בחירת וקטור השגיאה בצורה זו גרמה לנקודת תורפה מהותית שאיפשרה התקפה יעילה נגד המערכת. נראה היה שלא ניתן למצוא פתרון יעיל שעוקף את הבעיה ורבים סברו לאור זאת ש-GGH אינה ראויה לשימוש כיום בשל כך. אולם במרוצת השנים נמצאו פתרונות (להלן) והסתבר ש-GGH הוספדה מוקדם מדי.

לצורך הפענוח המקבל משתמש בטכניקת קירוב של Babai (היעילה רק כאשר הבסיס נוח) כדי להפוך את פעולת ההצפנה. דהיינו מייצג את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} כצירוף ליניארי של עמודות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} , מעגל את המקדמים של צירוף זה לשלמים הקרובים ביותר ומקבל נקודה בסריג. ייצוג הנקודה כצירוף ליניארי של עמודות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} הוא הווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} . ליתר דיוק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T=B^{-1}R} היא מטריצה יונימודולרית, המקבל מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} ואת $\mathbf {e}$. כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}=TR^{-1}c,\mathbf{e}=c-B\mathbf{v}} . מהנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} המקבל יכול לשחזר את המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} .

מדוע זה עובד. היות שהמטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T=B^{-1}R} היא יונימודולרית, הפונקציה ההפוכה להצפנה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}=TR^{-1}c} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{e}=c-B\mathbf{v}} . כזכור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=B\mathbf{v}+\mathbf{e}} לכן מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle cR^{-1}=(\mathbf{v}B+\mathbf{e})R^{-1}=\mathbf{v}TRR^{-1}+\mathbf{e}R^{-1}=\mathbf{v}T+\mathbf{e}R^{-1}}

מכפילים את הביטוי האחרון ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T^{-1}} כדי לבודד את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{v}} , ממנו אפשר לחלץ את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} . אלגוריתם בּבּאי מאפשר לצמצם את הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle eR^{-1}} מהמשוואה האמורה בתנאי שהוא מספיק קטן, כלומר הכניסות שלו הם ערכים ממשיים הנמוכים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2} .

בהצעה המקורית, הובאו שתי שיטות להכנת בסיס הסריג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} כך שייקרא "טוב". אחת היא לבחור מטריצה אקראית שהכניסות בה הם שלמים קטנים כלומר שהעמודות הן וקטורים בעלי מקדמים בטווח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{-4,-3,-2,-1,0,1,2,3,4\}} והאחרת היא לבחור את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R=kI_n+E} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_n} היא מטריצת היחידה מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\times n} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>1} הוא שלם בגודל בינוני ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} מטריצה אקראית המכילה וקטורים קטנים כמו בקודמת. כמו כן כדי להכין את המטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} הוצעו כמה דרכים כדי למנוע מצב שהמקדמים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} יתנפחו לממדים גדולים מדי מה שיגרום להתנפחות הצופן. טווח המסר הוא כל הקטורים ממעלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} עם מקדמים מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{-M,-(M-1),...,-1,0,1,M-1,M\}} עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M\in\mathbb{N}} כלשהו. יש צורך בשיטה בטוחה סמנטית להמרת המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} לוקטור האמור ולהפך.

חתימה דיגיטלית

אם נתונה מערכת מפתח ציבורי של GGH המתאימה לשריג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\in \mathbb{Z}^n} , באופן טבעי סכימת חתימה דיגיטלית תהיה כדלהלן: נתון המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} והתמצית שלו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(m)\in\mathbb{Z}^n} שחושבה על ידי פונקציית גיבוב בטוחה כלשהי, החתימה היא חישוב הנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}} בסריג האמור, הקרובה ביותר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(m)} . אימות החתימה מתבצע על ידי בדיקה שאכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}} נמצא בסריג כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}(R)^{-1}\in\mathbb{Z}^n } וכן שהיא אכן נקודה קרובה כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||\mathbf{s}-H(m)||} קטן מערך מפרמטר קרבה שנקבע כחלק מתהליך החתימה.

ב-2006 פרסמו עודד רגב ו-Phong Nguyen קריפטואנליזה של חתימת GGH ו-NTRU שמראה שאפשר לחשוף את המפתח הפרטי בזמן מאוד קצר תוך שימוש ב-400 חתימות בלבד. מסיבה זו חתימת GGH אינה בטוחה לשימוש מהיבט פרקטי.

ביטחון ויעילות

תוצאת צופן GGH מתנפחת באופן משמעותי לעומת המסר המקורי בערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2\text{ log }n)} . הערכה מדויקת של מידת ההתנפחות תלויה בגודל הכניסות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} שבתורו תלוי בגודל הכניסות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} . קיימות גרסאות של הצופן שמשפרות את המצב. Micciancio הציע להחליף את המפתח הציבורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=TR} במפתח הציבורי המבוסס על הצורה הנורמלית של הרמיט (HNF) של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} שהוא יותר קטן. שיפור נוסף הוא במקום להטמיע את המסר בנקודה בסריג אפשר להטמיעו בווקטור השגיאה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} וכן אם עובדים עם מקבילון במקום עם המטריצה מקורית הטקסט המוצפן יהיה קטן משמעותית.

ההתקפות האפשריות נגד מערכת GGH הם:

1. ניחוש המפתח הפרטי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} מתוך המפתח הציבורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . לצורך כך אפשר להשתמש באלגוריתם LLL על המפתח הציבורי. אם האלגוריתם מצליח מתקבלת המטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B'} שיכול להיות שתהיה טובה מספיק כדי לפתור את בעיית הווקטור הקצר ואז לשבור את המערכת. כדי למנוע התקפה כזו חובה לבחור בסיס מספיק גדול כך ששימוש באלגוריתם LLL לא יהיה יעיל.
2. ניסיון לנחש מידע על הטקסט המקורי לאור העובדה שווקטור השגיאה קטן. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=vB+e} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} הוא וקטור השגיאה אם מקדמים קטנים, אפשר בהתקפת כוח גס לנסות את כל האפשרויות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} . לצורך ההתקפה אפשר תחילה לחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle cB^{-1}} ואז לבדוק עבור כל עמודה אם הנורמה קטנה תמיד. אם כן יש סבירות שהעמודה מייצגת את המקדם המתאים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} . כדי למנוע התקפה זו סכימת ההמרה של המסר לנקודה בסריג חייבת להיות בטוחה או שאפשר לרפד את המסר בסכימת ריפוד תחילה.
3. ניסיון לפתור את בעיית הווקטור הקרוב ביותר בעזרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} באמצעות אלגוריתם ידוע כמו הטכניקה של בבאי. הבעיה כאמור קשה כל עוד הפרמטרים מבטיחים שהסריג אינו מכיל תבנית כלשהי המקלה על פתרון וכן שהוא מספיק גדול.

ב-1999 חוקרים מצאו בעיות מהותיות בסכמה המקורית שהוצעה על ידי גולדרייך גולדווסר והלוי, שנראה היה שלא ניתן לפתור אותן. ב-2012 הציעו Yoshino ו-Kunihiro פתרון. בגרסה המשופרת נראה שהבעיות תוקנו. אולם פותחו חלופות מתקדמות יותר כמו גרסאות של NTRU שגם יותר בטוחות וגם מציעות ביצועים אופטימליים ומהוות מתחרים ראויים לאלגוריתמים התקניים כמו RSA ודיפי הלמן.

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

דוגמה במספרים קטנים

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\in \mathbb{R}^2} סריג אשר הבסיס שלו הוא המטריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=\begin{pmatrix} 17 & 0 \\ 0 & 19 \end{pmatrix}}

וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T=\begin{pmatrix} 2 & 3 \\ 3 & 5 \end{pmatrix}} כך שמתקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=TR=\begin{pmatrix} 34 & 57 \\ 51 & 95 \end{pmatrix}} אם המסר הוא הווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v=(2,-5)} וכן וקטור השגיאה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e=(1,-1)} כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma=1} . אז הצפנה היא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=mBv+e=(-186,-362)}

לפענוח המקבל מחשב את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle cR^{-1}\approx (-10.94,-19.05)}

יוצא ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle vT=(-11,-19)} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle eB^{-1}\approx (0.06,-0.05)} . אם מעגלים את התוצאה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (-11,-19)} אפשר לחלץ את המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v=(-11,-19)T^{-1}=(2,-5)} .

ראו גם

• הצפנת מפתח ציבורי
• חתימה דיגיטלית
• NTRU

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

35538484GGH