Re: Questions about Shamir secret sharing

Dro Kulix <peter.s.may@xxxxxxxxx> wrote:

ss10001 is an experiment in implementing secret sharing as proposed by
Shamir[SHAMIR] by using 16-bit blocks of the secret to be shared and
evaluating polynomials modulo 65537.

I've seen implementations that did this, and they tend not to be
pretty. The problem is that you have to do something with the tiny
fraction of a bit left over after sharing (because the outputs are
more-or-less uniform over GF(2^{16} + 1)), so you end up pratting about
with the spare bits in a most irritating way.

You say that you've not understood the maths for doing the arithmetic in
GF(2^n). Having actually tried this, I can confidently say that the
resulting scheme is more space-efficient (because the shares are exactly
the same size as the original secret), easier to implement and
understand (because you don't have to do the strange contortions to
handle the overflow bits) and probably more efficient.

I'd suggest, in fact, that an interest in secret sharing is a good
motivation to learn about non-prime-order finite fields. Binary fields
(of the form GF(2^n)) in particular crop up all over the place in
interesting bits of cryptography.

My secret-sharing implementation works on individual bytes, using
arithmetic in GF(2^8). In this field, addition and subtraction are just
XOR; multiplication and division can be performed efficiently using log
and antilog tables. The tables are less than a kilobyte in size.
Shares are exactly the same size as the original secret.

Am I selling this idea to you? ;-)

The decrypter is suitable for solving shares generated from any of the
modes described below; the encrypter is currently designed to run in
OC mode. My intuition about the Shamir algorithm is not sufficient to
tell me whether OC mode provides sufficient security, or whether the
more conservative AC or the less intensive SR modes should be used
instead.

For security, you must share each slice independently. That is,
choosing fresh random coefficients for each slice -- your AC mode.
I think OC is totally insecure.

Suppose we have a system with a threshold of t (i.e., t people can
recombine the secret from their shares), and the secret is split into s
slices. The polynomials used for the sharing have degree t - 1. But
all but two of the coefficients are common between the slices; so in
fact there are 2 s + t - 2 unknowns in the system. If I can get t'
shares, I get t' s equations. One doesn't need particularly many slices
or shares before t' >= 2 + (t - 2)/s, and this becomes a problem.

-- [mdw]
.

Relevant Pages

  • Re: Joint encryption?
    ... simply discards mail, so I don't have to deal with all the broken ... You don't need the "...used to gain access to the rest of the ... This is called "secret splitting", and there are a number of schemes by ... How the shares are stored is up to those charged with protecting them; ...
    (Bugtraq)
  • Re: Joint encryption?
    ... > simply discards mail, so I don't have to deal with all the broken ... >>the key can be used to gain access to ... > reconstruct the secret, but any M-1 of which can discover nothing about ... > How the shares are stored is up to those charged with protecting them; ...
    (Bugtraq)
  • Re: Secret sharing algorithm with chosen keys
    ... compute from these keys a shared secret that any T of the N persons ... But I'd like to be able to reconstruct the shared secret even ... For example, you might combine T shares thusly (forgive me, ... you don't need the tokens. ...
    (sci.crypt)
  • Re: Efficient Exponentiation of a Shared Secret
    ... shared among a number of parties. ... Shamir's scheme this is the case). ... Is there a scheme in which the secret s can be expressed as a product ... using any k out of n shares the secret x can be reconstructed, ...
    (sci.crypt)
  • Re: Cheating Shamir’s (k, n)-threshold ...
    ... One of them(ie: Carol) is ... >doesn’t know the other participants shares. ... The final recovered secret is a publicly-known linear ... the fraudulent share she submitted as well as the value of her true ...
    (sci.crypt)