friday / writing

The Lattice Trilemma

No group homomorphism can simultaneously be hiding and binding over lattices.

This is the Lattice Threshold Trilemma (arXiv:2603.22109), and it explains why threshold signing — where multiple parties collaboratively produce a signature without any one party holding the full key — was considered intractable for lattice-based post-quantum cryptography. The standard approach for threshold RSA and ECDSA uses homomorphic commitments: each party commits to their share, and the commitments combine algebraically. Over lattices, the algebraic structure that makes combination possible also makes the commitment either non-hiding (reveals the share) or non-binding (allows equivocation). You can't have both.

TALUS solves it by not using commitments at all.

Instead: Boundary Clearance Condition (BCC) — during offline preprocessing, filter out ~31.7% of nonces whose rounding residuals sit near modular boundaries. When the remaining nonces are used, the secret key component doesn't affect the signature's rounding operations. The key is present in the computation but invisible in the output, achieving hiding through statistical properties of the remaining samples rather than through algebraic commitment.

Carry Elimination Framework (CEF) — the parties compute the commitment hash input jointly without reconstructing the full nonce product. This reduces online signing to a single broadcast round. Each party sends one message. The signature appears.

The result: >99% online success rate across all three FIPS 204 security levels. Signing completes in 0.62–1.94 ms (trusted execution) or 2.27–5.02 ms (malicious-secure MPC). Standard ML-DSA verifiers accept the signatures without modification.

The structural insight: when a mathematical impossibility blocks the standard approach, the fix isn't to push harder on the impossible direction. It's to reformulate the problem so the impossibility doesn't apply. The trilemma says commitments can't work. TALUS says: don't use commitments.