Draft:LNQC Post Quantum Cryptography

• Comment: There's no third-party, independent evaluation/research of this standard that we can find online, evident by how you published the npm 4 hours before this review... nhals8 (rats in the house of the dead) 12:35, 25 May 2026 (UTC)

LNQC Post Quantum Cryptography (PQC) is a family of post-quantum key encapsulation mechanisms (KEMs) whose security reduces to the hardness of the fixed-weight Learning Parity with Noise (LPN) problem over the binary field GF(2). Developed under Project LNQC by Sami Mirqulaja at Lanit Labs, the scheme restricts all cryptographic operations to constant-time binary matrix algebra, providing architectural immunity to timing and power analysis side-channel attacks without requiring masking or shuffling countermeasures. LNQC is offered in three security tiers (LNQC-256, LNQC-512, LNQC-714) and is implemented in Rust with WebAssembly (WASM) bindings, published as the npm package @lanitlabs/pqc-lnqc714.^{[1] [2]}

The advent of large-scale quantum computers threatens classical public-key cryptography through Shor's algorithm,^[3] which solves integer factorization and discrete logarithm problems in polynomial time, rendering RSA, ECDSA, and ECDH obsolete. In response, the U.S. National Institute of Standards and Technology (NIST) has standardized lattice-based schemes including ML-KEM (FIPS 203)^[4] based on Module-LWE over polynomial rings. Most NIST candidates require modular arithmetic with rejection sampling, introducing potential side-channel leakage vectors.

LNQC takes an alternative approach grounded in the LPN problem over GF(2), a strictly simpler algebraic structure whose best known quantum attack remains super-polynomial.

The Learning Parity with Noise (LPN) problem asks an attacker to recover a secret vector s given a random binary matrix A and a noisy vector t = As + e (modulo 2), where e is a sparse error vector with exactly w non-zero bits. The problem is NP-hard in its worst-case formulation^[5] and is believed to resist quantum algorithms, as its binary structure provides no multiplicative group for Shor's period-finding technique.

The best known classical attack, the Blum–Kalai–Wasserman (BKW) algorithm,^[6] reduces the dimension of s by iteratively finding linear combinations of samples that cancel blocks of coordinates at the cost of amplifying the noise rate. For the LNQC-512 tier, BKW requires more samples than the available budget to reduce the secret below half its original dimension before the accumulated noise becomes destructive, placing the scheme beyond BKW's practical reach.^[1]

The Learning With Errors (LWE) problem, introduced by Regev,^[7] operates over larger moduli and admits a worst-case hardness reduction from lattice problems. LPN can be viewed as LWE over GF(2), with the compromise that no worst-case-to-average-case reduction is known for binary LPN. However, LNQC's fixed-weight noise model provides stronger concrete security than Bernoulli noise of equivalent density, and the GF(2) arithmetic enables the constant-time guarantee that is the scheme's principal architectural advantage.

Unlike lattice-based schemes, LNQC restricts all cryptographic operations to binary matrix–vector products modulo 2:

• Key generation: ${\displaystyle \mathbf {t} =\mathbf {A} \mathbf {s} \oplus \mathbf {e} }${\displaystyle \mathbf {t} =\mathbf {A} \mathbf {s} \oplus \mathbf {e} }
• Encapsulation: ${\displaystyle \mathbf {U} =\mathbf {R} \mathbf {A} {\pmod {2}}}${\displaystyle \mathbf {U} =\mathbf {R} \mathbf {A} {\pmod {2}}}, ${\displaystyle \mathbf {V} =\mathbf {R} \mathbf {t} \oplus \mathbf {c} }${\displaystyle \mathbf {V} =\mathbf {R} \mathbf {t} \oplus \mathbf {c} }
• Decapsulation: ${\displaystyle {\tilde {\mathbf {c} }}=\mathbf {V} \oplus \mathbf {U} \mathbf {s} {\pmod {2}}}${\displaystyle {\tilde {\mathbf {c} }}=\mathbf {V} \oplus \mathbf {U} \mathbf {s} {\pmod {2}}}

All operations use only XOR and AND gates on binary vectors, producing no data-dependent branching or variable-time arithmetic. The Gallager bit-flipping decoder is bounded at a fixed maximum iteration count (200) regardless of syndrome weight, eliminating early-exit timing variation.^[1]

LNQC defines three security tiers, each with equal LPN dimension and sample count (n = m) but differing noise weights and LDPC parameters:

Each tier includes a Low-Density Parity-Check (LDPC) code constructed as a systematic linear code with a generator matrix derived from a regular parity-check matrix with a uniform column weight of 15. The systematic construction allows direct extraction of the shared secret from the first K positions of any valid codeword without additional decoding steps.

During decapsulation, a Gallager bit-flipping decoder^[8] iteratively corrects the residual LPN noise. Each iteration computes the syndrome, counts failed parity checks per bit, and flips bits with the maximum failure count. The decoder runs for up to 200 iterations and achieves a 0% decryption failure rate across test trials.^[1]

All randomness for key material, noise vectors, and ephemeral matrices is drawn from operating system entropy sources via getrandom (Linux getrandom syscall, Windows BCryptGenRandom, or browser crypto.getRandomValues). The LDPC construction uses a deterministic Xorshift64 PRNG seeded from the OS entropy pool, used only for LDPC matrix construction, never for security-critical key or ephemeral noise generation.^[2]

Input

Security parameters n, m, w (per-tier)

Output

Public key pk = (A, t), private key sk = s

1. Sample matrix A via an OS-seeded CSPRNG.
2. Sample vector s via an OS-seeded CSPRNG.
3. Generate a sparse noise vector e with exactly w non-zero entries by sampling w distinct indices without replacement.
4. Compute ${\displaystyle \mathbf {t} =(\mathbf {A} \mathbf {s} +\mathbf {e} ){\bmod {2}}}${\displaystyle \mathbf {t} =(\mathbf {A} \mathbf {s} +\mathbf {e} ){\bmod {2}}}.
5. Return pk = (A, t), sk = s.

Input

Public key pk = (A, t), message m

Output

Ciphertext ct = (U, V)

1. Encode the message into an LDPC codeword: ${\displaystyle \mathbf {c} =\mathbf {m} \cdot \mathbf {G} {\pmod {2}}}${\displaystyle \mathbf {c} =\mathbf {m} \cdot \mathbf {G} {\pmod {2}}}.
2. Sample an ephemeral matrix R with each row having exactly w non-zero entries.
3. Compute ${\displaystyle \mathbf {U} =(\mathbf {R} \mathbf {A} ){\bmod {2}}}${\displaystyle \mathbf {U} =(\mathbf {R} \mathbf {A} ){\bmod {2}}}.
4. Compute ${\displaystyle \mathbf {V} =(\mathbf {R} \mathbf {t} +\mathbf {c} ){\bmod {2}}}${\displaystyle \mathbf {V} =(\mathbf {R} \mathbf {t} +\mathbf {c} ){\bmod {2}}}.
5. Return ct = (U, V).

Input

Private key sk = s, ciphertext ct = (U, V)

Output

Recovered message m'

1. Compute the noisy codeword: ${\displaystyle \mathbf {r} =(\mathbf {V} -\mathbf {U} \mathbf {s} ){\bmod {2}}}${\displaystyle \mathbf {r} =(\mathbf {V} -\mathbf {U} \mathbf {s} ){\bmod {2}}}.
2. Set a temporary vector to equal r.
3. Loop for a maximum of 200 iterations:
   • Compute the syndrome. If the syndrome weight is zero, break the loop.
   • For each bit, count the failed parity checks.
   • Find the maximum failure count. If it is zero, break the loop.
   • Flip the bits that match the maximum failure count.
4. Extract the systematic message from the first K positions of the decoded vector.
5. Return m'.

LNQC is IND-CPA secure under the LPN hardness assumption. The public key (A, t) is a single LPN sample; by assumption, it is computationally indistinguishable from a uniform random pair. In the challenge ciphertext, the vector V is protected by Rt. Because the public key is pseudorandom, applying the Leftover Hash Lemma to the sparse matrix R makes Rt statistically close to uniform, rendering V information-theoretically independent of the message state.^[1]

All operations are binary dot-products, bit flips, and index sampling with no data-dependent branches. Execution time is invariant to all input values, eliminating timing, cache, and power leakage by construction.

• Bandwidth efficiency: Public key and ciphertext sizes are orders of magnitude larger than lattice-based alternatives, making LNQC unsuitable for bandwidth-constrained applications like standard TLS handshakes.
• No worst-case reduction: Unlike LWE, binary LPN lacks a worst-case-to-average-case reduction. Security arguments are based on concrete analysis of known attacks.
• Deployment state: The scheme currently provides IND-CPA security, with a Fujisaki-Okamoto transform upgrade required to achieve IND-CCA2 compliance.

• Learning Parity with Noise
• Low-density parity-check code
• Post-quantum cryptography
• Learning with errors