CS178 - intro to cryptography

general strategy

1. identify

2. translate into probability

3. look for invariance under XOR or randomness

negligible functions strategy

1. simplify

2. is 1/n negligible

ensembles strategy

1. check length

2. check independence

3. build simple test

perfect/semi-perfect/multi-message security strategy

1. implication (chain equalities or counterexample)

2. multi-message security (key reuse, partial leakage, repeated structure)

hybrid technique strategy

indistinguishability does not equal identical

pseudorandom generator strategy

1. construction validity

2. range-size

3. expansion construction

uniform

every possible value is equally likely

private key encryption correctness

m = m’

Pr[Dec(k,c) → m : Gen(λ) → k, Enc(k,m) → c] = 1

formal security definition

adversary a:

1. chooses m₀, m₁

2. challenger picks b in {0,1}

3. returns Enc(k, m_b)

4. A outputs guesses b’

wins if b = b’

secured if Pr[A wins] <= ½ + negligible(n)

one-time pad

• key is truly random

• key length = message length

• used only one

• encryption: XOR c = m XOR k

double one-time pag

encrypt messages twice using two INDEPENDent one-time pads

• pick random keys, k_1, k₂

• compute c = m XOR k₁ XOR k₂

(k = k₁ XOR k₂)

one-time perfect security

ciphertext reveals ZERO info about message

• key is random

• key length >= message length

• key is only used once

hybrid technique

1. generate random symmetric key

2. encrypt it w/ recipient’s public key

3. use symmetric key for bulk data

monotonicity property

Security improves as n grows and never regresses.

negligible functions

for every polynomial p(n): f(n) < 1/p(n)

“goes to 0 faster than any inverse polynomial”

used to measure acceptable attacker advantage

1/poly(n) : NO

2^-poly(n) : YES

multi-message security

adversary can see MANY ciphertexts, not just one and still must not learn anything useful

computational indistinguishability

• used when perfect security is impossible

• Distributions may differ, but no efficient algorithm can exploit the difference.

• two ensembles X_n, Y_n

• for all PPT distinguishers : |Pr[D(X_n) = 1 - Pr[D(Y_n) = 1] | <= negligible

pseudorandom generators (PRG)

• deterministic: G: {0,1}ⁿ → {0,1}^m

• efficient, expands length, output indistinguishable from uniform

• start key → PRG → long key → OTP-style expansion

one-way functions

• easy to compute, hard to invert

• PRGS exists IFF OWS exists