Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9566887A for ; 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 ; Wed, 28 Nov 2018 08:13:20 +0000 (UTC) Received: by mail-oi1-f182.google.com with SMTP id y23so21832243oia.4 for ; 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: In-Reply-To: From: Omer Shlomovits Date: Wed, 28 Nov 2018 10:13:08 +0200 Message-ID: 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 , bitcoin-dev@lists.linuxfoundation.org, Elichai Turkel , Roman Zeyde , Gary Benattar 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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
Hi,=C2=A0

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).
=C2=A0
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.

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



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

Are there any candidates for n= on-interactive threshold signatures?=C2=A0 Interactive signatures are not v= ery 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 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
The p= roject can be found here:=C2=A0https://github.com/KZen-networks/mul= ti-party-schnorr .=C2=A0
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

Hope you'll find it useful :)<= br style=3D"color:rgb(0,0,0)">Questions, s= uggestions and pull requests are welcome!
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000984f29057bb523b7--