הצפנה הסתברותית
שיטת הצפנה בה נוסף אלמנט אקראי / ויקיפדיה האנציקלופדיה encyclopedia
הצפנה הסתברותית (באנגלית: Probabilistic encryption) היא סכימת הצפנה סימטרית או אסימטרית שבה נוסף לתהליך ההצפנה אלמנט אקראי כך שהטקסט המוצפן המתקבל מאותו מסר יכול להיות שונה בכל הצפנה אפילו אם המפתח איתו הוצפן זהה, ואילו הפענוח תמיד דטרמיניסטי. באופן תאורטי, זוהי מכונת טיורינג הסתברותית שמצפינה את המסר הגלוי בהטלת מטבע, בניגוד לסכימות הצפנה דטרמיניסטיות כמו RSA או רבין שבהן הטקסט המוצפן נותר ללא שינוי אם המסר הגלוי והמפתח קבועים. המושג הוטבע לראשונה על ידי שפי גולדווסר וסילביו מיקאלי ב-1983 והדוגמאות המעשיות הראשונות הן הצפנת בלום גולדווסר וצופן אל-גמאל. מאז הפך המושג לאחד מיסודות ההצפנה המודרנית וסכימות רבות הומצאו בהשראתו. ידוע שכדי שסכימת הצפנה תחשב מוכחת כבטוחה סמנטית תחת מודל סיבוכיות סטנדרטי היא חייבת להיות הסתברותית, כיוון שבהצפנה דטרמיניסטית העובדה ששני טקסטים מוצפנים זהים משליכה בהכרח שטקסט המקור שלהם זהה, מכאן שמעט מידע מועבר ליריב ולכן אינה יכולה להיות בטוחה סמנטית. הוספת הסתברותיות (פסאודו-אקראיות) פותרת בעיה זו, כיוון שבסבירות מאוד גבוהה הצפנה חוזרת של בלוק טקסט מקורי תניב תוצאות שונות לחלוטין. אפשר להוסיף הסתברותיות גם לסכימות הצפנה דטרמיניסטיות כמו RSA על ידי ריפוד עם ביטחון תחת מודל אורקל אקראי (דוגמת OAEP).