ｽﾗｲﾄﾞﾀｲﾄﾙなし - ISIT Web Index Page

Scalable and Reliable
Key Distribution
Ryuzou NISHI†
† Institute of Systems & Information Technologies (ISIT)
1/
Introduction
Appearance of a large variety of
application of an information and
telecommunication
e.g. Internet, Home automation,
Sensor network, and so on
In the conventional point-to-point
communication, scalability is a issue.
Broadcast communication is desired
Issues of broadcast security
1. Communication reliability
・Re-transmission request is a
large load to transmitter
・In a case of failure of
receiving keys, it is
impossible to decrypt
following messages
2. Communication overhead
frequent key-update cause
communication overhead,
and the overhead causes a
degradation of
communication reliability
2/
Introduction
Our work
Area
： Key distribution for group key update
in case of members' joining in or leaving
from group in channel of poor quality,
e.g. wireless, power line communication.
Group key is used to encrypt or decrypt
messages and is shared among all the
members of a group.
Goal
： Reliable group key update where rekey
message size is independent of group size,
Previous Work
scalability
□ GKMP : Group Key Management Protocol
Key server distributes an updated key to each
member through unicast cannel
O(N)
□ LKH ： Logical Key Hierarchy
group key
Ka
O(N) → O(log(N))
Kc
Kb
Kd
Ke
Kf
Kg
M1
M2
M3
M4
4/
Previous Work
reliability
□ FEC : Forward Error Correction
In a sender, redundancy is added into an
original data.
If data error occur on the way, a receiver
corrects the error.
method
coding gain
BCH
2.1 dB
Convolution
5.1 dB
5/
Proposal : Basic idea
□ Updated key is distributed by using Direct
Sequence Spread Spectrum (DS-SS)
communication scheme which spreading code
are M-sequences (maximal-length sequences)
Updated
group key
ID
shift
multiplexer
secret key
M-sequence
Updated
group key
1 bit
M-sequence
1 period
ｔime
ｔime
secret key
6/
Proposal : Cyclic shift M-sequence
M-sequences（u0,u1,・・・,uN-1)
ui = +1 or -1 N: sequence's length
Cyclic shift M-sequences Ui = （ui,ui+1,・・・,uN-1 , u0,・・・, ui-1)
A cross-correlation between Ui and Uj is maximum N
at i=j, and -1 at i≠ｊ.
And a cross-correlation between －Ui and Uj is
maximum -N at i=j, and +1 at i≠ｊ.
i=j point
M-sequences' autocorrelation curve
M-sequences 1 period
7/
Proposal : Setup
1. The key server sends the secret key to each member in secure
channel where secret key is depicted by GK digits and maximum
number of each digit is N-1
2. The key server regroup all member into subgroups where the
maximum number of members of each subgroup is N
3. The key server sends the M-sequences and ID(1,2,...,GK)
Where a different subgroup uses a different M-sequence and
each member of a same subgroup uses a different cyclic shift Msequence generated from a same M-sequence.
Key server
M-seq.M1
ID1
M-seq.MNs
M-seq.M2
ID2
subgroup #1
subgroup #2
・・・
IDNs
subgroup #Ns
8/
Proposal : Basic idea
□ Updated key is distributed by using Direct
Sequence Spread Spectrum (DS-SS)
communication scheme which spreading code
are M-sequences (maximal-length sequences)
Updated
group key
ID
shift
multiplexer
secret key
M-sequence
Updated
group key
1 bit
M-sequence
1period
ｔime
ｔime
secret key
9/
Proposal : Secret key →
M-sequence
In the case that the number of k digit of member
M1's secret key is ik, cyclic shift M-sequence
（uik,uik+1,・・・,uN-1 , u0,・・・,uik-1） is generated by cyclically
shifting M-sequence （u0,u1,・・・,uN-1) ik times.
About each digit of the secret key, similar process
are done.
１-st digit
（ui1,ui1+1,・・・,uN-1 , u0,・・・,ui1-1）
GK-th digit
・・・
（uiGK,uiGK+1,・・・,uN-1 , u0,・・・,uiGK-1）
time
M-seq.１ period
M-seq.１ period
10/
Proposal : Basic idea
□ Updated key is distributed by using Direct
Sequence Spread Spectrum (DS-SS)
communication scheme which spreading code
are M-sequences (maximal-length sequences)
Updated
group key
ID
shift
multiplexer
secret key
M-sequence
Updated
group key
1 bit
M-sequence
1period
ｔime
ｔime
secret key
11/
Proposal : ID shift and multiplier
□ Sequence （Kid,Kid+1,・・・,KGK-1 , K0,・・・,Kid-1）
is generated by cyclically shifting updated
group key（K0,K1,・・・,KGK-1) id (value of ID)
times.
□ k-th value GKk(= +1or -1) of the sequence is
multiplied with cyclic shift M-sequence
（uik,uik+1,・・・,uN-1, u0,・・・,uik-1）
１-st digit
GK-th digit
GK1 ×（ui1,ui1+1,・・・,uN-1 , u0,・・・,ui1-1）・・・GKNr × （uiNr,uiNr+1,・・・,uN-1 , u0,・・・,uiNr-1）
time
M-seq.１ period
M-seq.１ period
12/
Proposal : Basic idea
□ Updated key is distributed by using Direct
Sequence Spread Spectrum (DS-SS)
communication scheme which spreading code
are M-sequences (maximal-length sequences)
Updated
group key
ID
shift
multiplexer
secret key
M-sequence
Updated
group key
1 bit
M-sequence
1period
ｔime
ｔime
secret key
13/
Proposal : Multiplexer
□ Multiplier's outputs of all members are
multiplexed as follows.
For example, multiplexing of two members
whose output sequence are U（u0,u1,・・・,uN-1)
and U'（u'0,u'1,・・・,u'N-1)
output seq. U（u0,u1,・・・,uN-1)
+
output seq. U'（u'0,u'1,・・・,u'N-1)
multiplexed seq. U+U'（u0+u'0, u1+u'1,・・・, uN-1+ u'N-1)
14/
Proposal : Decoding of group key
2N length shift-register
received signal
・・・
sampler
adder
decoded GK
・・・
2N length reference shift-register
Group key bit can be decoded from the polarity of the adder’s output
15/
Proposal : Decoding of group key
2N length shift-register
received
signal
・・・
sampler
adder
decoded
GK
・・・
2N length reference shift-register
Decoder's output includes the following signals
・auto-correlation ( this corresponds to sent group key )
・closs-correlation between cyclic shift M-sequences which
shift times are different, but original M-sequence is same.
・closs-correlation between different M-sequences
16/
Proposal : Example of decoder's output
group key size:128 bits、M-sequence size 127bit
Supportable group size
1bit
1bit
GKk(+) GKk(-)
quant. (+) quant.(-)
127 ×2
126
-126
19
-15
127 ×3
109
-125
25
-9
127 ×4
44
-188
GKk(+) : decoder’s output when polarity of the sent group key is plus(+)
GKk(－) : decoder’s output when polarity of the sent group key is minus(－)
1bit quant. (+) : multiplexer’s output is quantized by 1bit when polarity of the sent group key is plus(+)
1bit quant. (－) : multiplexer’s output is quantized by 1bit when polarity of the sent group key is plus( －)
The larger decoder‘s output absolute becomes, the stronger the immunity to the noise becomes.
rekey message size (bit)
GKMP
128× 3 ×127
128× 127
proposal
127
3 ×127
group size （number of members）
17/
Proposal : Reliability
Criterion : improved SNR for required reliability (error rate)
SNR : Signal to Noise Ratio
・Conventional approach ( approach using FEC without ARQ )
improved SNR
( by coding gain )
5 dB
( coding ratio : 0.5、convolutional coding )
・Proposal
improved SNR ( by despreading effect )
16 dB
( = 10 * log(44) )
18/
Proposal : Security
The proposal’s security is based on that member which
should be revoked, does not know the number of times of the
shift of cyclic shift M-sequences of other members
Can an attacker know the number of times of the shift, if he
know the original M-sequence and get the receiver?
…No.
Because the decoder output is multiplexed signal as follows.
Only legitimate member who knows the number of times of
the shift, can decode group key.
Decoder output
19/
Conclusion
We propose the scalable and reliable key distribution
scheme where rekey message size is indepedent of
group size by using DS-SS communication scheme
which spreading code is M-sequences including cyclic
shift M-sequences.
The proposal improves the reliability of key and
reduces the rekey message size.
20/

Download Report