Cryptography Reference
In-Depth Information
j
should vary with each block. It can
either increase sequentially or be chosen by a random number
generator. If a random number generator is used, it should be
a pseudo-random number generator that can be reseeded to
recover the information later.
mod
n
. The choice of
j
For most practical purposes, error-correcting codes are not ideal
ways to share secrets. While it is easy to construct a Hamming code
that can sustain one error, it is pretty inefficient to generate an error-
correcting code that contains
n
bits per block and still survive, say,
n−
2
errors. The theory is not optimized around this solution and, in
fact, the approach presented in this chapter can't detect more than
n
2
errors.
A better secret-sharing technique emerges directly from geome-
try. Imagine that you encode a message as a point in a plane. One
solution is to draw three lines through the point and distribute the
lines to different people. Two lines are enough to reconstruct the
point. The process can be turned into an error-correcting code just
by choosing the one point that represents the largest intersection
of lines. If you want to encode larger amounts of data, you can
use higher-dimensional spaces and use planes or higher dimensions.
This is close to what the Hamming codes are doing, but it is difficult
to think in these terms when only bits are being used.
3.3 Constructing Error-Correcting Codes
Hamming codes are easy and elegant error-correcting codes. Con-
[Ara88] and [LJ83] were
the source for this
material.
structing them and using them is relatively easy. The problem can
be thought of as taking your incoming message bits and then adding
parity bits that will allow you to correct the errors. The net effect is to
create an overdetermined collection of linear equations that can be
solved in only one way.
The easiest way to introduce the algorithm is by constructing an
Section 4.2 shows how
to use error-correcting
codesasawaytoshare
responsibility or split a
secret into multiple
parts. Better algorithms
follow.
example code that takes 11 bits and adds 4 new parity bits to the
mix so that an error of at most one bit can be corrected if it occurs.
The input bits will be
b
1
,...,b
15
.For
the purpose of illustrating the algorithm, it is easier to use binary
subscripts:
a
1
,...,a
11
. The output bits are
b
1111
.
The best way to illustrate the process is with a table of the output
bits. The input bits are merely copied over into an output slot with a
different number. This is easy to do in hardware if you happened to
be implementing such an algorithm in silicon. The extra parity bits
b
0001
through
