שידור מוצפן

היסטוריה

נושא הצפנה משודרת הועלה כבר ב-1991 על ידי שמשון ברקוביץ שהציע שימוש בחלוקת סוד כדי לפתור את הבעיה. הגדרה הפורמלית ראשונה וניתוח יסודי של הבעיה ניתנו ב-1993 על ידי עמוס פיאט ומוני נאור. הם הציעו אלגוריתם המבוסס על עץ בינארי שמאפשר למנוע מכל מספר של משתמשים מלקבל תוכן כל עוד לא יותר מ- מהם משתפים פעולה נגד המערכת. כמות המפתחות המוצפנים היא בסדר גודל של  וכל משתמש צריך לאחסן מספר מפתחות שהוא ביחס לוגריתמי ל-. כמות העבודה הנדרשת מכל משתמש היא  פענוחים. כמו כן הפרוטוקול תומך בסביבת Stateless ואינו דורש נוכחות (בלתי מקוון). 
רעיון השימוש בלוגיקה של עץ היררכי הומצא בנפרד ב-1990 על ידי וולנר (Wallner) וונג (Wong) שפיתחו שיטות לתקשורת בטוחה בתרחיש רב-נתיב (multicast) במצב מקוון. בשיטה זו שנקראת בקיצור LKH (להלן) יש צורך לשדר  מפתחות בכל פעם שמעדכנים את הרשימה (מבטלים משתמש), כל משתמש נדרש לאחסן  מפתחות וכן כמות העבודה שכל משתמש נדרש לבצע היא  פעולות פענוח (בממוצע רק 1). הפרוטוקול בטוח ללא תלות ב- אך כמות המידע המשודר היא  שזה יחסית גבוה אלא אם כן כל משתמש יאחסן יותר מידע. הנושא נחקר על ידי רבים אחרים.
השיטה subset difference (להלן) שהוצעה ב-2002 על ידי נאור ולוצפיץ' היא הטובה ביותר למצב Statesless. לפי שיטה זו התוכן המשודר דורש רק  הצפנות במקרה הממוצע כדי לבטל  משתמשים, כמות האחסון של כל מקבל היא  מפתחות. אין הגבלה על  וכן תהליך הקצאת המפתח הוא חישובי ולא מסתמך על תורת האינפורמציה. שמיר הלוי ואחרים הציעו שיפור לשיטה זו שנקרא LSD כמות האחסון מצטמצמת לפיה ל- וכמות התוכן היא בפקטור , כאשר  יכול 2.

שיטות ומבנים

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

1. אלגוריתם אתחול

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

CPRM/CPPM

Content Protection for Recordable Media and Pre-Recorded Media היא טכנולוגית ניהול זכויות דיגיטלי שפותחה ב-2001 על ידי 4C Entity (התאגדות של ארבעה ענקי אלקטרוניקה; IBM, אינטל, פנסוניק וטושיבה). CPRM/CPPM נועד בעיקר למצב 'חסר מעמד' (statelss). זהו מנגנון הכולל שיטות להגבלה ושליטה על מדיה דיגיטלית פיזית כמו תקליטורי DVD, כרטיסי זיכרון כמו SD או זיכרון הבזק בהתקן מארח (מחשב אישי או נגן). 
מרכז רישוי כלשהו מפיץ רשימת מפתחות סודיים להטמעה בכל התקן בעת ייצורו. מרכז הרישוי מספק גם בלוק מפתח (MKB) שנועד לצריבה בכל מדיה מתאימה. בלוק המפתח (Media Block Key) למעשה נחשב מעין "כותר" המכיל טקסט-מוצפן של מפתח השיחה איתו הוצפנה המדיה. ההנחה היא שהבלוק ממוקם בשטח מיוחד שבו מתאפשרת כתיבה חד-פעמית בלבד. המדיה הצרובה על גבי התקליטור למעשה מקודדת במצב מוצפן כאשר מפתח ההצפנה מוסתר בכותר. כאשר המשתמש מכניס תקליטור, ההתקן מחלץ את מפתח השיחה מהכותר בעזרת המפתח הסודי המוטמע בו וכך מפענח את המדיה שעל גבי התקליטור.
האלגוריתם שמיישם CPRM הוא למעשה וריאציה של שיטת פיאט-נאור שנקראת סכימת Subset-Cover. הוא מגדיר טבלה עם  שורות ו- עמודות, ומתייחסים לכל התקן (מקלט) כאל אוסף של  כניסות בטבלה, אחת בכל עמודה, כלומר  כאשר . אוסף כל תת-הקבוצות האפשריות  המוגדר על ידי האלגוריתם מתאים לאוסף התקנים שנמצאים באותה כניסה בעמודה נתונה. למשל  כולל את כל ההתקנים  כך ש-. עבור כל שורה  ועמודה  הסכימה מקצה מפתח המיוצג על ידי . בכל התקן  מוטמע מידע פרטי (סודי)  הכולל  מפתחות .
עבור קבוצה  של התקנים "מבוטלים" (Revoked), האלגוריתם מחלק את  כך שכל תת-קבוצה  מכוסה רק אם . בעוד שהסכימה מבטיחה שהתקן לא מאושר לא יכלל בכיסוי, יש סיכוי נמוך שהתקן מאושר לא יכלל גם הוא. כלומר ייתכן התקן לגיטימי שייחשב כלא תקף. בניגוד לשיטת נאור, תת-הקבוצות בסכימת CPRM/CPPM אינן זרות לגמרי ולכן הכיסוי אינו משולם. יתרה מזו הסיכוי שהתקן מאושר יפסל גדל ככל ש- גדל (מספר ההתקנים המבוטלים).
לשם השוואה לשיטת נאור אם  ו- אזי מנגנון CPRM/CPPM דורש  הצפנות, כמות האחסון במקלט או התקן עומדת על  מפתחות, וכמות החישוב הדרושה בצד ההתקן היא רק פעולת פענוח אחת. למשל ב-DVD בלוק המפתח MKB מכיל 3MB. חיסרון נוסף הוא בעובדה ש- מוגבל, כלומר מספר המכשירים המבוטלים המקסימלי שאפשר להגדיר בשיטה זו הוא בערך 10,000. בשיטת נאור אפשר להגיע ל-250,000.