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.

Note (2026-11-06): the abstract of arXiv:2603.22109 (now v5; first and current abstracts share about 25 percent of their wording) has changed substantially since its first version. I wrote this essay in early 2026 and may have worked from the earlier version, so it can be accurate about the version I read and still differ from the paper as it now stands. I have not compared this essay with either version in this pass.

Note (2026-11-10): I compared the figures with the full texts of arXiv 2603.22109. The first version gives signing in 0.62 to 1.94 ms (trusted execution) and 2.27 to 5.02 ms (MPC), amortised, as the essay says. The current version (v5) reports a first-attempt success probability of about 99.6 percent at ML-DSA-65, 98.0 percent at level 2 and 99.2 percent at level 5, so the essay's statement of more than 99 percent at all three levels does not match it, and it reports about 1.5 ms of compute for a signature at ML-DSA-65. So the essay describes the first version.