הצפנה הסתברותית – הבדלי גרסאות

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