CYG Chapter 4 Entropy and Perfect Secrecy

Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 4 Entropy and Perfect Secrecy

0.0 (0)

R. B.

Lernen

R. B.

Über diese Lernkartei

This flashcard set delves into advanced concepts of entropy and perfect secrecy in cryptography at the university level, focusing on definitions, theorems, and proofs related to Vernam cipher, entropy calculations, and information theory tools. It covers key topics like perfect secrecy conditions, entropy definitions, and the Noiseless Coding Theorem, providing essential insights for students and professionals in computer science and cryptography.

Karten

Lernende

Sprache

Englisch

Kategorie

Informatik

Stufe

Universität

Erstellt / Aktualisiert

21.03.2017 / 18.08.2017

Ähnliche Karteien

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’=M_i)=p_i, P(K’=K_j)=q_j

4. Random variable V’ with support C and P(C’=C_l)=r_l=Sum_{ij:e(Mi,Kj)=Cl} p_i*q_j

What are the entropies?

[tools.ps.entropyperfectsecrecy, 3]

1. H(M’) = - Sum_i=1^m p_i*log(p_i)

2. H(K’) = - Sumj₌₁^k q_j*log(q_j)

3. H(C’) = - Suml₌₁ⁿ r_l*log(r_l)

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 C_l of C₊ ↔ P(C’|M’)=P(C’) for all M_i 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

What is the assumption?

[theorem413.ps.entropyperfectsecrecy]

For every cs with M₊,K₊, and |M|=|K|=|C|

What is the definition?

[theorem413.ps.entropyperfectsecrecy, 1+2]

If (i) and (ii) holds then it has ps

(i) P(K’=K)=1/|K| for all K

(ii) For all M, C exists a unique K such that e(M,K)=C

What is the proof “←”?

[theorem413.ps.entropyperfectsecrecy, 3]

1. Show that P(C’|M’)=1/|K|

2. Show that P(C’)=1/|K|

3. Use corollary 4.11 to prove ps

What are the remarks?

[ps.entropyperfectsecrecy, 2]

1. If all sets are positive then only require |M|=|K| for ps

2. If M with p_i=0 then si of M’ and C’ still holds

What are the tools?

[vernam.ps.entropyperfectsecrecy, 5]

1. X={0,…,m-1} with M_N=C_N=K_N=X^N

2. Random variable M_N’ with support M_N

3. Random variable K_N’ iid with P(K_j’=i)=1/m

4. Encryption e(M,K) = ((a₁+s₁) mod m, …, (a_N+s_N) mod m)

5. C_N’ = e(M_N’,K_N’)

What is the definition?

[theorem415.vernam.ps.entropyperfectsecrecy]

Vernam cipher has ps

What is the proof?

[theorem415.vernam.ps.entropyperfectsecrecy]

Proof with theorem 4.13

What are the disadvantages?

[vernam.ps.entropyperfectsecrecy, 3]

1. |K₊|>=|M₊|

2. Keys have to be communicated over a secure channel in advance

3. Therefor exist only limited commercial applications

What happened nevertheless?

[vernam.ps.entropyperfectsecrecy]

It is said to be used in the cold war between Washington and Moscow

What are the properties of the outcome?

[randomexperiment.entropy.entropyperfectsecrecy, 2]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

1. Uncertainty and 2. information gain

When does it play a role?

[uncertainty.randomexperiment.entropy.entropyperfectsecrecy]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Before the experiment takes place

When does it play a role?

[informationgain.randomexperiment.entropy.entropyperfectsecrecy]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

After the experiment takes place

What are the tools?

[entropy.entropyperfectsecrecy, 2]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

1. X is random variable with finite support and distribution P(X=x_i)=p_i

2. Arbitrary constant c>1

What is the definition?

[informationcontent.entropy.entropyperfectsecrecy]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Information content of the event {X=x_j} is I_X(x_j) := -log_c(p_j)

What is the definition?

[entropy.entropy.entropyperfectsecrecy]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

H(X) := Sum_j=1^m p_j*I_X(x_j) // Average of information contents

What is the definition?

[jointentropy.entropy.entropyperfectsecrecy]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

H(X,Y) := Sum_i,j p_ij*log(p_ij)

What is the definition?

[conditionalentropy.entropy.entropyperfectsecrecy]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

H(X|Y) := Sum_i,j p_ij*log( P(X=x_i|Y=y_j) ) // So-called equivocation

What are the remarks for further entropy definitions?

[entropy.entropyperfectsecrecy, 3]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

1. log(0) = -inf

2. 0*log(0) = 0

3. Omit the constant c

What is the definition of a)?

[theorem43.entropy.entropyperfectsecrecy, 3]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

1. 0 <= H(X) <= log(m)

2. If one P(X=x_i)=1 then 0=H(X) // Singleton distribution

3. If for all P(X=x_i)=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 p_ij>0: P(X=x_i|Y=y_j)=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 := {x₁,…,x_m}

2. Code alphabet Y := {y₁,…,y_d}

3. Codeword g(x_j) with length n_j

4. G: (x₁,…,x_m) → (g(x₁),…,g(x_m))

5. Average length n = n(g) = Sum_j=1^m n_j*p_j

What is the definition?

[encoding.coding.entropyperfectsecrecy]

g: x_j → g(x_j)=(w_j1,…,w_jnj)

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

1 / 49

Lernkarten

What is the assumption?

[theorem413.ps.entropyperfectsecrecy]

For every cs with M₊,K₊, and |M|=|K|=|C|

What is the definition?

[theorem413.ps.entropyperfectsecrecy, 1+2]

If (i) and (ii) holds then it has ps

(i) P(K’=K)=1/|K| for all K

(ii) For all M, C exists a unique K such that e(M,K)=C

What is the proof “←”?

[theorem413.ps.entropyperfectsecrecy, 3]

1. Show that P(C’|M’)=1/|K|

2. Show that P(C’)=1/|K|

3. Use corollary 4.11 to prove ps

What are the remarks?

[ps.entropyperfectsecrecy, 2]

1. If all sets are positive then only require |M|=|K| for ps

2. If M with p_i=0 then si of M’ and C’ still holds

What are the tools?

[vernam.ps.entropyperfectsecrecy, 5]

1. X={0,…,m-1} with M_N=C_N=K_N=X^N

2. Random variable M_N’ with support M_N

3. Random variable K_N’ iid with P(K_j’=i)=1/m

4. Encryption e(M,K) = ((a₁+s₁) mod m, …, (a_N+s_N) mod m)

5. C_N’ = e(M_N’,K_N’)

What is the definition?

[theorem415.vernam.ps.entropyperfectsecrecy]

Vernam cipher has ps

What is the proof?

[theorem415.vernam.ps.entropyperfectsecrecy]

Proof with theorem 4.13

What are the disadvantages?

[vernam.ps.entropyperfectsecrecy, 3]

1. |K₊|>=|M₊|

2. Keys have to be communicated over a secure channel in advance

3. Therefor exist only limited commercial applications

What happened nevertheless?

[vernam.ps.entropyperfectsecrecy]

It is said to be used in the cold war between Washington and Moscow

Lernen

CYG Chapter 4 Entropy and Perfect Secrecy

Lernkarteien erstellen oder kopieren

Lernkarten

Bitte melde dich an

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog