ISE Cryptography — Quiz Solutions
L01: Introduction to Cryptography
10 questions · 1 mark each · 10 marks total.
Q01: Kerckhoffs’s Principle
Under Kerckhoffs’s Principle, the security of a cryptosystem must rest entirely on one component being kept secret from the adversary. Which component is it?
Answer:
The key.
Q02: Shannon cipher correctness
Let \(\mathcal{E} = (E, D)\) be a Shannon cipher defined over key space \(\mathcal{K}\), message space \(\mathcal{M}\), and ciphertext space \(\mathcal{C}\). Which equation expresses the correctness property of \(\mathcal{E}\)?
Answer:
\(D(k, E(k, m)) = m\) for all \(k \in \mathcal{K}\) and \(m \in \mathcal{M}\).
Q03: Uniform keys and the OTP
The proof that the one-time pad is perfectly secure relies on the key being sampled uniformly at random from \(\{0,1\}^L\). Suppose instead the key is drawn from a biased distribution where some keys are more likely than others. What specifically goes wrong in the proof of perfect security?
Answer:
Different plaintexts produce a given ciphertext with different probabilities, so observing the ciphertext reveals information about which plaintext was encrypted.
Q04: Why frequency analysis works
Frequency analysis is effective against simple substitution ciphers like the Caesar cipher. Which property of the plaintext distribution makes the attack possible in the first place?
Answer:
The plaintext is drawn from a low-entropy source in which some symbols are far more likely than others.
Q05: Many-time pad
Alice encrypts two different plaintexts \(m_1\) and \(m_2\) with the same one-time pad key \(k\), producing ciphertexts \(c_1\) and \(c_2\). Eve intercepts both ciphertexts but does not know \(k\). What can Eve compute from \(c_1\) and \(c_2\) alone?
Answer:
\(m_1 \oplus m_2\), because the keys cancel when the ciphertexts are combined.
Q06: OTP XOR computation
You are using the one-time pad on 8-bit messages. The key is \(k = 10110100\) and the plaintext is \(m = 01101001\). What is the ciphertext \(c = k \oplus m\)?
Answer:
\(11011101\)
Working: \(10110100 \oplus 01101001 = 11011101\).
Q07: Key length and perfect security
A Shannon cipher is defined over \((\mathcal{K}, \mathcal{M}, \mathcal{C})\) with \(\mathcal{K} = \{0,1\}^{80}\) and \(\mathcal{M} = \{0,1\}^{128}\). Based on what was proved in lecture, which statement is correct?
Answer:
It cannot be perfectly secure for these spaces, regardless of how \(E\) and \(D\) are defined.
Why: L01 proved that any perfectly secure Shannon cipher must satisfy \(|\mathcal{K}| \geq |\mathcal{M}|\). Here \(2^{80} < 2^{128}\), so the bound fails no matter how \(E\) and \(D\) are constructed.
Q08: Semantic security advantage
An adversary \(\mathcal{A}\) plays the semantic security attack game against a cipher \(\mathcal{E}\). Averaged over many rounds, \(\mathcal{A}\) correctly identifies the challenger’s chosen message 70% of the time. What is \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\)?
Answer:
\(0.4\)
Working: A win probability of 50% gives advantage 0 (pure guessing). A win probability of 100% gives advantage 1. The formula \(|2p - 1|\) fits both endpoints. Applying it: \(|2(0.70) - 1| = |0.40| = 0.40\). Equivalently, \(|\Pr[\text{correct}] - \Pr[\text{incorrect}]| = |0.70 - 0.30| = 0.40\).
Q09: Semantic security vs message recovery
A research group proves that no efficient adversary can recover the full plaintext from a ciphertext in fewer than \(2^{100}\) operations. Based on this proof alone, what can we conclude about the cipher’s semantic security?
Answer:
We cannot conclude whether it is semantically secure from this proof alone.
Why: Message-recovery hardness is necessary but not sufficient for semantic security. Semantic security requires that no adversary can distinguish encryptions of two chosen plaintexts; a cipher can resist full plaintext recovery while still leaking, say, the first bit of the message.
Q10: Shannon vs computational ciphers
Which of the following correctly describes the relationship between Shannon ciphers and computational ciphers as presented in the lecture?
Answer:
Every deterministic computational cipher is a Shannon cipher, but a probabilistic computational cipher need not be.