Re: Secret sharing algorithm with chosen keys

On 2009-02-24, Ilmari Karonen <usenet2@xxxxxxxxxxxxxx> wrote:

Actually, though, I think one should be able to do better by adapting
Blakley's scheme: Take the N random keys and interpret them as
N-dimensional hyperplanes; except for rare degenerate cases, these
hyperplanes will intersect at a single point. Now simply publish the
first N-T coordinates of the intersection point, essentially defining
a T-dimensional affine subspace of the full N-dimensional space which
includes the intersection point. The intersections of T of the random
hyperplanes with this affine space will then be enough to determine
the remaining T coordinates of the intersection point.

This is still less efficient than Shamir's scheme or even the normal
Blakley's scheme, requiring shares that are N times as long as the
secret. But that's still a lot better than N choose T.

As an addendum, it occurred to me after posting this that one might be
able to do something similar with Shamir's scheme: Interpolate an N-th
order polynomial through points defined by the random shares, let the
secret be its first root and publish N-T of the N coefficients.

Or, perhaps simpler, just generate N-T more points lying on the
polynomial and publish them. Then T of the random points, together
with the N-T published points, are sufficient to determine the secret
root.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
.

Relevant Pages

  • Re: Secret sharing algorithm with chosen keys
    ... That was the exact scheme I was going to propose, ... Take the N random keys and interpret them as ... N-dimensional hyperplanes; except for rare degenerate cases, ... first N-T coordinates of the intersection point, ...
    (sci.crypt)
  • Re: three 2s
    ... here is a scheme for expressing ... The 2 also provides a clear orientation for the x-axis. ... number represented is the x-coordinate of said intersection. ...
    (rec.puzzles)
Quantcast