Skip to main content

Week - 12

TITLE

Lecture 56:
Functional Encryption (Introduction)​

Homomorphic Encryption​

Idea​

  • Compute on encrypted data
Enc(m1);∘;Enc(m2)=Enc(f(m1,m2))Enc(m_1) ;\circ; Enc(m_2) = Enc(f(m_1, m_2))

✔ No need to decrypt

Use Case​

  • Alice stores encrypted data on cloud

  • Bob wants:

    m1+m2m_1 + m_2

  • Cloud computes directly on ciphertext

Types​

1. Additive Homomorphic​

Enc(m1)⋅Enc(m2)=Enc(m1+m2)Enc(m_1) \cdot Enc(m_2) = Enc(m_1 + m_2)

2. Multiplicative Homomorphic​

Enc(m1)⋅Enc(m2)=Enc(m1⋅m2)Enc(m_1) \cdot Enc(m_2) = Enc(m_1 \cdot m_2)

3. Fully Homomorphic (FHE)​

  • Supports: +,;×+,; \times

✔ Arbitrary computation

Examples​

ElGamal​

  • Multiplicative:
Enc(m1)⋅Enc(m2)=Enc(m1⋅m2)Enc(m_1) \cdot Enc(m_2) = Enc(m_1 \cdot m_2)

RSA​

  • Also multiplicative:
Enc(m)emod  nEnc(m)^e \mod n

✔ Not suitable for addition

Limitation​

  • Most schemes support only one operation
  • FHE → very expensive

Cloud Computing Scenario​

  • Alice:

    Enc(m1),;Enc(m2)Enc(m_1),; Enc(m_2)

  • Cloud computes:

    Enc(f(m1,m2))Enc(f(m_1, m_2))

  • Bob decrypts → gets result

✔ Data privacy preserved

Functional Encryption (FE)​

Idea​

  • Instead of full message:

    • Learn only: f(m)f(m)

Key Concept​

  • Secret key tied to function:

    SKfSK_f

  • Decryption reveals:

    f(m)f(m)

✔ Nothing else about (m)

Example​

  • Spam filter:

    • Output: spam / not spam\text{spam / not spam}

  • Without revealing full message

Attribute-Based Logic (Extension)​

  • Conditions like:
Age>35;∧;PhD\text{Age} > 35 ;\land; \text{PhD}

Collusion Problem​

  • Multiple users combine attributes

❌ May break policy

✔ Secure schemes prevent this

Applications​

  • Cloud computation
  • Access control
  • Data analytics
  • Auditing systems

Key Insight​

  • Homomorphic → compute on encrypted data
  • Functional → reveal only function output

Summary​

  • Homomorphic:

    Enc(m1),Enc(m2)→Enc(f(m1,m2))Enc(m_1), Enc(m_2) \rightarrow Enc(f(m_1,m_2))

  • Functional:

    SKf⇒f(m)SK_f \Rightarrow f(m)

✔ Advanced cryptography for privacy-preserving systems

TITLE

Lecture 57:
Discrete Logarithm Problem (DLP)​

Discrete Logarithm Problem (DLP)​

Definition​

  • Given cyclic group (G = \langle \alpha \rangle) of order (n)

  • Compute (a) such that:

β=αa\beta = \alpha^a log⁡αβ=a\log_\alpha \beta = a

Important Case​

  • Group:

    Zp∗\mathbb{Z}_p^*

  • (p) prime

  • (\alpha) = generator

✔ Problem is computationally hard

Brute Force Method​

  • Try all possible values:
a=0,1,2,…,p−1a = 0,1,2,\dots,p-1
  • Check:
αi=?β\alpha^i \stackrel{?}{=} \beta

⏱ Time complexity:

O(p)O(p)

Table Lookup Method​

  • Precompute:
(αi,i)(\alpha^i, i)
  • Store in table
  • Search for match with (\beta)

⏱ Time: fast lookup 💾 Space: large

Baby-Step Giant-Step (Shanks Algorithm)​

Idea​

Let:

n=∣G∣,m=⌈n⌉n = |G|,\quad m = \lceil \sqrt{n} \rceil

Step 1 (Baby Steps)​

Compute:

L1=αmj∣j=0,1,…,m−1L_1 = {\alpha^{mj} \mid j = 0,1,\dots,m-1}

Step 2 (Giant Steps)​

Compute:

L2=βα−i∣i=0,1,…,m−1L_2 = {\beta \alpha^{-i} \mid i = 0,1,\dots,m-1}

Step 3​

Find match:

αmj=βα−i\alpha^{mj} = \beta \alpha^{-i}

Then:

αmj+i=β\alpha^{mj+i} = \beta a=mj+ia = mj + i

Complexity​

O(n)O(\sqrt{n})

✔ Much faster than brute force

Example Result​

log⁡3525mod  809=309\log_3 525 \mod 809 = 309

Pohlig–Hellman Algorithm​

Idea​

  • If:
n=p1c1p2c2⋯pkckn = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}
  • Reduce problem into smaller subproblems

Goal​

Find:

amod  picia \mod p_i^{c_i}

Representation​

Write:

a=a0+a1q+a2q2+⋯+ac−1qc−1a = a_0 + a_1 q + a_2 q^2 + \dots + a_{c-1} q^{c-1}

Step (for each digit)​

Compute:

βn/q=αa0n/q\beta^{n/q} = \alpha^{a_0 n/q}

Let:

γ=αn/q\gamma = \alpha^{n/q}

Now find (a_0) using brute force:

γi=βn/q\gamma^i = \beta^{n/q}

Repeat​

  • Find (a_1, a_2, \dots)

Final Step​

Use Chinese Remainder Theorem:

amod  na \mod n

Key Insight​

  • Difficulty depends on factorization of (n)

✔ If (n) has small factors → easy ✔ If (n) has large prime factor → hard

Summary​

  • DLP:

    β=αa⇒a=log⁡αβ\beta = \alpha^a \Rightarrow a = \log_\alpha \beta

  • Methods:

    • Brute force → slow
    • BSGS → (O(n)O(\sqrt{n}))
    • Pohlig–Hellman → efficient if (n) factorable

✔ Foundation of:

  • Diffie–Hellman
  • ElGamal
  • ECC
TITLE

Lecture 58:
Implementation Attacks​

Side-Channel Attacks (Implementation Level)​

Core Idea​

  • Attack does not break algorithm mathematically
  • Instead, it uses physical leakage from implementation

Examples of leakage:

  • Time taken
  • Power consumption
  • Electromagnetic signals
  • Fault behavior

Types (FIPS Perspective)​

  1. Timing Attack
  2. Power Analysis Attack
  3. Electromagnetic (EM) Attack
  4. Fault Injection Attack

Timing Attack​

  • Observe execution time of operations

Example:

  • Modular exponentiation (a^b \mod n)

If using square-and-multiply:

b=(bkbk−1…b0)2b = (b_k b_{k-1} \dots b_0)_2
  • Different bits → different operations
  • Time variation leaks key bits

Idea​

  • If bit = 1 → multiply + square
  • If bit = 0 → only square

➡ Time difference ⇒ recover secret exponent

Countermeasures​

  • Constant-time implementation
  • Avoid data-dependent branches
  • Random delays (less reliable defense)

Power Analysis Attack​

Observation​

  • Power consumption varies per instruction

  • Example:

    • XOR → low power
    • Multiplication → higher power

Types​

1. Simple Power Analysis (SPA)​

  • Directly observe power trace
  • Identify operations visually

2. Differential Power Analysis (DPA)​

  • Statistical attack using many traces

DPA Method​

  1. Collect many traces:

    T1,T2,…,TNT_1, T_2, \dots, T_N

  2. Guess key bits

  3. Partition traces into two sets:

  • Based on predicted intermediate value
  1. Compute averages:
μ0, μ1\mu_0,\ \mu_1
  1. Difference:
Δ=μ1−μ0\Delta = \mu_1 - \mu_0

➡ Significant bias ⇒ correct key guess

Insight​

  • Noise reduces with averaging
  • Signal (key-dependent) becomes visible

Application Example (DES)​

  • Target: S-box output
  • Guess subkey bits
  • Use power traces to validate guess

Fault Attacks​

Idea​

  • Inject faults during computation
  • Compare correct vs faulty outputs

Example:

  • Flip bit during encryption
  • Analyze difference

Why Smart Cards are Vulnerable​

  • Physical access possible

  • Measurable:

    • Power
    • Timing
    • EM signals

Countermeasures​

Against Timing Attacks​

  • Constant-time exponentiation
Always perform square and multiply\text{Always perform square and multiply}

Against Power Attacks​

  • Noise addition

  • Masking:

    x→x⊕rx \rightarrow x \oplus r

  • Randomized computation

Against Fault Attacks​

  • Redundant computation
  • Consistency checks

Randomization Defense​

  • Multiply intermediate values with random numbers

Example:

ab→(a⋅r)bmod  na^b \rightarrow (a \cdot r)^b \mod n

➡ hides correlation

Key Insight​

  • Security ≠ only math
  • Implementation leaks secrets

Summary​

  • Side-channel attacks exploit:

    • Time
    • Power
    • Physical behavior

  • DPA:

    Δ=μ1−μ0\Delta = \mu_1 - \mu_0

  • Defense:

    • Constant-time
    • Masking
    • Randomization
    • Fault detection

✔ Real-world cryptography must secure implementation + algorithm

TITLE

Lecture 59:
The Secure Sockets Layer (SSL)​

Goal​

  • Provide security above TCP layer

  • Used for:

    • Web security (HTTPS)
    • Secure client–server communication

Layered Structure​

Application Layer
↑
SSL/TLS Protocol
↑
TCP
↑
IP

Two Main Components​

1. Record Layer​

  • Provides:

    • Confidentiality
    • Integrity
    • Authentication

Record Layer Process​

  1. Fragment data
  2. (Optional) Compression
  3. Add MAC
  4. Encrypt
  5. Add Header

Record Format​

  • Header fields:
Type;∣∣;Version;∣∣;Length\text{Type} ;||; \text{Version} ;||; \text{Length}

  • Version:

    • Major (e.g. 3 for SSLv3)
    • Minor (e.g. 0)

MAC Computation​

MAC=H(K;∣∣;message)\text{MAC} = H(K ;||; \text{message})
  • Ensures integrity

2. Higher-Level Protocols​

(a) Handshake Protocol​

  • Establishes:

    • Keys
    • Algorithms
    • Authentication

Steps​

  1. Client Hello

    • Version
    • Random number
    • Session ID
    • Cipher suites

  2. Server Hello

    • Selected cipher suite
    • Random number

  3. Certificate Exchange

    • Server sends certificate (X.509)

  4. Key Exchange

    • Shared secret established

  5. Finished Messages

    • Verify handshake integrity

(b) Change Cipher Spec​

  • Signals:

    • Switch to encrypted communication

(c) Alert Protocol​

  • Handles:

    • Errors
    • Warnings

Cipher Suite​

Defines:

  • Key exchange (RSA, DH)
  • Encryption algorithm (AES, etc.)
  • Hash/MAC (SHA, etc.)

Security Features​

Confidentiality​

C=EK(M)C = E_K(M)

Integrity​

MAC(M)\text{MAC}(M)

Authentication​

  • Using certificates (X.509)

Certificates​

  • Issued by Certificate Authority (CA)
  • Bind identity to public key

Key Insight​

  • SSL works on top of TCP

  • Provides:

    • Secure channel
    • End-to-end protection

Summary​

  • Record Layer:

    • Fragment → MAC → Encrypt

  • Handshake:

    • Key exchange + authentication

  • Security:

    • Confidentiality
    • Integrity
    • Authentication

✔ Foundation of HTTPS and secure web communication

TITLE

Lecture 60:
Pretty Good Privacy (PGP)​

Core Idea​

  • Provides secure email communication

  • Combines:

    • Symmetric cryptography
    • Public-key cryptography
    • Hash functions

Key Features (5 Services)​

1. Authentication (Digital Signature)​

  • Ensures sender identity

Steps:

  1. Compute hash:

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

  2. Sign using private key:

    S=Epriv(h)S = E_{\text{priv}}(h)

  3. Send:

    (M,S)(M, S)

✔ Provides:

  • Integrity
  • Authentication
  • Non-repudiation

2. Confidentiality​

  • Uses hybrid encryption

Steps:

  1. Generate session key:

    Ks=randomK_s = \text{random}

  2. Encrypt message:

    C=EKs(M)C = E_{K_s}(M)

  3. Encrypt session key:

    Epub(Ks)E_{\text{pub}}(K_s)

  4. Send:

    (C, Epub(Ks))(C,\ E_{\text{pub}}(K_s))

✔ Efficient + secure

3. Compression​

  • Applied before encryption
M→Compress(M)M \rightarrow \text{Compress}(M)

✔ Benefits:

  • Reduces size
  • Improves encryption speed
  • Adds security (less redundancy)

4. Segmentation​

  • Large messages are split:
M=M1∣∣M2∣∣…∣∣MnM = M_1 || M_2 || \dots || M_n

✔ Needed due to:

  • Email size limits

5. Email Compatibility (Radix-64 Encoding)​

  • Converts binary → ASCII
Binary→Base64\text{Binary} \rightarrow \text{Base64}

✔ Ensures:

  • Safe transmission over email systems

Complete PGP Flow​

Sender Side​

  1. Message:

    MM

  2. Hash + Sign:

    S=Epriv(H(M))S = E_{\text{priv}}(H(M))

  3. Append:

    M∣∣SM || S

  4. Compress:

    Z=Compress(M∣∣S)Z = \text{Compress}(M || S)

  5. Encrypt (symmetric):

    C=EKs(Z)C = E_{K_s}(Z)

  6. Encrypt session key:

    Epub(Ks)E_{\text{pub}}(K_s)

  7. Encode (Radix-64)

Receiver Side​

  1. Decode
  2. Decrypt session key
  3. Decrypt message
  4. Decompress
  5. Verify signature

Algorithms Used​

  • Symmetric:

    • AES / IDEA / 3DES

  • Public Key:

    • RSA

  • Hash:

    • SHA family

Additional Components​

Key ID​

  • Identifies which public key to use

Timestamp​

  • Indicates message creation time
  • Free & widely available
  • Flexible algorithm choices
  • Strong security
  • Independent of specific algorithms

Key Insight​

  • Uses hybrid cryptography: Fast (symmetric)+Secure key exchange (public-key)\text{Fast (symmetric)} + \text{Secure key exchange (public-key)}

Summary​

  • Services:

    • Authentication
    • Confidentiality
    • Compression
    • Segmentation
    • Encoding

  • Core encryption:

    C=EKs(M),Ks→Epub(Ks)C = E_{K_s}(M),\quad K_s \rightarrow E_{\text{pub}}(K_s)

✔ Widely used for secure email systems