Cryptography Reference
In-Depth Information
•
Unsort the list or somehow arrange for the receipient to get all
of the values of
{x
1
,...,x
n
}
through any means.
Information can be hidden in multiple locations and reordered
In a one-time hash
system, the sender
changes the cover data,
x
by the recipient without any communication from the source. The
only synchronization necessary is the choice of
f
and perhaps the
f
(
x
)
sends the
right message. [Shi99]
The message is usually
short because searching
for a
, until
key,
. The good news is that the multiple containers can move
through different channels on independent schedules and arrive in
any order without compromising the message.
Sorting the data allows the sender to scramble the cover data in
any random fashion, secure in the knowledge that the receiver will
be able to reorder the information correctly when it arrives.
Sorting is also a good alternative to choosing a subset of the cover
data to hold the hidden message. Other solutions use some key and
a random number generator to choose a random subset of the mes-
sage. Another solution is to apply some function,
k
x
requires brute
force. This is similar to
the mechanisms in
Chapter 9 which
permute the color of a
pixel until the parity
sends the right message.
, to the elements
in the data stream, sort the stream and then choose the first
f
n
to hold
the hidden message.
Of course, the success of these solutions depends entirely on the
choice of the function,
. Much of the problem is usually solved
once the data is converted into some digital format. It's already a big
number so sorting the values is easy. The identity function,
f
f
(
x
)=
x
,
is often good enough.
One potential problem can occur if multiple elements are iden-
tical or produce the same value of
f
That is, there exist
i
and
j
such
that
f
(
x
i
)=
f
(
x
j
). Inmany normal sorting operations, the values of
i
are used to break the tie, but this can't work because the sender
and the receiver may get the values of
and
j
x
in a different order.
If
x
i
=
x
j
, then it doesn't matter in which order they occur. But
x
i
=
x
j
, then problems may emerge if the sender and the receiver
do not place them in the same order. After the receiver extracts the
data from
if
x
j
, it could end up in the wrong order, potentially
confusing the rest of the extracted information.
There are two solutions to this problem. The simplest is to be cer-
tain that
x
i
and
f
(
x
i
)=
f
(
x
j
) only happens when
x
i
=
x
j
. This happens
when
is a pure encryption automorphism. This is often the best
solution. The other is to use some error correcting coding to remove
the damage caused by decoding problems. Some error-correcting
codescandowellwithseveralerrorsinarowandthiskindisessen-
tial. If
f
f
(
x
i
)=
f
(
x
j
), then they'll
generate two wrong errors in order. If there are multiple values that
produce the same
x
i
and
x
j
are misordered because
, then there will be multiple problems.
If it is not possible to guarantee that the values of
f
will be unique,
it makes sense to ensure that the same amount of information is
f
