The brave new world of bodacious assumptions in cryptography

Neal Koblitz and Alfred Menezes
Notices of the AMS, 57 (2010), 357-365.

Abstract: 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)