Mathematical Details

Notation Reference

LWE Definition

Two problems define LWE security:

LWE Key Generation

Security: Given $(pk = (\mathbf{A}, \mathbf{b}))$, recovering $sk = \mathbf{s}$ requires solving LWE. The error $\mathbf{e}$ is essential — without it, you'd have $\mathbf{b} = \mathbf{As}$ and solving for $\mathbf{s}$ is trivial (Gaussian elimination).

// LWE Key Generation (from our lwe.js)
function keyGen(n = 4, q = 97) {
  // Public matrix A: random entries mod q
  const A = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => randMod(q))
  );

  // Secret vector s: small values (centered binomial)
  const s = Array.from({ length: n }, () => mod(sampleError(2), q));

  // Error vector e from narrow distribution χ
  const e = Array.from({ length: n }, () => sampleError(1)); // |e_i| ≤ 1

  // b = A·s + e mod q  ← This is the LWE hard problem
  const As = matVecMulMod(A, s, q);  // matrix-vector multiply
  const b = As.map((v, i) => mod(v + e[i], q));

  return {
    publicKey: { A, b },   // (A, b) is public
    secretKey: s           // s is private
  };
}

LWE Encryption (Encapsulation)

The sender uses the receiver's public key to encapsulate a shared secret.

In our demo, we simplify to just $\mathbf{u} = \mathbf{A}^T\mathbf{r} + \mathbf{e}_1$ and derive the shared key directly from $K_A = \mathbf{b}^T\mathbf{r} \pmod{q}$, which captures the core LWE exchange logic.

// LWE Encapsulation (Sender side)
function encapsulate(publicKey, noiseBound = 1, n = 4, q = 97) {
  const { A, b } = publicKey;

  // Choose random r (small, like a one-time secret)
  const r = generateSecret(n, q);  // small values

  // Error vectors for encapsulation (adds security)
  const e1 = generateErrorVec(n, noiseBound);

  // Compute u = A^T · r + e1 mod q (ciphertext sent to Bob)
  const AT = transpose(A);
  const ATr = matVecMulMod(AT, r, q);
  const u = ATr.map((v, i) => mod(v + e1[i], q));

  // Alice's raw shared key: K_A = b^T · r (inner product)
  const kAlice = dotMod(b, r, q);

  return { ciphertext: u, rawSecret: kAlice };
}

LWE Decryption (Decapsulation)

So $K_B = K_A - \delta$. If the noise $|\delta| < q/4$, then rounding both $K_A$ and $K_B$ to the nearest multiple of $\lfloor q/4 \rfloor$ gives the same result. This is the reconciliation step.

// LWE Decapsulation (Receiver side)
function decapsulate(secretKey, ciphertext, q = 97) {
  // K_B = s^T · u mod q
  // When noise is small: K_B ≈ K_A ← the same key!
  const kBob = dotMod(secretKey, ciphertext, q);
  return kBob;
}

// Check correctness and derive key bytes
async function deriveKeyBytes(kAlice, kBob, q = 97) {
  const diff = Math.min(
    Math.abs(kAlice - kBob),
    q - Math.abs(kAlice - kBob)
  );
  const match = diff < Math.floor(q / 4);  // correctness bound!

  // Hash to get 32 uniform bytes (key derivation)
  const rounded = match ? round(kAlice) : kAlice;
  const buf = new TextEncoder().encode(`LWE_SECRET_${rounded}_q${q}`);
  const hashBuf = await crypto.subtle.digest('SHA-256', buf);

  return { match, difference: diff, keyBytes: new Uint8Array(hashBuf) };
}

Correctness Condition

For our demo parameters ($n=4, q=97$, errors in $\{-1,0,1\}$, secret in $\{0,1,2\}$):

Security Parameters

Full Source Code

The complete LWE implementation is in js/lwe.js. Key primitives:

// Correct modular reduction (handles negative numbers)
function mod(x, q) { return ((x % q) + q) % q; }

// Matrix-vector multiply mod q
function matVecMulMod(A, v, q) {
  return A.map(row =>
    mod(row.reduce((sum, a, j) => sum + a * v[j], 0), q)
  );
}

// Inner product mod q
function dotMod(a, b, q) {
  return mod(a.reduce((sum, x, i) => sum + x * b[i], 0), q);
}

// Sample from centered binomial distribution
// Models discrete Gaussian χ with parameter η
function sampleError(eta = 1) {
  let s = 0;
  for (let i = 0; i < 2 * eta; i++) {
    const arr = new Uint8Array(1);
    crypto.getRandomValues(arr);
    s += arr[0] & 1;   // uniform bit
  }
  return s - eta;  // center at 0: values in {-η, ..., η}
}
// E[sampleError] = 0, Var[sampleError] = η/2

// Hybrid key: SHA-256(ECDH_secret || LWE_secret || label)
async function deriveHybridKey(ecdhSecret, lweSecret) {
  const label = new TextEncoder().encode('HybridPQC-v1:ECDH+LWE');
  const material = concat(concat(ecdhSecret, lweSecret), label);

  const hashBuf = await crypto.subtle.digest('SHA-256', material);
  const hybridKeyBytes = new Uint8Array(hashBuf);

  // Import as AES-256-GCM key for direct use
  const aesKey = await crypto.subtle.importKey(
    'raw', hybridKeyBytes,
    { name: 'AES-GCM' }, false, ['encrypt', 'decrypt']
  );
  return { hybridKeyBytes, hybridKeyHex: toHex(hybridKeyBytes), aesKey };
}