4 - Cryptography and Computation after Turing

Summary

Abstract

This chapter explores a topic in the intersection of two fields to which Alan Turing has made fundamental contributions: the theory of computing and cryptography.

A main goal in cryptography is to prove the security of cryptographic schemes. This means that one wants to prove that the computational problem of breaking the scheme is infeasible, i.e., its solution requires an amount of computation beyond the reach of current and even foreseeable future technology. As cryptography is a mathematical science, one needs a (mathematical) definition of computation and of the complexity of computation. In modern cryptography, and more generally in theoretical computer science, the complexity of a problem is defined via the number of steps it takes for the best program on a universal Turing machine to solve the problem.

Unfortunately, for this general model of computation, no proofs of useful lower bounds on the complexity of a computational problem are known. However, if one considers a more restricted model of computation, which captures reasonable restrictions on the power of an algorithm, then very strong lower bounds can be proved. For example, one can prove an exponential lower bound on the complexity of computing discrete logarithms in a finite cyclic group, a key problem in cryptography, if one considers only so-called generic algorithms that cannot exploit the specific properties of the representation (as bit-strings) of the group elements.

Introduction

The task set to the authors of articles in this volume was to write about a topic of (general) scientific interest and related to Alan Turing's work. Here we present a topic in the intersection of computing theory and cryptography, two fields to which Turing has contributed significantly. The concrete technical goal of this chapter is to introduce the issue of provable security in cryptography. The article is partly based on Maurer (2005).

Computation and information are the two most fundamental concepts in computer science, much like mass, energy, time, and space are fundamental concepts in physics. Understanding these concepts continues to be a primary goal of research in theoretical computer science. As witnessed by Turing's work, many underlying questions are of as comparable intellectual depth to the fundamental questions in physics and mathematics, and are still far from being well understood.