Exercises: Chapter 30 — Quantum Cryptography and Post-Quantum Security

Exercise 30.1: LWE Parameter Sensitivity

Modify the LWE encryption code above to explore the relationship between noise parameter $\sigma$ and decryption error rate. Plot error rate vs. $\sigma$ for $\sigma \in \{1, 2, 3, 4, 5, 6\}$. At what $\sigma$ does the scheme become unusable? Explain why. Derive an approximate formula for the decryption error probability as a function of $\sigma$, $n$, and $q$.

Exercise 30.2: BB84 with a Beamsplitter Attack

Extend the BB84 simulation to model a beamsplitter attack, where Eve taps a fraction $\eta$ of each photon. Derive the relationship between $\eta$ and the induced QBER. Implement this in Qiskit and verify your derivation for $\eta \in \{0.1, 0.3, 0.5\}$. What is the maximum $\eta$ that Eve can use without exceeding the 11% QBER threshold?

Exercise 30.3: Hybrid Key Exchange

Implement a simplified hybrid key exchange in Python that combines a classical Diffie-Hellman key exchange (using cryptography library) with the LWE encryption from this chapter. The final shared secret should be SHA-256(DH_shared || LWE_shared). Explain why this construction is secure if either DH or LWE remains unbroken. What happens if both are broken simultaneously?

Exercise 30.4: Lamport Signature Implementation

Implement a complete Lamport one-time signature scheme using SHA-256 in Python. Generate keys, sign a 256-bit message, verify the signature, and demonstrate that signing a second message compromises security. Measure the key and signature sizes. How many Lamport signatures can a Merkle tree of height $h = 20$ support?

Exercise 30.5: Migration Planning

You are the CISO of a healthcare organization that stores patient records with a 50-year retention requirement. Your systems use RSA-2048 for TLS, ECDSA for code signing, and AES-256 for data at rest. Write a 1-page migration plan addressing: (a) which systems need immediate attention, (b) which PQC algorithms you would adopt and why, (c) how you would handle the transition without disrupting operations, and (d) how you would address the "harvest now, decrypt later" threat for data already transmitted.

Exercise 30.6: Shor's Algorithm Resource Estimation

Estimate the number of logical and physical qubits required to break RSA-2048 using Shor's algorithm. Assume: (a) 4,000 logical qubits, (b) surface code with distance $d = 27$ (requires $2d^2$ physical qubits per logical qubit), (c) physical gate error rate $p = 10^{-4}$. What is the total number of physical qubits? If each physical qubit requires $1\ \text{mm}^2$ of chip area, what is the total chip area? How does this compare to current superconducting quantum processors?

Exercise 30.7: Privacy Amplification

In BB84, after sifting, Alice and Bob share $n$ bits with QBER $\epsilon$. Privacy amplification compresses these to $k < n$ bits using a universal hash function, reducing Eve's information from $I_{\text{Eve}} = nh(\epsilon)$ to at most $2^{-s}$ where $s = n - k - I_{\text{Eve}}$. For $n = 10{,}000$ and $\epsilon = 0.05$, calculate: (a) the maximum key length $k$ for $s = 80$ bits of security, (b) the key generation rate (bits per sifted bit), and (c) the effective key rate if the initial key rate is 1 Mbps.

Exercise 30.8: McEliece Encryption

Implement a toy McEliece encryption system using a $[7, 4, 3]$ Hamming code. The generator matrix $G$ for the Hamming code is:

$$G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$$

Encrypt a 4-bit message $m = (1, 0, 1, 1)$ by computing $c = mG + e$ where $e$ is a random error vector of weight $t = 1$. Decode $c$ using the Hamming code's parity-check matrix to recover $m$. How many errors can the code correct? What happens if $t = 2$?

Exercise 30.9: QBER Threshold Calculation

Derive the BB84 QBER threshold of 11% from the condition that the secret key rate is positive. The secret key rate is $r = 1 - 2h(\epsilon)$ (where $h$ is the binary entropy function and $\epsilon$ is the QBER). Find the critical QBER $\epsilon_c$ where $r = 0$. How does this threshold change if Eve performs the optimal individual attack rather than intercept-resend?

Exercise 30.10: SIKE Attack Analysis

The Castryck-Decru attack on SIKE used Kani's theorem to reduce the isogeny problem to a discrete logarithm problem on a related curve. Research the attack and explain: (a) why the attack is polynomial-time (what mathematical structure does it exploit?), (b) what specific assumption about supersingular isogenies was broken, and (c) what lessons the PQC community should draw from this break. How does this compare to other PQC algorithm breaks (e.g., Rainbow, GeMSS)?