Secure communication

over an insecure channel.

Problem

A and B communicate, E evesdrops. E should not know what is communicated, and E should not be able to cause miscommunication between A and B.

Unbounded adversary

(Shannon) Theory of perfect secrecy. Adversary assumed to have unlimited computational resources. Secure encryption system exists only if $| S |$ is as large as $| m |$ .

One time pad

$E (p a d, m) = m \oplus p a d$ ; $D (p a d, c) = c \oplus p a d$ . Unbreakable even by computationally unbounded adversary: Modern cryptography abandons this. $\forall m, c : P r_{p a d} (E (p a d, m) = c) = 2^{- n}$ : so perfectly secret. But not good for 2 messages: $E (p a d, m_{1}) \oplus E (p a d, m_{2})$ reveals common bits.

Bounded adversary

Often parametrized by security parameter k.

Passive adversary

Possibly randomized algorithm which runs in poly(k) time, has passive access to everything on the insecure channel. May know probability distribution over messages.

Is said to break cryptosystem if it succeeds with non negligible probability: $\frac{1}{p o l y (k)}$ .

Active adversary

Passive adversary with extra powers. Can alter or stop messages, request polynomial number of cyphertexts to be decyphered.

A common active adversary attack is the replay attack.

Collusion attacks

Multiple adversaries share info and attack.

Proving security/ vulnerability

Security from evesdropping

Prob of predicting m given c = Prob of predicting m without c: seeing c gives no ‘information’.

Specify scheme

Describe Setup(l), encrypt, decrypt, keygen etc.. algs.

General strategy

Show security of B based on security of A: $S e c u r e (A) ⟹ S e c u r e (B) \equiv a t t a c k a b l e (B) ⟹ a t t a c k a b l e (A)$ : The latter form is more convenient to prove.

Make security game

Take polytime B attacker, call it Z. Make B challenger/ A attacker, call it Y. Take A challenger, call it X. Visualization: use boxes and arrows to see how Y uses Z to respond to X’s challenge.

Show success of attack wnnp

Security parameter l: All probabilities and running time are in terms of this. Use cases to analyze probability of success of attack.

Show equivalence of 2 models of security

Show that a successful attacker in one can be used to build a successful attacker in another.

Using hardness assumptions to prove security

Take hardness assumption H. Use this as A.

Tightness of assumption

Cryptosystem B, assumption A. Show that you can break A given attacker for B. Show that you can break B given attacker for A.

Security from weaker adversaries

Sometimes, proof of security against CPA is not known. So, security is proved against weaker adversaries. Eg: Security in random oracle model, selective security etc..

A stepping stone in finding proof of security against unhindered adversary.

Private key encryption

Communicators A and B; Encryption and decryption algorithms E, D; common secret key S; adversary may know (E, D), but not S; cleartext or plaintext message m; ciphertext c = E(m,S).

Substitution cipher

S = the permutation f. Easy to break by adversary who sees moderately many ciphertexts. \why

Public key cryptography

Aka assymetric key cryptography.

Weak definition

Uses trapdoor one way functions. Setup(l) = (PK, SK). Weak defn: E(m, PK) = c; D(c, SK) = m: If A transmits only 2 messages, Attacker could encrypt both messages and say what is being transmitted.

Strong defnition: blinding messages

So, random r is chosen, m is blinded using r to get m’, $E (m, r, P K) = c$ . D(c, SK) = m’, r; thence unblind to get m.

Blinding and unblinding is often done by computing a blinding factor (bf). Agents agree on bf in a way similar to key exchange protocols.

Hybrid cryptography

In practice, this is used, rather than pure public key cryptography as it is slow. Public key crypto is used only to share a common secret ‘session key’ S. S is then used to actually encrypt messages.

Semantic security: chosen plaintext attack (CPA)

Take challenger C and attacker A.

C sends PK to A. A sends plaintexts $m_{0}$ and $m_{1}$ to C. C picks $g \in_{U} {0, 1}$ and sends $c = E (m_{g}, r, P K)$ . A surmises and returns g.

If A has non negligible advantage over random guessing, the crypto scheme is broken by A.

Semantic security from CCA

Same as CPA security game, with extra powers to the attacker: The attacker A can ask for decryption of poly num of cyphertexts in two phases: one before challenger C sends $c = E (m_{g}, r, P K)$ , and one afterwards. In second phase, A cannot demand decryption of c. If given an invalide cyphertext, C responds with ‘invalid cyphertext’ or $⊥$ message.

Hybrid proofs

Eg: two public key schemes: X1, X2; new PK scheme X encrypts m to users using both; show $s e c u r e (X 1) \land s e c u r e (X 2) ⟹ s e c u r e (X)$ . So show $\neg s (X) ⟹ \neg s (X 1) \lor \neg s (X 2)$ : Consider CPA game where attacker B knows ${m_{0}, m_{1}}$ , X challenger A picks random bit g, encrypts $m_{g}$ ; gives B $c_{0} = e n c (m_{g}, X 1), c_{1} = e n c (m_{g}, X 2)$ ; B guesses g’; So $\neg s (X) \equiv P r (g^{'} = g) \geq 2^{- 1} + ϵ$ . Take $p_{1} = P r (g^{'} = 1 | g = 1), p_{0} = P r (g^{'} = 1 | g = 0)$ ; imagine hybrid case: $p_{h} = P r (g^{'} = 1 | e n c (m_{0}, X 1), e n c (m_{1}, X 2))$ . $\neg s (X) \equiv P r (g^{'} = g) \geq 2^{- 1} + ϵ \equiv 2 ϵ \leq | p_{1} - p_{0} | \leq | p_{1} - p_{h} | + | p_{0} - p_{h} | \equiv | p_{1} - p_{h} | \geq ϵ \lor | p_{0} - p_{h} | \geq ϵ \equiv \neg s (X 1) \lor \neg s (X 2)$ .

RSA

Choose random N=pq with p, q large primes : use rand alg; pick PK: exponent $e \in {1, . . ϕ (N) - 1}$ coprime with $ϕ (N)$ ; choose SK exp d to satisfy $d e = 1 mod ϕ (N)$ ; PK: (N, e); SK: (N, d). Message of length m; encrypt: $c = m^{e} \mod N$ : exponentiation by squaring; decrypt: $c^{d} \mod N$ .

Security from RSA hardness assumption. Vulnerable to CCA.

This is the fastest PK scheme.

ElGamal

$P K = (g, g^{y})$ . SK = y. Encr: Pick random r, make bf: $(g^{y})^{r}$ . $c = g^{r}, m . g^{y r}$ . Decr: Recover $(g^{r})^{y}$ , thence decrypt. Agreement on bf similar to DH key exchange.

Security from CPA if DDH hard

If DDH is hard, ElGamal is secure: Consider DDH Challenger DC, DDH attacker DA, El Gamal attacker A. DC picks random t, sets $T = g^{a b}$ if t=1. DC gives $g, g^{a}, g^{b}, T$ to DA. DA gives $P K = g, g^{a}$ to A. A gives $m_{0}$ and $m_{1}$ to DA. DA picks random b and gives A $c = T, m_{b} . T$ . If T is a valid bf, A returns g wnnp. Thence, DA can defeat DC wnnp: analyze probabilities of success for the cases where t=0 and t=1.

Vulnerability when DDH broken

Can use any DDH atatcker to break ElGamal: show with a security game.

True if there are efficiently computable bilinear maps.

CCA vulnerability

Attacker demands decryption of $c^{'} = g^{r + r^{'}}, h m_{b} . g^{y (r + r^{'})}$ , thence identifies $m_{b}$ : cyphertext for $h m_{b}$ used as some challengers may refuse to decrypt a previously sent msg.

CCA secure scheme from IBE scheme

PK = PP; SK = MSK, SigSK (Signature SK), SigPK. Enc(m) : choose random id, find \ $C T = E n c_{I B E} (P P, I D, m)$ , make CT, id, sigSK(CT). \ Dec: if $s i g P K (s i g S K (C T)) \neq C T$ abort; else get $K e y g e n (M S K, i d) = S K_{i d}$ ; do $D e c_{I B E} (C T, S K_{i d}) = m$ .

Speed

1 pairing costs approximately as much as 8 large exponentiations.

DLA based cryptosystem

Setup(l): $S K = (x, y) . P K = (g, u = g^{x}, v = g^{y})$ . Encrypt by selecting random a and b. Come to agreement on BF: $v^{a + b}$ .

Applications

Public key cryptography is highly secure. But, it is often slower compared to symmetric key encryption.

SSL uses public key cryptography for key exchange and symmetric encryption for privacy.

Key exchange

Diffie Hellman (DH)

A chooses generator g, prime p, random $a \in G$ . Sends $(g, p, g^{a} \mod p)$ to B. B picks random b, sends $g^{b} \mod p$ . Both $A$ and $B$ now find secrect key $S = g^{a b} \mod p$ .

3 party key exchange

A, B, C pick x, y, z; have bilinear map $e : G \times G \to G_{T}$ , generator $g \in G$ ; publish $g^{x}, g^{y}, g^{z}$ ; agree upon SK = $e (g, g)^{x y z} = e (g^{x}, g^{y})^{z}$ .

Access control

Server based vs encryption based.

Role based access control

Functional encryption: Specify access policy (a bool formula) as part of ct.

Want people with 2 attributes to access something: Share secret info $m \in G$ between 2 roles: Turn policy into a infix boolean tree: When you encounter $\land$ , split m into r, m-r. Subject to collusion attack: Solve by initially encrypting with requestor’s PK.

Broadcast encryption

Bandwidth limited. Eg: Direct TV, radio, GPS.

Like IBE. Setup(l,n): $P P, S K_{1} . . S K_{n}$ . \ $E n c (P P, m, S \subseteq [n]) : c$ . $D e c (c, i, S K_{i}, S \subseteq [n]) = m$ iff $i \in S$ .

Want collusion resistance. t-collusion resistance: $| c | \geq t^{2} \log n$ \why.

CPA Security

Challenger A, attacker B. A to B: PP; B to A: keygen requests, get ${S K_{i}}$ ; B to A: target set S’, chosen messages $m_{1}, m_{2}$ ; A picks random b, returns $e n c (P P, m_{b}, S^{'})$ . B can encrypt arbit m himself.

Static security: announce S’ first.

BB IBE based scheme

(BGW) Setup(l,n): Pick random a, g, ${u_{1} . . u_{n}}$ , ${r_{1} . . r_{n}}$ . $P P : e (g, g)^{a}, {u_{i}}$ . $S K_{i} : g^{a} u_{i}^{r_{i}}, g^{r_{i}}, \forall_{j \neq i} u_{j}^{r_{i}}$ .

$E n c (P P, m, S) : m e (g, g)^{a s}, g^{s}, \prod_{i \in S} u_{i}^{s}$ for random s: like BB IBE enc \ to $\prod_{i \in S} u_{i}^{s}$ : a SK for every S.

Dec: Want to find bf: $e (g, g)^{a s}$ ; so find $e (g^{s}, g^{a} u_{i}^{r_{i}})$ , find $e (g^{r_{i}}, \prod_{i \in S} u_{i}^{s}) = \prod_{i \in S} e (g^{r_{i}}, u_{i}^{s})$ , divide by $e (g^{s}, \prod_{j \in S, j \neq i} u_{j}^{r_{i}})$ .

Security against q-BDHE

A q-BDHE challenger, B q-BDHE attacker, C BGW attacker.

A to B: $g, h, g^{b}, g^{b^{2}}, . . g^{b^{q}}, g^{b^{q + 2}} . . g^{b^{2 a}}$ : no $g^{b^{q + 1}}$ ; see if $T \overset{_{?} =}{e} (g, h)^{b^{q + 1}}$ .

C to B: S’. B sets $h = g^{s}, a = b^{q + 1}$ ; picks $(y_{i})$ , sets $\forall i \in S^{'} : u_{i} = g^{y_{i}}$ , other i: $u_{i} = g^{b^{i}} g^{y_{i}}$ . B answers keygen reqs: need find $g^{a} u_{i}^{r_{i}} = g^{b^{n + 1}} (g^{b^{i}} g^{y_{i}})^{r_{i}}$ , don’t know $g^{a}$ , so try cancellation by picking $r_{i} = - b^{n + 1 - i}$ ; actually, to make $r_{i}$ look random, must add some $x_{i}$ . C to B: $m_{1}, m_{2}$ . B to C: picks $m_{b}$ , sends $m_{b} T, g^{s}, \prod_{i \in S^{'}} h^{y_{i}}$ .

Piracy of broadcast system

DRM impossibility argument: Can’t protect content from leaking out. Can only protect original broadcast stream. Traitor tracing: Who pirated the original stream?