Transcript Apresentação - Universidade de Aveiro

IEEE International Symposium on Information Theory
Toronto, Canada, July 2008
Information-Theoretic Security
Theory and Practice
João Barros
Instituto de Telecomunicações
Universidade do Porto
and EECS/MIT
Steven W. McLaughlin
School of Electrical and Computer
Engineering
Georgia Institute of Technology
Today’s Layered Architecture
Standard Protocol Stack
Application
Programs and applications
Transport
End-to-end reliability, cong. control
Network
Routing and forwarding
Link
Medium access control
Physical
Channel coding and modulation
Where is security ?
2
Security: a patchwork of add-ons…
Application
End-to-end cryptography
Transport
Secure Sockets Layer (SSL)
Network
Virtual private networks (IPSec)
Link
Physical
Admission control (e.g.WPA)
Physical-layer security ?
3
Information-Theoretic-Security – are we biased?
A typical graduate course in cryptography and security always starts by
discussing Shannon's notion of perfect secrecy (widely accepted as the
strictest notion of security):
Message W
Alice
key K
X
X
X
Bob
decoded
message Wb
p(w|x)=p(x)
key K
Eve
Then, it emphasizes its conceptual beauty.
Then, it states that it is basically “useless” for any practical application.
Computational Security
4
Main Questions in this Tutorial
 What are the fundamental security limits at the physical layer?
 Which notions of security are we talking about?
 Is information-theoretic security practical?
 What kind of code constructions can we use?
 How do we build protocols based on information-theoretic security?
 Can we combine physical-layer security with classical cryptography?
 How can we secure novel networking paradigms?
 How can we go beyond confidentiality at the physical layer?
 How can we increase our credibility in the security business?
5
Our program for today
 Theoretical Foundations
 Fundamentals of Information-Theoretic Security
 Strong Secrecy versus Weak Secrecy
 Secrecy Capacity of Noisy Channels
 Practical Techniques
 Combining Cryptography and Coding
 Secrecy Capacity Achieving Codes
 Secret Key Agreement at the Physical Layer
 Advanced Topics and Applications
 Multi-user Secrecy and Network Coding Security
 Active Attacks on Coded Systems
 Beyond Secure Communications
 10 Open Issues
6
What we will not do
 Provide an exhaustive review of related work
 Elaborate on the details of the proofs
 Cover all the topics in depth
 Adress quantum information theory
 Say bad things about modern cryptography
7
Theoretical Foundations
8
Notions of Security
k-bit
message W
Alice
X
key K
X
X
Bob
k-bit decoded
message Wb
key K
Eve
Computational Security
Information-Theoretic (Perfect or
unconditional) Security
 Alice sends a k-bit message W to Bob

using an encryption scheme;
strictest notion of security, no
computability assumption
 Security schemes are based on
 Prob{W | Eve’s knowledge}=Prob{W}
(unproven) assumptions of intractability of
certain functions;
 Typically done at upper layers of the
H(W|X)=H(W) or I(X;W)=0

e.g. One-time pad
[Shannon, 1949] : H(K) ≥ H(M)
protocol stack
9
One-time Pad
Alice
k-bit message W
Bob
k bits
k bits
Key
Key
Xk
Xk
k-bit decoded
message Wb
Xk
Eve
If Eve does not know the key and P(Key=k-tuple)=1/2k
then we have p(w|xk) = p(w).
10
Shannon’s Model
k-bit
message W
Alice
X
X
Bob
k-bit decoded
message Wb
key K
key K
X
Eve
This model is somewhat pessimistic, because most
communications channels are actually noisy.
11
[Wyner, 1975]
Wyner’s Wiretap Channel (I)
Reliability & Security
For Bob and Alice,
Prob{W≠Wb| Y n} → 0
With respect to Eve,
(1/n) I(W; Zn) → 0
as n → ∞
sends W
Alice
Xn
p(y|x)
Yn
decodes Wb
Bob
p(z|y)
Zn
Eve
Secrecy Capacity:
Largest transmission rate at which both conditions can be satisfied.
Positive secrecy capacity only in the degraded case.
12
[Wyner, 1975]
Wyner’s Wiretap Channel (II)
equivocation
rate
Xn
Alice
Yn
p(y|x)
Bob
H(W)
p(z|x)
D
Zn
CS
CM
Transmission
rate
Eve
Proof Idea:
 Alice assigns multiple codewords to each message, picks one at
random and thus exhausts Eve’s capacity.
 Converse uses Fano’s inequality and classical arguments.
Rate-equivocation region:
 Two critical corner points (CM , D) and (CS , H(W))
 Unusual shape (not convex)
13
Because the transmission range is so short, NFC-enabled transactions are inherently
secure. Also, physical proximity of the device to the reader gives users the reassurance
of being in control of the process.
14
Broadcast Channel with Confidential Messages
Yn
Bob
Xn
Alice
p(yz|x)
Zn
CS  max ( I (U ; Y )  I (U ; Z ))
Eve
[Csiszár & Koerner, 1978]
p (u , x )
U  X YZ
Secrecy capacity is strictly positive if Bob’s channel
is less noisy than Eve’s, i.e. I(X;Y)>I(X;Z)
15
[Maurer, 93]
Feedback (Public Discussion)
Yn
Bob
Xn
Alice
p(yz|x)
Zn
Eve
public
authenticated
feedback
channel
Secret Key agreement scheme
 Clever protocol allows Alice and Bob to increase their secrecy capacity by
exchanging information over the feedback channel
 This requires a public authenticated feedback channel!
16
Increasing the Secrecy Capacity via Feedback
 Suppose Alice, Bob and Eve are connected via binary symmetric
channels and a public authenticated feedback channel is available.
Noisy
Channel
Error-free
public
communication
Computation
Alice
X
V+X+E
V+X+E+X
V+E
Bob
X+E
V+X+E
V
V
Eve
X+D
V+X+E
V+X+E+X+D
V+E+D
 Bob and Eve observe different noises (D, E).
 Bob feeds back random value V plus what he observed (X+E)
 Eve ends up with more noise than Bob (as in the wiretap channel)
17
[Ahlswede and Csiszar, 93]
Source Model
Xn
p(x,y,z)
Yn
Zn
Alice
Bob
public
authenticated
feedback
channel
Eve
 Alice and Bob share common randomness.
 Eve gets to see a correlated random variable.
 Alice and Eve generate a secret key using the
public authenticated channel.
18
[Maurer & Wolf, 2000]
Notions of Security
 Weak secrecy
1
H (U n | X n )  1  
n
 Strong secrecy
H (U | X )  n  
n
n
 The secrecy capacity of the discrete memoryless wiretap
channel does not change with strong secrecy.
 Proof requires fundamental tools of theoretical computer
science (extractors)
19
Example of Weak Secrecy
Un
Binary data (n bits)
Kn
One-time-pad (n-k bits)
Xn
Protected data (n-k bits)
Unprotected data (k bits)
 This trivial scheme satisfies the weak secrecy condition
while disclosing an unbounded number of bits:
1
1
k
n
n
H (U | X )  (n  k )  1   1  
n
n
n
 Clearly, it does not satisfy the strong secrecy condition:
H (U n | X n )  n  k  n  
20
The Wireless Scenario
[Barros, Rodrigues, ISIT06]
Wireless Network with Potential Eavesdropping
Can we exploit channel variability
to help secure the communication?
21
System Model
 hM(i)=hM, i, and hW(i)=hW, i (quasi-static fading model)
 hM and hW independent and complex Gaussian distributed
 SNRs M hM2 and W hM2 exponentially distributed
ITI September 2007
22
Security Characterization
General goal is maximization of transmission rate from Alice to Bob
R=(1/n) H(Wk)…
… and minimization of Eve’s information rate about the message,
=(1/n) I(Wk;YWn)
Secrecy capacity is maximum transmission rate R with  < ε.
Cautionary Note
[Maurer & Wolf, 2000]
 Stronger secrecy condition for Discrete Memoryless Channels
 Not only the rate but the total amount of information leaked to the
eavesdropper decays exponentially fast with n.
 It is possible to prove strong secrecy results for wireless channels
[Barros & Bloch, 2008]
23
Instantaneous Secrecy Capacity
Instantaneous
signal-to-noise
ratios
 M  hM P /  M2
2
 W  hW P /  W2
2
The instantaneous secrecy capacity for quasi-static fading channels
follows directly from the Gaussian case.
Cs 
{
log( 1   M )  log( 1   W ),
0,
ITI September 2007
 M  W
 M  W
24
Secrecy Outage
The outage probability:
Pout Rs   Pr C s  Rs 
- Alice chooses a target secrecy rate Rs.
- if Rs<Cs then she can communicate securely.
- otherwise, information-theoretic security is compromised.
25
[Barros, Rodrigues, ISIT06]
Outage Probability
After some maths…
Pout Rs   1 
M
 2Rs  1 
M

exp 
Rs


 2 W
M


Impact of
Distance
Outage probability for normalized
target secrecy rate Rs=0.1.
Outage probability for normalized
target secrecy rate Rs=0.1.
26
Outage Secrecy Capacity
-outage secrecy capacity:
[Barros, Rodrigues, ISIT06]
1
 
Pout Cout     Cout    Pout
Normalized outage secrecy capacity for
an outage probability Pout=0.10.
Normalized outage secrecy capacity for
an outage probability Pout=0.75.
Thicker lines: AWGN case;
Thinner lines: Fading case.
Thicker lines: AWGN case;
Thinner lines: Fading case.
27
Average Secrecy Capacity
When it comes to
information-theoretic
security, fading is
really a friend and
not a foe.
Normalized average outage secrecy capacity.
Thicker lines: AWGN case;
Thinner lines: Fading case.
28
Imperfect CSI
[Bloch,Barros, Rodrigues, McLaughlin, ITW06]
 Assumptions
 Perfect CSI for the main channel
 Imperfect CSI for the wiretap channel
hˆM  hM
hˆW  hW  W
 Proceed as if CSI was correct
 Outage probability
P(Cˆ S  CS )  P(ˆW   W )
P (ˆW   W ) 
1 1
1

2 2 1 2 / 2
 In general, Alice underestimates the secrecy capacity
29
Some recent work on (weak) secrecy capacity

Secure space-time communications (Hero, 2003)

Secrecy rates for the relay channel (Oohama, 2004)

Secrecy capacity of SIMO channels (Parada and Blahut, 2005)

Secure MlMO with artificial noise (Negi and Goel, 2005)

Gaussian MAC and cooperative jamming (Tekin and Yener, 2005)

Secrecy capacity of slow fading channels (Barros and Rodrigues, 2006)

Multiple access channel with confidential messages (Liang and Poor, Liu et al., 2006)

Secure broadcasting with multiuser diversity (Khisti, Tchamkerten, and Wornell, 2006)

Ergodic secrecy capacity (Gopala, Lai and El Gamal, Liang, Poor and Shamai 2007)

Strong secrecy for wireless channels (Barros and Bloch, 2008)
… and many more.
ITI September 2007
30
Strong secrecy for Gaussian and Wireless Channels
[Nitinawarat, Allerton 2007]
 Strong secret key agreement from Gaussian random
variables
 Lattice codes
 Quantization with side information
[Barros and Bloch, ICITS 2008]
 Strong secrecy capacity for wireless channels
 Uses tools of [Maurer and Wolf, 2000]
 Maps messages to secret keys
 Multiple copies of weakly secure wiretap codes
 Quantization and Slepian Wolf codes
 Extractor functions for privacy amplification
31
Comments
 Information Theory provides you with tools to determine
fundamental security limits in particular at the physical layer;
 There exist codes which can guarantee both reliability and
information-theoretic security;
 Secure communication over wireless channels is possible even
when the eavesdropper has a better channel (on average);
 When it comes to security, fading is a friend and not a foe.
32
Practical Techniques
33
Is physical-layer security practical?
 Motivating examples
 secure error correcting codes and the channel
coding converse
 tandem error correction and cryptography
 coset codes for an erasure wiretapper
 Secret key agreement protocol for wireless channels
34
Secure Communication on two Gaussian channels
X
k-bit
message
w
Y
Tag
+
Reader
wb
Nm
Nw
+
Z
Attacker
Assume that the attacker
has worse SNR
Practical scenarios
RFID
Zoned security
Wiretap error control code
Specific error control code needed at Tag side
Low complexity encoder - possibly complex decoder
35
Secure Communication on two Gaussian channels
Transmit at Cwiretapper<R<Cmain
X
k-bit
message
w
Y
Tag
+
Reader
wb
Nm
Nw
+
Z
Attacker
Assume that the attacker
has worse SNR
36
Some common sense – use an error control code
X
k-bit
message
w
Y
Tag
+
Reader
wb
Nm
Nw
+
Z
Assume that the attacker
has worse SNR
Attacker
Very good error correcting
code with simple
encoder
Reader recovers bits
With good BER
37
Coding
X
k-bit
message
w
Y
Tag
+
Reader
wb
Nm
Nw
+
Z
Assume that the attacker
has worse SNR
Attacker
Very good error correcting
code with simple
encoder
Eve recovers bits
with worse BER
38
Coding with an advanced code
X
k-bit
message
w
Y
Tag
+
Reader
wb
Nm
Nw
+
Z
Attacker
39
Some secrecy rate tradeoffs
X
k-bit
message
w
Y
Tag
+
Reader
wb
Nm
Nw
+
Z
Attacker
40
System view
How would we combine this with encryption?
Key
Key
A
Tag
Encrypt
FEC
X
C1
Y
B
FEC
Decrypt
Reader
C2
Z
FEC
C
Key
Decrypt
Attacker
41
At the encryption level
Key
Key
A
Tag
A
Decrypt
Encrypt
BER~50
%
Reader
After FEC decoding
C
Key
Decrypt
Attacker
Assume Attacker SNR is ~1.5 - 2.0 dB worse than Bob’s
(e.g. near field communications)
42
At the encryption level
Key
Key
A
Tag
A
Decrypt
Encrypt
BER~50
%
C
Key
Reader
N/2 bits in error
Attacker does not know which ones
She needs to do 2 N search
Decrypt
Attacker
Assume all parties have a key
-Attacker has somehow figured out the key
-e.g. from a weak RFID security protocol
43
At the encryption level
Key
Key
A
Tag
A
Decrypt
Encrypt
BER~50
%
C
Key
Decrypt
Reader
N/2 bits in error
Attacker needs to
- guess the N coded bits correctly
- guess the M key bits correctly
She needs to do 2 N+M search
Attacker
This time: Assume Attacker does not have a key
44
Achieving the Secrecy Capacity with
Error Control Coding
45
Achieving secrecy capacity for any DMCs using
capacity achieving codes
k-bit
message w
Alice
X
C1
C2
Z
Y
Bob
k-bit decoded
message wb
C1: Main channel; Pr{Y|X}
C2: Wire tapper’s channel; Pr{Z|X}
Eve



Special case - C2 is worse than C1, (both DMCs)
Use 2k capacity-approaching codes: C1 , C2 , C3 , ...
To send a message w, set X=random codeword of Cw
 If Cw achieves capacity on C2 for each w => Security condition is satisfied!
 If union of {C1 , C2 , C3 , ... } is reliable across C1, wb=w is possible => Reliability
condition is satisfied!

[Thangaraj et al, 2004] have shown that such a selection of C1 , C2 , C3 , ...
is possible.
46
46
Motivating example: BEC wiretapper channel
X
k-bit
message w
X
Alice
Bob
o
1-e
wb
1
e
o
e
1-e
1
?
Z
Eve

Main channel is noiseless; wire-tapper’s channel is a BEC with
erasure probability e

Eve receives a subset of the transmitted bits (or packets)

Secrecy capacity is e
[Wyner and Ozarov, Wiretap Channel Type II]
47
47
Conventional Encoding & Decoding
X
k-bit
message w

X
Alice
Bob
wb=HXT
Conventional encoding: Select the codeword in C with message w
• •
•
•
•
Binary codewords of length n
•
• •
48
48
Security Encoding & Decoding
X
k-bit
message w

X
Alice
Bob
wb=HXT
Now for security - encode information in coset
•
••
• •
• •
•
• • •
Binary codewords + 1 translate (cosets)
• •
49
49
Security Encoding & Decoding
X
k-bit
message w
X
Alice
Bob

(n,n-k) code C with parity-check matrix H

Make C and H public

C has 2k cosets

wb=HXT
Encoding: Select the coset of C with message w, select
codeword in coset at random
• •
Binary codewords + 3 translates (cosets)
•
•
•• ••• •• •
• Secrecy rate = k/n
•
•
• ••
•• •
•
•
••
50
50
Security
k-bit
message w
Alice
X = x1 x2... xn
Bob
wb=HXT
BEC(e)
Z = x1…xs e e e...e
(e: erasure)
Eve

If each coset of C has a vector of the form x1...xs??...?,
 Pr{m|Z}=Pr{m}
• •
•
•
•• ••• •• •
•
•
•
• ••
•• •
•
•
••
51
51
Security Property of Codes
Z = x1
 g11
g
21

G


 g n k ,1
...
xs
?
?
 g1s
g1, s 1
...
?
g1, s  2
 g2s
g 2, s 1
g 2, s  2
 


 g n k , s g n k , s 1 g n  k , s  2

 g 2 n 

 

 g n k ,n 
 g1n
If the submatrix of G corresponding to
revealed positions has full column
rank, all cosets of C have a vector of the
form x1...xs??...?
52
52
LDPC Codes over a BEC

Urbanke and Richardson

Consider a (3,6)-regular LDPC matrix H; BEC threshold = 0.42

Threshold Interpretation: columns of H corresponding to the erased
Urbanke and Richardson, 2001
positions have full column rank if the erasure probability is less than 0.42
H
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
53
53
LDPC Matrix Connection
LDPC Codes over a Wire Tap Channel


Let G = (3,6)-regular LDPC matrix
The columns of G corresponding to the revealed positions have
full column rank if 1-e < 0.42 or the erasure probability is greater
than 0.58
Z = x1
...
xs
?
54
?
...
?
54
LDPC codes over a BEC-noiseless wire tap channel
k-bit
message w
Alice
X : randomly chosen from
coset of C with syndrome m
X = x1 x2... xn
Bob
wb=HXT
BEC(e)
Z
Eve

C : dual of an LDPC code with
 threshold e
 rate R; k=(1 – R)n; secrecy rate=1-R



Security guaranteed whenever 1-e <  or e > 1 – 
As e tends to 1 – R, we approach secrecy capacity
Capacity achieving codes for the erasure channel provide perfect
security on the erasure wiretap channel
55
55
Comments

Positive Aspects
 First practical codes to achieve perfect secrecy - encoder and
decoder are public
 Connection between coding threshold and security

Negative Aspects
 Channels C1 and C2 must be known
 Coding scheme above works if C1 is less noisy than C2

Other cases:
 BEC-BEC wire tap channel, BSC-Noiseless
 See:
 Thangaraj, Dihidar,Calderbank, McLaughlin, and Merolla “Applications
of LDPC Codes to the Wiretap Channel,” IEEE Trans IT Aug 2007
56
56
BREAK
57
Practical Secret Key Agreement
for Wireless Networks
58
How do we make this practical?
 To fully exploit the randomness of the channel for security
purposes we need secrecy capacity-achieving channel
codes.
 Unfortunately, it seems very difficult to design near-to-
optimal codes for the Gaussian wiretap channel....
 BUT fortunately secret key agreement is a somewhat
“easier” problem (learn from quantum key distribution)!

Alice and Bob only have to agree on a key based on common
randomness and not to transmit a particular message.
59
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
1
0
1
1
0
Nwt
+
Z
Q
Eve
Q
k-bit
message
1
0
1
0
1
me
1
1
0
1
1
Assume Eve has worse
channel
60
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
1
0
1
1
0
Nwt
+
Z
Q
Eve
Q
k-bit
message
1
0
1
0
1
me
1
1
0
1
1
Two steps
1. Reconciliation
2. Privacy amplification
61
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
1
0
1
1
0
Nwt
+
Z
Q
Eve
Q
k-bit
message
1
0
1
0
1
me
1
1
0
1
1
Two steps
1. Reconciliation
2. Privacy amplification
62
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
1
0
1
1
0
Nwt
+
Z
Q
Eve
Q
k-bit
message
1
0
1
0
1
me
1
1
0
1
1
Two steps
1. Reconciliation
2. Privacy amplification
63
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
1
0
1
1
0
Nwt
+
Z
Q
Eve
Q
k-bit
message
1
0
1
0
1
me
1
1
0
1
1
Two steps
1. Reconciliation
2. Privacy amplification
64
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
1
0
1
1
0
Nwt
+
Z
Q
Eve
Q
1
0
1
0
1
k-bit
message
me
1
1
0
1
1
Two steps
1. Reconciliation
2. Privacy amplification
65
Secret Key Agreement
Bob
X
Alice
+
Y
Nm
Q
011
Nwt
+
Z
1
0
1
1
0
Q
Eve
Q
1
0
1
0
1
k-bit
message
011
me
XXX
1
1
0
1
1
Two steps
1. Reconciliation
2. Privacy amplification
66
We can learn from Quantum Key Distribution
AB E
Transmission
Alice codes n random symbols X with quantum states
Bob measures received states to obtain correlated symbols Y
Analysis
Evaluation of information intercepted based by Eve based on simple statistical
measures (bit error rate, variance)
Reconciliation
Correction of errors
Minimum number of bits to transmit :
Privacy Amplification
Choice of key size
I rec  H ( X | Y )
security
parameter
k  n( H ( X )  I ( X ; Z )  I rec  r0 )
Secret information
after transmission
Random choice of compression function
Information exchanged
during reconciliation
kH ( K | Z , G)  k  2r0
67
How about wireless security?
[Barros, Rodrigues, ISIT06]
With fading the instantaneous secrecy
capacity can be strictly positive
• Goal: Exploit channel variability to secure information
68
Opportunistic Secret Key Agreement
[Bloch, Barros, Rodrigues, McLaughlin ’06]
Cs>0
Cs=0
share common
randomness generate
secret key
Cs=0
communicate securely
(e.g one-time pad)
69
Opportunistic secret key agreement
70
Reconciliation
•Correct discrepancies
between A and B using
reconciliation information.
• In practice small
overhead ǫ (10%), thus you
have to transmit
(1 + ǫ)H(X|YM) bits per
symbols.
• Assign binary labels to
each of the transmitted
symbol and use multilevel
coding. The syndromes are
used as reconciliation
information.
• Very similar to source
coding with side
information.
71
Two Modes of Operation
Perfect Information-theoretic Security: Generate a secret key and use it
as a one-time pad (perfect security at very low rates)
Combined physical layer and cryptography: Generate a secret key and
use a symmetric cipher such as AES (very high rates are possible)
Example: with fraction of time dedicated to secret key generation as
small as 1%, we can renew a 256-bit encryption key every 25kbits, i.e.
with SNR(M)=10dB and SNR(W)=20 dB, at an average rate of 2Mbps, this
would renew a key every 16 milliseconds.
72
Average secure communication rate
Case of perfect CSI - communication with one-time pad
Protocol optimal
73
Practical Considerations
It is possible to exploit the noise of fading channels to generate
secret keys, even with imperfect CSI:

Reconciliation efficiency ~90% over wide range of SNRs

Some latency and complexity (long block length of LDPC code)

Combine physical layer and standard cryptography
Ex: AES with high key regeneration rate
We require a small shared key for authentication.
M. Bloch, J. Barros, M. R. D. Rodrigues and S. W. McLaughlin,Wireless InformationTheoretic Security, IEEE Transactions on Information Theory, June 2008.
74
Advanced Topics and Applications
75
Network Security
What happens when we have multiple parties
communicating over unreliable noisy networks with
multiple eavesdroppers and jammers?
Y2
X1
X4
Network
Interference
Cooperation
Y1
Feedback
X2
X3
?
76
Multi-user Secrecy Generation
M users communicate messages F and agree on secret key K
 common secret key
P( K  K1  K2  ...  K M )  1
 secrecy against eavesdropper I ( K ; F )  0
 uniformity H ( K )  log | key space |
 secret key (SK) capacity is the largest entropy rate of K
77
[Csiszár and Narayan, 2006]
Example with three users and two-bit sequences
 Bob and Charlie observe sequences of Bernoulli (1/2) symbols.
 Alice observes the symbolwise XOR of their sequences.
B11B12
Alice
Optimal Secret Key Agreement
 Alice sends B11
B21B22
 Bob sends
Bob
B22
 Charlie sends B31  B32
Charlie
 All are able to recover B31
B31B32
 Eavesdropper is in the dark: I ( B11, B22 , B31  B32 ; B31 )  0
1
 SK rate: 1
2
H ( B31 ) 
2
78
Encoding Correlated Sources
Source 1
Source 2
U1
U2
Encoder 1
Encoder
Û1
R1
R2
Encoder 2
Decoder
Û2
Sink
p(u1,u2)
R2
H(U1U2)
H(U2)
Slepian
Wolf
1973
H(U2|U1)
Shannon
1948
H(U1|U2) H(U1)
R1 > H(U1|U2)
R2 > H(U2|U1)
R1+R2 > H(U1U2)
R1
H(U1U2)
79
Many correlated sources
U1
U2
1
2
Perfect reconstruction is
R10
possible if and only if
R20
c
R

H
(
U
(
S
)
|
U
(
S
))
 i0
0
RM0
UM M
iS
for all sets
S  {1,2,...., M },
S  S c  0,
S 0
80
[Maurer ‘93, Ahlswede and Csizár, ‘93]
Secret Key Capacity for Two Terminals
R1
U1
Alice
R1 > H(U1|U2)
Bob
R2
U2
R2 > H(U2|U1)
non-interactive communication
CSK  H (U1 ,U 2 )  [ H (U1 | U 2 )  H (U 2 | U1 )]
 I (U1;U 2 )
81
[Csiszár and Narayan, 2006]
Secret Key Capacity for Multiple Terminals
U5
U1
CSK  H (U1 ,U 2 ,...,U M )  Rmin
U6
Network
U2
U3
U4
Rmin is the minimum
sum rate required for all
terminals to be able to
reconstruct all sources
with arbitrarily small
probability of error.
Notice that in this case the eavesdropper observes
only the communication between the nodes and not
one of the correlated sources.
82
Extensions and Variations
 Secret key agreement with helpers [Csizár, Narayan, 2005]
 Multiple group keys with secrecy with respect to a prescribed
subset of users [Ye, Narayan, 2005]
 Satellite Channel Model [Csizár, Narayan, 2005]
 Secret key capacity when eavesdropper observes a
correlated source of randomness remains unsolved.
83
Active Attacker
 Adversary has access to the communications
channel used by the legitimate parties and can do
the following:
 Send / Receive;
 Read;
 Replay;
 Forge;
 Block;
 Modify;
 Insert;
84
84
[Maurer, 93]
[Maurer, Wolf, 03]
Secret Key Agreement with Public Discussion
Yn
Alice
Xn
p(yz|x)
Zn

Bob
Eve
public
unauthenticated
channel
Alice and Bob want to increase their secrecy capacity by exchanging
information over the feedback channel and generate a secret key.
 But what if Eve is allowed to read and write on the public channel?
 Adversary with infinite computing power;
 Adversary with complete control over public channel.
85
Source Model
Xn
Alice
Yn
Bob
p(x,y,z)
Zn
SA
SB
public
authenticated
channel
Eve
Alice and Bob see X n and Y n and exchange messages C:=(C1, C2, C3, . . .Ct)
 Outcome of the key generation process: H(SA|CX) = 0 or H(SB|CY ) = 0
 Alice sends (C1, C3, . . . , C2k+1, . . .), Bob sends (C2, C4, . . ., C2k, . . .)
 Eve gets to see a correlated random variable Zn and can read and write on
the public channel.
86
Impossibility Results
 Simulatability Condition
 To generate a key, Alice and Bob must have advantage over Eve
in terms of the distribution PXYZ;
 Eve cannot be able to generate from Z a random variable X’
which Bob, knowing Y, is unable to distinguish from X (and vice
versa).
 Secret Key Capacity with Active Adversary
 Either a secret key can be generated at the same rate as in the
(well-studied) passive-adversary case, or such secret key
agreement is completely impossible;
 if Eve can use Z to simulate X or to simulate Y the secret key
capacity is zero.
87
[Maurer, 2000]
Information-theoretically Secure Message Authentication
 We assume opponent has unlimited computing power and knows
everything about the system – except for a secret key.
 Can we provide bounds on an opponent´s cheating probability for a
given tolerable probability of rejecting a valid message?
 Hypothesis testing problem: decide whether a received message is
authentic or not:
 Either the message was generated by the legitimate sender knowing the
secret key;
 Or by an opponent without a priori knowledge of secret key.
88
Problem Setup
 Sender and receiver share a secret key K
 Sender: sequence of plaintext messages X1 , X 2 ,..., X n
 Each X i is authenticated by sending an encoded message
Yi which depends on K,Xi and encoded possibly also
using the previous plaintext messages X1 ,..., X i 1 and Y1 ,..., Yi 1
 Receiver:
 based on Yi , Z , and possibly also on X1 ,..., X i 1
and Y1 ,..., Yi 1 ,decides to either reject the message
or accept it as authentic
ˆ
 if case of acceptance: decodes Yi to a message X i
89
Possible Attacks
 The opponent with read and write access to communication
channel can use either of two different strategies for cheating
 Impersonation attack at time i : the opponent waits until he
has seen the encoded messages Y1 ,..., Yi 1 and then sends
a fraudulent message Yi which he hopes to be accepted
by the receiver as the ith message
 Substitution attack at time i : the opponents lets pass
messages Y1 ,..., Yi 1 ,intercepts Yi , and replaces it by a
different message Y which he hopes to be accepted by
i
the receiver
90
Results
 When a sequence of n messages X 1 ,..., X n is to be
authenticated, an opponent can choose the type of
attack with the highest success probability;
 A secret key K is used optimally when the maximum
of the success probability is minimal;
 When it is required that a legitimate message is
always accepted α=0 in all of these possible attacks,
max( PI ,1,...., PI ,n , PS ,n )  2

H (K )
n 1
91
PHY-Based Authentication
[Trappe et al, 2007]
 Spoofing detection
 Verify if a transmission came from a particular transmitter
 Location information can be extracted to authenticate a
transmitter relative to its previous location.
Bob
Probe Pulse
u(t)
Alice
1. Estimates channel
hEB (t,t)
2. Verification fails!!!
3. Does not accept Eve
as Alice!
1. Estimates channel
h = hAB (t,t)
2. Compares against
h’ = hAB (t-1,t)
3. Accepts transmission if
h = h’
Spoof Alice:
Probe Pulse
u(t)
Eve
92
Spread Spectrum Communications and Jamming
1
0
1 0 1 10 1 0 0 1 1 1 01 0 1 10 01 0 10 1 1 0 10 1 0
0 1 0 01 0 1 1 0 0 0 10 1 010 01 0 10 1 1 0 10 1 0
 Direct Sequence / Frequency Hopping use pseudo-random sequences to
spread the narrowband signal over a wide band of frequencies;
 Effective against narrow-band jamming; lowers probability of intercept; can
provide privacy if spreading sequence is kept secret;
 Used in Code Division Multiple Access (CDMA) systems.
93
[Médard, 1997]
Capacity of Channels with Correlated Jamming
NM
X
+
Alice
NW
Y
+
Bob
+
Z
Eve
 Repeat-back jamming in wireless networks (e.g. amplification, modification
retransmission of intercepted signals, inducing errors in radars and receivers).
 Jammer can cause a lot of harm even with access to only a noisy version of the
sent signal, with phase or timing jitter and with limited processing capabilities.
 Not detectable via the received power at Bob.
 Extended to Multiple Access Channels by [Shafiee and Ulukus, 2005]
94
[Tekin and Yener, 2006]
Cooperative Jamming in the Gaussian Multiple Access Channel
X1
U1
Alice
Charlie
Y
Encoder 1
U2
X2
Encoder 2
Decoder
Bob
Decoder
Eve
p(yz|x1 x2)
Z
 Secrecy conditions can be individual or collective yielding
different results for each case.
 Alice and Charlie can cooperate to increase Eve’s
uncertainty about the sent messages.
95
General Broadcast Channel with Multiple Secrecy Conditions
Y1
U2,U1
Alice
X
Encoder
Decoder 1
p( y1 y2 |x)
Û1
Bob
Û2
Y2
Decoder 2
Eve
 [Csiszár and Koerner, 1978] considered one secrecy
condition.
 [Liu et al. , 2006] provided inner bound for two secrecy
conditions, and also for interference channels.
96
Multiple Access Channel with confidential messages
Y1
X1
U1
Alice
p(u1) p(u2)
Y
Encoder 1
U0
X2
Charlie
Encoder 2
Decoder
Bob
Decoder
Eve
p(y1 y2 yz|x1 x2)
Z
U2
Y2
 Cooperative jamming over the Gaussian MAC
[Tekin and Yener, 2006]
 With channel outputs at the encoders + individual secrecy conditions
[Liang and Poor, 2006]
97
Relay Channel with confidential messages
 Discrete Memoryless Case [Oohama, 2004]
 Randomization helps to increase the rate-equivocation region.
Eve
Sn
Alice
Xn
p(yz|xs)
Zn
Yn
Bob
98
[Goel and Negi, 2005]
Exploiting MIMO
Bob
Alice
Eve
 Alice can leverage multiple antennas by transmitting
artificial noise into the null space of Bob
 This approach can be used effectively, even when position
of Eve is unknown.
99
Jamming to increase the secrecy capacity
NM
Y
X
+
Alice
NW
Bob
+
Z
Eve
1
P

CS  CM  CW  log 2 1  2
2
  M
P 
 1

  log 2 1  2 
 2
  W
 Can we increase the noise in Eve’s channel without affecting Bob?
100
Increasing the Secrecy Capacity with Jammers
101
Jammer Impact on Outage Secrecy Capacity in Fading Environment
102
Multiple Jammers in Fading Environment
103
[Ahlswede, Cai, Li and Yeung, 2000]
Store-and-Forward versus Network Coding
 In today’s networks, information is viewed as a
commodity, which is transmitted in packets and
forwarded from router to router pretty much as water
in pipes or cars in highways.
 In contrast, network coding allows intermediate
nodes to mix different information flows by combining
different input packets into one or more output
packets.
104
A simple three-node example
a
a
A
B
b
C
b
In the current networking paradigm we require 4 transmissions.
105
Network Coding
a
A
b
B
C
a+b
With network coding we require only 3 transmissions.
106
[Koetter and Médard, 2003]
Algebraic Framework for Network Coding
 Binary vector of length m: element in
F2 m
 Random processes at nodes
Y(e3 )   i X(v,i) 
i
 jY(e j )

j1,2
 Transfer matrix

z  xM
M  A(I  F)1 BT
 Generalized MIN-CUT MAX-FLOW Condition

M
  0

107
Packetized Network Coding
 Assume each packet carries L bits
 s consecutive bits can be viewed as a symbol in Fq
enc. vector

L
s
 Perform network coding on a symbol by symbol basis.
 Output packet also has length L.
 Send the coefficients (the “encoding vector”) in the header.
 Information is spread over multiple packets.
108
Practical Considerations
 Encoding: Elementary linear operations which can be implemented in a
straightforward manner (with shifts and additions).
 Decoding: Once a receiver has enough linearly independent packets, it can
decode the data using Gaussian elimination, which requires
operations.
 Generations: To manage the complexity and memory requirements, we mix
only generations with fixed number of packets and limit the field size. Each keeps
a buffer sorted by generation number. Non-innovative packets are discarded.
 Delay: Since we must wait until we have enough packets to decode, there is
some delay (not very significant, since we require less transmissions in many
relevant scenarios)
109
Benefits beyond throughput
 Reliability: Network Coding can achieve optimal delay and rate in the
presence of erasures and errors.
 Simpler Optimization: The multicast routing problem is NP-hard
(packing Steiner trees), however with network coding there exist
polynomial time algorithms.
 Robustness: Random network coding is completely decentralized
and preserves the information in the network, even in highly volatile
networking scenarios.
110
Applications of Network Coding
First real-life application in July 2007:
Microsoft Secure Content Downloader (a.k.a. Avalanche)
 Distributed Storage and Peer-to-Peer: robustness against failures
in highly volatile networks;
 Wireless Networks: Information dissemination using opportunistic
transmission;
 Sensor Networks: Data gathering with extremely unreliable sensing
devices;
 Network Management: Assessing critical network parameters (e.g.
topology changes and link quality)
111
Classes of Network Coding Protocols
We distinguish between two types of protocols:
 stateless network coding protocols, which do not rely on network
state information (e.g. topology or link costs) to decide when to mix
different packets (e.g. Random Linear Network Coding);
 state-aware network coding protocols, which rely on partial or
full network state information to compute a network code or
determine opportunities to perform network coding in a dynamic
fashion (e.g. COPE).
112
Network Coding Security Taxonomy
Network Coding
Protocols
State
information
Security
Infrastructure
Stateless
State-aware
Network codes
RLNC
[Ho et al, ’04]
Polynomial time
[Jaggi et al, ’05]
Detection Byzantine
[Ho et al, ’04]
COPE
[Katti et al, ’06]
Resilient codes
[Jaggi et al, ’06]
[Koetter, Kschischang, ’07]
Cooperative
Key Management
Cooperative Security
Signatures Content Dist.
[Gkantsidis, Rodriguez, ’06] [Zhao et al, ’07]
Secret Key Dist.
[Oliveira, Barros, ’07]
SPOC
[Vilela, Lima, Barros, ’08]
 some intrinsic  Prone to
security (no state
information)
 Prone to
Byzantine
attacks
Byzantine attacks
 Network state
information
- Extra redundancy
- Hash symbols
included in packets
- Cooperative security
schemes
- Homomorphic hash
functions
-Signatures
- Key distribution
- Confidentiality
113
Network Coding: A Free Cipher?
[Lima, Médard and Barros, ISIT’07]
 Nodes are assumed to be “nice but
S
a
T
curious” (comply with protocol but could
be malicious eavesdroppers)
b
a
b
U
b
a+b
a+b
Y
X
of confidentiality;
 Nodes T and U have partial information
W
a
 Intermediate nodes have different levels
about the data;
 Node W has full access to the data;
 Node X cannot decode any useful data –
a+b
a free cypher!
Z
Previous work considered wiretapping attacks on multiple links,
e.g. [Cai and Yeung,’02], [Feldman et al,’04] [Bhattad et al,’05]
114
Secure Network Coding
a
b
c
d
S
T
a+b+c+d+e+f+g
3a+b+c+d+5f
a+2b+c+d+4g
a+b+c+3d+5h
e
f
g
h
U
R
Nodes T and U have access to half
of the sent data.
5a+b+5h
6b+c+4g
b+7c+3a
b+c+9e
S
T
U
R
NodesT and U need to decode to
obtain partial data.
115
Algebraic Security Criterion
Definition (Algebraic Security Criterion): The level of security provided
by random linear network coding is measured by the number of
symbols that an intermediate node v has to guess in order to decode
one of the transmitted symbols.
 In other words, we compute the difference between the global rank
of the code and the local rank in each intermediate node.
116
Results
Theorem 1:The probability P(ld > 0) of recovering a strictly positive number
of symbols ld at the intermediate nodes (by Gaussian elimination) goes to
zero for sufficiently large number of nodes and alphabet size
Proof Idea:
An intermediate node can gain access to relevant information
1) when the partial transfer matrix has full rank
2) when the partial transfer matrix has diagonalizable parts.
Carry out independent analyzes in terms of rank and in terms of partially
diagonalizable matrices.
Show that the probability of having partially diagonizable matrices goes to zero for
sufficiently large number of nodes and alphabet size.
117
SPOC - Secure Practical netwOrk Coding
 Assured confidentiality against
attacker with access to all the links.
 Two types of coefficients:
 Locked
 Unlocked
 Same operations
 Requirements:
 Key management mechanism
118
SPOC - Secure Practical netwOrk Coding - Results
Number of AES encryption operations according to the payload
size, for SPOC (encryption of locked coefficients) versus traditional
encryption mechanism (encryption of the whole payload).
119
SPOC - Secure Practical netwOrk Coding - Results
Packet size overhead of including the locked coefficients, per packet.
120
[Lima, Vilela, Barros, Médard, 2008]
Mutual Information between Payload and Coding Coefficients
121
[Ho et al, ISIT 2004]
Detection of Byzantine Modification
 Hash symbols, calculated as simple polynomial functions of the
source data, are included in each source packet.
hash
enc. vector
L
s
 Receiver nodes check if decoded packets are consistent, i.e. have
matching data and hash values.
 Additional computation is minimal as no other cryptographic
functions are involved.
 Detection probability can be traded off against communication
overhead, field size (complexity) of the network code and the time
taken to detect an attack.
122
[Gkantsidis, Rodriguez, Infocom 2006]
Cooperative security for network coding
 Cooperation to achieve on-the-fly detection of malicious packets.
 Homomorphic hash functions: a hash of an encoded packet is easily
derived from the hashes of the previously encoded packets.
However, these hash functions are computationally expensive.
 To increase efficiency every node performs block checks with a
certain probability and alerts its neighbors upon detection.
 In addition, there exist techniques to prevent Denial of Service (DoS)
attacks aimed at the dissemination of alarms.
123
[Jaggi et al. , Infocom 2006]
Resilient Network Codes
[Koetter and Kschischang, 2007]
 Use the error correction capabilities of linear network coding.
 An active attacker can be viewed as a second source of data.
 Add enough redundancy to allow the destination to distinguish
between valid and erroneous packets.
 Some information may have to be protected by a shared secret key.
124
Sensor Networks
Task: Collect and transmit data
through secure links
Data confidentiality
Constraints:
Energy
Limited Data Rate
Processing Power
Memory
Secret Key Distribution
How can each pair of neighboring
nodes share a secret key?
125
Key Pre-distribution
 Goal: Store keys into the memory of the sensor
nodes for them to share a secret with their
neighbors after the deployment.
 Challenges:




Minimize the impact of compromised nodes;
Efficient use of the resources;
Scalability in dynamic environments;
Avoid single points of attack.
126
[Oliveira and Barros, 2007]
Secret Key Distribution using Network Coding
 Our approach:
 Key pre-distribution scheme;
 Efficient use of resources;
 Uses a mobile node to “blindly” complete the key distribution
process;
 Designed for dynamic scenarios.
 Prior to sensor node deployment:
 Generate a large pool of keys and their identifiers;
 Load different keys and the corresponding identifiers into the
memory of each sensor node;
 Store in the memory of the mobile node all the keys encrypted with
the same one-time pad and their corresponding identifiers.
127
[Oliveira and Barros, 2007]
Secret Key Distribution in WSNs
 After sensor node deployment:
K i ( A)  R
Ki(B)  R
A
K i ( A)
S
K i ( A)  R  K i ( B )  R
...
K i (.)  R
Hello
Hello
i ( A)
B
Ki(B)
i (B )
K i ( A)  K i ( B )
K i ( A)  K i ( B )
K i ( A)  K i ( B )  K
Kii((BA))
K i ( A)  K i ( B )  K i ( B )
EKi ( A) (mAB )
EKi ( B ) (mB A )
128
One-Time Pad Security
[Oliveira, Costa and Barros, 2007]
 One-time pad is secure if the key is:
Truly random;
Never reused;
Kept secret.

The knowledge of {K1  R, K 2  R,..., K m  R} does not
increase the information that the attacker has about any one
key
PK i  x | K1  R  y1 ,..., K m  R  ym   PK i  x  
1
, i  1,..., m
n
2
129
Extensions and Variations
 Mobile key distribution for many nodes
 Group and cluster keys
 Key revocation
 Key renewal
 Authentication
130
Millionaires- problem
Suppose 2 millionaires
want to determine which
one is richer, without
revealing the precise
amount of their wealth.
In the general secure multi-party computation problem, users
u1, u2, ..., un possess data d1, d2, ..., dn and want to compute the
outcome of a public function F(d1, d2, ..., dn ) without revealing
d1, d2, ..., dn .
131
Other Problems beyond Secure Communication
 Communicating securely is not the only problem in cryptography.
 Problem: Suppose Alice and Bob are linked through a network and want
to flip a coin. How can they ensure that the coin flip is fair?
$
Network
$
 Solution: Alice and Bob send one bit each in separate envelopes. They
open the envelopes simultaneously and take the XOR of the two bits.
 The protocol works if and only if
 Bob knows nothing about Alice’s bit before he sends his envelope;
 Alice cannot change her bit once the envelope is sealed.
 ...and vice versa (for Bob’s bit).
132
Bit Commitment
b
Alice puts a bit b
in a strong box
Commit
Open
Alice gives this box to Bob.
She cannot change b
b
Later Alice can
unveil b to Bob
A commitment scheme is said to be secure if it is:
• Binding: the probability that Alice can successfully open two
different commitments is negligible.
• Concealing: Bob gets at most negligible information on b
before the opening phase.
• Correct: The probability that honest Alice fails to open
a commitment is negligible.
133
Bit Commitment over the erasure channel
p-Erasure
Channel
Xn
n
Yn
n
b = parity(X)
Commit Phase:
• Alice selects a random codeword with parity equal to the value she
wants to commit to and sends it to Bob through the erasure channel.
Open Phase:
• Alice sends the codeword she has sent in the commit phase over a
noiseless channel. Bob rejects if the codeword he receives differs in at
least one position from the codeword he received through the noisy
channel.
134
Bit Commitment over the erasure channel
p-Erasure
Channel
Xn
n
Protocol Analysis:
Yn
n
b = parity(X)
n
• Bob learns the commitment with probability PB  (1  p)
• Alice unveils a bit different than the one she committed to
and is not detected with probability PA  p
Problems:
•Non-negligible error probability (binding condition)
•The channel is used n times to commit to a single bit.
135
Commitment Rate and Capacity
If we commit to a string of length k, what is the
maximum commitment rate k/n of a secure protocol we
can achieve (i.e., capacity)?
Binary string b  {0,1}k
n 
P

 0
Bob learns b with probability B 
n 
 0
Alice cheats successfully with probability PA 
Commitment rate
k
R
n
Commitment capacity
Ccom  max R
PX
136
The Commitment Capacity of DMC’s
 Define a “redundant” channel (a channel is called non-redundant
if none of its output distributions is a convex combination of its
other output distributions).
 Redundancy can be “cut” from a channel, by removing all input
symbols which are convex combinations of others.
 If after removing the redundancy of a channel, its equivocation
becomes zero, the channel is called trivial.
The commitment capacity of a DMC equals its
equivocation H(X|Y) after its redundancy is
removed.
[Winter, Nascimento, Imai ’03]
137
How about the Gaussian Channel?
Motivation:
- more realistic channel model (e.g. wireless medium)
- commitment capacity for continuous channels unknown
- techniques differ from the discrete case
Yi  X i  Z i
Xi
+
Yi
Z i  N (0,  2 )
1 n 2
Average Power Constraint:
xi  P

n i 1
Channel Capacity:
C
Zi
1
P 

log 1  2 
2
 

138
How about the Gaussian Channel?
Caveat: practical wiretap codes are hard to design!
139
Commitment rate
Using a wiretap interpretation of commitment, we can prove that
Ccom
1 
P  1 
P 
 log 1  2   log 1  2 
2   C*  2   G 
 Any positive  C * will give us a binding protocol, by making it
arbitrarily small, we get that the maximum achievable rate can
be made arbitrarily large
The commitment capacity of the Gaussian
channel is infinite.
140
Commitment from Secret Key Agreement
[Bloch, Barros and McLaughlin, 2007]
141
Beyond secure communication
Cryptographic protocols based on noisy channels,
Crépeau, 1997
Commitment Capacity of Discrete Memoryless Channels,
Winter, Nascimento, Imai, 2003
Oblivious Transfer using noisy channels,
Crépeau. Morozov, Wolf, 2004
Pseudo-signatures, Broadcast, and Multi-party Computation,
M. Fitzi, S. Wolf, and J. Wullschleger, 2004
Commitment Capacity of Gaussian Channels,
Barros, Imai, Nascimento and Skudlarek 2006
Practical Information-Theoretic Commitment
Bloch, Barros and McLaughlin, 2007
142
Physical-Layer Security:
10 Open Issues
143
#1
How can we provide rigorous descriptions of security primitives?
k-bit message
W
Alice
X
X
key I
Bob
k-bit decoded
message Wb
key K
X
Eve
Computational Security
 Security schemes are based on
(unproven) assumptions of
intractability of certain functions;
Information-Theoretic (Perfect or
unconditional) Security
 strictest notion of security, no
computability assumption
H(M|X)=H(M) or I(X;M)=0
 Typically done at upper layers of
the protocol stack
 Implementable at the physical layer
144
#2
What are the fundamental limits of security for strong secrecy?
Xn
Alice
p(y|x)
Yn
Bob
p(z|x)
Zn
Eve

Theoretical results from the seventies (Wyner, Csiszár and Koerner)

Caveat: eavesdropper must have a worse channel.

Renaissance of information-theoretic security in the last 2 years.

Most results are based on weak secrecy conditions (equivocation rate)

Strong secrecy is possible (requires CS techniques)
145
#3
How can we leverage state-of-the art channel coding to enhance
security at the physical layer?
X
k-bit
message
w
Y
Tag
+
Reader
w’
Nm
Nw
+
Z
Attacker
146
#4
How do we construct secrecy achieving codes for wireless
channels?
X
k-bit
message w
X
Alice
Bob
o
1-e
1
e
o
wb
e
1-e
1
?
Z
Eve
Main channel is noiseless; wire-tapper’s channel is a BEC with erasure
probability e
Eve receives a subset of the transmitted bits (or packets)
For this instance (only), we have secrecy capacity achieving codes.
147
#5
How can we borrow from quantum cryptography?

Common Randomness: Alice and Bob share correlated
random sequences.

Reconciliation: Alice sends Bob enough side information
for Bob to reconstruct Alice’s sequence.

Privacy Amplification: Alice and Bob use hash functions to
maximize Eve’s equivocation.
148
#6
How can we leverage fading?
Wireless Network with Potential Eavesdropping
• Goal: Exploit channel variability to secure information at the
physical-layer.
149
#7
How can we provide security for network coding?
a b
S
a
T
Intermediate nodes have different
levels of confidentiality;

Nodes T and U have partial
information about the data;

Node W has full access to the data;

Node X cannot decode any useful
data – a free cypher?

Active attacks can compromise the
information flow.
b
a
b
U
W
a
b
a+b
a+b

X
a+b
Y
Z
a b
a b
150
#8
How can we use coding ideas to distribute secret keys?
 Problem:
 How can each pair

of sensor nodes agree

on a secret key?
 Our approach:
 Key pre-distribution scheme;
 Uses a mobile node to complete
the key distribution process
blindly using network coding;
 Reduced memory requirements;
151
#9
How can we use physical-layer techniques to go beyond secure
communication?

Cryptography is not only concerned with communicating securely.

Based on noisy channels and state-of-the-art error correction codes
we can implement bit commitment and oblivious transfer, which are
the building stones of secure multi-party computation.

Authentication is a vital issue and could potentially be carried out
over noisy channels possibly without initial shared secret.
[Wolf and Maurer’98], [Trappe et al’07 ]

How about anonymity?

How about non-repudiation?
152
Classical Cryptography under the Computational Model
Advantages

no publicly-known, efficient
attacks on public-key
systems
 security is provided on a
block-to-block basis
 if cryptographic primitive is
secure then every encoded
block is secure
 systems are widely deployed,
technology is readily
available, inexpensive
Disadvantages




Security is based on unproven
assumptions
No precise metrics
 trade off between reliability and
security as a function of the
block length is unknown
 security of the cryptographic
protocol is measured by whether
it survives a set of attacks or
not.
Conventional model (error free
channel) secrecy capacity of these
systems is zero
can’t guarantee reliable and
perfectly secure system
153
Physical layer security
under the information-theoretic (perfect) security model
Advantages:
 No computational restrictions
placed on eavesdropper
 Very precise statements can
be made about the information
that is leaked
 Quantum key distribution
implemented
 Wireless solutions appear
 Suitably long codes get
exponentially close to perfect
secrecy
Disadvantages:
 Information-theoretic security
is an average-information
measure.
 Requires assumptions about
the communication channels
that may not be accurate in
practice.
 Limits its application
 A few systems (e.g QKD) are
deployed but the technology
is not as widely available and
is expensive.
154
#10
It may well be worth rethinking our security architecture.
Application
Transport
Network
Link
Physical
Bottom-up Security?
 How can we combine physical-layer security and
cryptographic protocols?
155
Acknowledgements and credits

Matthieu Bloch, Georgia Tech

Miguel Rodrigues, University of Porto

Andrew Thangaraj, IIT Madras

Rob Calderbank, Princeton

Anderson Nascimento, University of Brasilia

Muriel Medard, MIT

Luísa Lima, University of Porto

João Paulo Vilela, University of Porto

Paulo Oliveira, University of Porto

Rui Costa, University of Porto

Demijan Klinc, Georgia Tech
156