Cryptography Reference
In-Depth Information
way for the decoder to know which pixels could have been rounded
up
or
down. The trick to the algorithms is to use a set of linear
equations and working with the perturbable pixels to ensure that the
equations produce the right answer. If the sender and the receiver
both use the same equations, the message will get through.
These equations are
often called wet paper
codes and are based on
solutions developed to
work with bad memory
chips with stuck cells.
[FGS04]
pixels in the image. Here's an algorithm for a
way to change the values that are close in order to hide a message,
m
0
,m
1
,m
2
,...
Let there be
n
:
1. Run your quantization algorithm to quantize all of the pixels.
This will produce a set of bits,
b
i
,for
0
≤ i<n
.Inourblack
and white example, the value of
b
i
is the value after the round-
ing off. In practice, it might be the least-significant bit of the
quantization. When these bits are places in a vector, they are
called
b
.
k
2. Examine the quantization algorithm and identify
bits that are
b
i
could be either a
0
or a
1
.
In our black and white example, these might be gray values of
128
close and could be quantized so that
±
. The number of bits that are close enough, that is within
±
, determine the capacity of the image.
3. Construct a
. This might be shared in pub-
lic, computed in advance, or constructed with a cryptograph-
ically secure pseudo-random stream dictated by a shared pass-
word.
k×n
binarymatrix,
D
4. Arrange for row
m
i
.Since
this is a binary matrix with bit arithmetic, this means that the
i
of this matrix to encode message
n
entries in row
select a subset of the pixels in the image. When
the bits from these pixels are added up, they should equal
i
m
i
.
In other words,
Db
=
m
5. The problem is that
Db
will not equal
m
unless we arrange for
some of the
b
values to change. If we could change all of the
D
m
bits in
b
, then we could simply invert
D
and compute
.If
we can only change
values, we still produce the right answer.
In other words, we need to find some slightly different values,
ˆ
k
,where
ˆ
b
b
i
=
b
i
when
b
i
is not one of the
k
values that can be
changed. On average, only 50% of the
k
values will actually be
changed.
6. Gaussian elimination can solve these equations and find the
values for
ˆ
b
.
