Cryptography Reference
In-Depth Information
the sequence of productions, but you don't have to use these arbi-
trarily complex routines. If the grammar is designed correctly, it is
easy enough for anyone to parse the data.
There are two key rules to follow. First, make sure the grammar
is not
ambiguous
; second, keep the grammar in
Greibach Normal
Form
. If the same sentence can emerge froma grammar through two
different sets of productions, then the grammar is
ambiguous
.This
makes the grammar unusable for hiding information because there
is no way to accurately recover the data. An ambiguous grammar
might be useful as a cute poetry generator, but if there is no way to
be sure what the hiddenmeaning is, then it can't be used to hide data.
Here's an example of an ambiguous grammar:
→
Start
noun verb
who what
→
noun
Fred
Barney
→
verb
went fishing.
went bowling.
who
→
Fred went
Barney went
what
→
bowling
fishing
The sentence “Fred went fishing” could be produced by two dif-
ferent steps. If you were hiding data in the sentence, then “Barney
went bowling” could have come from either the bits 011 or the bits
110. Such a problemmust be avoided at all costs.
If a context-free grammar is in Greibach Normal Form (GNF), it
means that the variables are at the end of the productions. Here are
some examples:
Production
In GNF?
Start
→
noun verb
YES
→
where
in
direction
Iowa.
in
direction
Minnesota.
NO
→
where
in
direction state
.
in
direction state
.
YES
→
what
bowling
fishing
YES
Converting any arbitrary context-free grammar into Greibach
Normal Formis easy. Addproductions until you reach success. Here's
the extended example from this section with a new variable,
state
,
that places this in GNF.
Start
→
noun verb
noun
→
Fred
Barney
verb
→
went fishing
where
went bowling
where
where
→
in
direction state
direction
→
northern
southern
state
→
Iowa.
Minnesota.
