Why is syndrome decoding hard, and how does this enable encryption?
Think about your answer, then reveal below.
Model answer: Syndrome decoding is NP-hard: given a parity-check matrix H and syndrome s = H * e, recover the error vector e. This is hard for random codes because there are many possible error vectors. However, specific code structures (e.g., Goppa codes) have polynomial-time decoders. McEliece encryption hides a code with a known decoder: the private key is the code structure, the public key is a scrambled version of the parity-check matrix. Encryption adds random errors; the ciphertext is corrupted codeword + errors. Decoding requires the private code structure. An attacker sees only the scrambled matrix and must solve syndrome decoding (NP-hard).
The security relies on hiding structure in a random-looking matrix, exploiting the hard average case (random codes) while maintaining easy worst-case (known codes).
Question 2 Multiple Choice
What is the main practical disadvantage of code-based cryptography compared to RSA?
ACode-based schemes are slower to encrypt/decrypt
BCode-based schemes have much larger public keys (kilobytes vs. bytes)
CCode-based schemes are less secure than RSA
DCode-based schemes do not provide digital signatures
McEliece public keys are several kilobytes, while RSA keys are typically 256-512 bytes. This large key size is the main obstacle to adoption. Recent improvements reduce key size, but code-based schemes remain bulkier than classical cryptosystems. Decryption/encryption time is comparable, and digital signature schemes exist (CFS signatures, though slower). The post-quantum advantage (resistance to quantum attacks) justifies the overhead for applications where quantum threats are real.
Question 3 True / False
Why is code-based cryptography post-quantum secure?
TTrue
FFalse
Answer: True
The hardness of syndrome decoding (and the related Decoding Problem) has no known polynomial-time quantum algorithm. Grover's algorithm provides only quadratic speedup on brute-force search, which is insufficient to break the parameters used. Shor's algorithm (which breaks RSA, ECC) does not apply because syndrome decoding is not a hidden-structure problem like factoring/discrete log. This provides strong confidence (though not proof) that code-based schemes remain secure against quantum computers.