In public-key cryptography, the security level indicates the strength of an adversary in breaking a scheme or solving a problem, which can be seen as the time cost of breaking a scheme or solving a problem. Generating a scheme with a security parameter $k$ does not mean that this scheme has $k$-bit security. The real security level depends on the mathematical primitive and the scheme construction.

Suppose all potential attack algorithms to break a proposed scheme have been found with the following distinct time cost and advantage

$$\{ (t_{i},\varepsilon_{i}) \mid i \in I \}$$


$$2^{k^*} = \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$$

Then we sat this scheme is $k^*$-bit security.

My question is why the form is $t_{i}/\varepsilon_{i}$?

Of course the security level depends on the time cost $t$ and the advantage $\varepsilon$. I assume that

$$2^{k^*} = \inf \{ f(t_{i}, \varepsilon_{i}) \mid i \in I \}$$

Thus, there are some basic properties of $f$.

P1. For $t_{2} > t_{1}$ and $\varepsilon_{2} > \varepsilon_{1}$, $f(t_{2}, \varepsilon_{1}) > f(t_{1}, \varepsilon_{1}) > f(t_{1}, \varepsilon_{2})$. If we assume that $f$ is smooth, then we can let $df/dt > 0$ and $df/d\varepsilon < 0$.

P2. For every attack algorithm, $f(t, \varepsilon) \leq 2^k$.

P1 and P2 hold true if we let $f(t,\varepsilon) = t / \varepsilon$.

However, there are many functions that satisfy these properties. And I think $f$ should also satisfy more properties.

For example, given an attack algorithm $A$, for the trivial modification of $A$, the value of $f$ should be the same. Let $A_{n}$ be an algotithm that calls $A$ for $n$ times, $A_{n}(x) = 1$ if and only if there are more than $n/2$ times that $A(x) = 1$. We know that $$\frac{t_{A_{3}}}{\varepsilon_{A_{3}}} = \frac{3 t_{A}} {3\varepsilon_{A}/2} \neq \frac{t_{A}} {\varepsilon_{A}} $$

I try to explain the "trivial modification" more clearly. If there is an oracle machine $M$ which is independent of the scheme, then I think $M^{A}$ should be a "trivial modification" of $A$. I believe that the power of $M^{A}$ should not be stronger than $A$. However, I do not know how to define the oracle machine $M$ in a formal way. So, I give above example of $M$ such that $M$ asks oracle $A$ for $n$ times and the output of $M^{A}$ only depends on these $n$ answers. We do not care about the specific attack algorithm $A$ is (and whether $A$ has the accesses to some oracles.)


2 Answers 2


The value $t/\epsilon$ is the expected amount of time required for an attacker to "win". E.g., if he has a 50% $(\epsilon = 0.5)$ probability to guess a key in $t = 10$ seconds, then the expected length of time for him to guess the key is $t/\epsilon = 10s/0.5 = 20s$

The example you provided is a bit unspecified, and it's not clear to me that $A_3$ is a "trivial modification" of $A$, what a "trivial modification" means, or why we would expect a "trivial modification" to retain the security of the original.

To be more concrete consider two examples:

First, a blockcipher $E$ with 128 bits of security (for simplicity, 128-bit keys and 128-bit blocks). Then $E'_{k1,k2}(x) = E_{k1}(E_{k2}(x))$ could be considered a "trivial modification" of $E$ and has, as you say, pretty much the same security level --- in this case, 129 bits due to a meet-in-the-middle attack.

On the other hand, if you view the blockcipher $E$ as a PRF, then the "trivial modification" $E'_{k1,k2}(x) = E_{k1}(x) \oplus E_{k2}(x)$ has significantly more security --- we've gone from ~64 bits of security (generic birthday-bound attack) to ~85 bits of security (c.f "The sum of PRPs is a secure PRF" by Stefan Lucks).

So in the absence of more specific information about your $A_3$, it's entirely reasonable that $A_3$ may have either about the same, significantly more, or even significantly less security than $A$.

A final note I don't know what text your definition comes from, but although it's a completely reasonable definition for "bits of security" --- a term often used informally --- it's a bit incomplete since it doesn't account for possible limits to the number of queries an attacker can make, or the amount of pre-computation he could perform before being provided with oracle access.

  • $\begingroup$ The definition is cited from here (4.1.12) $\endgroup$
    – Blanco
    Mar 8, 2019 at 13:02
  • $\begingroup$ Actually, I do not know what kinds of modification should be "trivial modification". So I just give an example. I do not believe that $f(t, \varepsilon) = t/\varepsilon$ is the best function. So, I want more evidences to show that the value $t/\varepsilon$ makes sense. Your modification is about the encryption algorithm. I do not know how do you compare the security between $E$ and $E'$. It seems that you still consider some attack algorithm $A$ and the value of $t_{A}/\varepsilon_{A}$. My modification is about the attack algorithm itself. $\endgroup$
    – Blanco
    Mar 8, 2019 at 13:40
  • $\begingroup$ This is largely a good answer, but beware (a) the use of time as the only cost, because in many cases you can reduce time by running more machines in parallel at the same cost; and (b) the use of single-target attacks as a proxy for the cost of multi-target attacks, when in many cases like a block cipher an attack on $n$ targets simultaneously can be $n$ times cheaper than an attack on one target and about $n^3$ times faster—so to find the first of a billion 128-bit keys for a block cipher the cost is well below $2^{100}$, which is why I advise against saying AES128 gives 128-bit security. $\endgroup$ Mar 8, 2019 at 16:32

There have been some papers recently suggesting alternative measures of bit security (roughly meaning alternative $f(\cdot)$), at least in indistinguishability games. The two I know are

Both papers have the same definition in search games, where (at least where it is publicly verifiable if you "found the right thing")

I don't believe they answer your question though, which appears to be trying to pin down the form of $f(\cdot)$ "from first principles". The motivating factor of the aforementioned papers is really resolving a certain "paradox" regarding notions of bit security for PRGs, I would suggest just reading the intro to the Micciancio Walter paper for details.


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.