Cryptography Reference
In-Depth Information
But this is a problem with cryptography. Changing one bit of an en-
cryption key is usually enough to ruin decryption—even if only the
least significant bits that change.
The best solution is to return to finite collections of integers mod
some prime number. Adi Shamir Shamir used this domain to hide
secrets by choosing polynomials from this domain [Sha79]. Instead
of lines or planes to hide the information, he chose
k −
1 degree
p
(
x
) , where the first parameter,
p 0 =
p
(0) ,holdsthe
polynomials,
secret. (This is a line when
k
=2 .) One point on the polynomial
goes to each part holder.
parts can be used to reconstruct the
polynomial and determine the secret,
k
p
(0) .
Here are the basic steps:
1. Choose a value of
q
that is prime and greater than
n
.
2. Find a randompolynomial,
p
(
x
) ,ofdegree
k−
1 by selecting
k−
1
random integers between 0 and
q
. These will be the coefficients
of the polynomial,
p 1 ...p k 1 .
p 0 is the secret to be stored away.
3. k 1
i is the polynomial.
i=0 p i x
4. Choose
n
points,
x 1 ...x n . These should be distinct and nonzero.
Compute
p
(
x 1 )
...p
(
x n ) . These are the
n
parts to be distributed
to part holders with the values of
x i .Anysubsetof
k
are enough
to determine
p
(
x
) and the secret
p 0
.
5. To recover the value of
p 0 , use Lagrangian interpolation. That
is, you can use the points to estimate the derivatives of the
polynomial at a point.
This solution uses only integers. It should be obvious that you
need
points to recover the polynomial. The easiest way to see this
is to realize that having
k
k −
1 points gives no information about
p
(0) .
In fact, for any potential value of
p
(0) you might guess, there is some
p
that generates it. You can find this
p
by taking the
k −
1 points
and your guess for
(0) and generating the polynomial. So, if there
is a one-to-one mapping between these guesses, then the system is
perfect . The part holder has no advantage over the outside guesser.
The scheme also offers greater efficiency for cases where
p
k
is a
reasonably large number.
In Section 4.2, the geometrical solution
was to create a
k
-dimensional space and fill it with
k −
1 dimen-
sional hyperplanes. Intersecting
hyperplanes was enough to reveal
the point. The problem with this solution is that the hyperplanes
take up more and more space as
k
grows larger. I don't mean they
consume more abstract space—they just require more space to hold
k
Search WWH ::




Custom Search