The brave new world of bodacious assumptions in cryptography
Neal Koblitz and Alfred Menezes
Notices of the AMS, 57 (2010), 357-365.
There is a lot at stake in public-key cryptography. It is, after all,
a crucial component in efforts to reduce identity theft, online fraud,
and other forms of cybercrime. Traditionally, the security of a
public-key system rests upon the assumed difficulty of a certain
mathematical problem. Hence, newcomers to the field would logically
expect that the problems that are used in security proofs come from a
small set of extensively studied, natural problems. But they are in for
an unpleasant surprise. What they encounter instead is a menagerie of
ornate and bizarre mathematical problems whose presumed intractability
is a basic assumption in the theorems about the security of many of the
cryptographic protocols that have been proposed in the literature.
Journal paper Video review (Brian Snow)