הוכח, שביטחון סמנטי שקול להגדרת ביטחון מערכת הצפנה שנקראת 'אי-יכולת הבחנה' (indistinguishability) המסומנת בקיצור IND, שפירושה שהיריב לא יכול להבחין בין טקסטים מוצפנים של המערכת לבין טקסט אקראי אמיתי בהסתברות גבוהה מחצי בשיעור שאינו זניח (non-negligable). אפשר לחלק את ההגדרה של ביטחון סמנטי לכמה דרגות בהתאם ליכולות היריב מהקל לכבד. מהיבט תאורטי ההנחה היא שליריב בעל עוצמת חישוב גבוהה גישה ל"אורקל הצפנה" או "אורקל פענוח". ההבדל ביניהם הוא שבראשונה היריב מקבל תוצאות הצפנה של טקסטים קריאים אותם הוא מגיש לאורקל לפי בחירתו, מה שקרוי התקפת גלוי-נבחר, או בקיצור IND-CPA. יש לציין שבהצפנה אסמטרית מעצם ההגדרה, היריב יכול תמיד לקבל הצפנה של טקסטים קריאים כרצונו, בגלל שיש לו גישה למפתח הציבורי. בשנייה הוא מגיש טקסטים מוצפנים לאורקל לפי בחירתו ומקבל בחזרה את הפענוח שלהם. זוהי התקפת מוצפן-נבחר בקיצור IND-CCA שהיא ההגדרה היותר מחמירה וגם היא מתחלקת לשני סוגים CCA1 ו-CCA2 (ראו גם חשילות).
כל פרימיטיב קריפטוגרפי דטרמיניסטי כמו RSA אם משתמשים בו ישירות, לא יעמוד במבחן הגדרה זו כיוון שבהינתן שני מסרים שהוצפנו עם מפתח זהה הטקסט המוצפן ייראה תמיד זהה. עובדה זו 'מדליפה' מידע כלשהו אפילו אם מועט ליריב פוטנציאלי ועל כן אינו בטוח סמנטית.
במודלים המתוארים מוקנת ליריב עוצמה רבה, במיוחד במודל CCA2. הגישה לאורקל משמעה במציאות גישה מלאה למערכת ההצפנה באופן שניתן להצפין או לפענח מבלי לראות את מפתח ההצפנה. לא תמיד המודלים הללו קיימים במציאות, אך יש סיטואציות שבהן זה אפשרי במידה חלקית. למשל אם המערכת מפיקה הודעות שגיאה שונות בהתאם לסיטואציות שונות או שזמן התגובה של המערכת משתנה באופן ניכר בהתאם למצבים שונים כגון שגיאה באחד הפרמטרים, הרי שהמערכת מדליפה באופן עקיף מידע מסוים למתקיף שיכול לעזור לו לפרוץ אותה. קיימות דוגמאות מעשיות של התקפות מוצלחות נגד מערכות אבטחה על בסיס מידע כזה. בהקשר הזה, הודעת השגיאה עצמה נחשבת ל'אורקל'.
הקשר לסודיות מושלמת.
ביטחון סמנטי הוא גרסה חלשה של סודיות מושלמת. לפי שאנון שיטת הצפנה תקרא מושלמת אם יריב פסיבי אפילו בעל עצמת חישוב בלתי מוגבלת, לא יוכל ללמוד מאומה אודות טקסט המקור מהתבוננות בטקסט-המוצפן בלבד, כיוון שכל טקסט יכול היה להיות המקור במידה שווה. לכן ציתות לערוץ התקשורת בו עובר המידע המוצפן לא יועיל ליריב במאומה. ביטחון סמנטי לעומת זאת מוגבל ליריב בעל עצמת חישוב מוגבלת בזמן ומקום.
ההגדרה הפורמלית של סודיות מושלמת היא; עבור כל שני מסרים אקראיים כלשהם המסומנים בקיצור formula_4 אם ההתפלגות של ההצפנה formula_5 וההצפנה formula_6 זהה לחלוטין ולא ניתן להבחין ביניהם בשום אופן, אזי ההצפנה מספקת סודיות מושלמת. למשל הוכח שאם formula_7 הוא מחרוזת אקראית כלשהי (לפחות כמו המסר עצמו) הרי ש-XOR של המסר עם formula_7 מספק ביטחון מושלם, כלומר הצופן אינו טומן בחובו שום מידע לגבי המקור. ההוכחה נכונה רק אם formula_7 נבחר באקראי בהסתברות שווה, מתוך מרחב המפתחות שגודלו לפחות כמרחב המסר, כלומר formula_10.
אם מפתח ההצפנה הוא כאורך המסר מתקבל פנקס חד-פעמי והוא בטוח ללא סייג, בתנאי שנעשה בו שימוש פעם אחת בלבד (ומכאן השם). מסיבות ברורות, עובדות אלו מציבות קושי בשימוש בשיטה מבחינה מעשית. יתרה מזו, את המפתח צריך להעביר בערוץ בטוח (למשל: על ידי שליח נאמן) לצד המקבל, כדי שיוכל לפענח איתו את המידע המוצפן; ואם יימצא ערוץ כזה, שניתן להעביר דרכו מפתח כה ארוך בסודיות - אז אפשר באותה מידה להשתמש באותו ערוץ כדי להעביר את המסר עצמו, ואז אין צורך במפתח כלל. כדי להצפין באופן יעיל (אך לא מושלם), יש למצוא דרכים להעביר מסרים גדולים בערוץ פתוח ללא הגבלה, עם מפתח קטן ככל האפשר, ובגודל קבוע. אולם אז מאבדים את תכונת הסודיות המושלמת, כי בדרך זו מועבר ליריב מידע, באמצעות מפתח קטן בהרבה מהמסר (ההנחה היא, שליריב ידוע אורך המפתח איתו נעשה שימוש).
למעשה, כעת בידי היריב שתי אופציות, שאותן תמיד יוכל לנצל כדי לתקוף את הצופן, ללא תלות בביטחונו. הראשונה: ניחוש אקראי. אם מפתח ההצפנה שאיתו נעשה שימוש בגודל formula_11 סיביות והוא נבחר באקראי מתוך הטווח המקסימלי של המפתחות האפשריים, ההסתברות שהניחוש יצליח היא formula_12. אך אם המפתח קל לניחוש, כגון: אם נבחר מתוך רשימה קצרה של מפתחות, או שמכיל יתירות מסוימת - דהיינו שאינו אקראי לחלוטין, הניחוש הרבה יותר קל. האופציה השנייה היא כוח גס, דהיינו הניסיון לנחש מהו המפתח על ידי formula_13 ניסיונות הצפנה במקרה הממוצע, עם כל המפתחות האפשריים. אם התקפת איזון זמן/זיכרון אפשרית או תקיפת היפגשות באמצע (MITM), התוקף יכול להשתמש בטבלאות חיפוש. למשל אפשר לאחסן טבלה של כל אפשרויות ההצפנה (עם כל המפתחות האפשריים) ולחפש התאמה. חיפוש בטבלה אמנם מתבצע בזמן של formula_14 אך דרישות הזיכרון מאידך אינן מעשיות. אף על פי שקיימות טכניקות לאיזון בין צריכת זיכרון לזמן חישוב, אם המפתח גדול התקפה כזו לא תהיה מעשית.
פונקציית זניחות.
בניסוח פורמלי, indistinguishability (אי-יכולת הבחנה) פירושה שאם נתונה סכמת הצפנה ופענוח (בקיצור: Enc/Dec), הפרמטר formula_15 ומפתח אקראי formula_7, אז לכל שני מסרים formula_17 כלשהם ופונקציה בוליאנית formula_18 בסיבוכיות לפי פרמטר formula_19 (הפרמטרים יובהרו בהמשך), מתקיים:
כלומר: בהינתן תוצאות ההצפנה של שני המסרים, היריב לא יכול לזהות בהבדל משמעותי (שאינו זניח) ביניהם, ולומר מי מהן היא תוצאה של המסר הראשון ומי מהן של השני. רצוי שהפרמטר formula_19 יהיה גדול, מסדר גודל של formula_22. הפרמטר formula_15 הוא טווח השגיאה, כלומר המידה שבה הפונקציה היא זניחה (להלן).
כלי שימושי להגדרת בטיחות ההצפנה היא המושג פונקציה זניחה (Negligible function). הפונקציה formula_24 נקראת זניחה, אם לכל פולינום formula_25 ו-formula_11 גדול מתקיים:
כלומר: תכונת אי-ההבחנה מתקיימת, אם ההסתברות שהיריב יצליח לזהות הבדל בין שני המסרים המוצפנים גדול מחצי בשיעור כה קטן, עד שהוא זניח (לא מורגש). לדוגמה: formula_28 היא פונקציה זניחה, היות שהיא מתכנסת ל-0 בקצב "מהיר"; לעומת זאת, formula_29 אינה פונקציה זניחה. שני פרמטרים שימושיים נוספים להגדרה קונקרטית של ביטחון סמנטי, הם הפונקציה formula_30 שהיא כמות המידע שיש בידי התוקף לגבי ההתפלגות formula_31 של טווח המסר formula_32 לפני ההצפנה והפונקציה formula_33 מייצגת את המידע שהתוקף מעוניין להשיג לגבי formula_34 על ידי ציתות. ייתכן שהתוקף מעוניין בחשיפת המסר כולו או מסתפק בסיבית אחת בלבד.
ההגדרה הקונקרטית של ביטחון סמנטי, בהינתן סכמת הצפנה (Enc,Dec), הפרמטרים formula_35, אם עבור כל התפלגות formula_31 וכל פונקציה formula_37 ופונקציה formula_38. עבור כל אלגוריתם formula_39 בסיבוכיות formula_40 קיים אלגוריתם formula_41 בסיבוכיות formula_42, כך שמתקיים:
במילים, ההסתברות שאלגוריתם formula_39 עם פונקציית ההצפנה formula_45 יפיק פלט formula_33 כלומר ישיג את היעד שנקבע, לא גדולה בשיעור שעולה על formula_15, מההסתברות ש-formula_41 יצליח לעשות זאת (ללא ההצפנה). כלומר המידע הנוסף לתוקף על ידי ההצפנה זניח. פרמטרים מעניינים מבחינה מעשית יכולים להיות למשל: formula_49 ו-formula_50 וסיבוכיות formula_51 צריכה להיות קטנה מאוד. אפשר לראות שאם formula_52 ו-formula_19 לא מוגבל, ההגדרה המתוארת תהיה מקבילה לסודיות מושלמת.
התקפת גלוי-נבחר.
כאשר בידי התוקף ידע מוקדם לגבי זוגות טקסט-מוצפן/טקסט-מקור מתאימים, שהוצפנו במפתח שאינו ידוע לו. למשל אם ביכולתו לבקש הצפנה של טקסט גלוי כלשהו לפי בחירתו, או כאשר מסר שהיה בתחילה סודי הפך לאחר הזמן להיות לא סודי (כך שעלה בידו להשיג את המקור ואת ההצפנה שלו אך לא את המפתח). לסוג כזה של התקפה קוראים התקפת גלוי-נבחר או בקיצור CPA. אי יכולת הבחנה תחת התקפת גלוי נבחר המסומנת בקיצור IND-CPA, פירושה שמניחים שהתוקף יכול לבחור זוגות טקסטים גלויים כלשהם, להציגם בפני אורקל הצפנה, שמחזיר לו הצפנה של אחד מהם באופן אקראי (לפי הטלת מטבע) ותפקידו לנסות להבחין איזה מהטקסטים ששלח הוצפן. ההצפנה תהיה בטוחה תחת הנחה זו, רק אם אין בידי התוקף יתרון כלשהו שעוזר לו לגלות איזה מהטקסטים הוצפן בהסתברות גבוהה מחצי בשיעור כלשהו שאינו זניח (non-negligible).
בניסוח פורמלי עבור סכמת הצפנה (Enc,Dec), פונקציה בוליאנית formula_18 בסיבוכיות formula_55, פרמטר formula_15 המייצג פונקציית זניחות כלשהי ושני מסרים אקראיים כלשהם formula_1, מתקיים:
צריך לשים לב שבהצפנה א-סימטרית מעצם הגדרתה ליריב תמיד תהיה היכולת לבחור זוגות טקסט-גלוי/טקסט-מוצפן. כמו כן קיימות הגדרות מחמירות של ביטחון סימנטי מסוג זה תחת התקפת מוצפן-נבחר שהיא יותר חזקה, המסומנת בקיצור IND-CCA.
בעיקרון כל פונקציה פסאודו-אקראית מוכחת יכולה לשמש לבניית סכמת הצפנה שתהיה בטוחה לפי הגדרת IND-CPA וכן IND-CCA.
היסטוריה.
המושג ביטחון סמנטי הועלה לראשונה על ידי גולדווסר ומיקלי במאמרים מ-1982 הדנים בחסרונות של הצפנה א-סימטרית דטרמיניסטית דוגמת RSA והציעו רעיון שנקרא הצפנה הסתברותית שאמורה להתמודד עם חסרונות אילו. צופן אל-גמאל הוא הדוגמה הטובה ביותר לכך. הם הציעו דרך משלהם ליישום הצפנה הסתברותית הנקראת הצפנת בלום-גולדווסר.
דוגמאות.
שיטת הצפנה דטרמיניסטית כמו RSA מכילה מטבעה מספר חולשות מהותיות: