הצפנה לא-קומוטטיבית

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

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

פרוטוקולים לא-קומוטטיביים

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

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

פרוטוקול Ko-Lee

מידע ציבורי: חבורה $G$ ושתי תתי-חבורות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B \le G} שאיבריהם מתחלפים (היינו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall a \in A , b \in B : ab = ba} ).

אליס בוחרת באקראי איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in A} ושולחת אל בוב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{-1} g a} .
בוב בוחר באקראי איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \in B} ושולח אל אליס את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b^{-1} g b} .
המפתח המשותף שלהם הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (ab)^{-1} g (ab) = (ba)^{-1} g (ba)} .

פרוטוקול Anshel-Anshel-Goldfeld

מידע ציבורי: איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1, \dots , a_n, b_1, \dots, b_m \in G} .

אליס בוחרת מילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} באיברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1, \dots , a_n} , ושולחת אל בוב את האיברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{-1} b_1 x, \dots x^{-1} b_m x} .
בוב בוחר מילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} באיברים $b_{1},\dots ,b_{m}$ , ושולח אל אליס את האיברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^{-1} a_1 y, \dots y^{-1} a_n y} .
המפתח המשותף הוא הקומוטטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [x,y] = x^{-1} y^{-1} x y} .

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

פרוטוקול Shpilrain-Ushakov

מידע ציבורי: חבורה $G$ , איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \in G} . ושתי תתי-חבורות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B \le G} שאיבריהם מתחלפים.

אליס בוחרת איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 \in A , b_1 \in B} ושולחת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 g b_1} .
בוב בוחר איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_2 \in A , b_2 \in B} ושולח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_2 g a_2} .
המפתח המשותף הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 b_2 g b_1 a_2} .

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

פרוטוקול שלושת המעברים של Shamir

פרוטוקול זה הוא פרוטוקול שליחת מפתח (Key transport protocol), כלומר פרוטוקול בו אחד הצדדים מעביר מפתח אל האחר (הם לא מחליפים מפתח ביניהם). הפרוטוקול נקרא על שמו של עדי שמיר.

מידע ציבורי: חבורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} ושתי תתי-חבורות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B \le G} שאיבריהם מתחלפים. כדי לשלוח מילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} אל אליס, בוב ואליס יפעלו כך:

בוב בוחר שני איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1, X_2 \in A} ושולח אל אליס את האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1 W X_2} .
אליס בוחרת שני איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_1, Y_2 \in B} ושולחת אל בוב את האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_1 X_1 W X_2 Y_2} .
בוב מכפיל בהפכיים של האיברים שלו ושולח אל אליס: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1^{-1}(Y_1 X_1 W X_2 Y_2)X_2^{-1}=Y_1 W Y_2} (בגלל החילופיות).
אליס מכפילה בהפכיים של האיברים שלה, ומקבלת את המפתח: הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle Y_{1}^{-1}(Y_{1}WY_{2})Y_{2}^{-1}=W} .

סיבות בטיחות

בטיחות הפרוטוקולים השונים לעיל תלויה בקיומם את הבעיות הבאות:

בעיית חיפוש המצמיד (Conjugator Search Problem)- בבעיה זו, שואלים האם בהינתן שני האיברים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h=x^{-1} g x , g} , ניתן למצוא איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} שיצמיד את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} , כלומר כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^{-1} g y = h} . לעיתים דורשים תנאים נוספים על המצמיד, למשל שהוא יבוא מתת-חבורה נתונה כלשהי, כמו בפרוטוקולים לעיל. סיבת הבטיחות בפרוטוקולים רבים היא בדיוק בעיית חיפוש המצמיד, ועל כן יש לבחור חבורות בהן הבעיה קשה.

גרסה נוספת של הבעיה היא בעיית חיפוש המצמיד הסימולטני' - בהינתן ההצמדות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{-1} g_1 x , \dots , x^{-1} g_n x} והאיברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_1, \dots, g_n} , למצוא את המצמיד $x$ . בבעיה זו ניתן יותר מידע, ויש בה שימוש למשל בפרוטוקול AAG' אך גם היא מתגלה כקשה מספיק בפלטפורמות הנכונות.

בעיית הפירוק (Decomposition Problem)- בעיה זו ניתן לנסח גם בתורה הקומוטטיבית. ניסוח הבעיה הוא: בהינתן שני האיברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h= x g y , g} , למצוא איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 , a_2 } מתוך חבורה נתונה מראש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 g a_2 = h} . בעיה זו היא הסיבה לבטיחות של פרוטוקול Shpilrain-Ushakov.

חבורות יישום

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

תכונות שהחבורות צריכות לקיים

פרט לדרישה שבחבורות לא יהיו פתרונות פשוטים לבעיות לעיל, יש לדרוש כי לחבורה תהיה בעיית מילה פשוטה.

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

צורה נורמלית

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

כעת, כשאמרנו לעיל 'יש לשלוח את האיבר...', מה שבאמת שולחים הוא צורה נורמלית של האיבר. אם בוחרים חבורה טובה אפשר לחשב אותה ביעילות, לעיתים קל להכפיל איברים בעזרתה, וקל לזהות שתי מילים בעזרתה.

עם זאת, לעיתים צורות נורמליות נותנות יותר מדי מידע ומהוות פרצה להתקפות, כדוגמת התקפות מבוססות אורך או התקפות על בעיית הפירוק.

הצגה

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

דוגמאות

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

חבורת הצמות

ערך מורחב – חבורת הצמות#חבורת הצמות והצפנה

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

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

חבורות ארטין

ערך מורחב – חבורת ארטין#שימושים בהצפנה

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

משפחות מסוימות של חבורת ארטין הן לינאריות.

חבורת תומפסון

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x_1, x_2, \dots \mid x_i^{-1} x_k x_i=x_{k+1}, k>i \rangle}

לחבורה זו יש גם הצגות סופיות, אך דווקא בעזרת ההצגה האינסופית הזו ניתן להציג צורה נורמלית שלה - כל איבר ניתן לרשום ביחידות בצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{i_1}\dots x_{i_t}x_{j_s}^{-1} \dots x_{j_1}^{-1}} , כאשר האינדקסים מסודרים בסדר עולה, ואם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_,x_i^{-1}} שניהם מופיעים, אז גם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{i+1}} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{i+1}^{-1}} . צורה זו ניתן לחשב בסיבוכיות זמן ריצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(|W| log |W|)} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |W|} הוא אורך המילה הנתונה.

שתי תתי-חבורות מתחלפות של חבורת תומפסון שהוצעו על ידי המחברים הן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A= \langle x_0 x_1^{-1}, \dots , x_0,x_s^{-1} \rangle , B = \langle x_{s+1},x_{s+2},\dots \rangle} .

חבורות מטריצות

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

דוגמאות מפורשות הן חוג מטריצות מעל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{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 F_p[x]/\langle x^n \rangle} .

רעיונות מרכזיים

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

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

לקריאה נוספת

Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov (2008). Group-based Cryptography. Berlin: Birkhäuser Verlag.{{cite book}}: תחזוקה - ציטוט: multiple names: authors list (link)
Benjamin Fine; et al. (2011). "Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems". {{cite web}}: Explicit use of et al. in: |last1= (עזרה)
David Garber (2008). "Braid Group Cryptography".
S.R. Blbackburn, C. Cid, C. Mullan (2010). "Group Theory In Cryptography".{{cite web}}: תחזוקה - ציטוט: multiple names: authors list (link)