Skip to main content

Week - 9

TITLE

Lecture 41:
Universal Hashing​

Universal Hashing (Idea)​

  • Avoid worst-case inputs by randomly choosing hash function at runtime

Definition​

A family of hash functions ( H\mathcal{H} ) is universal if:

Pr⁡h∈H[h(x)=h(y)]≤1m,x≠y\Pr_{h \in \mathcal{H} }[h(x) = h(y)] \le \frac{1}{m}, \quad x \ne y

Why Useful​

  • Prevents adversarial inputs
  • Guarantees low expected collisions
  • Works even if input is malicious

Collision Indicator​

Define:

Cxy={1h(x)=h(y)0otherwiseC_{xy} = \begin{cases} 1 & h(x) = h(y) \\ 0 & \text{otherwise}\\ \end{cases}

Expectation​

E[Cxy]=Pr⁡[h(x)=h(y)]=1mE[C_{xy}] = \Pr[h(x)=h(y)] = \frac{1}{m}

Expected Collisions for Key (xx)​

Let set size = (nn)

E[collisions with x]=n−1m≈αE[\text{collisions with } x] = \frac{n-1}{m} \approx \alpha

(where α=nm\alpha = \frac{n}{m} )

Key Result​

E[collisions]≤αE[\text{collisions}] \le \alpha

✔ Small load factor → fewer collisions

Construction of Universal Family​

Example form:

ha(k)=(∑i=1raiki)mod  mh_a(k) = \left( \sum_{i=1}^{r} a_i k_i \right) \mod m

  • Parameters:

    • (ai)(a_i) chosen randomly
    • Each (ai∈0,1,…,m−1)(a_i \in { 0,1,\dots,m-1 } )

Size of Family​

If there are (r) parameters:

∣H∣=mr|\mathcal{H}| = m^r

Bad Hash Functions​

  • Cause:

    h(x)=h(y)h(x) = h(y)

  • Count of such “bad” functions:

≤mr−1\le m^{r-1}

Probability of Bad Choice​

mr−1mr=1m\frac{m^{r-1}}{m^r} = \frac{1}{m}

✔ Matches universal condition

Two-Level (Perfect Hashing)​

Idea​

  • First level:

    • Distribute keys into buckets

  • Second level:

    • Build separate hash table for each bucket

Property​

For bucket with nin_i keys:

Expected collisions∝ni2\text{Expected collisions} \propto n_i^2

Guarantee​

  • Total space:

    O(n)O(n)

  • Expected collisions:

    <12< \frac{1}{2}

✔ Can achieve perfect hashing (no collisions)

Key Insight​

  • Randomization removes worst-case
  • Universal hashing → expected O(1)O(1) operations
  • Perfect hashing → collision-free lookup
TITLE

Lecture 42:
Cryptographic Hash Function​

Hash Function (Cryptographic Requirements)​

  • Maps arbitrary input → fixed size output
h:0,1∗→0,1nh: {0,1}^* \rightarrow {0,1}^n

Required Properties​

1. Arbitrary Input Size​

  • Accept any length message

2. Fixed Output Size​

  • Output length is constant

3. Pre-image Resistance (One-way)​

Given:

h(x)h(x)

Hard to find:

xx

4. Second Pre-image Resistance​

Given:

xx

Hard to find:

x′≠x such that h(x′)=h(x)x' \ne x \text{ such that } h(x') = h(x)

5. Collision Resistance​

Hard to find:

x≠y such that h(x)=h(y)x \ne y \text{ such that } h(x) = h(y)

Use in Authentication​

Basic Method​

  • Alice sends:

    (M,;h(M))(M,; h(M))

  • Bob:

    • Computes: h(M)h(M)
    • Compares

❌ No security (attacker can modify both)

With Secret Key (MAC)​

  • Shared key:

    KK

  • Alice sends:

    (M,;h(K∣∣M))(M,; h(K || M))

  • Bob verifies:

    h(K∣∣M)h(K || M)

✔ Provides authentication

With Encryption​

  • Alice sends:

    M∣∣EK(h(M))M || E_K(h(M))

  • Bob:

    • Decrypts: h(M)h(M)
    • Verifies

✔ Authentication + confidentiality

With Digital Signature​

  • Alice signs:

    S=EdA(h(M))S = E_{d_A}(h(M))

  • Sends:

    (M,;S)(M,; S)

  • Bob verifies:

    h(M)=DeA(S)h(M) = D_{e_A}(S)

✔ Strong authentication + non-repudiation

Hash Construction (Iterative)​

  • Message split into blocks:

    M1,M2,...,MtM_1, M_2, ..., M_t

  • Initial value:

    H0=IVH_0 = IV

  • Process:

Hi=f(Hi−1,Mi)H_i = f(H_{i-1}, M_i)
  • Final hash: HtH_t

Key Insight​

  • Hash ensures integrity
  • MAC → adds authentication
  • Signature → adds identity proof

Final Note​

  • Secure hash must satisfy:

    • One-way
    • Collision resistant
    • Efficient

✔ Used in all modern cryptographic systems

TITLE

Lecture 43:
Secure Hash Algorithm (SHA)​

Secure Hash Algorithms​

SHA Family​

  • Developed by NIST (1993)
  • SHA-1 later replaced older versions

Variants​

  • SHA-1 → 160-bit
  • SHA-256 → 256-bit
  • SHA-384 → 384-bit
  • SHA-512 → 512-bit

Message Preprocessing (SHA-1)​

Step 1: Padding​

  • Append:

    1 followed by 0s1 \text{ followed by } 0\text{s}

  • So that length ≡ 448 mod 512

Step 2: Append Length​

  • Add original length (64-bit)

Step 3: Blocks​

  • Divide message into: 512-bit blocks512\text{-bit blocks}

Initialization​

  • Initial hash values (IV): H0,H1,H2,H3,H4H_0, H_1, H_2, H_3, H_4

Processing (Per Block)​

  • 80 rounds

  • Uses:

    • Logical functions
    • Constants
    • Message schedule

Compression​

For each block:

CVi+1=Compress(CVi,Mi)CV_{i+1} = \text{Compress}(CV_i, M_i)

Final Hash​

Digest=CVL\text{Digest} = CV_L

Birthday Attack​

  • Based on probability of collisions

Probability Idea​

  • Want: P(collision)>0.5P(\text{collision}) > 0.5

Approximation​

P≈1−e−k22nP \approx 1 - e^{-\frac{k^2}{2n}}

Solve for k​

k22n≈ln⁡2\frac{k^2}{2n} \approx \ln 2 k≈2nln⁡2≈nk \approx \sqrt{2n \ln 2} \approx \sqrt{n}

Example (Birthday Problem)​

  • Total days:

    n=365n = 365

  • Required people:

    k≈23k \approx 23

✔ >50% chance of same birthday

Implication in Hashing​

  • For n-bit hash:
Collision effort≈2n/2\text{Collision effort} \approx 2^{n/2}

Example​

  • SHA-1 (160-bit):
280 operations for collision2^{80} \text{ operations for collision}

Key Insight​

  • Collisions easier than brute force
  • Due to: Birthday paradox\text{Birthday paradox}

Final Notes​

  • SHA-1 → broken (collision attacks exist)

  • Use:

    • SHA-256 or higher

✔ Stronger security against collisions

TITLE

Lecture 44:
Digital Signature Standard (DSS)​

Parameters​

  • Primes:

    p,;q(q∣p−1)p,; q \quad (q \mid p-1)

  • Generator:

    g=hp−1qmod  pg = h^{\frac{p-1}{q}} \mod p

Key Generation​

  • Private key:

    x∈1,2,...,q−1x \in {1,2,...,q-1}

  • Public key:

    y=gxmod  py = g^x \mod p

Signing​

  • Hash message:

    H=h(M)H = h(M)

  • Choose random:

    k∈1,2,...,q−1k \in {1,2,...,q-1}

Compute​

r=(gkmod  p)mod  qr = (g^k \mod p) \mod q s=k−1(H+xr)mod  qs = k^{-1}(H + xr) \mod q

Signature​

(r,s)(r, s)

Verification​

  • Check: 0<r,s<q0 < r,s < q

Compute​

w=s−1mod  qw = s^{-1} \mod q u1=Hwmod  qu_1 = Hw \mod q u2=rwmod  qu_2 = rw \mod q

Compute​

v=((gu1⋅yu2)mod  p)mod  qv = ((g^{u_1} \cdot y^{u_2}) \mod p) \mod q

Validity​

v=r⇒validv = r \Rightarrow \text{valid}

Correctness​

s=k−1(H+xr)s = k^{-1}(H + xr) ⇒k=(H+xr)s−1\Rightarrow k = (H + xr)s^{-1}

Substitute in:

gk=gHs−1⋅gxrs−1g^k = g^{H s^{-1}} \cdot g^{x r s^{-1}} =gu1⋅yu2= g^{u_1} \cdot y^{u_2}

Key Points​

  • Uses hash:

    h(M)h(M)

  • Random:

    k must be secret and uniquek \text{ must be secret and unique}

  • Security based on:

    Discrete Log Problem\text{Discrete Log Problem}

Important Notes​

  • Reusing (k) → private key leak
  • Requires secure random generation

Final Insight​

  • Signature = pair:

    (r,s)(r,s)

  • Verification uses:

    • Public key
    • Hash
    • Modular arithmetic

✔ Standardized digital signature scheme

TITLE

Lecture 45:
More on Key Exchange Protocol​

3-Party Key Exchange (Basic Idea)​

  • Parties: Alice, Bob, Charlie

  • Public:

    g,;pg,; p

  • Secrets:

    a,;b,;ca,; b,; c

Exchange​

  • Alice sends:

    gag^a

  • Bob sends:

    gbg^b

  • Charlie sends:

    gcg^c

Goal​

  • Shared key: K=gabcmod  pK = g^{abc} \mod p

Problem​

  • With normal exponentiation:

    • Requires multiple rounds
    • Not efficient

Bilinear Pairing Setup​

  • Groups:

    G1 (additive),G2 (multiplicative)G_1 \text{ (additive)}, \quad G_2 \text{ (multiplicative)}

  • Pairing:

    e:G1×G1→G2e: G_1 \times G_1 \rightarrow G_2

Properties​

1. Bilinearity​

e(aP,bP)=e(P,P)abe(aP, bP) = e(P,P)^{ab}

2. Non-degeneracy​

e(P,P)≠1e(P,P) \ne 1

3. Computability​

  • Efficient to compute

Public Setup​

  • Generator:

    P∈G1P \in G_1

  • Public:

    P,;G1,;G2,;eP,; G_1,; G_2,; e

Private Keys​

a,;b,;ca,; b,; c

Exchange (1 Round)​

  • Alice sends:

    aPaP

  • Bob sends:

    bPbP

  • Charlie sends:

    cPcP

Key Computation​

Alice​

K=e(bP,cP)a=e(P,P)abcK = e(bP, cP)^a = e(P,P)^{abc}

Bob​

K=e(aP,cP)b=e(P,P)abcK = e(aP, cP)^b = e(P,P)^{abc}

Charlie​

K=e(aP,bP)c=e(P,P)abcK = e(aP, bP)^c = e(P,P)^{abc}

Shared Key​

K=e(P,P)abcK = e(P,P)^{abc}

✔ Same for all three

Key Insight​

  • Pairing enables:

    multiplication of exponents across parties\text{multiplication of exponents across parties}

  • Achieves:

    • 3-party key agreement
    • Single round communication

Notes​

  • Used in:

    • Identity-based cryptography
    • Advanced protocols

  • Still active research area