Why is the security level defined by $\log _{2} \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$

Question

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 \}$$

Let

$$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.)

Answer 1

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.

Answer 2

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

• On the Bit Security of Cryptographic Primitives by Micciancio and Walter, and

• Bit Security as Computational Cost for Winning Games with High Probability, by Watanabe1 and Yasunaga

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.