5
$\begingroup$

In Katz & Lindell's Introduction to modern cryptography (3d edition) we have the following statements in chapter 3:

A scheme is secure if for every probabilistic polynomial-time adversary $A$ carrying out an attack (of some formally specified type), the probability that $A$ succeeds in the attack (where success is also formally specified) is negligible.

Such a definition is asymptotic because it is possible that for small values of $n$ an adversary can succeed with high probability. (where $n$ is the security parameter)

More formally:

A scheme is secure if for every PPT adversary $A$ carrying out an attack, and every polynomial $p$, there is an integer $N$ such that when $n > N$ the probability that $A$ succeeds in the attack is less than $\frac{1}{p(n)}$.

Question: What does this mean in practice (i.e. in the real world)? For a given concrete scheme, is it possible to determine how large $n$ should be for $A$ to succeed with probability less than $\frac{1}{p(n)}$ ? If not, what is the point of such security definitions and their associated proofs?

$\endgroup$
1
  • $\begingroup$ That depends on your adversary. however, in general, we say that an event with $1/2^{100}$ probability is not going to happen. $\endgroup$
    – kelalaka
    Apr 16 at 17:36

2 Answers 2

5
$\begingroup$

As for what is the point of asymptotic definitions: Suppose you want to formalize the following qualitative desiderata:

  1. Honest parties and adversaries are "efficient" algorithms.
  2. An "efficient" algorithm composed with another "efficient" algorithm is also "efficient."
  3. "Security" means that every "efficient" adversary has only "tiny" chance of breaking the cryptography.

You can't formalize these rules coherently by just considering concrete running time. For example, you can't say that "efficient" means "runs in < $2^{64}$ steps", because this definition doesn't satisfy property #2. You are forced to consider asymptotic running time.

If you agree that a linear-time algorithm with small big-$O$ constants is "efficient", then you have no choice but to define "efficient" to mean "polynomial-time" -- this is the smallest class of algorithms that includes linear-time algorithms and enjoys this closure property.

In many situations, if an adversary has probability $p$ of breaking security, then running that adversary $t$ times gives you roughly $t \cdot p$ probability of breaking security. Based on the previous paragraph, we are obliged to consider any $t$ that is polynomial in the security parameter. So we need a definition of "tiny" such that any "tiny" function times any polynomial is still "tiny". If you agree that a "tiny" function should also approach a limit of zero, then it turns out that the biggest class of functions that satisfy the necessary closure property is our usual definition of "negligible".

So, the usual asymptotic way of defining security is an inevitable consequence of the criteria above.


is it possible to determine how large $n$ should be

This question can only be answered with a concrete security analysis. Sometimes it is relatively straight-forward to extract a concrete analysis from an asymptotic one, but other times it is non-trivial.

$\endgroup$
2
  • $\begingroup$ Thank you for this clear response. However, as a beginner, I keep worrying that these asymptotic definitions are meaningless abstractions that do not impact the design and implementation of real ciphers, and that my time would be better spent elsewhere. $\endgroup$
    – Mr. B
    Apr 17 at 11:49
  • $\begingroup$ It is possible to design things that are "secure" under these definitions, but wildly impractical or even useless. But I don't think it's fair to say that asymptotic security has no bearing on practical security. It is generally quite obvious whether a construction/proof is really abusing the peculiarities of the asymptotic world (e.g., "on security parameter $\lambda$, run this other scheme on security parameter $\lambda^{1/4}$...") $\endgroup$
    – Mikero
    Apr 17 at 20:54
5
$\begingroup$

Opinions differ.

It is now becoming more common to prove concrete security statements (an adversary against X using resources Y with advantage Z becomes an adversary against X' using resources Y' with advantage Z', and the relationship between Y, Z, Y' and Z' is explicitly given). As a general rule, such statements trivially become asymptotic statements. The opposite is not true, so concrete statements contain more information than asymptotic statements.

However, there are typically a lot of headaches involved with concrete security statements, since exact resource calculation is often exceedingly tedious. (How much does forwarding and doing a trivial amount of rewriting messages actually cost? How did we actually model the random oracle, and what does that mean anyway? Etc.)

Some people find it acceptable to be a bit sloppy here. Others prefer asymptotic (and perfectly sound) formulations. Yet others go for a mix, giving as exact as possible relations.

(Personally, I prefer a bit of sloppy concreteness, but that's probably because I am a sloppy thinker.)

One should also mention that if you actually take this stuff seriously and want to use the security proofs to find parameters that are actually meaningful (theoretically sound), you will need concrete security statements, as well as estimates of concrete hardness of the underlying hard problems. This leads to a strong desire for tightness in security proofs.

Other people see the security proof as a technique we use to rule out trivial breaks, and instead select parameters based on the best known attack. That also makes sense as an approach.

Finally, sometimes people just want to teach techniques and stuff. They don't actually care about real-world security in that context. In that case, an asymptotic formulation avoids a lot of complexity and allows the author to focus on the interesting things, instead of boring technicalities.

Also, keep in mind that specifying security levels is always a trade-off. Focusing too much on the exact number of bits of security (and what that actually means, exactly) is usually not productive. Instead, suggest an adversarial resource level and a failure rate that your application/end users can live with, and work from there.

$\endgroup$
2
  • $\begingroup$ Does this mean it is not really useful to study asymptotic security proofs? I worry that these are meaningless abstractions and that I would be better off reading other books. $\endgroup$
    – Mr. B
    Apr 17 at 12:17
  • $\begingroup$ Nah. The cryptologic ideas are the same, concrete or asymptotic. The ideas are the important stuff. Just don’t worry - at this stage - too much about what «secure» means. Worry instead about what an adversary is and when the adversary wins. And how you turn adversaries into algorithms that do useful stuff. $\endgroup$
    – K.G.
    Apr 17 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.