Bounded Noise

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: arora_ge_linearization, overdetermined_system_gf, quadratic_to_linear

Summary

Walkthrough of the CUSTOM Crypto Bounded Noise. 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

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())

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

Key Takeaways / Lessons

• Mastering arora_ge_linearization, overdetermined_system_gf, quadratic_to_linear was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-23 • CUSTOM • Bounded Noise • Difficulty: Medium