Error Correction - Disappearing Cryptography - page 40

or zeros in a row.
This technique can be taken one step further that takes it outside
of the realm of error-correcting codes entirely. If you're planning to
use the error-correcting codes to give you enough room to add some
randomness to the data, then you're going to lose many of the error-
correcting properties. For instance, one flipped bit can convert 110 ,
a value representing 1 ,into 010 ,avaluerepresenting 0 . In essence,
youmight want to forget about the error-correcting ability altogether
and just construct a list of codes that represent each bit. 1 might be
encoded as 001 , 100 , 011 ,and 111 ,while 0 may be encoded as 110 ,
101 , 010 ,and 000 . The main advantage of this approach is that the
distribution of zeros and ones can be even more balanced. In the 3-
bit code used as an example in this section, there are an average of
2.25 bits used to encode a 1 and .75 used to encode a 0 . This means a
file with a high percentage of ones, for instance, will still have a high
percentage after the encoding. Using random codes assigned to each
bit can remove this bias.

3.2.2 Error Correction and Secret Sharing

Error-correcting codes have a functional cousin known as secret shar-
ing - that is, a class of algorithms that allow a file be split into

m parts

Secret sharing is
described in detail in
Chapter 4.

parts are necessary to reconstruct it. Obviously,
an error-correcting code that could handle up to

so that only m − k

bits
would works similarly. Simply encode the file using this method and
then break up the

k errors in m

different files.
There is one problem with this approach. Some bits are more
privileged than others in some error-correcting schemes. For in-
stance, the next section on Hamming codes describes a code that
takes 11 bits and adds 4 parity bits that will correct any single er-
ror. Ideally, a file encoded with this code could be broken into 15
parts and any 14 parts would suffice to recover the data. But, there
are only 11 bits of data in every block of 15 bits. The other 4 parity
bits are used just to correct the errors. If the

m bits into m

th bit of each block al-

i

th part, then the right 11 parts would suffice. The
key is to distribute the bits so this never happens. Here are the steps:

ways goes in the i

1. Choose an error-correcting code that offers the right recovery
properties. It is easy to find Hamming codes that recover single
errors.

2. Encode the file using this technique.

3. If there are files, then place one

bit from each block in each file. That is, place bit

n bits in each block and n

i in file i +