A couple of people have taken me to task for complicating the question
about One Time Pads. The purpose of my original text was just to say that
yes, there are other useful and deployed algorithms out there that have
unconditional security, and that it is not the case that One Time Pads are
special in that sense. I have often seen the claim that "only one time pads
are provably secure", and this bugs me.
>Greg Rose wrote:
> >
> > At 11:01 PM 1/3/2001 +0000, someone wrote:
> > >Don't you think that's a pretty good reason for singling it out? Is
> > >there any additional merit in the more complex realisations?
> >
> > I just meant that there's a widespread assumption that the *only*
> > unconditionally secure algorithm is the One Time Pad. This assumption is
> > incorrect. But I don't think it is worth cluttering the list with this
> > point... I shouldn't have said anything.
>
>Well, it may be, but that would require answering the second question in
>the affirmative: do they have any additional merit?
Well, I gave one example. Shamir Secret Sharing is:
. unconditionally information-theoretically secure
. requires truly random information to be secure
. is clearly useful
. is implemented in a number of publicly available packages
. is not equivalent to a one-time-pad except in a degenerate case
>Clearly I can obfuscate any crypto algorithm by adding other stuff to it
>(e.g. Blowfish+RSA by using the first two primes above the key to
>generate an RSA key) but it doesn't get us anywhere.
Yes, there are an infinite number of ways to use shared random information
in complicated ways, or to complicate other algorithms, but that wasn't
what I was getting at.
>What intrigues me is the idea that there may (or may not) be more to the
>methods you describe than mere obfuscation, though I doubt there is.
To further expand the stated example, the way Shamir secret sharing works
is to give to n parties information such that any t (threshold) of them can
reconstruct the secret. It does this by choosing AT RANDOM t-1 coefficients
of a t-th degree polynomial, and using the secret data as the other
coefficient. The "shares" are the values of the polynomial evaluated at
independent points. When you have only t-1 data points, the interpolating
polynomial is incompletely specified, and the set of possible polynomials
(and therefore the set of possibilities for the secret) is as large as the
underlying group. When there are t data points available, the interpolating
polynomial is completely specified, and the data is uniquely revealed. See
page 526 of the Handbook of Applied Cryptography for the full detail here,
in particular note 12.72.
I claim that this is not obfuscation, and is a non-trivial application. QED.
I guess I should mention that the packages I've looked at that implement it
use non-random numbers generated for example by DES, thus artificially
limiting its security (for example, with two shares, one could brute-force
the DES key to verify guesses for the "randomly generated" coefficients and
recover the secret, even if more than two shares were otherwise needed). So
it really is like the OTP in that regard -- if the numbers are truly
random, it is provably perfectly secure, but if they aren't, all bets are off.
>Feel free to reply to this on the list. :-)
Done.
regards,
Greg.
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
