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
>>
>