hannon's perfect secrecy_important point of ppt.ppt

Certainly! Here’s a detailed overview of Shannon's Perfect Secrecy, focusing on the essential points and concepts.

### Shannon's Perfect Secrecy

#### Introduction
- **Definition**: Perfect secrecy is a concept in cryptography where the ciphertext provides no information about the plaintext without the key.
- **Origin**: Introduced by Claude Shannon in his 1949 paper "Communication Theory of Secrecy Systems."

#### Claude Shannon
- **Background**: Known as the father of information theory.
- **Contribution**: Applied mathematical principles to cryptography, defining the criteria for unbreakable encryption systems.

#### Key Concepts of Perfect Secrecy
- **Mathematical Definition**: A cryptosystem achieves perfect secrecy if, for every plaintext and ciphertext, the probability of the plaintext given the ciphertext is equal to the probability of the plaintext.
\[ P(M|C) = P(M) \]
- **M**: Message (plaintext)
- **C**: Ciphertext
- **P(M)**: Probability of message M
- **P(M|C)**: Conditional probability of M given C

#### One-Time Pad (OTP)
- **Example of Perfect Secrecy**: The One-Time Pad is a cryptographic algorithm that achieves perfect secrecy.
- **How It Works**:
- **Key**: A random key as long as the message.
- **Encryption**: Each bit/character of the plaintext is XORed with the corresponding bit/character of the key.
- **Decryption**: The ciphertext is XORed with the same key to retrieve the original plaintext.
- **Security**: The key must be truly random, used only once, and kept completely secret.

#### Properties and Implications
- **Unbreakable Encryption**: With perfect secrecy, the ciphertext is statistically independent of the plaintext.
- **Key Length**: The key must be at least as long as the message.
- **Practical Considerations**:
- **Key Management**: Generating, distributing, and securely storing long keys can be impractical for many applications.
- **Use Cases**: Used in scenarios requiring the highest security, such as military communications.

#### Limitations and Practicality
- **Scalability**: Perfect secrecy requires impractically large keys for lengthy messages.
- **Modern Cryptography**: While perfect secrecy is ideal, practical cryptographic systems use computational security (e.g., AES, RSA) which are secure based on the computational difficulty of breaking them.

#### Conclusion
- **Significance**: Shannon’s Perfect Secrecy sets a theoretical benchmark for cryptographic security.
- **Legacy**: Influences modern cryptographic research and standards, despite practical limitations for everyday use.

### References
- **Claude Shannon's Paper**: "Communication Theory of Secrecy Systems" (1949)
- **Books**: "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, "Applied Cryptography" by Bruce Schneier

This content covers the fundamental aspects of Shannon's Perfect Secrecy, suitable for a detailed understanding or presentation.

1. Hannon’s Perfect Secrecy
Name: Pravinraam R
Roll no: 22BECY042
subject: Internet Security
1

2. 2
Perfect Secrecy: Shannon
(Information-Theoretic) Security
•Basic Idea: Ciphertext should provide no
“information” about Plaintext
•Have several equivalent formulations:
–The two random variables M and C are independent
–Observing what values C takes does not change what
one believes the distribution M is
–Knowing what is value of M does not change the
distribution of C
–Encrypting two different messages m
0 and m
1 results
in exactly the same distribution.

3. Perfect Secrecy Definition 0
Definition. (Gen,Enc,Dec) over a message space M is
perfectly secure if
 probability distribution over M
The random variables M and C are independent.
That is,
 message mM
 ciphertext c C
Pr [M=m C=c] = Pr [M = m] Pr [C = c]
3

4. Perfect Secrecy Definition 1
Definition 2.1 (From textbook). (Gen,Enc,Dec) over
a message space M is perfectly secure if
 probability distribution over M
 message mM
 ciphertext cC for which Pr[C=c] > 0
We have
Pr [M=m | C=c] = Pr [M = m].
4

5. Definition 0 equiv. Definition 1
•Definition 0 implies Definition 1
–Idea: Given Pr [M=mC=c] = Pr [M = m] Pr [C = c], for
any c such that Pr [C = c] > 0, divide both sides of the
above with Pr [C = c], we have Pr [M=m | C=c] = Pr [M
= m].
•Definition 1 implies Definition 0
–Idea:  cC s.t. Pr[C=c] > 0
Pr [M=m | C=c] = Pr [M = m], multiple both side by
Pr[C=c], obtain Pr [M=mC=c] = Pr [M = m] Pr [C = c]
 cC s.t. Pr[C=c] = 0 we have Pr [M=mC=c] = 0 = Pr
[M=m] Pr[C=c]
5

6. Perfect Secrecy. Definition 2.
Definition in Lemma 2.2. (Gen,Enc,Dec) over a
message space M is perfectly secure if
 probability distribution over M
 message mM (assuming Pr[M=m]>0)
 ciphertext cC
We have
Pr [C=c | M=m] = Pr [C = c].
•Equivalence with Definition 0 straightforward.
6

7. Perfect Indistinguishability
Definition in Lemma 2.3. (Gen,Enc,Dec) over a message space
M is perfectly secure if
 probability distribution over M
 messages m
0,m
1M
 ciphertext cC
We have
Pr [C=c | M=m
0] = Pr [C=c | M=m
1]
To prove that this definition implies Definition 0, consider Pr
[C=c].
7

8. Adversarial Indistinguishability
•Define an experiment called PrivK
eav
:
–Involving an Adversary and a Challenger
–Instantiated with an Adv algorithm A, and an
encryption scheme  = (Gen, Enc, Dec)
8
Challenger Adversary
k  Gen()
b 
R
{0,1}
chooses m
0
, m
1
Mm
0, m
1
C=E
k
[m
b
]
b’ {0,1}
PrivK
eav
= 1 if b=b’, and PrivK
eav
= 0 if b b’

9. Adversarial Indistinguishability
(con’d)
Definition 2.4. (Gen,Enc,Dec) over a message
space M is perfectly secure if
 adversary A it holds that
Pr[PrivK
eav
A,
=1] = ½
Proposition 2.5. Definition 2.1 is equivalent to
Definition 2.4.
9

10. 10
Perfect Secrecy
•Fact: When keys are uniformly chosen in a cipher,
a deterministic cipher has Shannon security iff.
the number of keys encrypting m to c is the same
for any pair of (m,c)
•One-time pad has perfect secrecy (Proof?)
–In textbook

11. 11
The “Bad News” Theorem for Perfect
Secrecy
•Question: OTP requires key as long as messages, is this an
inherent requirement for achieving perfect secrecy?
•Answer. Yes. Perfect secrecy implies that key-length
 msg-length
Proof:
•Implication: Perfect secrecy difficult to achieve in practice
P
l
a
i
n
t
e
x
t

s
p
a
c
e
C
i
p
h
e
r
t
t
e
x
t

s
p
a
c
e

12. 12
Key Randomness in One-Time Pad
•One-Time Pad uses a very long key, what if the
key is not chosen randomly, instead, texts from,
e.g., a book are used as keys.
–this is not One-Time Pad anymore
–this does not have perfect secrecy
–this can be broken
–How?
•The key in One-Time Pad should never be reused.
–If it is reused, it is Two-Time Pad, and is insecure!
–Why?

13. THANK YOU
13