שידור מוצפן

בקריפטוגרפיה, סכימת שידור מוצפן (Broadcast Encryption) היא טכניקה לשידור יעיל של תוכן מוצפן לקבוצה דינאמית של משתמשים מורשים באופן שרק הם יוכלו לפענחו. כלומר כל המשתמשים שברשותם מקלט מתאים מסוגלים לקלוט את התוכן המשודר, אך רק קבוצה של משתמשים מורשים תוכל ליהנות ממנו, בעוד שהיתר אמורים לראות תוכן בלתי קריא. לעיתים נוח להתייחס לזה כאל 'סכימת ביטול' שמטפלת בצורך למנוע ממקלט אחד או יותר מלקלוט שידור מסוים.

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

• שלם וצפה; שיטות שידור בתשלום של תוכן אחיד למשתמשים מרובים.
• רב-נתיב; פרוטוקול תקשורת לניתוב מידע יחיד לנקודות מרובות.
• וידאו על פי דרישה; שירות אינטראקטיבי להעברת תכנים לפי דרישה.
• הזרמת מדיה; טכניקות העברת מדיה רציפה ומתמשכת על ידי ספקי תוכן.
• זכויות יוצרים; הגבלת גישה והגנה מפני העתקה פיראטית של מדיה דיגיטלית כמו תקן Advanced Access Content System.
• שימוש אפשרי נוסף הוא אבטחת שיתוף מידע במחשוב ענן.

היישומים השונים מכתיבים גישות שונות לניהול ועדכון רשימת המשתמשים הלגיטימיים. משתמשים מוסרים מהרשימה עקב אי תשלום, תפוגה של מנוי או שימוש בלתי הולם. מקרה מיוחד של הבעיה נקרא "State-less", כלומר משתמש לגיטימי לא יוכל להקליט את היסטוריית התכנים שקיבל כדי לשנות את מעמדו באופן שיאפשר לו לראות תכנים בלתי מורשים. במקרה זה ההחלטה האם משתמש רשאי לקבל תוכן מבוקש מתבססת רק על השידור הנוכחי והקונפיגורציה הראשונית שלו. 'משתמש חסר מעמד' נחוץ במקרים בהם השידור מופץ להתקנים שאינם בהכרח מקוונים, כגון נגן DVD במקרה זה ה"שידור" הוא בעצם התקליטור.

הגדרות כלליות

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

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

• רוחב פס נמוך; כלומר התרחבות מינימלית של התוכן עקב ההצפנה.
• דרישות אחסון נמוכות; שכל משתמש יאלץ להחזיק בכמות נמוכה ביותר האפשרית של מידע פרטי כמו מפתחות הצפנה.
• זמינות; אפשרות למצב של שידור "חסר מעמד" כך שהמשתמש אינו נדרש להיות מקוון כמו תקליטור.
• עמידות; תכונה חשובה של שידור מוצפן היא היכולת להתנגד לשיתוף פעולה או "קואליציה" של מספר משתמשים כנגד המערכת על מנת לקבל מידע בלתי מורשה.

בדרך כלל יש איזון בין הצורך בביטחון לעומת נוחות. לפעמים מתפשרים בביטחון השידור המוצפן על מנת להבטיח תעבורה גבוהה או תקורה נמוכה. על מנת להעריך או להשוות בין שיטות שידור מוצפן, צריך להגדיר מספר פרמטרים. קבוצת כל המשתמשים הרשומים במערכת מסומנת ב-${\mathcal {N}}$ ומכילה $N=|{\mathcal {N}}|$ חברים. הקבוצה ${\mathcal {R}}\subset {\mathcal {N}}$ היא תת-קבוצה המכילה $r=|{\mathcal {R}}|$ משתמשים בלתי מורשים (Revoked) שיש לבטל את תקפות מפתחות ההצפנה שלהם ולא לאפשר להם ליהנות מהתוכן (כגון, אם לא שילמו עבורו). $M$ מייצג את התוכן המיועד לשידור במצבו הגלוי, אותו השרת צריך להצפין ולשדר באופן כזה שרק תת-הקבוצה $u\in {\mathcal {N}}\setminus {\mathcal {R}}$ (המורשים פחות המבוטלים) תוכל לפענחו, בעוד שקואליציה של $t$ או פחות משתמשים החברים ב-${\mathcal {R}}$ לא תוכל. כמובן שאם אחד מהמשתמשים המורשים משתתף בקואליציה לא ניתן להגן על סודיות התוכן. מקרה כזה מוגדר כ'בגידה' והטיפול בה נעשה באמצעות מנגנון מעקב (Traitor tracing) להלן. מערכת שידור מוצפן כוללת שלושה מרכיבים עיקריים:

1. סכימת הקצאת מפתח. שהיא שיטת איתחול המייצרת ומפיצה מפתחות הצפנה סודיים לכל המשתמשים הרשומים.
2. אלגוריתם שידור. בהינתן תוכן $M$ וקבוצה בלתי מורשית ${\mathcal {R}}$ מפיק ומשדר את $M'$ לכל $N$ המשתמשים הרשומים.
3. אלגוריתם פענוח. משתמש לגיטימי שאינו נכלל בקבוצה ${\mathcal {R}}$ המקבל את $M'$ משחזר את התוכן המקורי $M$ באמצעות המפתח הסודי שברשותו משלב 1.

היסטוריה

נושא הצפנה משודרת הועלה כבר ב-1991 על ידי שמשון ברקוביץ שהציע שימוש בחלוקת סוד כדי לפתור את הבעיה. הגדרה הפורמלית ראשונה וניתוח יסודי של הבעיה ניתנו ב-1993 על ידי עמוס פיאט ומוני נאור. הם הציעו אלגוריתם המבוסס על עץ בינארי שמאפשר למנוע מכל מספר של משתמשים מלקבל תוכן כל עוד לא יותר מ-$k$ מהם משתפים פעולה נגד המערכת. כמות המפתחות המוצפנים היא בסדר גודל של $O(k{\text{ log}}^{2}k)$ וכל משתמש צריך לאחסן מספר מפתחות שהוא ביחס לוגריתמי ל-$k$. כמות העבודה הנדרשת מכל משתמש היא $O(r/k)$ פענוחים. כמו כן הפרוטוקול תומך בסביבת Stateless ואינו דורש נוכחות (בלתי מקוון).

רעיון השימוש בלוגיקה של עץ היררכי הומצא בנפרד ב-1990 על ידי וולנר (Wallner) ווונג (Wong) שפיתחו שיטות לתקשורת בטוחה בתרחיש רב-נתיב (multicast) במצב מקוון. בשיטה זו שנקראת בקיצור LKH (להלן) יש צורך לשדר $2{\text{ log }}N$ מפתחות בכל פעם שמעדכנים את הרשימה (מבטלים משתמש), כל משתמש נדרש לאחסן ${\text{log }}N$ מפתחות וכן כמות העבודה שכל משתמש נדרש לבצע היא ${\text{log }}N$ פעולות פענוח (בממוצע רק 1). הפרוטוקול בטוח ללא תלות ב-$k$ אך כמות המידע המשודר היא $r{\text{ log }}N$ שזה יחסית גבוה אלא אם כן כל משתמש יאחסן יותר מידע. הנושא נחקר על ידי רבים אחרים.

השיטה subset difference (להלן) שהוצעה ב-2002 על ידי נאור ולוצפיץ' היא הטובה ביותר למצב Statesless. לפי שיטה זו התוכן המשודר דורש רק $1.38r$ הצפנות במקרה הממוצע כדי לבטל $r$ משתמשים, כמות האיחסון של כל מקבל היא $\textstyle {\frac {1}{2}}{\text{ log}}^{2}N$ מפתחות. אין הגבלה על $r$ וכן תהליך הקצאת המפתח הוא חישובי ולא מסתמך על תורת האינפורמציה. שמיר הלוי ואחרים הציעו שיפור לשיטה זו שנקרא LSD כמות האחסון מצטמצמת לפיה ל-${\text{log}}^{1+\epsilon }N$ וכמות התוכן היא בפקטור $r/\epsilon$, כאשר $\epsilon$ יכול 2.

שיטות ומבנים

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

Subset Cover

הבסיס התיאורתי למשפחת האלגוריתמים Subset-Cover מתחיל במושג שהגו לראשונה פיאט ונאור שנקרא סכימת ביטול "k-resilient" הפועלת כך שבהינתן קבוצה $U$ של $n$ חברים, הסכימה תהיה עמידה כנגד קואליציה $S$ של עד $k$ חברים. לשם כך מקצים מפתחות הצפנה סודיים ונפרדים $K_{B}$ עבור כל תת-קבוצה $B\subset U$ אפשרית כאשר $0\leq |B|\leq k$, אותו מעבירים לכל משתמש $u\in U-B$ (לכל המשתמשים החברים ב-$U$ אך אינם נמנים עם $B$). אפשר לדמות זאת באנלוגיה למצב שבו המפתחות נרשמים על גבי מצחם של כל המשתמשים, כל אחד יכול לראות את המפתחות של כולם למעט המפתח הרשום על מצחו. אם הקבוצה $T$ היא אוסף חברים מורשים, מפתח ההצפנה הסודי עבורם הוא XOR של כל המפתחות $K_{B}$ כאשר $B\subset U-T$. כל קואליציה של $S\leq k$ חברים תחסר את המפתח $K_{S}$ (המשויך להם) ולכן לא תוכל לחלץ את המפתח של $T$ בתנאי שמתקיים $S\cap T=\emptyset$.

הסכימה המתוארת הוכחה בטוחה מהיבט תיאורתי אך אינה יעילה, כדי לכסות את כל האפשרויות, כל משתמש נדרש לאחסן $\textstyle \sum _{i=0}^{k}{\binom {n}{k}}$ מפתחות (לדוגמה; עבור עשרה משתמשים שמתוכם חמשה מבוטלים, כל משתמש נדרש לאחסן 638 מפתחות). במקרה הפרטי שבו $k=1$ (כלומר רק משתמש אחד מבוטל) מספר המפתחות שכל אחד נדרש לשמור הוא $n+1$. אפשר לשפר את הסכימה על ידי הסתמכות על פונקציה חד-כיוונית ואז הביטחון אינו אבסולוטי אלא חישובי. מדמים את רשימת המשתמשים לעץ בינארי שכל עלה בו מתאים למשתמש אחד. מקצים מפתח אקראי לשורש העץ ולכל צומת מקצים רקורסיבית מפתח מתאים על ידי פונקציה פסאודו-אקראית $f:\{0,1\}^{\ell }\mapsto \{0,1\}^{2\ell }$ שמקבלת קלט מפתח של צומת אב ומפיקה פלט כפול באורכו, מחצית אחת מקצים לבן השמאלי והמחצית השנייה לבן הימני. היתרון שבשיטת בנייה זו הוא שכעת כל משתמש נדרש לדעת בעיקרון רק מפתח של אב קדום כלשהו שלו, כי המפתח שלו הוא תוצאה של הפעלת הפונקציה הפסאודו-אקראית באופן רקורסיבי במסלול מהשורש ועד לעלה שלו. כעת כדי לבטל עלים מסוימים מסירים את המסלולים המקשרים ביניהם לבין שורש העץ, כך למעשה נוצר "יער" של $\lceil {\text{log }}n\rceil$ תת-עצים, כל משתמש צריך לקבל כעת את מפתחות של כל שורשי תת-העצים. כעת אם המדיה מוצפנת עם XOR של כל המפתחות המשויכים למשתמשים שהוסרו, כל משתמש $x$ יכול לחשב כל מפתח מלבד המפתח המשויך אליו ולכן אינו יכול לחלץ את המפתח לתוכן. המשתמשים המורשים לעומת זאת מקבלים את המפתח כשהוא מוצפן עם המפתח הפרטי שהם משתפים עם השרת.

דרך אחרת היא לבסס את הסכימה על בעיה מתורת המספרים דוגמת RSA. השרת מכין מפתח שורש שהוא $n=pq$, כפולה של שני ראשוניים גדולים, בוחר יוצר $g$ מסדר גבוה וכל משתמש $i$ מקבל את $g_{i}=g^{p_{i}}$ כאשר כל $p_{i}$ זרים הדדית. המפתח המשותף לקבוצה $T$ הוא $g_{T}=g^{p_{T}}{\text{ mod }}n$ כאשר $\textstyle p_{T}=\prod _{i\in T}p_{i}$ ואז המשתמש $i$ מחלץ את המפתח המשותף על ידי $\textstyle g_{T}=g_{i}^{\prod _{j\in T-\{i\}}p_{j}}{\text{ mod }}n$ כלומר חזקה של כל המפתחות למעט המפתח שלו. הוכח שהסכימה הזו בטוחה בהנחה שפירוק לגורמים היא בעיה קשה וכל מה שנדרש לאחסן הוא רק מפתח אחד.

בשתי הסכימות השרת אינו נדרש לשדר כלל מידע נלווה לתוכן המוצפן, כיוון שהמפתחות הוקצו מראש ובידי המשתמשים המידע הדרוש לחילוץ מפתח השיחה. אולם שיתוף פעולה של שני משתמשים מאפשר להם לשבור בקלות את המערכת. אלגוריתם Complete Subset Cover מרחיב את הרעיון הבסיסי לעמידות כנגד $k>1$ מבוטלים וכן מצמצם את דרישות האחסון ברמת משתמש במחיר שהשרת ישדר לפני כל תוכן מוצפן מידע מסוים שנקרא "כותר". בכללות הוא מגדיר אוסף של תת-קבוצות $S_{1},...,S_{w}$ כאשר $S_{j}\subseteq {\mathcal {N}}$. מקצים מפתח סודי ארוך טווח (קבוע) $L_{j}$ לכל $S_{j}$ ולכל $u\in S_{j}$ מקצים מידע פרטי $I_{u}$ איתו הוא אמור לשחזר את $L_{j}$. בהינתן קבוצה ${\mathcal {R}}$ של משתמשים מבוטלים יתר המשתמשים ${\mathcal {N}}\setminus {\mathcal {R}}$ מחולקים לתת-קבוצות זרות $S_{i_{1}},...,S_{i_{m}}$ כך שמתקיים:

${\mathcal {N}}\setminus {\mathcal {R}}=\bigcup _{j=1}^{m}S_{i_{j}}$.

$K$ מוצפן $m$ פעמים עם המפתחות $L_{i_{1}},...,L_{i_{m}}$ בהתאמה.

לצורך כך יש להגדיר שני פרימיטיבים קריפטוגרפיים: (1) צופן מהצורה $F_{K}:\{0,1\}^{*}\mapsto \{0,1\}^{*}$ להצפנת התוכן $M$ עם $K$ שצריך להיות חדש עבור כל תוכן. הצופן צריך להיות מהיר ולא אמור לגרום להתנפחות התוכן עקב ההצפנה. הוא יכול להיות צופן זרם בטוח כמו Salsa20. וכן (2) צופן מהצורה $E_{L}\{0,1\}^{\ell }\mapsto \{0,1\}^{\ell }$ עם מפתח ארוך-טווח $L$ שהמרכז משתף עם כל משתמש בנפרד. יכול להיות צופן בלוקים כמו AES. מסיבות של יעילות רצוי ש-$K$ יהיה קצר (להגנה על זכויות יוצרים אין צורך בהצפנה כבדה) ורק המפתח ארוך הטווח צריך להיות באורך מלא (בדרך כלל 128 סיביות). בגלל שאורך הכותר תלוי בגודל הבלוק של צופן הבלוקים, אפשר להשתמש בחלופה חסכונית כך; $[{\text{Prefix}}_{|K|}E_{L}({\mathcal {U}})]\oplus K$ במקום בלוק מלא. כאשר הביטוי ${\text{Prefix}}_{i}(S)$ פירושו $i$ הסיביות הראשונות של הערך $S$ וכן ${\mathcal {U}}$ הוא מחרוזת אקראית כלשהי באורך בלוק מלא.

תיאור הסכימה

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

כל משמש $u$ מקבל מידע סודי $I_{u}$ באופן כזה שעבור כל $1\leq i\leq w$ כאשר $u\in S_{i}$, מאפשר לו לחלץ את המפתח $L_{i}$ לקבוצה שלו $S_{i}$. את $L_{i}$ אפשר להכין בשתי דרכים, בחירה אקראית (אמיתית) ונפרדת עבור כל מפתח, מה שמספק ביטחון אבסולוטי מהיבט של תורת האינפורמציה כמו פנקס חד-פעמי או כפונקציה של מידע סודי אחר שאז ביטחונו נשען על הפונקציה הפסאודו-אקראית מה שמספק ביטחון חישובי.

2. אלגוריתם שידור

מרכז שמעוניין לשדר או להפיץ תוכן מוצפן פועל כדלהלן;

1. בוחר מפתח שיחה אקראי $K$.

2. בהינתן קבוצה ${\mathcal {R}}$ של משתמשים מבוטלים, המרכז מפריד את כל המשתמשים הבלתי מבוטלים ל-$m$ תת-קבוצות זרות $S_{i_{1}},...,S_{i_{m}}$ ומקצה להם מפתחות סודיים $L_{i_{1}},...,L_{i_{m}}$ בהתאמה.

3. המרכז מצפין את מפתח השיחה $m$ פעמים עם כל המפתחות $L_{i}$ ומשדר את התוכן כדלהלן:

$\langle [i_{1},i_{2},...,i_{m},E_{L_{i_{1}}}(K),...,E_{L_{i_{m}}}(K)],F_{K}(M)\rangle$

החלק שמופיע בסוגריים המרובעות נקרא "כותר" והחלק האחרון הוא גוף התוכן.

3. אלגוריתם פענוח

מקבל מורשה $u$ הקולט את השידור: $[\langle i_{1},i_{2},...,i_{m},C_{1},C_{2},C_{m}],M'\rangle$ פועל כדלהלן:

1. מוצא את $i_{j}$ כך שמתקיים $u\in S_{i_{j}}$ (תת-הקבוצה אליה הוא שייך) במקרה שהוא נמנה עם הקבוצה ${\mathcal {R}}$ התוצאה היא null.

2. מחלץ את המפתח המתאים $L_{j}$ באמצעות $I_{u}$.

3. מפענח את מפתח השיחה: $K=D_{L_{i_{j}}}(C_{j})$.

4. מפענח את התוכן: $D_{K}(M')$.

עיקר העבודה ביישום הסכימה האמורה היא (1) הכנת אוסף של כל תת-הקבוצות האפשריות של המשתמשים הרשומים (2) הקצאת מפתח לכל תת-קבוצה אפשרית באוסף, (3) "כיסוי" כל המשתמשים הלגיטימיים פחות המבוטלים בתת-קבוצות נפרדות ו-(4) הגדרת שיטה שבה כל משתמש יוכל למצוא את המפתח המתאים לקבוצה שלו. אלגוריתם Subset-Cover ניתן למימוש באופן הבא: אוסף הקבוצות מתאים לכל תת-העצים בעץ בינארי מלא בעל $N$ עלים, כל עלה כנגד משתמש אחד. סך הכול עלים וצמתים הוא $2N-1$. כל צומת $v_{i}$ מייצג תת-עץ בעץ הכללי, כל משתמש $u$ נמנה עם תת-הקבוצה $S_{i}$ אך ורק אם שורש תת-הקבוצה $v_{i}$ הוא אב קדום שלו. לכל צומת מוקצה מפתח $L_{i}$ וכל משתמש $u$ מקבל ${\text{log }}N+1$ מפתחות המשויכים לכל הצמתים במסלול המקשר מהעלה שלו לשורש העץ. אם אוסף המשתמשים $u_{1},...,u_{r}$ שייכים לקבוצה ${\mathcal {R}}$, מפרידים את יתר העלים בעץ לתת-קבוצות נפרדות על ידי הכנת "עץ שטיינר" מכוון, בקיצור ($ST({\mathcal {R}}$ שהוא עץ פורש מינימלי הנוצר על ידי $r$ העלים $u_{i}$ המקושרים לשורש העץ באמצעות תוספת קשתות המינימלית האפשרית. כעת תת-הקבוצות האחרות הן למעשה כל תת-העצים "התלויים", כלומר העצים אשר שורשיהם סמוכים לצמתים בעץ $ST({\mathcal {R}})$ בעלי דרגה 1, אך אינם נמצאים בו. אוסף הקבוצות הללו נקרא "כיסוי" ומספרם הוא בערך $r\cdot (i-{\text{log }}r)+1$. ישנן כמה דרכים כדי למצוא במהירות וביעילות חברות באחת מהקבוצות של משתמש נתון $u$, אפשר להשתמש למשל בטבלת גיבוב או בקוד תיקון שגיאות. רצוי שהמידע בכותר יהיה דחוס ככל האפשר. עם אופטימיזציה אפשר להגיע לתצורה שבה החיפוש נעשה בסיבוכיות של ${\text{log log }}N$ השוואות. כמות המפתחות שכל משתמש יאחסן תעמוד על ${\text{log }}N$, מספר המפתחות המוצפנים שהשרת משדר $\textstyle r{\text{ log }}{\frac {N}{r}}$ ואילו התוכן מוצפן רק פעם אחת.

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. הוא מגדיר טבלה עם $A$ שורות ו-$C$ עמודות, ומתייחסים לכל התקן (מקלט) כאל אוסף של $C$ כניסות בטבלה, אחת בכל עמודה, כלומר $u=[u_{1},...,u_{C}]$ כאשר $u_{i}\in \{0,1,...,A-1\}$. אוסף כל תת-הקבוצות האפשריות $S_{1},...,S_{w}$ המוגדר על ידי האלגוריתם מתאים לאוסף התקנים שנמצאים באותה כניסה בעמודה נתונה. למשל $S_{r,i}$ כולל את כל ההתקנים $u=[u_{1},...,u_{C}]$ כך ש-$u_{i}=r$. עבור כל שורה $i$ ועמודה $j$ הסכימה מקצה מפתח המיוצג על ידי $L_{i,j}$. בכל התקן $u=[u_{1},...,u_{C}]$ מוטמע מידע פרטי (סודי) $I_{u}$ הכולל $C$ מפתחות $L_{u_{1},1},L_{u_{2},2},...,L_{u_{C},C}$.

עבור קבוצה ${\mathcal {R}}$ של התקנים "מבוטלים" (Revoked), האלגוריתם מחלק את ${\mathcal {N}}\setminus {\mathcal {R}}$ כך שכל תת-קבוצה $S_{i,j}$ מכוסה רק אם $S_{i,j}\cap {\mathcal {R}}=\emptyset$. בעוד שהסכימה מבטיחה שהתקן לא מאושר לא יכלל בכיסוי, יש סיכוי נמוך שהתקן מאושר לא יכלל גם הוא. כלומר ייתכן התקן לגיטימי שייחשב כלא תקף. בניגוד לשיטת נאור, תת-הקבוצות בסכימת CPRM/CPPM אינן זרות לגמרי ולכן הכיסוי אינו משולם. יתרה מזו הסיכוי שהתקן מאושר יפסל גדל ככל ש-$r$ גדל (מספר ההתקנים המבוטלים).

לשם השוואה לשיטת נאור אם $C={\text{log }}N$ ו-$A=r$ אזי מנגנון CPRM/CPPM דורש $r{\text{ log }}N$ הצפנות, כמות האחסון במקלט או התקן עומדת על ${\text{log }}N$ מפתחות, וכמות החישוב הדרושה בצד ההתקן היא רק פעולת פענוח אחת. למשל ב-DVD בלוק המפתח MKB מכיל 3MB. חסרון נוסף הוא בעובדה ש-$r$ מוגבל, כלומר מספר המכשירים המבוטלים המקסימלי שאפשר להגדיר בשיטה זו הוא בערך 10,000. בשיטת נאור אפשר להגיע ל-250,000.

LKH

תיאור עץ LKH

שיטת Logical-tree-hierarchy פותחה בעיקר לרב-נתיב במצב מקוון ונכללה בהצעה לתקן RFC-2627. המערכת מנהלת מפתח הצפנה משותף יחיד עבור קבוצת כל המשתתפים הפעילים ${\mathcal {N}}$ שנקרא Net Key שמועבר אליהם באמצעות פרוטוקול העברת מפתח קריפטוגרפי כמו דיפי-הלמן. המערכת מוסיפה או מסירה משתתף (אחד בכל מהלך) על ידי אלגוריתם הקצאת מפתח שבו המערכת מחשבת ומקצה מפתחות הצפנה לכל המשתתפים הלגיטימיים. התהליך מנוהל על ידי שרת שמדווח לכל משתתפים על המהלכים שבוצעו. המשתתפים מיוצגים על ידי העלים בעץ בינארי מאוזן בגובה ${\text{log }}N$, לכל צומת $v_{i}$ מוקצה מפתח $K_{i}$. כל משתתף $u_{i}$ מקבל (בתהליך שנקרא Rekeying באמצעות המפתח הראשי) את כל המפתחות המשויכים לכל הצמתים במסלול המקשר משורש העץ לעלה שלו (לדוגמה בתרשים משתתף מספר 3 מקבל את המפתחות B,I,M). כדי להסיר את העלה $u$ מקצים מפתחות חדשים $K_{i}'$ לכל הצמתים $v_{i}$ לאורך המסלול המקשר מהעלה שהוסר ועד שורש העץ. כעת אם $v_{i}$ הוא צומת הנמצא על המסלול, $v_{j}$ צומת בן הנמצא על המסלול ו-$v_{l}$ הוא צומת בן שאינו על מסלול. את המפתח $K_{i}'$ של הצומת $v_{i}$ מצפינים על ידי המפתחות $K_{j}'$ ו-$K_{l}$ (שים לב שהאחרון לא התעדכן) כלומר $\langle E_{K_{j}'}(K_{i}'),E_{K_{l}}(K_{i}')\rangle$. במקרה ש-$v_{i}$ הוא צומת אב של העלה $u$ מבצעים רק הצפנה אחת עם הצאצא של $u$. המפתחות החדשים המוצפנים משודרים לכל המשתתפים הפעילים. האלגוריתם מחייב העברה של $2{\text{ log }}N$ מפתחות בכל פעולה כזו, כל משתתף נדרש לאחסן ${\text{log }}N$ מפתחות וכמות העבודה המקסימלית הנדרשת מכל משתתף היא ${\text{log }}N$ הצפנות (בממוצע נדרשת רק הצפנה אחת).

להלן טבלה להמחשה של תהליך הפצת מפתחות (Rekeying) של פרוטוקול LKH שתי העמודות האחרונות מתייחסות למספר המשתתפים שצריכים לקבל שידור בכל פעם שנוסף או מבוטל משתתף אחד בשידור.

מספר משתתפים	מעלה ($k$)	אחסון פר משתתף	שידורי מפתח יחיד ($kd-1$)	שידורי מפתחות מרובים $d(k-1)$
8	2	4	5	8
16	2	5	7	16
2048	2	12	21	2048
131072	2	18	33	131072

Subset Difference

תיאור עץ משתמשים בשיטת Subset Difference

מבנה subset difference מגדיר אוסף של תת-קבוצות של משתמשים $S_{1},...,S_{w}$ כאשר $S_{j}\in {\mathcal {N}}$. לכל תת-קבוצה מקצים מפתח הצפנה $L_{j}$, לכל משתמש $u$ משייכים מידע סודי $I_{u}$ איתו הוא יכול לחלץ את המפתחות של תת-הקבוצות אליהן הוא משויך. בהינתן הקבוצה ${\mathcal {R}}$ של משתמשים מבוטלים, יתר המשתמשים מחולקים לקבוצות זרות $S_{i_{1}},...,S_{i_{m}}$ מהאוסף אשר 'מכסות' לגמרי את כל המשתמשים, כלומר כל משתמש חבר בלפחות קבוצה אחת כזו. מפתח שיחה $K$ מוצפן $m$ פעמים עם $L_{i_{1}},...,L_{i_{m}}$ והתוכן מוצפן עם $K$. כל המשתמשים משויכים לעלים בעץ בינארי מאוזן בגובה ${\text{log }}N$ אוסף הקבוצות $S_{1},...,S_{w}$ בהגדרה הוא מהצורה "קבוצה $G_{1}$ פחות הקבוצה $G_{2}$" כאשר $G_{2}\subset G_{1}$. שתי הקבוצות מתאימות לעלים של שני תת-עצים בינאריים בהתאמה. לכן תת-קבוצה $S$ כלשהי מיוצגת על ידי שני צמתים בעץ הראשי $v_{i},v_{j}$ כך ש-$v_{i}$ הוא אב קדום של $v_{j}$ מסמנים זאת על ידי $S_{i,j}$ (כמתואר בתרשים). העלה $u$ הוא בתת-קבוצה $S_{i,j}$ אם ורק אם הוא בתת-העץ שהשורש שלו הוא $v_{j}$. במילים אחרות $u\in S_{i,j}$ אם $v_{i}$ הוא אב קדום שלו אך לא $v_{j}$. הרעיון הוא שעבור כל תת-קבוצה ${\mathcal {R}}$ של משתמשים מבוטלים אפשר למצוא קבוצה של לכל היותר $s2-1$ תת-קבוצות מהאוסף אשר מכסה את כל המשתמשים ב-${\mathcal {N}}\setminus {\mathcal {R}}$.

אם יוקצה עבור כל משתמש מפתחות קבועים עבור אוסף כל הקבוצות מספר המפתחות עבור כל משתמש יהיה $N$. במקום זאת אפשר לצמצם את המידע הזה באופן כזה שרק $\textstyle {\frac {1}{2}}{\text{ log}}^{2}N$ מפתחות יאוחסנו, את המפתח הנכון המשתמש מחלץ באמצעות מבנה עץ דמוי GGM. לכל צומת מקצים שלושה מספרים אקראיים באמצעות מחולל פסאודו-אקראי בטוח, לכל צומת מצמידים תוויות המכילות את המספרים האקראיים $G_{L}$ תווית עבור צד שמאל, $G_{R}$ תווית עבור צד ימין ו-$G_{M}$ תווית המייצגת את המפתח הסודי המשויך לעלה (כמתואר בתרשים). שים לב שלא ניתן לשחזר את המפתח של צומת נתון ללא ידיעת צומת האב.

בעת הפענוח המשתמש $u$ מקבל את המחרוזת הבאה:

$\langle [i_{1},...,i_{m},E_{L_{i_{1}}}(K),E_{L_{i_{2}}}(K),...,E_{L_{i_{m}}}(K)],F_{K}(M)\rangle$

תחילה מוצא את תת-הקבוצה $S_{i,j}$ אליה הוא משויך ומחשב את המפתח המתאים $L_{i,j}$ באמצעות הפעלת הפונקציה הפסאודו ראנדומלית על צמתי האב ${\text{log }}N$ פעמים. באמצעות טבלת גיבוב אפשר לצמצם את פעולת החיפוש של המשתמש ל-$O({\text{loglog }}N)$. לאחר מכן כל מה שנדרש הוא פעולת פענוח אחת כדי לחלץ את התוכן המוצפן.

הפונקציות $F_{K}$ ו-$E_{L}$ מייצגות אלגוריתמים להצפנה כאשר הראשון מומלץ שיהיה צופן זרם והאחרון צופן בלוקים כמו AES.