Bounded Noise

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-23 | Status: Solved Techniques: arora_ge_linearization, overdetermined_system_gf, quadratic_to_linear

Summary

Task: LWE instance with binary error e in {0,1}, n=25 secret variables, m=625 samples over GF(65537). Solution: Arora-Ge linearization — since e*(e-1)=0, each sample yields a quadratic equation in the secret; linearize all degree-2 monomials to get an overdetermined linear system with 351 variables and 625 equations, solve over GF(q).

Bounded Noise — CryptoHack (Post-Quantum / LWE)

Description

The Learning With Errors problem is hard because of the noise. What if we try to make the noise smaller?

Given an LWE instance with parameters:

• n = 25 (secret dimension)
• m = n² = 625 (number of samples)
• q = 65537 (prime modulus)
• e ∈ {0, 1} (binary error!)

The secret key is derived from the flag: the flag bytes are encoded as base-q digits of an integer, producing a 25-element vector over GF(q).

 python read-only • copy allowed Copy
A = random m×n matrix over GF(q)
e = random vector with entries in {0, 1}
b = A * secret + e

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

Standard LWE is hard because the error hides the linear relationship. But here the error is binary — it takes only values 0 or 1. This is the setting of the Arora-Ge attack (2011).

The key algebraic observation: for any e ∈ {0, 1}:

e * (e - 1) = 0

For each sample (a_i, b_i), the error is e_i = b_i - a_i · s. Substituting:

(b_i - a_i · s) * (b_i - a_i · s - 1) = 0   (mod q)

Expanding this gives a quadratic equation in the n = 25 secret variables s_1, ..., s_25. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

Linearization: Replace every degree-2 monomial s_j * s_k (for j ≤ k) with a fresh variable z_{j,k}. The number of linearized variables is:

C(25, 2) + 25 + 1 = 300 + 25 + 1 = 326 monomials

(Including the constant term, we get 326 monomials, but the system has 351 total linearized variables counting all degree-≤2 terms.)

With m = 625 equations and ~351 unknowns, the system is overdetermined. Solve it as a linear system over GF(q).

 python read-only • copy allowed Copy
#!/usr/bin/env sage
import json
from sage.all import *
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Load data
with open("output.txt") as f:
    data = json.load(f)

A_data = sage_eval(data["A"])
b_data = sage_eval(data["b"])

q = 65537
F = GF(q)
n = 25
m = n * n  # 625

A = Matrix(F, A_data)
b = vector(F, b_data)

# Build linearized system
# Monomials: 1, s_0, ..., s_{n-1}, s_0*s_0, s_0*s_1, ..., s_{n-1}*s_{n-1}
# Index mapping for degree-2 monomials
mono_idx = {}
idx = 0
# constant
mono_idx[(-1, -1)] = idx; idx += 1
# linear: s_j
for j in range(n):
    mono_idx[(j, -1)] = idx; idx += 1
# quadratic: s_j * s_k for j <= k
for j in range(n):
    for k in range(j, n):
        mono_idx[(j, k)] = idx; idx += 1
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

num_vars = idx  # 1 + 25 + 325 = 351

# For each sample: (b_i - a_i*s)(b_i - a_i*s - 1) = 0
# Expand: b_i^2 - b_i - (2*b_i - 1)*sum(a_ij*s_j) + sum_j sum_k a_ij*a_ik*s_j*s_k = 0
L = Matrix(F, m, num_vars)

for i in range(m):
    # Constant term: b_i^2 - b_i = b_i*(b_i - 1)
    L[i, mono_idx[(-1, -1)]] = b[i] * (b[i] - 1)

    # Linear terms: -(2*b_i - 1) * a_ij * s_j
    coeff_lin = -(2 * b[i] - 1)
    for j in range(n):
        L[i, mono_idx[(j, -1)]] = coeff_lin * A[i, j]

    # Quadratic terms: a_ij * a_ik * s_j * s_k
    for j in range(n):
        for k in range(j, n):
            val = A[i, j] * A[i, k]
            if j == k:
                L[i, mono_idx[(j, k)]] = val
            else:
                L[i, mono_idx[(j, k)]] = 2 * val  # s_j*s_k appears twice
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Solve L * z = 0 (homogeneous, but constant column is included)
# Rearrange: move constant column to RHS
rhs = -L.column(0)
coeff = L[:, 1:]
sol = coeff.solve_right(rhs)

# Extract secret from linear variables (indices 0..n-1 of sol)
secret = [int(sol[j]) for j in range(n)]

# Reconstruct flag
flag_int = 0
for i in range(len(secret) - 1, -1, -1):
    flag_int = flag_int * q + secret[i]

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(flag_int).decode())

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍