Integer polynomial shares leak the constant term

A polynomial’s degree does not determine secrecy by itself. Arithmetic domain, sampling distribution, and allowed evaluation points are equally important. A threshold argument proved over a finite field cannot be applied unchanged to an oracle returning unrestricted integer evaluations.

Research anchor and scope

Jorian Woltjer’s MSS analysis studies a degree-30 integer polynomial with a 256-bit constant, at most 19 queries, and a positive input cap of 2^15. The first version accepted arbitrarily negative inputs; the revised version added a lower bound but retained integer-residue leakage. The source’s explanatory zero-input line should not be adopted: with the displayed Python polynomial, 0**0 is 1, so evaluation at zero returns the constant.

Separate algebra from implementation

Write an oracle as P(x) = c0 + c1*x + ... + cd*x^d. Over the integers, every nonconstant term is divisible by x, therefore P(x) mod |x| = c0 mod |x| for any nonzero integer input. This statement is independent of the polynomial degree and does not require interpolation.

A toy polynomial P(x) = 23 + 9*x + 4*x^2 gives P(5)=168 and P(7)=282. Reducing the answers gives residues 3 modulo 5 and 2 modulo 7. CRT yields 23 modulo 35. If the constant is known to be smaller than 35, it is fully determined from two evaluations even though the quadratic has three coefficients.

Plan around the information budget

Choose pairwise coprime admissible inputs and track the product of their moduli. The constant becomes unique within a known interval only when that product covers the interval. Large admissible primes are a convenient choice, but primality itself is not essential; coprimality is. If inputs overlap in factors, compute the least common multiple and compatibility conditions instead of multiplying every input blindly.

For a negative-input bypass, reduce by the positive absolute value of the input. Programming languages disagree about remainder signs. A modulus larger than the coefficient’s bound makes its residue equal to the coefficient; visual digit separation is unnecessary. Check output-size limits and parser limits before assuming a huge evaluation will be returned intact.

Recognition and limits

Look for a scheme named after a familiar cryptographic construction that omits its field modulus. Trace the arithmetic through serialization: a bounded integer, a floating-point conversion, or an implicit field reduction changes the oracle. Proper Shamir sharing evaluates a uniformly sampled polynomial over a specified finite field at distinct nonzero coordinates; reducing its already reduced output modulo the input coordinate does not reproduce this leakage. Query restrictions alone cannot restore that missing domain assumption.