Re: Secret sharing algorithm with chosen keys

On 2009-02-24, James Taylor <usenet@xxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

Couldn't Thomas do what he was proposing to do in the T=N case, but do
that for each possible set of T people where T<N do you think? He could
then protect the shared secret with multiple decryption keys, each key
being the XOR of one possible set of T people. This wouldn't scale well
to large numbers of N and T but might suffice for his purpose (depending
on the exact nature of his purpose, of course).

Of course, I'm the novice round here so I've probably overlooked
something.

That was the exact scheme I was going to propose, so either it makes
sense or we've both overlooked something. :)

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.

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

Relevant Pages

  • Re: Secret sharing algorithm with chosen keys
    ... N-dimensional hyperplanes; except for rare degenerate cases, ... first N-T coordinates of the intersection point, ... This is still less efficient than Shamir's scheme or even the normal ... secret be its first root and publish N-T of the N coefficients. ...
    (sci.crypt)
  • Re: Simple queries on intersection of hypersurfaces
    ... Imagining that it may be a four-dimensional surface of a ... Would the zone of intersection be a 4-1 dimensional object by definition ... a 3-sphere is a sphere. ... for example, parallel hyperplanes do not intersect ...
    (sci.math)
  • Re: Simple queries on intersection of hypersurfaces
    ... Imagining that it may be a four-dimensional surface of a ... Would the zone of intersection be a 4-1 dimensional object by definition ... a 3-sphere is a sphere. ... for example, parallel hyperplanes do not intersect ...
    (sci.math)
  • 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)
  • Re: A family of inequalities of degree 3
    ... that *every* closed convex set can be represented ... as the intersection of countably many hyperplanes... ... Yet another proof that my postings are too long to be read. ...
    (sci.math)
Quantcast