Years ago I remember Maxwell being very sniffy about the threshold ECDSA ideas that involved Paillier. There was a swathe of implementations in the last I guess, 6 years or so but, somehow I started reading some papers that were released since 2021 (links below) and realized .. it's kind of a shit show out there. The main protocols are the old Lindell one and GG18/GG20 ; they're using zk proofs and paillier to basically share keys for an ECDSA calculation. It is complex, and it doesn't "flow" as nicely as using one prime order group. An example: in one of the ZK proofs in GG18, you need to calculate a value t_1 = e * beta + gamma, where e is a typical fiat shamir hash, beta is the secret and gamma is a blinding factor. this looks very familiar right? (s = k + ex), but there's a vital detail: t_1 is *just an integer*, not an element of a finite field. Hence, even though e and beta might be values in a field of order N, let's say, then if you choose gamma to also be in that same 0..N-1 set, you've suddenly leaked the secret!
Why? Because e*beta is in the range 0..N^2, not 0..N. The way to exploit that is to just divide by e: t1/e = beta + gamma/e. And since gamma/e is less than 1 with probability 0.5, the right hand side is basically just beta!
This is one example, but others included improperly formed paillier public keys and absence of range proof checks, seen in implementations in the wild. Both Binance and Bitgo had the dubious privilege of being mentioned as having implementations that could leak the entire set of private keys in *one* signature - even covertly (i.e. the signing goes through). Not saying everything hasn't been fixed from these reports, but, sheesh.
https://eprint.iacr.org/2021/1621
https://eprint.iacr.org/2023/1234
https://eprint.iacr.org/2019/114
#cryptography
waxwing /
npub1va…knuu7
2024-12-07 17:12:47
Author Public Key
npub1vadcfln4ugt2h9ruwsuwu5vu5am4xaka7pw6m7axy79aqyhp6u5q9knuu7Published at
2024-12-07 17:12:47Event JSON
{
"id": "56769eb8518a434da7ef5ca9b1d663de8188bcbe7eee25efa1334b24bc0b0151",
"pubkey": "675b84fe75e216ab947c7438ee519ca7775376ddf05dadfba6278bd012e1d728",
"created_at": 1733591567,
"kind": 1,
"tags": [
[
"t",
"cryptography"
],
[
"r",
"https://eprint.iacr.org/2021/1621"
],
[
"r",
"https://eprint.iacr.org/2023/1234"
],
[
"r",
"https://eprint.iacr.org/2019/114"
]
],
"content": "Years ago I remember Maxwell being very sniffy about the threshold ECDSA ideas that involved Paillier. There was a swathe of implementations in the last I guess, 6 years or so but, somehow I started reading some papers that were released since 2021 (links below) and realized .. it's kind of a shit show out there. The main protocols are the old Lindell one and GG18/GG20 ; they're using zk proofs and paillier to basically share keys for an ECDSA calculation. It is complex, and it doesn't \"flow\" as nicely as using one prime order group. An example: in one of the ZK proofs in GG18, you need to calculate a value t_1 = e * beta + gamma, where e is a typical fiat shamir hash, beta is the secret and gamma is a blinding factor. this looks very familiar right? (s = k + ex), but there's a vital detail: t_1 is *just an integer*, not an element of a finite field. Hence, even though e and beta might be values in a field of order N, let's say, then if you choose gamma to also be in that same 0..N-1 set, you've suddenly leaked the secret!\n\nWhy? Because e*beta is in the range 0..N^2, not 0..N. The way to exploit that is to just divide by e: t1/e = beta + gamma/e. And since gamma/e is less than 1 with probability 0.5, the right hand side is basically just beta!\n\nThis is one example, but others included improperly formed paillier public keys and absence of range proof checks, seen in implementations in the wild. Both Binance and Bitgo had the dubious privilege of being mentioned as having implementations that could leak the entire set of private keys in *one* signature - even covertly (i.e. the signing goes through). Not saying everything hasn't been fixed from these reports, but, sheesh.\n\nhttps://eprint.iacr.org/2021/1621\n\nhttps://eprint.iacr.org/2023/1234\n\nhttps://eprint.iacr.org/2019/114\n\n#cryptography\n\n",
"sig": "ada042ae53f0f0b61ef4418422200925bdc61d822150d359e9d4f39294a1d56af7eeafacf50f4a5dff9c8fc9f621ed2288a05e3c553b7fa2f73f2b0d81750c7f"
}