הבעיה הכללית שנקראת בעיית שידור מוצפן מתעוררת בתרחישים שונים כמו העברת תכנים בסגנון שלם וצפה והיא כדלהלן: שרת מרכזי מעוניין לשדר תוכן רב לקבוצה גדולה של מקלטים, כך שרק תת-קבוצה מוגדרת מראש תוכל לפענח את התוכן המשודר. דרך נאיבית לפתור את הבעיה היא להפיץ מראש לכל המשתמשים הרשומים במערכת מפתחות הצפנה סודיים, כל משתמש מקבל מפתח שונה. את המפתח הסודי אפשר להעביר בדרך בטוחה כלשהי או להטמיעו בתוך חומרת המקלט באופן בטוח. זה לא מעשי להצפין ולשדר את התוכן עצמו מספר מרובה של פעמים עם מפתח אחר בכל פעם אלא במקום זאת, השרת מכין תחילה מפתח שיחה, מצפין את גוף התוכן, מצפין את המפתח איתו השתמש במספר הפעמים הדרוש עבור כל משתמש מורשה (עם המפתח הסודי המשותף לו ולשרת) ואז משדר את כל המפתחות המוצפנים יחד עם התוכן המוצפן, רק המשתמשים המחזיקים במפתחות המתאימים יוכלו לחלץ את מפתח ההצפנה מהמידע הנלווה ולפענח את התוכן. דרך זו אינה יעילה במיוחד בעיקר ברשת מרובת משתתפים כי נפח המידע שהשרת צריך לשדר מלבד התוכן גדל משמעותית, כלומר גודל המפתחות המוצפנים כפול מספר המשתמשים.
אפשר לחלק את המשתמשים הרשומים לתת-קבוצות (למשל תת-קבוצה אפשרית היא כל המשתמשים שהזמינו תוכן מסוים) ולהקצות מראש לכל תת-קבוצה אפשרית מפתח הצפנה מתאים, כך שהשרת צריך להצפין ולשדר את התוכן רק פעם אחת עבור תת-הקבוצה המתאימה ואינו נדרש לשדר מלבד התוכן שום דבר. אולם במקרה כזה כל משתמש רשום יאלץ להחזיק בכמות עצומה של מפתחות (מפתח אחד עבור כל תת-קבוצה אפשרית שהוא עשוי להיות חבר בה). המטרות הן למצוא דרך מאוזנת שבה כמות המפתחות שמשתמש בודד צריך להחזיק תהיה המינימלית האפשרית, שתעבורת הרשת לא תגדל משמעותית עקב התרחבות המידע המוצפן וכן כמות העבודה שתידרש מכל משתמש כדי לפענח את התוכן שיקבל לא תהיה גבוהה. בכללות התכונות המינימליות הדרושות ממערכת שידור מוצפן הן:
בדרך כלל יש איזון בין הצורך בביטחון לעומת נוחות. לפעמים מתפשרים בביטחון השידור המוצפן על מנת להבטיח תעבורה גבוהה או תקורה נמוכה. על מנת להעריך או להשוות בין שיטות שידור מוצפן, צריך להגדיר מספר פרמטרים. קבוצת כל המשתמשים הרשומים במערכת מסומנת ב-formula_1 ומכילה formula_2 חברים. הקבוצה formula_3 היא תת-קבוצה המכילה formula_4 משתמשים בלתי מורשים (Revoked) שיש לבטל את תקפות מפתחות ההצפנה שלהם ולא לאפשר להם ליהנות מהתוכן (כגון, אם לא שילמו עבורו). formula_5 מייצג את התוכן המיועד לשידור במצבו הגלוי, אותו השרת צריך להצפין ולשדר באופן כזה שרק תת-הקבוצה formula_6 (המורשים פחות המבוטלים) תוכל לפענחו, בעוד שקואליציה של formula_7 או פחות משתמשים החברים ב-formula_8 לא תוכל. אם אחד מהמשתמשים המורשים משתתף בקואליציה לא ניתן להגן על סודיות התוכן. מקרה כזה מוגדר כ'בגידה' והטיפול בה נעשה באמצעות מנגנון מעקב (Traitor tracing) להלן. מערכת שידור מוצפן כוללת שלושה מרכיבים עיקריים:
היסטוריה.
נושא הצפנה משודרת הועלה כבר ב-1991 על ידי שמשון ברקוביץ שהציע שימוש בחלוקת סוד כדי לפתור את הבעיה. הגדרה הפורמלית ראשונה וניתוח יסודי של הבעיה ניתנו ב-1993 על ידי עמוס פיאט ומוני נאור. הם הציעו אלגוריתם המבוסס על עץ בינארי שמאפשר למנוע מכל מספר של משתמשים מלקבל תוכן כל עוד לא יותר מ-formula_16 מהם משתפים פעולה נגד המערכת. כמות המפתחות המוצפנים היא בסדר גודל של formula_17 וכל משתמש צריך לאחסן מספר מפתחות שהוא ביחס לוגריתמי ל-formula_16. כמות העבודה הנדרשת מכל משתמש היא formula_19 פענוחים. כמו כן הפרוטוקול תומך בסביבת Stateless ואינו דורש נוכחות (בלתי מקוון).
רעיון השימוש בלוגיקה של עץ היררכי הומצא בנפרד ב-1990 על ידי וולנר (Wallner) וונג (Wong) שפיתחו שיטות לתקשורת בטוחה בתרחיש רב-נתיב (multicast) במצב מקוון. בשיטה זו שנקראת בקיצור LKH (להלן) יש צורך לשדר formula_20 מפתחות בכל פעם שמעדכנים את הרשימה (מבטלים משתמש), כל משתמש נדרש לאחסן formula_21 מפתחות וכן כמות העבודה שכל משתמש נדרש לבצע היא formula_21 פעולות פענוח (בממוצע רק 1). הפרוטוקול בטוח ללא תלות ב-formula_16 אך כמות המידע המשודר היא formula_24 שזה יחסית גבוה אלא אם כן כל משתמש יאחסן יותר מידע. הנושא נחקר על ידי רבים אחרים.
השיטה subset difference (להלן) שהוצעה ב-2002 על ידי נאור ולוצפיץ' היא הטובה ביותר למצב Statesless. לפי שיטה זו התוכן המשודר דורש רק formula_25 הצפנות במקרה הממוצע כדי לבטל formula_26 משתמשים, כמות האחסון של כל מקבל היא formula_27 מפתחות. אין הגבלה על formula_26 וכן תהליך הקצאת המפתח הוא חישובי ולא מסתמך על תורת האינפורמציה. שמיר הלוי ואחרים הציעו שיפור לשיטה זו שנקרא LSD כמות האחסון מצטמצמת לפיה ל-formula_29 וכמות התוכן היא בפקטור formula_30, כאשר formula_31 יכול 2.
שיטות ומבנים.
להלן פירוט שלוש שיטות בסיסיות לפתרון בעיית שידור מוצפן שהמכנה המשותף שלהן בתהליך הקצאת המפתחות הוא השימוש במבנה דמוי עץ. מקצים מפתח ראשי לשורש העץ ולכל יתר הצמתים והעלים מקצים מפתחות בשיטת GGM שהוצעה על ידי גולדרייך, גולדווסר ומיקאלי שהיא סוג של פונקציה פסאודו-אקראית.
Subset Cover.
הבסיס התאורטי למשפחת האלגוריתמים Subset-Cover מתחיל במושג שהגו לראשונה פיאט ונאור שנקרא סכימת ביטול "k-resilient" הפועלת כך שבהינתן קבוצה formula_32 של formula_33 חברים, הסכימה תהיה עמידה כנגד קואליציה formula_34 של עד formula_16 חברים. לשם כך מקצים מפתחות הצפנה סודיים ונפרדים formula_36 עבור כל תת-קבוצה formula_37 אפשרית כאשר formula_38, אותו מעבירים לכל משתמש formula_39 (לכל המשתמשים החברים ב-formula_32 אך אינם נמנים עם formula_41). אפשר לדמות זאת באנלוגיה למצב שבו המפתחות נרשמים על גבי מצחם של כל המשתמשים, כל אחד יכול לראות את המפתחות של כולם למעט המפתח הרשום על מצחו. אם הקבוצה formula_42 היא אוסף חברים מורשים, מפתח ההצפנה הסודי עבורם הוא XOR של כל המפתחות formula_36 כאשר formula_44. כל קואליציה של formula_45 חברים תחסר את המפתח formula_46 (המשויך להם) ולכן לא תוכל לחלץ את המפתח של formula_42 בתנאי שמתקיים formula_48.
הסכימה המתוארת הוכחה בטוחה מהיבט תאורטי אך אינה יעילה, כדי לכסות את כל האפשרויות, כל משתמש נדרש לאחסן formula_49 מפתחות (לדוגמה; עבור עשרה משתמשים שמתוכם חמישה מבוטלים, כל משתמש נדרש לאחסן 638 מפתחות). במקרה הפרטי שבו formula_50 (כלומר רק משתמש אחד מבוטל) מספר המפתחות שכל אחד נדרש לשמור הוא formula_51. אפשר לשפר את הסכימה על ידי הסתמכות על פונקציה חד-כיוונית ואז הביטחון אינו אבסולוטי אלא חישובי. מדמים את רשימת המשתמשים לעץ בינארי שכל עלה בו מתאים למשתמש אחד. מקצים מפתח אקראי לשורש העץ ולכל צומת מקצים רקורסיבית מפתח מתאים על ידי פונקציה פסאודו-אקראית formula_52 שמקבלת קלט מפתח של צומת אב ומפיקה פלט כפול באורכו, מחצית אחת מקצים לבן השמאלי והמחצית השנייה לבן הימני. היתרון שבשיטת בנייה זו הוא שכעת כל משתמש נדרש לדעת בעיקרון רק מפתח של אב קדום כלשהו שלו, כי המפתח שלו הוא תוצאה של הפעלת הפונקציה הפסאודו-אקראית באופן רקורסיבי במסלול מהשורש ועד לעלה שלו. כעת כדי לבטל עלים מסוימים מסירים את המסלולים המקשרים ביניהם לבין שורש העץ, כך למעשה נוצר "יער" של formula_53 תת-עצים, כל משתמש צריך לקבל כעת את מפתחות של כל שורשי תת-העצים. כעת אם המדיה מוצפנת עם XOR של כל המפתחות המשויכים למשתמשים שהוסרו, כל משתמש formula_54 יכול לחשב כל מפתח מלבד המפתח המשויך אליו ולכן אינו יכול לחלץ את המפתח לתוכן. המשתמשים המורשים לעומת זאת מקבלים את המפתח כשהוא מוצפן עם המפתח הפרטי שהם משתפים עם השרת.
דרך אחרת היא לבסס את הסכימה על בעיה מתורת המספרים דוגמת RSA. השרת מכין מפתח שורש שהוא formula_55, כפולה של שני ראשוניים גדולים, בוחר יוצר formula_56 מסדר גבוה וכל משתמש formula_57 מקבל את formula_58 כאשר כל formula_59 זרים הדדית. המפתח המשותף לקבוצה formula_42 הוא formula_61 כאשר formula_62 ואז המשתמש formula_57 מחלץ את המפתח המשותף על ידי formula_64 כלומר חזקה של כל המפתחות למעט המפתח שלו. הוכח שהסכימה הזו בטוחה בהנחה שפירוק לגורמים היא בעיה קשה וכל מה שנדרש לאחסן הוא רק מפתח אחד.
בשתי הסכימות השרת אינו נדרש לשדר כלל מידע נלווה לתוכן המוצפן, כיוון שהמפתחות הוקצו מראש ובידי המשתמשים המידע הדרוש לחילוץ מפתח השיחה. אולם שיתוף פעולה של שני משתמשים מאפשר להם לשבור בקלות את המערכת. אלגוריתם Complete Subset Cover מרחיב את הרעיון הבסיסי לעמידות כנגד formula_65 מבוטלים וכן מצמצם את דרישות האחסון ברמת משתמש במחיר שהשרת ישדר לפני כל תוכן מוצפן מידע מסוים שנקרא "כותר". בכללות הוא מגדיר אוסף של תת-קבוצות formula_66 כאשר formula_67. מקצים מפתח סודי ארוך טווח (קבוע) formula_68 לכל formula_69 ולכל formula_70 מקצים מידע פרטי formula_71 איתו הוא אמור לשחזר את formula_68. בהינתן קבוצה formula_8 של משתמשים מבוטלים יתר המשתמשים formula_74 מחולקים לתת-קבוצות זרות formula_75 כך שמתקיים:
formula_77 מוצפן formula_78 פעמים עם המפתחות formula_79 בהתאמה.