Offensive Security Researcher & Quantum Cryptography Analyst

Niederreiter Algorithm: Working, Explanation, and Code-Based Cryptography

Abdul Wahab Junaid
Niederreiter algorithm and working of this algorithm

Niederreiter algorithm and working of this algorithm

I look at the Niederreiter cryptosystem as the lesser-known sibling of McEliece — both are built on error-correcting codes, but Niederreiter flips the encoding approach around, using a parity-check matrix instead of a generator matrix, and encoding messages as error patterns rather than as codewords. I find it especially relevant today because code-based cryptography, including Niederreiter’s construction, is one of the main families of algorithms being standardized for post-quantum cryptography, since it resists Shor’s algorithm in a way that RSA and ECC do not.

History and Background

I trace the Niederreiter cryptosystem to Harald Niederreiter’s 1986 paper, which proposed a knapsack-style, code-based public-key encryption and signature scheme as an alternative to the McEliece cryptosystem introduced eight years earlier, in 1978. Niederreiter’s original construction used generalized Reed-Solomon (GRS) codes, but that version was broken by Sidelnikov and Shestakov in 1992 because GRS codes have too much algebraic structure that leaks through the public key. The community responded by adapting Niederreiter’s approach to use binary Goppa codes instead — the same code family McEliece originally used — which has kept the scheme secure to this day. I find it notable that Niederreiter’s system was later proven by Li, Deng, and Wang in 1994 to be essentially equivalent in security to McEliece’s, despite looking quite different on the surface.

Problem Statement

I want a public-key encryption scheme whose security does not rely on integer factorization or discrete logarithms (both breakable by Shor’s algorithm on a quantum computer), but instead on a different hard problem: decoding a general linear code, which is known to be NP-hard in the worst case. I want to hide the structure of an efficiently-decodable code (like a Goppa code) behind random-looking transformations so that an attacker only sees what looks like a generic, hard-to-decode linear code.

Core Concepts

How It Works

I walk through key generation, encryption, and decryption:

  1. Key generation: Choose a binary Goppa code with parameters $[n, k, 2t+1]$ that has an efficient decoding algorithm correcting up to $t$ errors, and derive its $(n-k) \times n$ parity-check matrix $H$.
  2. Choose a random non-singular $(n-k) \times (n-k)$ matrix $S$ (a scrambler) and a random $n \times n$ permutation matrix $P$.
  3. Compute the public key as $\hat{H} = S \cdot H \cdot P$, which looks like a random parity-check matrix but secretly still corresponds to the efficiently-decodable Goppa code.
  4. The private key is the triple $(S, H, P)$ along with the Goppa code’s decoding algorithm.
  5. Encryption: To encrypt a message, first encode it as a length-$n$ binary vector $e$ of weight exactly $t$ (this is the key structural difference from McEliece — the message itself becomes the error pattern, not the plaintext bits directly).
  6. Compute the ciphertext as the syndrome $s = \hat{H} \cdot e^T$.
  7. Decryption: Compute $S^{-1} s = H P e^T$, then apply the efficient Goppa decoding algorithm to recover $P e^T$ (since $H$’s decoder can find the weight-$t$ error vector matching a given syndrome), then apply $P^{-1}$ to recover $e$, from which the original message is decoded.

Working Principle

I see the core trick as hiding an easy syndrome-decoding problem (correctable using the Goppa code’s efficient algorithm) inside what looks, to an outside observer, like a hard generic syndrome-decoding problem. The scrambler $S$ and permutation $P$ scramble the structure of $H$ enough that an attacker cannot recognize it as a Goppa code’s parity-check matrix, so they are forced to attempt to solve the syndrome decoding problem directly on $\hat H$, which for a random-looking matrix and appropriate parameters is computationally infeasible using known classical or quantum algorithms.

Mathematical Foundation

I define the public parity-check matrix as:

$$ \hat{H} = S \cdot H \cdot P $$

where $S \in \mathbb{F}_2^{(n-k)\times(n-k)}$ is invertible and $P \in \mathbb{F}_2^{n \times n}$ is a permutation matrix. Encryption of an error vector $e$ of Hamming weight $t$ is:

$$ s = \hat{H} e^T = S H P e^T $$

Decryption recovers the intermediate syndrome:

$$ S^{-1}s = H (P e^T) $$

The private Goppa decoder finds the unique weight-$t$ vector $e’ = Pe^T$ satisfying $H e’^T = S^{-1}s$, since Goppa codes guarantee unique decodability for weight $\leq t$ under the condition:

$$ t \leq \left\lfloor \frac{d-1}{2} \right\rfloor $$

where $d$ is the code’s minimum distance. Finally:

$$ e = P^{-1} e’ $$

recovers the original error pattern, which directly encodes the message. The overall security relies on the assumed hardness of the general syndrome decoding problem:

$$ \text{Given } \hat H, s: \text{ find } e \text{ with } \hat{H}e^T = s, \ \text{wt}(e) = t $$

which is NP-hard in general, and for well-chosen Goppa code parameters, has no known efficient classical or quantum algorithm.

Diagrams

flowchart TD
    K1[Select Goppa code with parity-check matrix H] --> K2[Choose random S and permutation P]
    K2 --> K3[Public key: H_hat = S * H * P]
    K3 --> E1[Encode message as weight-t vector e]
    E1 --> E2[Ciphertext s = H_hat * e^T]
    E2 --> D1[Compute S^-1 * s = H * P * e^T]
    D1 --> D2[Goppa decode to recover P*e^T]
    D2 --> D3[Apply P^-1 to recover e, then decode message]

Pseudocode

Function NiederreiterKeyGen(n, k, t):
    (H, decoder) = GenerateGoppaCode(n, k, t)      // parity-check matrix (n-k) x n
    S = RandomInvertibleMatrix(n-k, n-k)
    P = RandomPermutationMatrix(n)
    H_hat = S * H * P
    publicKey = H_hat
    privateKey = (S, H, P, decoder)
    return (publicKey, privateKey)

Function NiederreiterEncrypt(message, H_hat, n, t):
    e = EncodeAsWeightTVector(message, n, t)       // message -> length-n vector, weight t
    s = H_hat * transpose(e)
    return s

Function NiederreiterDecrypt(s, privateKey):
    (S, H, P, decoder) = privateKey
    s_prime = inverse(S) * s
    e_prime = decoder(H, s_prime)                  // find weight-t e' with H*e'^T = s_prime
    e = inverse(P) * e_prime
    message = DecodeFromWeightTVector(e)
    return message

Step-by-Step Example

I use a small toy example with $n=7$, $k=4$, $t=1$, based loosely on a Hamming-code-like parity-check structure (real Niederreiter uses Goppa codes, but a Hamming code illustrates the syndrome mechanics simply). Suppose the private parity-check matrix is:

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

I choose $S$ as a random invertible $3\times3$ matrix and $P$ as a permutation of the 7 columns, giving a scrambled public matrix $\hat H = SHP$. To encrypt, I represent my message as choosing which single position (since $t=1$) is “in error” — say position 5. My error vector is $e = 0000100$. Ciphertext is $s = \hat H e^T$, which is just the 5th column of $\hat H$. On the receiving end, the legitimate receiver computes $S^{-1}s$, recovering the 5th column of $H$ itself (after undoing $S$), and then a simple lookup (or syndrome decoding table for a Hamming code) tells them exactly which single column of $H$ matches, so they recover $Pe^T$, then apply $P^{-1}$ to identify position 5 as the true error location, decoding back the intended message value.

Time Complexity

I break the analysis into key generation, encryption, and decryption. Key generation requires constructing a Goppa code and computing matrix products, roughly $O(n^3)$ for the matrix multiplications involved (dominated by dense $(n-k)\times n$ by $n \times n$ multiplication). Encryption is a single matrix-vector multiplication:

$$ T_{\text{encrypt}} = O(n(n-k)) $$

Decryption dominates with the Goppa decoding algorithm (e.g., Patterson’s algorithm), which typically runs in:

$$ T_{\text{decrypt}} = O(n \cdot t) \text{ to } O(t^2 \log n) $$

depending on the exact decoding algorithm used, plus $O(n(n-k))$ for the initial matrix-vector multiplications to undo $S$ and $P$.

Space Complexity

I need to store the public key $\hat H$, an $(n-k) \times n$ binary matrix, requiring:

$$ S_{\text{public}} = O(n(n-k)) $$

bits. The private key needs $S$, $H$, and $P$, which together also take $O(n(n-k) + n^2)$ space. Niederreiter public keys tend to be somewhat smaller than McEliece’s generator-matrix-based public keys for comparable security, since only the parity-check matrix (not the full generator matrix) needs to be stored, though in some encodings the practical difference is modest.

Correctness Analysis

I consider the scheme correct because the Goppa decoding algorithm is guaranteed to uniquely recover any error vector of weight $t \leq \lfloor (d-1)/2 \rfloor$ from its syndrome, a well-established coding-theory result. Since encryption always produces error vectors of exactly weight $t$ within this bound, decryption using the correct private key always succeeds in recovering the exact original error pattern, and therefore the exact original message, with no probability of failure under the idealized assumptions (correct code parameters, no transmission errors beyond what the scheme already accounts for).

Advantages

Disadvantages

Applications

Implementation in C

I implement a simplified toy version using a small Hamming-like parity-check matrix (not a full Goppa code, which is significantly more involved) to demonstrate the syndrome encryption/decryption mechanics.

#include <stdio.h>
#include <string.h>

#define N 7   /* codeword length */
#define R 3   /* n - k, number of parity-check rows */

/* Toy parity-check matrix H (7,4) Hamming-like code */
int H[R][N] = {
    {1,0,0,1,1,0,1},
    {0,1,0,1,0,1,1},
    {0,0,1,0,1,1,1}
};

/* Compute syndrome s = H * e^T (mod 2) */
void compute_syndrome(int e[N], int s[R]) {
    for (int i = 0; i < R; i++) {
        s[i] = 0;
        for (int j = 0; j < N; j++) {
            s[i] ^= (H[i][j] & e[j]);
        }
    }
}

/* Decode: find which single column of H matches syndrome s (weight-1 error) */
int syndrome_decode(int s[R]) {
    for (int col = 0; col < N; col++) {
        int match = 1;
        for (int row = 0; row < R; row++) {
            if (H[row][col] != s[row]) {
                match = 0;
                break;
            }
        }
        if (match) return col; /* error position */
    }
    return -1; /* no single-error match found */
}

int main() {
    int e[N] = {0,0,0,0,1,0,0}; /* error/message at position 4 (0-indexed) */
    int s[R];

    /* Encryption: compute syndrome */
    compute_syndrome(e, s);
    printf("Ciphertext (syndrome): ");
    for (int i = 0; i < R; i++) printf("%d ", s[i]);
    printf("\n");

    /* Decryption: recover error position from syndrome */
    int pos = syndrome_decode(s);
    printf("Decrypted error position: %d\n", pos);
    printf("Recovered vector e: ");
    for (int i = 0; i < N; i++) printf("%d ", (i == pos) ? 1 : 0);
    printf("\n");

    return 0;
}

I keep the demonstration to a weight-1 error case for clarity; real Niederreiter implementations use Goppa codes and typically correct many errors ($t$ often in the dozens) using algebraic decoding algorithms rather than a brute-force column search.

Sample Input and Output

Ciphertext (syndrome): 1 0 1
Decrypted error position: 4
Recovered vector e: 0 0 0 0 1 0 0

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version