Cryptography Reference
In-Depth Information
(x,y)
, is split into two parts by finding two random
lines that intersect at
(
Figure 4.1: A secret,
x
x, y
)
.(
y
is chosen at random.)
unanswered questions about what happens if the same system is
used to encrypt data over and over again with different keys.
2
The
simplest approach is the best in this case.
4.2.2 Letting Parts Slide
Obviously, there are many reasons why you might want to recover
some secret if you don't have all of the parts. The most basic algo-
rithms are based on geometry. Imagine that your secret is a number,
x
and join the two values to-
gether so they represent a point on a plane. To split up this secret into
twoparts,justpicktwolinesatrandomthatgothroughthepoint.-
(See Figure 4.1.) The secret can be recovered if the intersection of
. Now, choose an arbitrary value for
y
Gus Simmons' chapter
on Shared Secrets
[Sim93] is a great
introduction to the
topic.
the two lines is found. If only one line is available, then no knows
what the secret might be.
If there are two lines, then both parts need to be available to find
the solution. This technique can be extended so there are
n
parts, but
any two parts are enough to recover the secret.
Simply choose
n
lines that go through
(
x, y
)
at random. Any pair
will intersect at
(
)
and allow someone to recover the secret, as
in Figure 4.2. When the secret must be split into
x, y
n
parts and any
k
must be available to recover the secret, then the same approach
2
Some good introduction papers include [CW93].
