Code-Based Cryptography

Core Idea

Code-based cryptography constructs public-key encryption and signatures from error-correcting codes. The most famous is McEliece encryption, which hides a systematic error-correcting code as a random matrix. Encryption adds random errors; decryption uses the hidden code structure to correct errors and recover the message. Code-based schemes are post-quantum secure: no known polynomial-time quantum algorithms break them, and the underlying problem (syndrome decoding) is NP-hard. Challenges include large public keys and ciphertexts, but recent improvements (quasi-dyadic codes, rank metrics) reduce overhead. Code-based cryptography is standardized (NIST lattice-based competition) and increasingly deployed.

Explainer

Code-based cryptography provides an alternative to number-theoretic assumptions (RSA, discrete log, elliptic curves). It is grounded in coding theory, with security reduced to the hardness of syndrome decoding. This geometric perspective on cryptography offers both theoretical and practical advantages.

McEliece Cryptosystem: (1) Privately choose an [n, k] error-correcting code with efficient decoder (e.g., Goppa code). (2) Compute parity-check matrix H. (3) Scramble H with invertible matrices to create public key H'. (4) Encryption: choose message m (k bits), compute ciphertext c = m * G' + e (where G' is generator from H', e is random error). (5) Decryption: use private code decoder to correct e and recover m.

Security: An attacker sees H' and ciphertexts c. To decrypt, must recover e from c and H' (syndrome decoding), which is NP-hard for random codes.

Post-Quantum Security: No known polynomial-time quantum algorithms solve syndrome decoding. Grover's algorithm provides only quadratic speedup (1/2 exponent reduction), insufficient to break parameters.

Challenges:

• Large public keys (kilobytes vs. RSA's hundreds of bytes).
• Large ciphertexts (overhead from error correction).
• Slow encryption/decryption (matrix-vector operations over finite fields).

Optimizations:

• Quasi-dyadic codes: structured codes reducing key size to kilobytes.
• Rank-metric codes: exploit rank over finite fields; smaller parameters.
• Hybrid schemes: combine code-based with other PQC for smaller keys.

Code-based cryptography is a leading post-quantum candidate, with implementations now available and potential for wider deployment as quantum computing approaches.