1 of 38

Introduction to Cryptography�- Information Theoretic Crypto

NISHANTH CHANDRAN

2 of 38

What was/is cryptography?

Dictionary Definition of Cryptography

“art of writing and solving codes”

Wikipedia Definition

“securing communication against adversarial behavior”

Today

A scientific discipline using mathematical techniques to secure digital information
Encompasses data protection during storage, communication, and even computation

3 of 38

What the summer school will cover

How to securely communicate and store data using encryption and signature schemes
How to formalize when a cryptographic scheme is secure
What is meant by pseudorandomness and one-way functions?
Hash functions and their uses
How to prove something about your secret without revealing anything about it
How multiple entities can compute jointly on all their data without revealing it in the clear to anyone
How to obfuscate your program securely
And finally, topics related to blockchains

4 of 38

Securely Communicate – �Private Key Encryption Schemes

Alice

Bob

5 of 38

Private Key Encryption (Scenarios)

Alice and Bob meet ahead of time to share private key��(or use more expensive public key encryption to share private key)

Alice encrypts her own data with private key and later decrypts

6 of 38

Keys and Kerckhoff’s Principle�The cipher method must not be required to be secret

Significantly easier to keep key secret

In case secret is compromised, easier to change

Significant benefit to public review�(Today, several competitions to pick best ciphers etc.)

7 of 38

Historical Ciphers – Caesar Cipher

Problem 1:

“Key” fixed

De vita Caesarum Divus iulius

8 of 38

Historical Ciphers – �Shift Cipher

Problem 2:

Only 26 options for keys

Brute-force Attack�(or exhaustive search)

Key should be large�enough – say 2⁸⁰ options

De vita Caesarum Divus iulius

9 of 38

Mono-alphabetic Substitution Cipher

Brute force impractical

However, susceptible to frequency attacks

Exploit statistical properties of English�(or underlying message space)

10 of 38

Avg. letter frequencies of English-language text

Record frequency of letters�in ciphertext

Correlate with frequency of�plaintext letters

11 of 38

Principles of Modern Cryptography

Formal Definitions of Security

What the adversary/attacker can see/do

What security you require? �That is, what should the attacker not be able to learn/do?

Can you “prove” this?

12 of 38

Private Key Encryption - Defining

What does the adversary/attacker get?

One ciphertext, many ciphertexts? (Ciphertext only attack)
Plaintext/Ciphertext pairs? (Known-plaintext attack)
Plaintext/Ciphertext pairs of adversary’s choice (Chosen-plaintext attack)
Get some ciphertext’s decrypted? (Chosen-ciphertext attack)

What should the attacker not be able to do?

Impossible to recover key?
Impossible to recover the plaintext?
Impossible to recover any character of the plaintext?
Regardless of any information an attacker already has, ciphertext should leak no additional information about the underlying plaintext

13 of 38

Proving Schemes Secure

14 of 38

Generating Randomness

Assume:

Parties can generate unlimited independent, unbiased (i.e., uniform) bits.
In practice, not easy
Get small amount of unpredictable data from physical processes (say on the chip)
Must “convert” them into uniform bits�(through a process known as randomness extraction)

Toy Problem:

�Given coin where Pr[H] = p & Pr[T] = 1-p, �how to obtain unbiased bits 0 and 1? �(i.e. where Pr[0] = Pr[1]?)

15 of 38

Perfectly Secure Private Key Encryption

16 of 38

Keys, Messages, Ciphertexts

17 of 38

Keys, Messages, Ciphertexts

Pr[M = “attack today”] = 0.7

Pr[M = “don’t attack”] = 0.3

20 of 38

Perfect Secrecy (Claude Shannon)

21 of 38

Shift Cipher is NOT perfectly secure

22 of 38

Perfect Indistinguishability Definition

23 of 38

Perfect Secrecy and Perfect Indistinguishability Definitions are Equivalent

25 of 38

An (equivalent) Game Based Definition

26 of 38

The One-Time Pad (Gilbert Vernam)

One Time Pad is Perfectly Secure

Perfect Indistinguishability 🡪 Perfect Secrecy

27 of 38

Moscow-Washington Hotline �(During the Cold War)�One-Time Pad

28 of 38

Limitations of One Time Pads

29 of 38

Perfect Secrecy �🡪 Long Keys

30 of 38

Shannon’s Theorem

33 of 38

Secret Sharing