Cryptography Reference
In-Depth Information
use these keys to identify
n
different sets of
m
elements from
the file.
3. Tune the hiding algorithm so it can hide information in
mn
elements in such a way that the information can be recovered
even if
(
n −
1)
m
elements are not available or damaged.
4. Hide the information.
5. Distribute the
different people whomight have
a reason to extract the information. The algorithm will still
work because the information was hidden with such redun-
dancy that only one subset is necessary.
n
“keys” to the
n
Hartung and Girod use the term “public-key” for the
n
values of
{k
1
,...,k
n
}
, even though they do not behave like many traditional
public keys. The keys do offer a good amount of antifraud protec-
tion. Anyone possessing one
k
i
can extract the information, but they
cannot embed new information. If the holder of the value of
k
i
tries
to embed a new signal, it will probably be invisible to the holders of
the other
n −
1
keys because their keys define different subsets. The
k
i
can change the elements as much as possible, but this
won't change the information extracted by others.
Of course, this approach does have limitations. The values of
holder of
k
i
are not truly public because they can't circulate without restrictions.
They also can't be used to encrypt information so that they can only
be read by the holder of a corresponding private key. But the results
still have some applications in situations where the power of keys
needs to be reined in.
12.5 Zero Knowledge Approaches
Zero knowledge proofs are techniques for proving you know some
information without revealing the information itself. The notions
began evolving in the 1980s as cryptographers and theoretical com-
puter scientists began exploring the way that information could be
segregated and revealed at optimal times. In one sense, a zero knowl-
edge proof is an extreme version of a digital signature.
Here's an example of a zero knowledge proof. Let
G
be a graph
with a set of nodes (
{v
1
,v
2
,...,v
n
}
) and a set of edges connecting
the nodes (
{
(
v
i
,v
j
)
,...}
). This graph can be
k−
colored if there exists
some way to assign one of
nodes so that
no edge joins two nodes with the same color. That is, there does not
exist an
k
different colors to the
n
i
and a
j
such that
f
(
v
i
)=
f
(
v
j
)
and
(
v
i
,v
j
)
is in the set of
