SHAMIR SECRET SPILLING

crypto

---

Challenge

A Shamir secret-sharing scheme hands out 16 clean shares of a degree-15 polynomial P(x) (whose constant term is the flag) plus 24 more shares that are supposed to lie on the same polynomial but are actually evaluations of a slightly different polynomial Q(x), each perturbed by a small unknown error. Since the errors are small (bounded by a known constant B) relative to the field modulus, this is a polynomial-reconstruction-with-errors problem — solvable with lattice reduction instead of guessing.

Solution

Fully interpolate P(x) from the 16 clean points via Lagrange interpolation. For each noisy point, evaluate P there and subtract to get a sample of the error polynomial E(x) = Q(x) - P(x), which is zero at the 16 clean x-coordinates and small-but-nonzero at the 24 noisy ones. Interpolate a base solution E0(x) satisfying all 40 points, then build a lattice whose rows encode: modulus-reduction freedom at each of the 24 noisy points, multiples of the vanishing polynomial Z24(x) (which is zero at exactly those 24 points, so its multiples don't disturb them), and the affine shift E0(x) weighted by the known error bound B. Running LLL on that lattice surfaces the one short vector representing the true, small error term at each point:

M = [[0] * dim for _ in range(dim)]
row = 0
for i in range(24):                       # modulus-reduction rows
    M[row][i] = MOD; row += 1
for i in range(8):                        # Z24(x) multiples
    for j in range(len(Z24_coeffs)):
        if i + j < 32: M[row][i + j] = Z24_coeffs[j]
    row += 1
for i in range(32):                       # affine shift, weighted by B
    M[row][i] = E0_coeffs[i]
M[row][32] = B

reduced = ddm_lll(DomainMatrix(M, (dim, dim), ZZ).rep)
for r in reduced:
    if abs(r[32]) == B:
        e0 = r[0] if r[32] == B else -r[0]
        q0 = (P_coeffs[0] + e0) % MOD
        flag = long_to_bytes(int(q0))

The recovered short vector's first coordinate is the true error on the constant term; adding it back to P(x)'s constant term recovers the flag directly.