public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: "Ondřej Vejpustek" <ondrej.vejpustek@satoshilabs.com>
To: Gregory Maxwell <greg@xiph.org>,
	roconnor@blockstream.io, bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
Date: Thu, 18 Jan 2018 14:50:41 +0100	[thread overview]
Message-ID: <4003eed1-584f-9773-8cf9-6300ebd1eac6@satoshilabs.com> (raw)
In-Reply-To: <CAAS2fgRQk4EUp6FO2f+RkJpDTyZX0N4=uGp7ZF=0aUchZX8hSA@mail.gmail.com>

Thank you for your comments, Gregory and Russell!

Gregory, thank you for you explanation of perfect secrecy, there is no
need for that, however. I'm professional mathematician and cryptographer.

> I read the above
> as "these are similar because they are based on math"...
They are based on algebra (group and commutative ring theory), which is
a great similarity. RSA and SHA, for example, are based on completely
distinct parts of mathematics.

> Complicated does not mean secure. And from an information theoretic
> perspective the hash does almost nothing (other then some small
> destruction of entropy due to its lack of perfect uniformity which is
> information theoretically equivalent to using a smaller perfect code).
> using error correcting codes and truncated hash functions create
identical amounts of information theoretic redundancy
I agree, see my last note in the previous mail. Adding redundancy by a
hash function is more secure than adding redundancy by a linear
relations. Just my opinion.

I see the difference between RSA and SSS you mentioned and I understand
your arguments about perfect secrecy. Just two comments:
  (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.
  (2) SSS is information-theoretic secure if you know k-1 or less
shares, where k is the threshold. But the proof doesn't hold if you know
for example a small part of every share.

> It is of no use to apply the precautionary principle against
impossible attacks, especially at the cost of losing the useful
properties of a real error correcting codes that would provide actual
guarantees against likely errors.
The discussion isn't about mathematics or about security proofs but
about cryptographic scheme design. In our use case you cannot assume
that all premises of security proof theorems (including SSS's perfect
secrecy) hold true (see the comment above).

In my opinion, to make a cryptographic scheme more robust it's better to
stick to general "intuitive" principles. Of course you have to consider
the advantages and disadvantages of this approach. That's why we
disclosed our draft and welcome all comments.

> The discussion of using a proper code was primarily related to the
> outer check value which protects the shares themselves and is sitting
> unprotected in plaintext
OK then. I was defending the hash in the inner check value.


  parent reply	other threads:[~2018-01-18 13:51 UTC|newest]

Thread overview: 32+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-01-17 11:39 [bitcoin-dev] Satoshilabs secret shared private key scheme Ondřej Vejpustek
2018-01-17 15:28 ` Russell O'Connor
2018-01-17 15:36   ` Gregory Maxwell
2018-01-17 15:31 ` Gregory Maxwell
2018-01-18  5:00   ` Matt Corallo
2018-01-18 13:50   ` Ondřej Vejpustek [this message]
2018-01-18 14:34     ` Gregory Maxwell
2018-01-18 16:59       ` Ondřej Vejpustek
2018-01-18 18:58         ` Gregory Maxwell
2018-01-22 15:00           ` Ondřej Vejpustek
2018-01-22 19:21           ` Russell O'Connor
2018-01-23  1:05             ` Gregory Maxwell
2018-01-23 13:54           ` Ondřej Vejpustek
2018-01-23 14:16             ` Adam Back
  -- strict thread matches above, loose matches on Subject: below --
2018-01-08  4:22 Gregory Maxwell
2018-01-08  6:33 ` nullius
2018-01-08 12:39 ` Pavol Rusnak
2018-01-08 12:45   ` Peter Todd
2018-01-08 13:00     ` Pavol Rusnak
2018-01-08 19:37       ` Peter Todd
2018-01-08 22:26         ` Ben Kloester
2018-01-09  0:37           ` Peter Todd
2018-01-08 23:47   ` Gregory Maxwell
2018-01-09  0:40     ` Rhavar
2018-01-09  1:13       ` Peter Todd
2018-01-09 12:44         ` jens
     [not found]         ` <274aad5c-4573-2fdd-f8b0-c6c2d662ab7c@gibsonic.org>
2018-01-12  9:50           ` Peter Todd
2018-01-09 15:12     ` Pavol Rusnak
2018-01-10 20:28       ` Pavol Rusnak
2018-01-10 23:47         ` Gregory Maxwell
2018-01-11  9:55           ` Pavol Rusnak
2018-01-09 16:20   ` Russell O'Connor

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=4003eed1-584f-9773-8cf9-6300ebd1eac6@satoshilabs.com \
    --to=ondrej.vejpustek@satoshilabs.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=greg@xiph.org \
    --cc=roconnor@blockstream.io \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox