mirror of
https://github.com/luxfi/threshold.git
synced 2026-10-30 15:15:53 +00:00
Abhishek Krishna
9789bf63b1
Issue #20 (Threshold-FHE: replace fake partial-decrypt stub with real Lagrange-interpolated distributed decryption) is the goal; this PR is the precursor primitive — a big.Int sibling of the existing curve.Scalar Lagrange. It is the function the real CombineShares will call once the PartialDecrypt side lands. What this adds: LagrangeAtZeroBigInt(shares, modulus) -> p(0), error Returns p(0) where p is the polynomial of minimal degree passing through (x_i = bigEndianBytes(id_i) mod modulus, y_i = shares[id_i]) for every party.ID in shares. All arithmetic in F_modulus; modulus is expected prime (Lagrange combine requires modular inverses to exist). Error contract is explicit and deterministic: - empty shares - modulus <= 1 or nil - two party IDs reducing to the same x-coordinate (caught up front before any contribution is summed, so failures don't taint state) - zero denominator (x_j == x_i mod modulus) - non-invertible denominator (composite modulus path) Result is always canonicalized to 0 <= result < modulus. Why a big.Int sibling and not reuse the existing curve.Scalar version: the LWE/RLWE ciphertext modulus that TFHE decryption combines in is not an elliptic-curve scalar field — it's a ring/lattice modulus (the PN9QP28_STD128 set referenced in issue #20 uses 28-bit and 54-bit coefficient moduli). curve.Scalar can't represent those without shoehorning, and reusing it would conflate two distinct algebraic contexts in the same call site. Keeping them sibling functions in the same package matches the structure FROST / CMP already uses. Test coverage: - constant polynomial (every share == c → p(0) == c) - random degree-(t-1) polynomial, recover p(0) for (3,3), (3,5), and (11,21) thresholds; uses a near-2^64 prime for the (11,21) case to exercise the multi-word path - subset independence: two disjoint t-sized subsets of a (t,n) sharing recover the same secret - canonical range invariant (0 <= result < modulus) - empty shares, invalid modulus, duplicate x-coordinate error paths What this does NOT close: Issue #20 is fully closed only when protocols/tfhe/tfhe.go stops being an HMAC stub and PartialDecrypt produces real LWE partial-decryption shares. That's the PartialDecrypt side. This PR is the Combine side — the math the real CombineShares will call. They can land independently; the Combine is testable in isolation against a hand-rolled polynomial, which is what the test file does. Refs: - issue #20 (this repo) - LP-137 (TFHE Real Threshold Spec, referenced in protocols/tfhe/tfhe.go header) - LP-181 Magnetar (prerequisite chain per project memory) - luxfi/fhe PR #21 (prior art, closed; partial-decrypt API shape)