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

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

הצורך בהצפנה היסתברותיתהסתברותית נובע מבעיה מהותית שקיימת בכל סכימת הצפנה דטרמיניסטית המבוססת על [[פונקציה חד כיוונית]] עם דלת מלכודת. למשל אם נתונה פונקציה חד-כיוונית <math>f</math> כך שקל לחשב את <math>y=f(x) </math> אך קשה לחשב את הפונקציה ההופכית <math>x=f^{-1}(y)</math> ללא דלת המלכודת:

#העובדה ש-<math>f</math> חד-כיוונית אינה מעידה בהכרח שלא ניתן לחלץ מידע חלקי לגבי <math>x</math>. לדוגמה אם <math>y\equiv g^x\text{ mod }p</math> כאשר <math>p</math> ראשוני ו-<math>g</math> הוא [[חבורה (מבנה אלגברי)#יוצרים ויחסים|יוצר]] של <math>Z_p^*</math> אזי <math>x</math> אינו מספר זוגי אם ורק אם <math>y</math> הוא [[שארית ריבועית]] מודולו <math>p</math> וקיים אלגוריתם היסתברותיהסתברותי יעיל שבאמצעותו אפשר לחשב אם מספר הוא שארית ריבועית מודולו מספר ראשוני כלשהו. לכן תמיד אפשר לדעת מהי הסיבית הפחות משמעותית של <math>x</math>.

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