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

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

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

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

חבורות יישום

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

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

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

צורה נורמלית

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

הצגה

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

דוגמאות

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

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

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

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

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