CYG Chapter 4 Entropy and Perfect Secrecy
Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 4 Entropy and Perfect Secrecy
Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 4 Entropy and Perfect Secrecy
-
- 1 / 49
-
Cartes-fiches
What are the properties of the outcome?
[randomexperiment.entropy.entropyperfectsecrecy, 2]
1. Uncertainty and 2. information gain
When does it play a role?
[uncertainty.randomexperiment.entropy.entropyperfectsecrecy]
Before the experiment takes place
When does it play a role?
[informationgain.randomexperiment.entropy.entropyperfectsecrecy]
After the experiment takes place
What are the tools?
[entropy.entropyperfectsecrecy, 2]
1. X is random variable with finite support and distribution P(X=xi)=pi
2. Arbitrary constant c>1
What is the definition?
[informationcontent.entropy.entropyperfectsecrecy]
Information content of the event {X=xj} is IX(xj) := -logc(pj)
What is the definition?
[entropy.entropy.entropyperfectsecrecy]
H(X) := Sumj=1m pj*IX(xj) // Average of information contents
What is the definition?
[jointentropy.entropy.entropyperfectsecrecy]
H(X,Y) := Sumi,j pij*log(pij)
What is the definition?
[conditionalentropy.entropy.entropyperfectsecrecy]
H(X|Y) := Sumi,j pij*log( P(X=xi|Y=yj) ) // So-called equivocation
What are the remarks for further entropy definitions?
[entropy.entropyperfectsecrecy, 3]
1. log(0) = -inf
2. 0*log(0) = 0
3. Omit the constant c
What is the definition of a)?
[theorem43.entropy.entropyperfectsecrecy, 3]
1. 0 <= H(X) <= log(m)
2. If one P(X=xi)=1 then 0=H(X) // Singleton distribution
3. If for all P(X=xi)=1/m then H(X)=log(m) // Uniform distribution
What is the definition of b)?
[theorem43.entropy.entropyperfectsecrecy, 3]
1. 0 <= H(X|Y) <= H(X)
2. If for all i,j with pij>0: P(X=xi|Y=yj)=1 then 0=H(X|Y)
3. If X and Y si then H(X|Y)=H(X)
What is the definition of c)?
[theorem43.entropy.entropyperfectsecrecy, 2]
1. H(X,Y) <= H(X) + H(Y)
2. If X and Y si then equality
What is the definition of d)?
[theorem43.entropy.entropyperfectsecrecy]
H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) // Chainrule
What are the tools?
[coding.entropyperfectsecrecy, 5]
1. Source alphabet X := {x1,…,xm}
2. Code alphabet Y := {y1,…,yd}
3. Codeword g(xj) with length nj
4. G: (x1,…,xm) → (g(x1),…,g(xm))
5. Average length n = n(g) = Sumj=1m nj*pj
What is the definition?
[encoding.coding.entropyperfectsecrecy]
g: xj → g(xj)=(wj1,…,wjnj)
What are the characteristics?
[encoding.coding.entropyperfectsecrecy, 2]
1. Is injective
2. If G injective then g is uniquely decodable/decipherable
What is description?
[theorem45.coding.entropyperfectsecrecy]
Noiseless Coding Theorem
What is the definition of a)?
[theorem45.coding.entropyperfectsecrecy]
If g is uniquely decodable then H(X)/log(d) <= n(g)
What is the definition of b)?
[theorem45.coding.entropyperfectsecrecy]
There exists a g for n(g) < H(X)/log(d) +1
What are the conclusions about?
[theorem45.coding.entropyperfectsecrecy, 4]
1. Highest compression
2. Length of encoding
3. Fraction of possible reductions
4. Redundancy R
What is the definition?
[compression.theorem45.coding.entropyperfectsecrecy]
Highest compression of a source is approximately H(X)/log(d)
What is the definition?
[lengthencoding.theorem45.coding.entropyperfectsecrecy]
Encoding with fixed length codes needs approximately length n=logd(m)
What is the definition?
[fraction.theorem45.coding.entropyperfectsecrecy]
Fraction of possible reductions is H(X)/(logd(m)*log(d)) = H(X)/log(m) <= 1
What is the definition?
[redundancy.theorem45.coding.entropyperfectsecrecy]
We call the remainder 1-H(X)/log(m) redundancy R
What is the motivation?
[stationarysources.coding.entropyperfectsecrecy]
Occurrences of characters in NL are not si
What is the tool?
[stationarysources.coding.entropyperfectsecrecy]
{Xn} is a stationary sequence of random variables
What is the definition?
[entropy.stationarysources.coding.entropyperfectsecrecy]
Hinf(X) = limN→inf H(X1,…,XN)/N
What is the definition?
[redundancy.stationarysources.coding.entropyperfectsecrecy]
R = 1 – Hinf(X)/log(m)
Name an example?
[coding.entropyperfectsecrecy]
English has Hinf(X)~1.25 and R~73%
What are the tools?
[ps.entropyperfectsecrecy, 4]
1. cs with finite sets M, K and C
2. cs with sets of positive probability M+, K+ and C+
3. Random variables M’, K’ with support M, K and P(M’=Mi)=pi, P(K’=Kj)=qj
4. Random variable V’ with support C and P(C’=Cl)=rl=Sumij:e(Mi,Kj)=Cl pi*qj
What are the entropies?
[tools.ps.entropyperfectsecrecy, 3]
1. H(M’) = - Sumi=1m pi*log(pi)
2. H(K’) = - Sumj=1k qj*log(qj)
3. H(C’) = - Suml=1n rl*log(rl)
What are the equivocations?
[tools.ps.entropyperfectsecrecy, 2]
1. Key equivocation H(K’|C’)
2. Message equivocation H(M’|C’)
What is the definition of a)?
[theorem47.ps.entropyperfectsecrecy]
H(K’|C’) = H(M’|C’) + H(K’|M’,C’) with H(K’|C’) >= H(M’|C’)
What is the proof for a)?
[theorem47.ps.entropyperfectsecrecy, 3]
1. Use chainrule twice for H(K’|C’) and H(M’|C’)
2. H(M’|K’,C’) of H(K’|C’) is zero
3. H(K’|M’,C’) of H(M’|C’) is not zero
What is the definition of b)?
[theorem47.ps.entropyperfectsecrecy]
H(K’|C’) = H(M’) + H(K’) - H(C’)
What is the proof for b)?
[theorem47.ps.entropyperfectsecrecy, 1+4]
1. Use fact that H(X,Y,f(X,Y))=H(X,Y) for any f
2. H(K’|C’) = H(K’,C’) - H(C’) // Chainrule
3. = H(M’,K’,C’) - H(C’) // M’=d(C’,K’)
4. = H(M’,K’) - H(C’) // C’=e(M’,K’)
5. = H(M’) + H(K’) - H(C’) // M’,K’ are si
What is the first definition?
[ps.entropyperfectsecrecy]
If for a cs H(M’,C’)=H(M’) holds then it has ps
What is the second definition?
[ps.entropyperfectsecrecy]
If P(M’|C’)=P(M’) for all Cl of C+ ↔ P(C’|M’)=P(C’) for all Mi of M+ then a cs has ps // Corollary 4.11
What is the definition of a)?
[lemma412.ps.entropyperfectsecrecy]
For any cs holds |C+|>=|M+|
What is the definition of b)?
[lemma412.ps.entropyperfectsecrecy]
If a cs has ps then |K+|>=|C+| holds
