Cryptography Reference
In-Depth Information
you that there are no holes out there. You just know that in the past,
others have tried and failed to break similar systems. This is good
news, but it is not conclusive. There might be new holes that are easy
to exploit in these grammar-basedmimic functions, but that are hard
to use in other systems.
The principal difficulty
of your case lay in the
fact of there being too
much evidence. What
was vital was overlaid
and hidden by what
was irrelevant.
—Arthur Conan Doyle
in
The Naval Treaty
These holes are fairly common in theoretical approaches. For in-
stance, there are very few proofs that show how hard it is to solve
some mathematical problems. Sorting numbers is one of the few
examples. It has been shown that if you have a list of
n
numbers,
then it takes time proportional to
is some machine-
based constant [AHU83]. This is a nice result, but it doesn't make a
good theoretical basis for a cryptographically secure system. There
are other algorithms for sorting that can succeed in a time propor-
tional to
cn
log
n
where
c
is a different machine-based constant. These
algorithms only work if you can place absolute bounds on the size of
the numbers before beginning (64 bits is usually enough).
The other approach is to create different attacks against the sys-
tem and see if it is strong enough to withstand them. This can cer-
tainly show the strength of the system, but it too can never be conclu-
sive. There is no way to be sure that you've tried all possible attacks.
You can be thorough, but you can't be complete.
Still, probing the limits of grammar-based mimic functions is an
important task. The best theoretical bounds that exist are based on
work exploring the limits of computers that try to learn. In this area,
many researchers have based their work on Les Valiant's PAC model
from probablistic learning [Val84]. In it, a computer is given some
examples from a particular class and it must try to learn as much as
possible about the class so it can decide whether a new example is
part of it. The computer's success is measured probabilistically and
it succeeds if it starts getting more right than wrong.
There are many different forms of PAC algorithms. In some, the
computer is given examples that are just in the class. In others, the
computer gets examples from within and without the class. Some-
times, the computer can even create examples and ask whether that
example is in or out of the class. This type of algorithm has the po-
tential to be the most powerful, so it helps if the theoretical bounds
can defend against it.
Michael Kearns and Les Valient show that “learning” boolean for-
mulas, finite automata, or constant-depth threshold circuits is at
least as difficult as inverting RSA encryption or factoring Blum in-
tegers (
kn
,where
k
=
3mod4
). The proof shows this by casting the factoring process into
each of these different models of computation. [KV89, Kea89]
x
,suchthat
x
=
pq
,where
p
and
q
are prime, and
p, q
