סודיות מושלמת
הגדרה פורמלית

לצורך ההגדרה הפורמלית של סודיות מושלמת יש צורך להגדיר מספר מושגים בסיסיים. אלגוריתם הצפנה מורכב משלושה אלגוריתמים;
אלגוריתם הכנת מפתח Gen שמפיק מפתח הצפנה  k מתוך מרחב המפתח  {\mathcal {K}} באופן הסתברותי בהתפלגות מסוימת, בדרך כלל התפלגות אחידה.
אלגוריתם הצפנה Enc שמקבל כקלט  k\in {\mathcal {K}} ו- m\in {\mathcal {M}}, מצפין את  m עם המפתח  k ומחזיר את  c\in {\mathcal {C}}. באופן פורמלי  c={\text{Enc}}_{k}(m). יש לציין שאלגוריתם ההצפנה יכול להיות הסתברותי במובן שעבור אותו מסר ואותו מפתח יכול להיות פלט שונה בכל הרצה של האלגוריתם. כדי להבדיל בין שני המקרים יש כאלו שמסמנים את ההצפנה ההסתברותית:  c\longleftarrow {\text{Enc}}_{k}(m).
אלגוריתם פענוח Dec הוא אלגוריתם דטרמיניסטי שמקבל את  c\in {\mathcal {C}} ואת  k\in {\mathcal {K}} ומחזיר תמיד את  m\in {\mathcal {M}} שהוצפן עם  k.
ההנחה היא שהאלגוריתם שלם במובן שתמיד מתקיים  {\text{Dec}}_{k}(c)=m בהסתברות 1. במילים אחרות
עבור כל מפתח  k\in {\mathcal {K}} מסמנים את ההסתברות שהמפתח שנבחר על ידי האלגוריתם Gen הוא  k בביטוי  \Pr[K=k]. באותו אופן, ההסתברות שטקסט גלוי ספציפי יישלח היא  \Pr[M=m] וההסתברות שטקסט מוצפן כלשהו יופק על ידי האלגוריתם היא  \Pr[C=c]. יש לציין ראשית, שהתפלגות הטקסט הגלוי  m נפרדת ובלתי תלויה בהתפלגות המפתח  k. יתרה מזו, המפתח נקבע ומשותף לשני הצדדים לפני שנודע מהו הטקסט הגלוי. בנוסף יש לציין שההנחה היא שההתפלגות של  m ידועה. המתקיף או מנתח הצופן, אינו יודע בוודאות איזה טקסט גלוי יישלח אחרת אין כל טעם בהצפנה. לעומת זאת יש בידו מידע כללי בהסתברות מסוימת לגבי הסיכויים שטקסט מסוים יישלח לעומת טקסט אחר. לדוגמה עשוי להיות מצב שהמתקיף יודע שהטקסט הגלוי "attack tomorrow" יישלח בהסתברות של שבעים אחוז לעומת "don't attack" בהסתברות של 30 אחוז. לכן  \Pr[M={\text{''attack tomorrow''}}]=0.7 וכן  \Pr[M={\text{''don't attack''}}]=0.3. ללא הגבלת הכלליות ההנחה היא שההתפלגויות תמיד גדולות מאפס.
ההגדרה האינטואיטיבית של סודיות מושלמת היא שבהינתן יריב שידועה לו התפלגות הטקסט הגלוי, כלומר יודע מהי ההסתברות שטקסט מסוים יישלח ומגיע לידיו טקסט מוצפן כלשהו, באופן אידיאלי, ראיית הטקסט המוצפן אינה משפיעה על ידיעתו המוקדמת. במילים אחרות, עבור כל טקסט גלוי ההסתברות שהוצפן אינה משתנה גם לאחר שהיריב ראה את הטקסט המוצפן. והדברים נכונים גם אם היריב בעל עוצמת חישוב בלתי מוגבלת.
בניסוח פורמלי: סכימת הצפנה  ({\text{Gen}},{\text{Enc}},{\text{Dec}}) מעל מרחב המסרים  {\mathcal {M}} תקרא בעלת סודיות מושלמת אם ורק אם עבור כל התפלגות של  {\mathcal {M}}, כל טקסט גלוי  m\in {\mathcal {M}} וכל טקסט מוצפן  c\in {\mathcal {C}} מתקיים:
הכוונה היא שההסתברות שיתקבל  c מסוים בהינתן  m מסוים שווה להסתברות שיתקבל  c ללא ידיעת  m.
הוכחה:
נתונה התפלגות מסוימת של  {\mathcal {M}} ונתונים  m\in {\mathcal {M}} ו- c\in {\mathcal {C}}. אם מכפילים את שני האגפי המשוואה האמורה ב- \Pr[M=m]/\Pr[C=c] מתקבל
לפי חוק בייס האגף השמאלי שווה בדיוק ל- \Pr[M=m|C=c] לכן  \Pr[M=m|C=c]=\Pr[M=m] ולכן הצופן מושלם. הדברים נכונים גם בכיוון ההפוך.
שאנון הוכיח שכדי שצופן יקרא מושלם חובה שאורך מפתח ההצפנה יהיה לפחות כאורך הטקסט המיועד להצפנה. בניסוח פורמלי:
ההוכחה לכך היא נניח שהתנאי האמור לא מתקיים ו- |{\mathcal {K}}|<|{\mathcal {M}}|. יהי  {\mathcal {M}}(c) קבוצת כל המסרים האפשריים שהם פענוח אפשרי של  c. כלומר
היות שפונקציית הפענוח דטרמיניסטית, עבור כל מסר  {\hat {m}} קיים לפחות מפתח אחד  {\hat {k}} כך שמתקיים  {\hat {m}}={\text{Dec}}_{\hat {k}}(c) מזה נובע  |{\mathcal {M}}(c)|\leq |{\mathcal {K}}|. בהנחה ש- |{\mathcal {K}}|<|{\mathcal {M}}| נכון בהכרח קיים  m'\in {\mathcal {M}} שאינו נמנה עם  {\mathcal {M}}(c). אבל
מה שמפר את הסודיות המושלמת של הצופן. מזה אפשר להסיק שכל מערכת הצפנה שבה מפתח ההצפנה קטן מהטקסט הגלוי אינה יכולה להיקרא מושלמת בשום אופן. יתרה מזו אפשר להוכיח גם שכדי שההצפנה תהיה מושלמת לא ניתן להשתמש באותו מפתח להצפנת שני מסרים או יותר.