📅 Original date posted:2018-11-28
📝 Original message:On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote:
> Are there any candidates for non-interactive threshold signatures? Interactive
> signatures are not very suitable for air-gapped use cases.
I think you can work around this to some extent by "batching" signing
requests.
(Background:
For interactive multisignatures (threshold or not), the protocol is:
produce secret nonce r, calculate public nonce R=r*G
everyone shares H(R)
everyone shares R, checks received values match received hashes
everyone calculates s=r+H(R',P',m)*p, shares s
For deterministic nonces, you generate r=H(p,m) based on the message
being signed and your private key, so can only start this process when
you start signing, and the sharing rounds mean interactivity.
)
But you don't strictly need deterministic nonces, you just have to never
use the same nonce with a different message. If you arrange to do that
by keeping some state instead, you can calculate nonces in advance:
phase 1:
produce secret nonces r1..r1024, calculate R1..R1024
share H(R1)..H(R1024)
phase 2:
store other parties hashes, eg as H1..H1024
share R1..R1024
phase 3:
check received nonces match, ie H(R1)=H1, etc
phase 4:
request to sign msg m, with nonce n
if nonce n has already been used, abort
mark nonce n as having being used
lookup other signer's nonces n and sum them to get R'
calculate s = rn + H(R',P',m)*p
share s
That way you could do phases 1-3 once, and then do 1024 signatures during
the month on whatever your current timetable is.
You could also combine these phases, so when you get a signing request you:
* receive msg to sign m, n=4; everyone else's R4, H(R5)
* check H(R4) = previously received "H(R4)"
* calculate R4' by summing up your and everyone's R4s
* bump state to n=5
* do the signature...
* send sig=(s,R4), R5, H(R6)
which would let you have an untrusted app that does the coordination and
shares the nonces and nonce-hashes, and getting all the needed air-gapped
communication in a single round. (This is effectively doing phase 3 and
4 for the current signature, phase 2 for the next signature, and phase
1 for the signature after that all in one round of communication)
That seems almost as good as true non-interactivity to me, if your signing
hardware is capable of securely storing (and updating) a few kB of state
(which is probably not quite as easy as it sounds).
Cheers,
aj
Anthony Towns [ARCHIVE] /
npub17r…x9l2h
2023-06-07 18:15:23
in reply to nevent1q…xldx
Author Public Key
npub17rld56k4365lfphyd8u8kwuejey5xcazdxptserx03wc4jc9g24stx9l2hPublished at
2023-06-07 18:15:23Event JSON
{
"id": "f17498c8b894805aa8d5f1f7390a74a66c0ffd179803915f8a9ce2c895d6cce5",
"pubkey": "f0feda6ad58ea9f486e469f87b3b9996494363a26982b864667c5d8acb0542ab",
"created_at": 1686161723,
"kind": 1,
"tags": [
[
"e",
"cd7e024950034674de771ae97f0f4a7d697cc0813c8ea05376c31db3ca1405a1",
"",
"root"
],
[
"e",
"1005b4f9fdd51422aeb6835bbfb351460edbc07247baf736f21784a223b4203a",
"",
"reply"
],
[
"p",
"c17b4e785b1b6f810b8d1567cbc57ebefa8d20c59ada2f5d1c9537d41251a6ed"
]
],
"content": "📅 Original date posted:2018-11-28\n📝 Original message:On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote:\n\u003e Are there any candidates for non-interactive threshold signatures? Interactive\n\u003e signatures are not very suitable for air-gapped use cases.\n\nI think you can work around this to some extent by \"batching\" signing\nrequests.\n\n(Background:\n\nFor interactive multisignatures (threshold or not), the protocol is:\n\n produce secret nonce r, calculate public nonce R=r*G\n everyone shares H(R)\n everyone shares R, checks received values match received hashes\n everyone calculates s=r+H(R',P',m)*p, shares s\n\nFor deterministic nonces, you generate r=H(p,m) based on the message\nbeing signed and your private key, so can only start this process when\nyou start signing, and the sharing rounds mean interactivity.\n\n)\n\nBut you don't strictly need deterministic nonces, you just have to never\nuse the same nonce with a different message. If you arrange to do that\nby keeping some state instead, you can calculate nonces in advance:\n\nphase 1:\n produce secret nonces r1..r1024, calculate R1..R1024\n share H(R1)..H(R1024)\n\nphase 2:\n store other parties hashes, eg as H1..H1024\n share R1..R1024\n\nphase 3:\n check received nonces match, ie H(R1)=H1, etc\n\nphase 4:\n request to sign msg m, with nonce n\n if nonce n has already been used, abort\n mark nonce n as having being used\n lookup other signer's nonces n and sum them to get R'\n calculate s = rn + H(R',P',m)*p\n share s\n\nThat way you could do phases 1-3 once, and then do 1024 signatures during\nthe month on whatever your current timetable is.\n\nYou could also combine these phases, so when you get a signing request you:\n\n * receive msg to sign m, n=4; everyone else's R4, H(R5)\n\n * check H(R4) = previously received \"H(R4)\"\n * calculate R4' by summing up your and everyone's R4s\n * bump state to n=5\n * do the signature...\n\n * send sig=(s,R4), R5, H(R6)\n\nwhich would let you have an untrusted app that does the coordination and\nshares the nonces and nonce-hashes, and getting all the needed air-gapped\ncommunication in a single round. (This is effectively doing phase 3 and\n4 for the current signature, phase 2 for the next signature, and phase\n1 for the signature after that all in one round of communication)\n\nThat seems almost as good as true non-interactivity to me, if your signing\nhardware is capable of securely storing (and updating) a few kB of state\n(which is probably not quite as easy as it sounds).\n\nCheers,\naj",
"sig": "5f3d3799e08a817ed2adbcba9475fdd3db24f317f31dc7f164ff6586c05d8e6878ae9c3c577534a00681052b6c1ed76211d06ec5796676cbe52bf62652235325"
}