This is way above my paygrade, but I find this stuff interesting and forcing myself to write about it sometimes helps me improve my understanding of these things a little.

In the quest to achieve quantum resistance, one sort of signature that people are developing is lattice-based signatures. Blockstream had a nice write up about these sorts of signatures recently - #1492552.

While the conversation about quantum often remains at the "burn or steal" level, there are many things to consider in any move from elliptic-curve cryptography to something else: for instance, some of the properties of bitcoin on which we have come to rely turn out to not work so well (or at least, not work the same) with some quantum-resistant cryptographic schemes.

Here's an example:

One of the properties of lattice-based signatures is that they might leak your key:

If an attacker looks at enough of your signatures, they will notice this statistical shift and potentially compromise the secret key.

To solve this many lattice-based protocols do something called rejection sampling, which looks like this:

After the signer generates the signature z, they check to see if the addition of the secret key shifted the value too much. If the signature looks "biased" and risks leaking the key (as in the Figure above), they simply throw it away and try again with a new random number. This process is repeated several times until the resultant signature perfectly masks the secret key (shown by the dashed line in the Figure above).

The result is that a signer will generate a signature and check to see if it leaks meaningful information about your private key. If it does, then it tries to generate a new signature. In the case where you are using a multisignature, this might be awkward. It is especially so if the signature you are creating is supposed to have the property that it doesn't look like a multisignature.

So, here comes this Trilithium thing. It seems to be a protocol for making shares out of a key for lattice-based signatures.

In this paper, we present Trilithium: a protocol for distributed key generation and signing compliant with FIPS 204 (ML-DSA). Our protocol allows two parties, “server” and “phone” with assistance of correlated randomness provider (CRP) to produce a standard ML-DSA signature. We prove our protocol to be secure against a malicious server or phone in the universal composability model, introducing some novel techniques to argue the security of two-party secure computation protocols with active security against one party, but only active privacy against the other. We provide an implementation of our protocol in Rust and benchmark it, showing the practicality of the protocol. As additional contribution, we propose an actively secure generalization of Attrapadung et al. (ASIA CCS ’22) comparison protocol and a new rounding protocol for fractions with private numerator.

Seems cool!

h/t to arbed_out on X.