MIME-Version: 1.0
Sender: gmaxwell@gmail.com
In-Reply-To: <4003eed1-584f-9773-8cf9-6300ebd1eac6@satoshilabs.com>
References: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com>
	<CAAS2fgRQk4EUp6FO2f+RkJpDTyZX0N4=uGp7ZF=0aUchZX8hSA@mail.gmail.com>
	<4003eed1-584f-9773-8cf9-6300ebd1eac6@satoshilabs.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Thu, 18 Jan 2018 14:34:24 +0000
Message-ID: <CAAS2fgSw0mAQPJ-ai-3kFr7pWXd7pjbrEoXN4r6Ak3o4c8_vjw@mail.gmail.com>
To: =?UTF-8?Q?Ond=C5=99ej_Vejpustek?= <ondrej.vejpustek@satoshilabs.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
Precedence: list

On Thu, Jan 18, 2018 at 1:50 PM, Ond=C5=99ej Vejpustek
<ondrej.vejpustek@satoshilabs.com> wrote:
>   (1) Our proposal doesn't use SSS for the whole secret, but it divides
> the secret into bytes and uses SSS for every byte separately. This
> scheme is weaker because to reconstruct n-th byte it suffices to have
> n-th bytes from k shares.

If being secure against partial share leakage is really part of your
threat model the current proposal is gratuitously insecure against it.
And the choice of check algorithm really doesn't matter for that.

For example,  in a 2-of-3 share  say I have the first half of shares
1,2 and the second half of shares 2,3  with the current proposal the
secret is directly revealed, even though I didn't have any single
complete share.

If partial share disclosure were an actual concern, I would recommend
that after sharing and before encoding for transmission (e.g. before
applying check values and word encoding to the share) the individual
shares be passed through a large block unkeyed cryptographic
permutation.  Under reasonable-ish assumptions about the difficulty of
inverting the permutation with partial knowledge, this transformation
would prevent attacks from leaks of partial share information.