Advanced Cryptography: PKI, Post-Quantum, Homomorphic Encryption & Zero-Knowledge

TAKEAWAYS:

• PKI Extensions: Understand how Certificate Revocation Lists (CRLs) and Online Certificate Status Protocol (OCSP) dynamically manage trust in digital certificates, critical for eSewa’s secure transactions.
• Post-Quantum Cryptography: Learn lattice-based and hash-based algorithms (e.g., Kyber, SPHINCS+) that resist quantum attacks, vital for Nepal’s Ncell’s future-proof encryption.
• Fully Homomorphic Encryption (FHE): Discover how computations can occur on encrypted data (e.g., Microsoft SEAL library) without decryption, enabling privacy-preserving cloud services like Daraz’s secure order processing.
• Zero-Knowledge Proofs (ZKPs): Master zk-SNARKs (used in Zcash) and zk-STARKs, which let users prove knowledge (e.g., age verification in Pathao) without revealing data.
• Blockchain Cryptography: Analyze Merkle trees, digital signatures, and consensus algorithms (PoW/PoS) powering NEPSE’s secure trading platform and global DeFi apps.
• Side-Channel Attacks: Learn how timing attacks and power analysis exploit physical implementations, and countermeasures like constant-time algorithms used in banking ATMs.

1. Public Key Infrastructure (PKI) Extensions: Beyond Certificates

PKI’s core (certificates, CAs) is extended to handle scalability, revocation, and interoperability in large-scale systems like eSewa or NEPSE.

Key Extensions

How OCSP Works (vs. CRL)

sequenceDiagram
    participant User
    participant Client
    participant OCSPResponder
    participant CA

    User->>Client: Requests secure connection (e.g., eSewa login).
    Client->>OCSPResponder: Sends certificate + serial number for OCSP request.
    OCSPResponder->>CA: Queries revocation status.
    CA-->>OCSPResponder: Returns "good" or "revoked" response.
    OCSPResponder-->>Client: Sends OCSP response (signed by CA).
    Client-->>User: Proceeds only if "good".

Worked Example: eSewa’s Certificate Revocation

• Scenario: A merchant’s private key is leaked. eSewa’s CA:
  1. Publishes the merchant’s certificate serial number in a CRL (daily update).
  2. Clients (users) download the CRL before processing payments.
  3. If the merchant’s cert is in the CRL, the transaction is blocked.
• OCSP Alternative: The user’s app queries OCSP in real-time:

  GET /ocsp?cert=merchant_cert&issuer=esewa_ca
  

  Response: good (proceed) or revoked (warn user).

2. Post-Quantum Cryptography (PQC): Defending Against Shor’s Algorithm

Quantum computers threaten RSA/ECC by solving integer factorization/logarithms in polynomial time. NIST’s PQC standardization (2022–2024) selects algorithms resistant to quantum attacks.

Top PQC Candidates

Why Lattice-Based?

• Hardness: No efficient quantum algorithm breaks lattice problems.
• Efficiency: Kyber-768 (post-quantum secure) is ~2x slower than ECDH but scalable.
• Hybrid Schemes: Combine PQC with ECC/RSA for backward compatibility (e.g., TLS 1.3 drafts).

Worked Example: Ncell’s Post-Quantum Key Exchange

• Current: Uses ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) for session keys.
• Future: Replaces ECDHE with Kyber-768 in its 5G network:
  1. Alice and Bob agree on a shared secret using Kyber’s module-LWE (Learning With Errors) problem.
  2. Even if a quantum computer intercepts the exchange, it cannot derive the secret.
  3. Ncell’s base stations use hybrid mode: Kyber for PQ security + ECDHE for legacy devices.

3. Fully Homomorphic Encryption (FHE): Computing on Encrypted Data

Definition: Allows computations on encrypted data without decryption. Introduced by Craig Gentry (2009).

How FHE Works

1. Bootstrapping: Refreshes encrypted data to correct noise accumulation.
2. Gate Evaluation: Computes logical operations (AND/OR) on ciphertexts.
3. Homomorphic Operations: Supports addition/multiplication (e.g., E(a + b) = E(a) + E(b)).

FHE in Practice

stateDiagram-v2
    [*] --> Encrypt: Data encrypted under FHE scheme
    Encrypt --> Compute: Server performs operations (e.g., SQL queries)
    Compute --> Decrypt: Client decrypts result
    Decrypt --> [*]

Real-World Example: Microsoft SEAL Library

• Use Case: Daraz wants to process orders without seeing customer data.
  1. Customer encrypts order details (e.g., E(quantity * price)) using SEAL.
  2. Daraz’s server computes E(total_cost) without decrypting.
  3. Result is sent back encrypted; customer decrypts locally.

Limitations:

• Overhead: 1000x slower than plaintext operations.
• Memory: Ciphertexts are ~100x larger than plaintext.
• Bootstrapping Cost: Dominates runtime (e.g., 10ms per operation).

4. Zero-Knowledge Proofs (ZKPs): Proving Without Revealing

Definition: A prover convinces a verifier of a statement’s truth without disclosing the statement itself.

Types of ZKPs

zk-SNARKs Workflow

sequenceDiagram
    participant Prover
    participant Verifier
    participant TrustedSetup

    TrustedSetup->>Prover: Generates proving/verifying keys.
    Prover->>Verifier: Sends proof (e.g., "I know a valid signature").
    Verifier->>Prover: Challenges with randomness.
    Prover->>Verifier: Returns succinct proof.
    Verifier->>Prover: Accepts if proof is valid.

Worked Example: Pathao’s Age Verification

• Problem: Drivers must prove they’re ≥18 without sharing IDs.
• Solution: zk-SNARK-based app:
  1. Driver’s phone generates a zero-knowledge proof of age (using a trusted setup).
  2. Pathao’s server verifies the proof without seeing the birth date.
  3. Only validity is checked (e.g., "This proof corresponds to age ≥18").

zk-STARKs Advantage:

• No Trusted Setup: Unlike zk-SNARKs, zk-STARKs don’t require secret parameters.
• Quantum-Resistant: Based on hash functions (e.g., SHA-256).

5. Blockchain Cryptography: Beyond Bitcoin

Blockchains rely on cryptographic primitives for security, decentralization, and immutability.

Key Techniques

Merkle Tree in NEPSE Trading

graph TD
    A["Root Hash"] --> B["Left Subtree"]
    A --> C["Right Subtree"]
    B --> D["Transaction 1"]
    B --> E["Transaction 2"]
    C --> F["Transaction 3"]
    C --> G["Transaction 4"]

• Use: A trader verifies their transaction is in a block by hashing their TX → parent → root.
• Efficiency: Only log(n) hashes needed to verify inclusion.

Worked Example: NEPSE’s Hybrid PoS

• Problem: Pure PoW is energy-intensive; pure PoS risks centralization.
• Solution: NEPSE uses PoS + BFT (Byzantine Fault Tolerance):
  1. Validators are chosen by stake weight (not mining power).
  2. Threshold signatures ensure no single validator can forge blocks.
  3. Merkleized directed acyclic graphs (MDAGs) improve scalability.

Bitcoin block header and transaction format (Image: Wargo, CC BY-SA 4.0, via Wikimedia Commons)

6. Side-Channel Attacks and Countermeasures

Definition: Exploit physical implementations (timing, power, EM leaks) rather than cryptographic weaknesses.

Attack Types

Worked Example: ATM Skimming via Power Analysis

• Attack:
  1. Criminal measures power spikes during PIN entry.
  2. Correlates spikes to key presses (e.g., higher power = ‘1’).
• Countermeasure: Constant-time AES ensures every S-box lookup takes the same time.

In the Real World

1. eSewa’s Hybrid PKI:

   • Uses OCSP stapling (pre-signed OCSP responses) to reduce latency in mobile payments.
   • Policy: Certificates expire every 90 days; Mechanism: Automated CRL updates via Let’s Encrypt-style ACME protocol.

2. Ncell’s 5G and Post-Quantum Migration:

   • Piloting Kyber-512 for IMS (IP Multimedia Subsystem) key exchange.
   • Real Scenario: A quantum hacker intercepts a call setup but cannot decrypt due to lattice-based KEM.

3. Daraz’s Privacy-Preserving Auctions:

   • Uses FHE to let sellers bid on inventory without revealing prices to Daraz’s servers.
   • Example: A seller encrypts E(price = 500 + 10% margin); Daraz computes E(winning_bid) without decryption.

4. Pathao’s zk-Identity:

   • Partners with ID.me to use zk-SNARKs for driver KYC, reducing fraud without storing PII.

5. NEPSE’s Blockchain Pilot:

   • Tests threshold ECDSA for multi-signature trade orders to prevent insider collusion.

Exam Tip

1. PKI Extensions:

   • Must-know: Differentiate CRL (periodic lists) vs. OCSP (real-time queries).
   • Scenario Question: "How would eSewa handle a revoked merchant certificate?" → Answer: OCSP stapling + CRL fallback.

2. Post-Quantum Cryptography:

   • NIST’s PQC Project: Memorize Kyber (KEM), Dilithium (signatures), and SPHINCS+ (hash-based).
   • Exam Trap: Don’t confuse lattice-based (Kyber) with hash-based (SPHINCS+).

3. FHE:

   • Key Point: "FHE enables privacy-preserving outsourced computation." Link to cloud security.
   • Weakness: Always mention performance overhead in answers.

4. ZKPs:

   • zk-SNARK vs. zk-STARK: SNARKs need a trusted setup; STARKs don’t.
   • Application: "How can Pathao verify age without seeing IDs?" → zk-SNARKs.

5. Blockchain:

   • Merkle Trees: Draw the structure and explain verification efficiency.
   • Consensus: Compare PoW (Bitcoin), PoS (Ethereum 2.0), and PBFT (NEPSE hybrid).

6. Side-Channel Attacks:

   • Countermeasures: Always pair attacks with fixes (e.g., timing attacks → constant-time code).
   • Real Example: "How would you secure an ATM from power analysis?" → Masking + blinding.

Pro Tip: For 6-mark questions, use the STAR method:

• Scenario (e.g., "eSewa’s payment system"),
• Technique (e.g., "OCSP stapling"),
• Advantage (e.g., "reduces latency"),
• Result (e.g., "95% faster verification").