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

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

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

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

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

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

פרוטוקול Ko-Lee

מידע ציבורי: חבורה $G$ ושתי תתי-חבורות $A,B\leq G$ שאיבריהם מתחלפים (היינו $\forall a\in A,b\in B:ab=ba$).

1. אליס בוחרת באקראי איבר $a\in A$ ושולחת אל בוב את $a^{-1}ga$.
2. בוב בוחר באקראי איבר $b\in B$ ושולח אל אליס את $b^{-1}gb$.
3. המפתח המשותף שלהם הוא $(ab)^{-1}g(ab)=(ba)^{-1}g(ba)$.

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

מידע ציבורי: איברים $a_{1},\dots ,a_{n},b_{1},\dots ,b_{m}\in G$.

1. אליס בוחרת מילה $x$ באיברים $a_{1},\dots ,a_{n}$, ושולחת אל בוב את האיברים $x^{-1}b_{1}x,\dots x^{-1}b_{m}x$.
2. בוב בוחר מילה $y$ באיברים $b_{1},\dots ,b_{m}$, ושולח אל אליס את האיברים $y^{-1}a_{1}y,\dots y^{-1}a_{n}y$.
3. המפתח המשותף הוא הקומוטטור $[x,y]=x^{-1}y^{-1}xy$.

בוב ואליס אכן יכולים לחשב את הקומוטטור - למשל אליס יודעת את המבנה של המילה $x$ שבחרה, ולכן יכולה לחשב את $y^{-1}xy$ (כי היא יודעת את ההצמדה של כל היוצרים), ואז להכפיל ב-$x^{-1}$ משמאל ולקבל את הקומוטטור.

פרוטוקול Shpilrain-Ushakov

מידע ציבורי: חבורה $G$, איבר $g\in G$. ושתי תתי-חבורות $A,B\leq G$ שאיבריהם מתחלפים.

1. אליס בוחרת איברים $a_{1}\in A,b_{1}\in B$ ושולחת $a_{1}gb_{1}$.
2. בוב בוחר איברים $a_{2}\in A,b_{2}\in B$ ושולח $b_{2}ga_{2}$.
3. המפתח המשותף הוא $a_{1}b_{2}gb_{1}a_{2}$.

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

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

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

מידע ציבורי: חבורה $G$ ושתי תתי-חבורות $A,B\leq G$ שאיבריהם מתחלפים. כדי לשלוח מילה $W$ אל אליס, בוב ואליס יפעלו כך:

1. בוב בוחר שני איברים $X_{1},X_{2}\in A$ ושולח אל אליס את האיבר $X_{1}WX_{2}$.
2. אליס בוחרת שני איברים $Y_{1},Y_{2}\in B$ ושולחת אל בוב את האיבר $Y_{1}X_{1}WX_{2}Y_{2}$.
3. בוב מכפיל בהפכיים של האיברים שלו ושולח אל אליס: $X_{1}^{-1}(Y_{1}X_{1}WX_{2}Y_{2})X_{2}^{-1}=Y_{1}WY_{2}$ (בגלל החילופיות).
4. אליס מכפילה בהפכיים של האיברים שלה, ומקבלת את המפתח: $Y_{1}^{-1}(Y_{1}WY_{2})Y_{2}^{-1}=W$.

סיבות בטיחות

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

• בעיית חיפוש המצמיד (Conjugator Search Problem)- בבעיה זו, שואלים האם בהינתן שני האיברים: $h=x^{-1}gx,g$, ניתן למצוא איבר $y$ שיצמיד את $g$ אל $h$, כלומר כך ש-$y^{-1}gy=h$. לעיתים דורשים תנאים נוספים על המצמיד, למשל שהוא יבוא מתת-חבורה נתונה כלשהי, כמו בפרוטוקולים לעיל. סיבת הבטיחות בפרוטוקולים רבים היא בדיוק בעיית חיפוש המצמיד, ועל כן יש לבחור חבורות בהן הבעיה קשה.

גרסה נוספת של הבעיה היא בעיית חיפוש המצמיד הסימולטני' - בהינתן ההצמדות $x^{-1}g_{1}x,\dots ,x^{-1}g_{n}x$ והאיברים $g_{1},\dots ,g_{n}$, למצוא את המצמיד $x$. בבעיה זו ניתן יותר מידע, ויש בה שימוש למשל בפרוטוקול AAG' אך גם היא מתגלה כקשה מספיק בפלטפורמות הנכונות.

• בעיית הפירוק (Decomposition Problem)- בעיה זו ניתן לנסח גם בתורה הקומוטטיבית. ניסוח הבעיה הוא: בהינתן שני האיברים $h=xgy,g$, למצוא איברים $a_{1},a_{2}$ מתוך חבורה נתונה מראש $A$, כך ש-$a_{1}ga_{2}=h$. בעיה זו היא הסיבה לבטיחות של פרוטוקול Shpilrain-Ushakov.

חבורות יישום

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

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

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

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

צורה נורמלית

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

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

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

הצגה

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

דוגמאות

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

חבורת הצמות

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

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

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

חבורות ארטין

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

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

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

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

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

$\langle x_{1},x_{2},\dots \mid x_{i}^{-1}x_{k}x_{i}=x_{k+1},k>i\rangle$

לחבורה זו יש גם הצגות סופיות, אך דווקא בעזרת ההצגה האינסופית הזו ניתן להציג צורה נורמלית שלה - כל איבר ניתן לרשום ביחידות בצורה $x_{i_{1}}\dots x_{i_{t}}x_{j_{s}}^{-1}\dots x_{j_{1}}^{-1}$, כאשר האינדקסים מסודרים בסדר עולה, ואם $x_{,}x_{i}^{-1}$ שניהם מופיעים, אז גם $x_{i+1}$ או $x_{i+1}^{-1}$. צורה זו ניתן לחשב בסיבוכיות זמן ריצה $O(|W|log|W|)$, כאשר $|W|$ הוא אורך המילה הנתונה.

שתי תתי-חבורות מתחלפות של חבורת תומפסון שהוצעו על ידי המחברים הן: $A=\langle x_{0}x_{1}^{-1},\dots ,x_{0},x_{s}^{-1}\rangle ,B=\langle x_{s+1},x_{s+2},\dots \rangle$.

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

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

דוגמאות מפורשות הן חוג מטריצות מעל $\mathbb {n}$ - אך צריך לבחור $n$ גבוה במיוחד. הצעה נוספת היא להשתמש בשדות סופיים, להן מימוש יעיל בהינתן פולינום אי פריק מהמעלה הרצויה. ניתן גם להשתמש בחוגים עם נילפוטנטים, כדוגמת $F_{p}[x]/\langle x^{n}\rangle$.

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

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

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

לקריאה נוספת

• 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)