{\huge Psst---It's The Definition}

Definitions are extremely important \vspace{.5in}

Shafi Goldwasser and Silvio Micali won the 2012 ACM Turing Award last March for their seminal work in cryptography. We are not a year late saying this---that is how the award is dated. By contrast, the official Academy Awards website says that the 2012 Oscars mean the ones for films in 2011, so February's ceremony was the 2013 Oscars. The Turing Award is not like an Oscar anyway, as it is for lifetime achievement. The ACM-EATCS Gödel Prize, whose just-announced winners we intend to hail soon, is more like an Oscar in that it honors specific performances (papers) within a limited timespan. Like the Oscar, some have won it more than once, including Shafi, while we cannot tell from the definition whether the Turing Award can be won twice.

Today Ken and I wish to talk about the role that definitions play in math and theory.

Shafi and Silvio won the prestigious award not mostly for a deep theorem---although both have proved some very deep results---but rather for creating the ``right'' definition for security. Well actually the definition needed some work after their famous 1981 paper, as noted here and as we expand below. But it was an important milestone in the history of modern cryptography.

This phenomenon of creating the right definition as a seminal result in math is actually a recurrent theme. Deep results are important, and are the life-force of math, but the right definitions can advance a field more. A deep theorem closes a door: X is now known to be true. A deep definition opens a door: Y and Z and $latex {\dots}&fg=000000$ are now new questions to be considered. We have previously talked about how ``the right definition'' can enable proving a theorem, and about different roles of definitions, but great definitions are known for larger impacts.

Let's take a look at some of the great definitions. The list is obviously personal and incomplete, and we invite you to add to it.

Six Examples

$latex {\bullet }&fg=000000$ Numbers. Leopold Kronecker was apparently referring to $latex {\mathbb{Z}}&fg=000000$ not $latex {\mathbb{N}}&fg=000000$ when saying what were made by ``the dear God'' while ``everything else is human work.'' So perhaps he excluded zero and the negative integers as ``definitions,'' but that still leaves the rationals, the reals, and the complex numbers as some of the most important definitions of all.

$latex {\bullet }&fg=000000$ ZF. Ernst Zermelo and Abraham Fraenkel created this definition of the most popular modern view of set theory.

$latex {\bullet }&fg=000000$ Lebesgue measure. Henri Lebesgue defined the measure in 1901, and later it was in his dissertation in 1902. Modern analysis would be very different without this beautiful definition. There are other notions of measure and related integrals, but Lebesgue's definition is wonderful.

$latex {\bullet }&fg=000000$ Turing Machines. Alan Turing---you knew that---created this definition in his famous work on the Halting Problem and undecidability. Where would complexity theory be today without this simple, intuitive, but brilliant definition?

$latex {\bullet }&fg=000000$ Complexity Classes. We earlier singled out Hartley Rogers and his classic 1967 textbook for the importance of defining classes of languages, and perhaps the influence goes back to Rogers' work in the 1950's. But the seminal 1965 paper that won Juris Hartmanis and Richard Stearns their own Turing Awards is what introduced complexity classes in the way known by our field, long before the theory of $latex {\mathsf{NP}}&fg=000000$-completeness revealed the scientifically amazing extent to which problems ``quantize'' into a relative handful of complexity classes. Another reason for class accomplishing more motion advancing the field than problem is that the definition of the class expresses the computational goal or barrier.

$latex {\bullet}&fg=000000$ PAC Learning. Ideas of computational learning had existed for decades prior to 1983, of both recursion-theoretic and artificial-intelligence flavors, but had limited boosting power compared to the explosion that followed Leslie Valiant's PAC definition that year. His paper and concept were the first things cited in his own Turing Award, and he has just published a book titled simply, Probably Approximately Correct.

How to Tell a Secret

Many good definitions come from a direct construction of a mathematical object or logical property. However, sometimes this involves choices of details that are in line with the way the intended application is framed but are not really part of the concept. They may be representation-dependent, such as in a particular cryptographic system. This occurred with initial attempts to define,

What is a secret?

Similarly, what is security, what is a secure system? No one could say directly.

One approach was to classify protocols that were known or believed to be secure apart from ones known to be compromised, with the idea of:

How to tell a secret---apart from a non-secret?

But this is still wrong---it is still trying to say what a secret ``is.'' Anything can be a secret---what you need to define is whether it stays a secret. This requires a definition that is operational. The brilliant first insight of Shafi and Silvio was to shift the definition from knowing something to whether you gain the power to do something else.

How to Tell a Secret Hasn't Been Told

Suppose $latex {x}&fg=000000$ is a secret---remember $latex {x}&fg=000000$ could be any string of some length $latex {n}&fg=000000$. We whisper a string $latex {y}&fg=000000$---we intend $latex {y}&fg=000000$ to be the encoding of $latex {x}&fg=000000$ but again it could be anything. How can we tell that telling $latex {y}&fg=000000$ didn't give away anything about $latex {x}&fg=000000$? We consider $latex {x}&fg=000000$ given away if a probabilistic polynomial-time algorithm (PPTA) $latex {A}&fg=000000$ given $latex {y}&fg=000000$ gains the ability to succeed on a task involving $latex {x}&fg=000000$, with tangibly higher probability than it could without $latex {y}&fg=000000$.

Let's suppose the task is directly to learn some bit $latex {i}&fg=000000$ of $latex {x}&fg=000000$. Suppose $latex {A(n,i,y)}&fg=000000$ gets $latex {x_i}&fg=000000$ correct with some probability $latex {q > 0.5}&fg=000000$. Was $latex {y}&fg=000000$ to blame for this? We can say $latex {y}&fg=000000$ was not to blame if there is another PPTA $latex {A'}&fg=000000$ such that $latex {A'(n,i)}&fg=000000$ gets $latex {x_i}&fg=000000$ correct with probability $latex {q - \epsilon}&fg=000000$, where $latex {\epsilon}&fg=000000$ is negligible in terms of $latex {n}&fg=000000$. That is, we can simulate $latex {A}&fg=000000$ by an $latex {A'}&fg=000000$ that does almost as well without $latex {y}&fg=000000$.

To be more general, let $latex {P(x)}&fg=000000$ stand for any easily-computed property of the strings $latex {x}&fg=000000$, which are drawn from $latex {\{0,1\}^n}&fg=000000$ under some distribution $latex {\cal D}&fg=000000$. Then the basic simulation idea of semantic security is:

for every PPTA $latex {A}&fg=000000$ there is a PPTA $latex {A'}&fg=000000$ such that over all lengths $latex {n}&fg=000000$, drawing $latex {x}&fg=000000$ according to $latex {\cal D}&fg=000000$,

$latex \displaystyle \left|\Pr_x[A(n,y) = P(x)] - \Pr_x[A'(n) = P(x)]\right| < \epsilon.&fg=000000$

Now comes a question: What if there are two secrets $latex {x_1,x_2}&fg=000000$, and $latex {P(x_1,x_2)}&fg=000000$ is the property that they are different? If the encoding $latex {y}&fg=000000$ is always a simple function of $latex {x}&fg=000000$, then whether $latex {y_1 \neq y_2}&fg=000000$ would give this property away. For general properties this already indicates that the encryption must be probabilistic, producing multiple valid $latex {y}&fg=000000$'s for the same $latex {x}&fg=000000$. The decoding can still be deterministic---in practice often aided by trap-door information generated by the system. Moreover, probabilistic encryption enables achieving security for any $latex {\cal D}&fg=000000$, with similar import to allowing an adversary to choose the plaintext $latex {x}&fg=000000$.

Simulation and probabilistic encryption, in the complexity context, were Shafi's and Silvio's two main innovations. Well so was building a cryptosystem that worked, but we're talking about definitions. Simulation was the right concept, and shortly founded their wonderful work on zero-knowledge proofs. However, it was still not the right definition.

Playing Games is Fairer

This is a problem peculiar to definitions: it's not enough to say the right thing, they have to say it the right way. To use the definition in formulas for a proof, we need good syntax not just semantics.

The problem for crypto was having all these loose quantities: $latex {P}&fg=000000$, $latex {\cal D}&fg=000000$, and even the arbitrary success probability $latex {q}&fg=000000$ for $latex {A(n,y)}&fg=000000$. They made the definition hard to prove for specific systems, which came with their own multiple quantities. But by the time of their 1984 journal paper, Shafi and Silvio had found a way to shave the definition.

Let's go back to $latex {x_1}&fg=000000$ and $latex {x_2}&fg=000000$. Let the adversary choose them, and let's run the system over and over again.

Each time, the adversary picks one of $latex {x_1}&fg=000000$ or $latex {x_2}&fg=000000$, encodes it as $latex {y}&fg=000000$, and sends $latex {y}&fg=000000$ to our algorithm $latex {A}&fg=000000$. Can $latex {A(n,y)}&fg=000000$ tell whether $latex {y}&fg=000000$ came from $latex {x_1}&fg=000000$ or from $latex {x_2}&fg=000000$? That's the game, and though the definition had a new name, it came out the same:

A cryptosystem satisfies indistinguishability under chosen plaintext attack (IND-CPA) if for every PPTA $latex {A}&fg=000000$, the success rate of $latex {A(n,y)}&fg=000000$ in this game is no more than $latex {0.5 + \epsilon}&fg=000000$, where $latex {\epsilon}&fg=000000$ is a negligible function of $latex {n}&fg=000000$.

This definition has no $latex {P}&fg=000000$, no $latex {\cal D}&fg=000000$, and fixes $latex {q}&fg=000000$ to be the convenient ``fair'' value one-half. It doesn't even have $latex {A'}&fg=000000$. It says that no information about any one secret is being given away, if there is no feasible way to tell its encodings apart from those of anything else with better success than random guessing. Under quite general conditions on a cryptosystem, Shafi and Silvio proved that the system is semantically secure if and only if it satisfies IND-CPA. That may have been a difficult proof, but it was just one proof. The point is that when you make a new system, IND-CPA is usually a lot easier to prove for it than the original definition---conditioned on some hardness assumption, of course. The point is even stronger when specific settings such as public-key cryptography add their own particular quantities to the applicable forms of these definitions, as in the original papers.

Open Problems

What is your favorite definition?

Again we congratulate Shafi and Silvio on their award. As a footnote, the June Comm. ACM article by Neil Savage dates their achievement to 1983 and equates semantic security with CPA-IND. It leads by saying:

...Yet it was not until 1983 ... that cryptographers actually defined what they were doing.