SD e LSD
Lezione tenuta dal
Presentazione di:
Prof. P. D’Arco
Gaetano Ragozzino
SD (Subset Difference)


Obiettivo:Ridurre la lunghezza dell’header da O(r*lg(N/r))
a O(r)
Idea: Ampliare la collezione di sottoinsiemi {S1…Sn} con cui
ricoprire N\R
1)Collezione di sottoinsiemi S1…Sw con cui ricoprire N\R

Si,j={sottoinsiemi di foglie discendenti da vi ma non da vj}

SD={tutti i sottoinsiemi differenza Si,j}
vi
vi
vj
vj
…
…
…
2)Assegnamento di chiavi Li,j ai sottoinsiemi Si,j


1°Caso: Li,j scelte indipendentemente e uniformemente a
caso
2°Caso: Li,j calcolate attraverso un generatore pseudo
casuale
m
3) Partizionamento di N\R=U Si
i=1

Dato R, calcoliamo l’albero di Steiner (ST(R)) e poniamo
T=ST(R)
1
2
4
3
6
5
9
18
11
22
13
27
Procedura di partizionamento




1.Siano vi e vj due foglie t.c. il più piccolo antenato v non
contenga altre foglie di T. Siano ve e vk figli di v t.c. vi
discende da ve e vj da vk.
2.Se ve è diverso da vi aggiungi Se,i. Se vk è diverso da vj
aggiungi Sk,j.
3.Rimuovi da T tutti i discendenti di v e trasforma v in una
foglia.
4.Se rimane una foglia termina, altrimenti ritorna al passo
1.
1) 3)
1
v
2
3
ve
vk
4
8
16
9
17
6
5
18
R
10
19
20
21
12
11
22
R
23
7
24
25
13
26
14
27
R
R={18,22,27}; vi=18; vj=22; v=2; ve=4; vk=5;
2)S4,18, S5,22
28
29
15
30
31
1) 3)
v
1
ve=vi
vk
2
3
Rimane solo la radice
6
7
12
24
25
13
26
27
vj=R
vi=2; vj=27; v=1; ve=2; vk=3;
2)S4,18, S5,22,, S3,27
14
28
29
15
30
31
1
2
3
4
8
16
9
17
6
5
18
R
S4,18
10
19
20
21
12
11
22
23
7
24
R
25
13
26
14
27
28
R
S5,22
S3,27
<S4,18, S5,22, S3,27, EL4,18(k), EL5,22(k), EL3,27(k), Ek(M)>
Header
29
15
30
31
Taglia Header?


Lemma. Dato un qualsiasi insieme di revocati R, il metodo
precedente partiziona N\R in al più 2r-1 sottoinsiemi
disgiunti.
Ad ogni passo vengono aggiunti alla copertura al più due
sottoinsiemi differenza e il numero di revocati diminuisce di
uno ad eccezione dell’ultimo passo che potrebbe non ridurre
il numero di revocati e aggiungere un sottoinsieme.
Quanto vale |SD|?

Ipotesi: numero utenti N potenza di 2.
vi
vi
1
vj
2
S1,2
1
3
S1,3
vj
vj
vj
2
3
vj vj
vj
4
5
6
vj
7
Allora vj può assumere:
2k+(2k -1) -1= 2*2k -2
posizioni
|SD|=2
S1,2
S1,3
S1,4
S1,5
S1,6
S1,7
|SD|=6
Sia vi il nodo radice di un
albero di altezza k.
Quanto vale |SD|?

Quante posizioni vi può assumere?

Consideriamo l’albero T con altezza k=2
vi
#sottoalberi di altezza
1
vi
vi
2
4
k=2 => 2lg4-2=1
3
5
6
7
#sottoalberi di altezza
k=1 => 2lg4-1=2
Quanto vale |SD|?

Quindi:
lgN

#Si,j= k=1
S [2*2k-2]*2lgN-k
#sottoalberi Ti di altezza k
#posizioni che vj può assumere in Ti
lgN
= 2* S
k=1
2k*2lgN-k
lgN
-2* k=1
S 2lgN-k
Quanto vale |SD|?
lgN
lgN
k=1
k=1
=2* S N -2* S 2lgN-k

Sia l=lgN-k; Per k=1, si ha l=lgN-1; Per k=lgN, si ha l=0;

Poichè S 2i=2m+1-1, risulta
m
i=0
lgN
lgN-1
k=1
l=0
= 2* S N -2* S 2l
= 2*N*lgN -2N+2
= O(N*lgN)
2)Assegnamento di chiavi Li,j a Si,j


1°Caso: Li,j scelte indipendentemente e uniformemente a
caso
Quanto vale |Iu|?
Tk
vj non è sulla path
k
u
memorizza
#chiavi
Li,j
proporzionale al #nodi di Tk che
non si trovano sulla path u-root
u
Quanto vale |Iu|?

Relativamente all’albero Tk
Iu=2k+2k-1-(k+1)=2*2k-k-2
path
#foglie
#nodi
interni

Quindi occorre tener conto di tutti gli alberi di altezza k, per
1<=k<=lgN
Quanto vale |Iu|?
lgN

Iu= k=1
S
(2k+1-k-2)=
lgN
= 2* k=1
S
2k
lgN
S
k=1
2k+1
lgN
– k=1
S (k+2)
lgN
- k=1
S k -2*lgN
m
m
h=1
i=0
Poichè S h =m(m+1)/2 e S 2i=2m+1-1, risulta
= 2*(2lgN+1-2) –lgN(lgN+1)/2 -2*lgN
= 4*N -4 –lgN(lgN+1)/2 -2lgN
= O(N)
2)Assegnamento di chiavi Li,j a Si,j

2°Caso: Li,j calcolate attraverso un generatore pseudo
casuale

G:{0,1}n

S – label casuale del nodo,
S
{0,1}3n
G_L (S)

G_L(S) – label del figlio sinistro,

G_R(S) – label del figlio destro,
G_M(S) – chiave del nodo.
G (S) =
G_L (S)
G_M (S)

G_R (S)
G_R (S)
Calcolo della chiave Li,j associata a Si,j
S=Li
vi
G_L (Li)
G_R (Li)
G_L(G_L (Li))
G_R(G_L(G_L (Li)))
G_L(G_L(G_L (Li)))
vj
…
…
…
LABELi,j = G_R(G_L(G_L (Li)))
Li,j = G_M (LABELi,j )
Calcolo e distribuzione delle etichette LABELi,j



Ogni utente corrisponde ad una foglia
dell’albero.
Ad ogni nodo interno vi viene associato un
valore casuale Li
Le etichette LABELi,j associate ai sottoinsiemi
differenza Si,j sono calcolate a partire da Li
Calcolo e distribuzione delle etichette LABELi,j



Per ogni antenato vi di u con label
casuale Li, u riceve tutte le etichette
pseudocasuali LABELi,j associate ai nodi
vj che sono a distanza uno dalla path da
vi ad u.
vi
A partire da esse, l’utente u può
calcolare le etichette di tutti i
sottoinsiemi differenza Si,j a cui
appartiene,
relativamente
all’albero
radicato in vi.
Calcolata l’etichetta LABELi,j, l’utente
può calcolare la chiave Li,j
u
Etichette


Quante etichette deve memorizzare u per poter calcolare le
chiavi Li,j di tutti i sottoinsiemi differenza a cui appartiene?
Ogni path con k nodi contribuisce con k-1 etichette, quindi
lgN+1
#totetichette = S (k-1)+1
k=1
= lgN*(logN+1)/2+1
= O(lg2N)
Perché funziona? (light …)
• Osservazione 1. Ogni nodo vj che non è un antenato di u in Ti
ha un’etichetta LABELi,j che può essere calcolata a partire da
un’etichetta di un nodo a distanza uno dalla path u – root di Ti
• Osservazione 2. Un utente u non è in grado di calcolare chiavi
associate a sottoinsiemi differenza a cui non appartiene
LSD (Layered Subset Difference)

Idea: “sfoltire” la collezione di sottoinsiemi di SD {S1…Sw} e
permettere di ricoprire N\R ancora con O(r) sottoinsiemi ma
in modo tale che l’utente u memorizzi O(lg3/2N) etichette
vi
1
vk
2
3
vj
4
8
5
9
10
6
11
12
7
13
14
15
Si,,j = Si,k U Sk,,j
Se vi,vk,vj sono vertici che occorrono in questo ordine lungo una
path radice-foglia allora Si,j può sempre essere ottenuto come
l’unione di Si,k e Sk,j, cioè, se “serve” Si,j si possono usare Si,k e Sk,j

La collezione di insiemi Si,j in LSD si ottiene restringendo i
livelli in cui i vertici vi e vj possono stare
Livello
Speciale
lgN
Strato
2lgN
Livelli speciali e strati

Identifichiamo nell’albero lgN livelli speciali. I livelli tra due
livelli speciali compresi gli estremi formano uno strato. Si,j è
nella collezione di sottoinsiemi di LSD se e solo se :

vi giace su un livello speciale

vi e vj appartengono allo stesso strato
Esempio di funzionamento
v1
v2
v3
v4
v5
v8
u1
v9
u2
u3
u4
v6
v10
u5
v11
u6
u7
u8
v12
u9
v7
v13
v14
v15
u10 u11 u12 u13 u14 u15 u16
SD: Sv4,u1, Sv10,u5, Sv11,u8, Sv3,u12;
LSD: Sv4,u1, Sv10,u5, Sv11,u8, Sv3,v6, Sv6,u12;
Livelli speciali
Strati
Collezione di sottoinsiemi LSD

Insiemi Si,j che soddisfano le condizioni sono detti utili

lgN(lgN* lgN) + lgN*lgN = 0(lg3/2N)
#strati
#etichette di
ogni strato
#livelli
speciali
#posizioni di vj nel caso
peggiore(vi sul 1°livello
speciale)
Riferimenti
D. Naor, M. Naor and J. Lotspiech.
Revocation and Tracing Schemes for Stateless Receivers.
Advances in Cryptology, Proceedings of Crypto'01, Lecture Notes in
Computer Science, Vol. 2139, pp. 41--62, 2001.
D. Halevy and A. Shamir.
The LSD Broadcast Encryption Scheme.
Advances in Cryptology, Proceedings of Crypto '02, Lecture Notes in
Computer Science, Vol. 2442, pp. 47--60, 2002.