הצפנה הסתברותית

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

מידע חלקי

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

1. אין הוכחה בהכרח שאם $f$ חד-כיוונית יהיה תמיד קשה להפוך אותה גם כאשר $x$ הוא בעל מבנה מיוחד. הדוגמה הכי פשוטה היא בהינתן פונקציית RSA ידוע שקל לחשב ערכים קטנים של $x$ אם המעריך (מפתח ההצפנה) קטן, כך שהתוצאה אינה גדולה מהמודולוס.
2. העובדה ש-$f$ חד-כיוונית אינה מעידה בהכרח שלא ניתן לחלץ מידע חלקי לגבי $x$. לדוגמה אם $y\equiv g^{x}{\text{ mod }}p$ כאשר $p$ ראשוני ו-$g$ הוא יוצר של $Z_{p}^{*}$ אזי אף על פי שזו פונקציה חד כיוונית שקשה להפוך אם ל-$p-1$ יש גורם ראשוני גדול, העובדה היא ש-$x$ אינו מספר זוגי אם ורק אם $y$ הוא שארית ריבועית מודולו $p$ וקיים אלגוריתם הסתברותי יעיל להכריע אם מספר הוא שארית ריבועית מודולו מספר ראשוני כלשהו. לכן תמיד אפשר לדעת מהי הסיבית הפחות משמעותית של $x$.

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

סכימה קונקרטית

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

הבעיה מוגדרת כדלהלן: נתון מודולוס $n$ שהוא כפולה של שני ראשוניים $p,q$ אם $x$ זר ל-$n$ אז $x$ הוא שארית ריבועית (quadratic residue) ביחס למודולוס $n$ אם למשוואה

$x\equiv y^{2}{\text{(mod }}n)$

יש פתרון שלם $y$, אחרת אמרים ש-$x$ אינו שארית ריבועית (quadratic non-residue). ללא ידיעת הגורמים הראשוניים קשה להכריע בשאלה.

הסכימה הבאה מנצלת עובדה זו למערכת הצפנה. החיסרון שלה הוא שהטקסט המוצפן עבור כל סיבית מידע גדול (לפחות 1,024 סיביות). היא פועלת כדלהלן:

בהינתן פרמטר ביטחון $k$ המשתמש A מכין את הפרמטרים הבאים:

1. בוחר באופן אקראי שני מספרים ראשוניים $p_{1}$ ו-$p_{2}$ באורך $k$ סיביות
2. מחשב את $n=p_{1}p_{2}$
3. בוחר שלם $y$ כך ש-$y$ אינו שארית ריבועית מודולו $n$ ולו סימן יעקובי $+1$.
4. המפתח הפרטי הוא המספרים הראשוניים $p_{1}$ ו-$p_{2}$
5. המפתח הפומבי הוא הערכים $n$ ו-$y$.

אם B רוצה להצפין עבור A מחרוזת סיביות של טקסט גלוי כלשהו $b={b_{1},...,b_{l}}$ באורך $l$ סיביות הוא מבצע:

1. עבור $i=1$ עד $l$:
   1. בוחר שלם אקראי $r_{i}\in Z_{n}^{*}$
   2. אם $b_{i}=1$ מציב $c_{i}=yr_{i}^{2}{\text{ mod }}n$
   3. אחרת אם $b_{i}=0$ מציב $c_{i}=r_{i}^{2}{\text{ mod }}n$
2. הטקסט המוצפן הוא $c=c_{1},...,c_{l}$

לפענוח הטקסט המוצפן $c$ המשתמש A מחשב כדלהלן:

1. עבור כל סיבית $c_{i}$ מציב $b_{i}=Q_{n}(c_{i})$. כאשר $Q_{n}$ הוא אלגוריתם פולינומי שמכריע בשאלה האם שלם כלשהו הוא שארית ריבועית מודולו מספר פריק שהגורמים הראשוניים שלו ידועים, (ראו סימן לז'נדר או מבחן אוילר). אם האלגוריתם מחזיר אמת הסיבית $b_{i}$ היא '1' אחרת '0'.
2. הטקסט המקורי הוא $b$.

סיבוכיות ההצפנה היא בסדר גודל $O(lk^{2})$ וסיבוכיות הפענוח היא $O(lk^{3})$ כאשר $k$ הוא פרמטר הביטחון (אורך כל אחד מהמספרים הראשוניים בסיביות) ו-$l$ אורך המסר $b$ בסיביות.

אפשר לראות ש-$c_{i}$ הוא שארית ריבועית מודולו $n$ רק אם $b_{i}=0$. כיוון שקל לדעת אם מספר הוא שארית ריבועית מודולו מספר ראשוני אך קשה לעשות זאת מודולו מספר פריק, המשתמש הלגיטימי שהגורמים הראשוניים של $n$ ידועים לו יכול בקלות לחשב את $Q_{n}(c_{i})$ ולגלות האם $b_{i}=0$ או $b_{i}=1$. בגלל אקראיות $r$ בכל פעם שתתבצע הצפנה של $b$ יתקבל ערך אחר כך שהתוקף אינו יכול ללמוד מאומה מהתבוננות בטקסט המוצפן.