הצפנת קריימר-שופ

הצפנת קריימר-שׁוּפּ (באנגלית: Cramer–Shoup cryptosystem) היא מערכת הצפנה א-סימטרית פרקטית, מוכחת כבטוחה סמנטית נגד התקפת מוצפן-נבחר שהומצאה ב-1998 על ידי רונלד קריימר מהמכון הטכנולוגי של ציריך וויקטור שופ ממעבדות IBM והוצגה בוועידת CRYPTO '98 בקליפורניה. ביטחונה מסתמך על קושיה המשוער של בעיית הכרעה דיפי-הלמן והיא הרחבה של צופן אל-גמאל. שבניגוד לאחרון שנקרא חשיל ואינו מוגן כלל כנגד התקפת מוצפן-נבחר (בקיצור CCA), לגרסת קריימר-שופ נוספו כמה אלמנטים כדי להבטיח אי-חשילות (Non-malleability) ועמידות כנגד התקפת CCA בשילוב של פונקציית גיבוב חד-כיוונית אוניברסלית ומחולל מספרים אקראיים בטוח.

מודל ביטחון

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

ביטחון

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

CS-Lite

בעיקרון מערכת הצפנת קריימר-שופ יכולה להיות מוכחת כבטוחה בשתי דרכים. הראשונה המתוארת לעיל שאינה עושה שימוש במודל אורקל אקראי והיא מוכחת תחת ההנחה שבעיית הכרעת דיפי-הלמן בקיצור DDH קשה וכן שפונקציית הגיבוב  בטוחה והשנייה עם רעיון מודל אורקל אקראי. התכונה המעניינת שלה היא שמודל האורקל האקראי מהווה מעין משוכה נוספת במקרה שההנחה הראשונה נכשלת. לכן אפשר להוכיח את ביטחונה תחת הנחה קלה יותר כמו הקושי שבבעיית דיפי-הלמן החישובית.
הווריאציה שנקראת CS-Lite היא גרסה פשוטה יותר של מערכת קריימר-שופ ללא פונקציית גיבוב. שהיא בטוחה לפי מודל פחות מחמיר שנקרא IND-CCA1. לפי מודל זה המערכת צריכה להיות בטוחה תחת התקפת מוצפן נבחר לא אדפטיבית שבה התוקף רשאי להגיש שאילתות לאורקל כל עוד לא קיבל לידיו את האתגר שהוא הטקסט המוצפן אותו הוא מעוניין לשבור. מרגע שהגיע האתגר לידיו אין הוא רשאי יותר לפנות לאורקל. ביטחון המערכת CS-Lite עונה להגדרה זו.