path: root/69/cfcdce9d1b98a4eb9d5fdca9765b974e1c5f8d

Return-Path: <omer.shlomovits@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 9566887A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 28 Nov 2018 08:13:21 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi1-f182.google.com (mail-oi1-f182.google.com
	[209.85.167.182])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C9F8F19B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 28 Nov 2018 08:13:20 +0000 (UTC)
Received: by mail-oi1-f182.google.com with SMTP id y23so21832243oia.4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 28 Nov 2018 00:13:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to
	:cc; bh=dUhyOnkTjXXVVJlnaB1wqKr7wWzV5l7NcUEscqDsjTY=;
	b=uGb5e5EoXAUCJPtgLsAIof3DxXPiPGZIX7lT6koNXsAMUlVUR8YJNXdTVQGko025V1
	AnsagGGUg2m7K9/JiYU2Qoi38jXNl7Z0kZ4b2a//1D5W89ZLbOq5Eyhf26m9E0fr97Y7
	me6lIgk4CujRb7bh5NuC72ARDRJkuteOJ6RFLChHucxDJXV3HMzCd8b0SRUoL3BJ3Wuc
	6QDs/epb15IbqCy2L621bPPQK/4YgreVoLJWgrYJJU+8UUA/HzD2EGJUanNeSFGED6Gm
	auoa5pP0Ej99tD0ufoeJ86yLMTbPXT8i180HkXADJg9BBapCnyg00sRbk3wAJBFS/2bQ
	Zyvg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:references:in-reply-to:from:date
	:message-id:subject:to:cc;
	bh=dUhyOnkTjXXVVJlnaB1wqKr7wWzV5l7NcUEscqDsjTY=;
	b=A5atmow1xYmSW8O4XXqsju6pYogXYt0Y/NWIUvHIUNF6BPlFmqcES8yoH1JENnq956
	TQBkleIzNgmXZu4nDLhq5g4XbuNr4sfkV/71m9W3FzdEa8WvWDO+HAOyNkPcSzm71jlL
	+H+P0BnmjO0bVKXpjA6rSX+ZGNB3S9CIGz4KSEpx7NO2ssGZAsv1VTUnMthDvjxUDgyt
	/E4AHsAlRLQRrGqikIa8L8CRBhUkDowT5MGgpQ5Dr08NkOnLJMCwHLuLsr+zuiBNJRnI
	zml7k/tggB4vlCizC4AsLPgW1gDIsmf+YFuvfdDFyM3W/V4TcuHKgSvz03NichyH/DOc
	l4EQ==
X-Gm-Message-State: AGRZ1gKL7qjCpq19uF+qCAi0xA5j2S8x6yPWtTusHu2US8y9xOO5u8bY
	OK/te8dMMFEUdApebDyvkDbplZxD1tBI8L2/NWM=
X-Google-Smtp-Source: AJdET5fgkLQw6S+0y/AVdQkUNMh/ciDGymUlQv1v7EbochIdthdSe+OlXqCj8hHUYcLBHD5jAcKS23VkTuu7Wr0Kw1U=
X-Received: by 2002:aca:4c02:: with SMTP id z2mr19012302oia.318.1543392800033; 
	Wed, 28 Nov 2018 00:13:20 -0800 (PST)
MIME-Version: 1.0
References: <CALhDas2W5QEPmw8JEgak0zf7y3N0UFTiMVk-djR8x9_WYZiyfQ@mail.gmail.com>
	<CAB0O3SVjhXVV4PKYPh+2O4xZomcyT-T2Mis1A8riTtrnUUigig@mail.gmail.com>
In-Reply-To: <CAB0O3SVjhXVV4PKYPh+2O4xZomcyT-T2Mis1A8riTtrnUUigig@mail.gmail.com>
From: Omer Shlomovits <omer.shlomovits@gmail.com>
Date: Wed, 28 Nov 2018 10:13:08 +0200
Message-ID: <CALhDas1F6guAvPtTcSR+NJ+cybH-wcJu14ZmiQaSNX98OcWYBw@mail.gmail.com>
To: c1.bitcoin@niftybox.net
Content-Type: multipart/alternative; boundary="000000000000984f29057bb523b7"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 28 Nov 2018 08:18:25 +0000
Cc: Morten Dahl <mortendahlcs@gmail.com>, bitcoin-dev@lists.linuxfoundation.org,
	Elichai Turkel <elichai.turkel@gmail.com>, Roman Zeyde <mail@romanzey.de>,
	Gary Benattar <g.benattar@gmail.com>
Subject: Re: [bitcoin-dev] Multi party Schnorr Rust implementation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Nov 2018 08:13:21 -0000

--000000000000984f29057bb523b7
Content-Type: text/plain; charset="UTF-8"

Hi,

AFAIK, There is no way to do threshold signatures non-interactively for the
general case of t out of n. Even if you are willing to maintain additional
data structure on top of the standard and change verification algorithm
(see for example appendix B in [1] where they use bitmaps).

The best way that I came up with so far (which I plan to implement in the
library) is to take SS01 paper [2], this also the paper cited in
bip-schnorr [3], and to replace Pedersen VSS with Feldman VSS (Feldman VSS
implementation can be found in [4] ). Basically taking the DKG from GG18
without paillier and the dlog pok (threshold ecdsa paper [5]) and use it
for the threshold schnorr DKG and for the ephemeral key distributed
generation. This will cause the lost of Robustness but will be more
efficient.

Generally speaking - the purpose of using threshold security is to replace
hw security. The assumption is that you would rather trust that no more
than t out of n different machines will get corrupted at same time than to
trust one secure hardware. Maybe that relax a bit the demand for using air
gapped devices?


[1] https://docs.zilliqa.com/whitepaper.pdf
[2]
https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/provably_secure_distributed_schnorr_signatures_and_a_threshold_scheme.pdf
[3]
https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#multisignatures-and-threshold-signatures
[4]
https://github.com/KZen-networks/curv/tree/master/src/cryptographic_primitives/secret_sharing
[5] http://stevengoldfeder.com/papers/GG18.pdf

On Wed, Nov 28, 2018 at 8:33 AM Devrandom <c1.bitcoin@niftybox.net> wrote:

> Hi Omer,
>
> Are there any candidates for non-interactive threshold signatures?
> Interactive signatures are not very suitable for air-gapped use cases.
>
> On Tue, Nov 27, 2018 at 11:18 AM Omer Shlomovits via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hello all,
>>
>> I am working for the past few months with collaborators (in cc) on
>> providing Rust reference implementations to existing multi party schemes
>> for Schnorr signatures [1]. This includes aggregated signatures,
>> accountable signatures (which for n out of n are multi-signatures) and
>> threshold signatures (wip).
>> The project can be found here:
>> https://github.com/KZen-networks/multi-party-schnorr .
>> We aim that if the protocol is run in a configuration of a single party
>> it will be bip-schnorr [2] compliant.
>>
>> Hope you'll find it useful :)
>> Questions, suggestions and pull requests are welcome!
>>
>>
>> [1]
>> https://github.com/KZen-networks/multi-party-schnorr/tree/master/papers
>> [2] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

--000000000000984f29057bb523b7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div di=
r=3D"ltr"><div dir=3D"ltr">Hi,=C2=A0<div><br></div><div>AFAIK, There is no =
way to do threshold signatures non-interactively for the general case of t =
out of n. Even if you are willing to maintain additional data structure on =
top of the standard and change verification algorithm (see for example appe=
ndix B in [1] where they use bitmaps).</div><div>=C2=A0</div><div>The best =
way that I came up with so far (which I plan to implement in the library) i=
s to take SS01 paper [2], this also the paper cited in bip-schnorr [3], and=
 to replace Pedersen VSS with Feldman VSS (Feldman VSS implementation can b=
e found in [4] ). Basically taking the DKG from GG18 without paillier and t=
he dlog pok (threshold ecdsa paper [5]) and use it for the threshold schnor=
r DKG and for the ephemeral key distributed generation. This will cause the=
 lost of Robustness but will be more efficient.</div><div><br></div><div>Ge=
nerally speaking - the purpose of using threshold security is to replace hw=
 security. The assumption is that you would rather trust that no more than =
t out of n different machines will get corrupted at same time than to trust=
 one secure hardware. Maybe that relax a bit the demand for using air gappe=
d devices?=C2=A0</div><div><br></div><div><br></div><div>[1]=C2=A0<a href=
=3D"https://docs.zilliqa.com/whitepaper.pdf">https://docs.zilliqa.com/white=
paper.pdf</a></div><div>[2]=C2=A0<a href=3D"https://github.com/KZen-network=
s/multi-party-schnorr/blob/master/papers/provably_secure_distributed_schnor=
r_signatures_and_a_threshold_scheme.pdf">https://github.com/KZen-networks/m=
ulti-party-schnorr/blob/master/papers/provably_secure_distributed_schnorr_s=
ignatures_and_a_threshold_scheme.pdf</a></div><div>[3]=C2=A0<a href=3D"http=
s://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#multisignat=
ures-and-threshold-signatures">https://github.com/sipa/bips/blob/bip-schnor=
r/bip-schnorr.mediawiki#multisignatures-and-threshold-signatures</a><br></d=
iv><div>[4] <a href=3D"https://github.com/KZen-networks/curv/tree/master/sr=
c/cryptographic_primitives/secret_sharing">https://github.com/KZen-networks=
/curv/tree/master/src/cryptographic_primitives/secret_sharing</a></div><div=
>[5]=C2=A0<a href=3D"http://stevengoldfeder.com/papers/GG18.pdf">http://ste=
vengoldfeder.com/papers/GG18.pdf</a></div></div></div></div></div></div></d=
iv><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Wed, Nov 28, 2018 at =
8:33 AM Devrandom &lt;<a href=3D"mailto:c1.bitcoin@niftybox.net">c1.bitcoin=
@niftybox.net</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div d=
ir=3D"ltr"><div>Hi Omer,</div><div><br></div>Are there any candidates for n=
on-interactive threshold signatures?=C2=A0 Interactive signatures are not v=
ery suitable for air-gapped use cases.<br><br><div class=3D"gmail_quote"><d=
iv dir=3D"ltr">On Tue, Nov 27, 2018 at 11:18 AM Omer Shlomovits via bitcoin=
-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #c=
cc solid;padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"lt=
r"><div dir=3D"ltr">Hello all,<div><br></div><div>I am working for the past=
 few months with collaborators (in cc) on providing Rust reference implemen=
tations to existing multi party schemes for Schnorr signatures [1]. This in=
cludes aggregated signatures, accountable signatures (which for n out of n =
are multi-signatures) and threshold signatures (wip).=C2=A0</div><div>The p=
roject can be found here:=C2=A0<a href=3D"https://github.com/KZen-networks/=
multi-party-schnorr" target=3D"_blank">https://github.com/KZen-networks/mul=
ti-party-schnorr</a> .=C2=A0</div><div>We aim that if the protocol is run i=
n a configuration of a single party it will be bip-schnorr [2] compliant.=
=C2=A0</div><div><br></div><div><font face=3D"arial, helvetica, sans-serif"=
><span style=3D"color:rgb(0,0,0)">Hope you&#39;ll find it useful :)</span><=
br style=3D"color:rgb(0,0,0)"><span style=3D"color:rgb(0,0,0)">Questions, s=
uggestions and pull requests are welcome!</span></font><br></div><div><br><=
/div><div><br></div><div>[1]=C2=A0<a href=3D"https://github.com/KZen-networ=
ks/multi-party-schnorr/tree/master/papers" target=3D"_blank">https://github=
.com/KZen-networks/multi-party-schnorr/tree/master/papers</a></div><div>[2]=
=C2=A0<a href=3D"https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.=
mediawiki" target=3D"_blank">https://github.com/sipa/bips/blob/bip-schnorr/=
bip-schnorr.mediawiki</a></div></div></div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>
</blockquote></div>

--000000000000984f29057bb523b7--