Relative bits of security of slower functions

Leaving memory-hardness assumptions aside, some slow hash functions are iterated salted hash-chain versions of regular cryptographic hashes. This is usually defined by a round parameter i.e., in PBKDF2. Is there any cryptography paper that addresses security-bits definition based on the factor of rounds of linear successive invocations (not parallel) for one output computation?

I.e., a concrete example: is breaking a pre-image of sha3(fresh_salt, input_value) easier than sha3(sha3(sha3(sha3(fresh_salt, input_value)))) for some low entropy input_value (i.e., 64bits), and if yes does the latter offer 2-bits of extra security because the relative effort required by the attacker is 4 times more? Any research paper that discusses that (relative adversarial effort required between independent or linearly-dependent functions vs. pragmatic bits of offered security)?

• This question is similar to Security implications of slow-by-design hashes on relative security vs. hash size, but I'm mostly interested in a security proof related answer.

There have been refined notions of what it means for a protocol to have $\lambda$-bits of security. The best-known one is probably the Micciancio-Walter On the Bit Security of Cryptographic Primitives.

The notion of bit security there is different whether one is working with a

• decision game, where it is $\min_A\log_2 \frac{T(A)}{(\mathsf{adv}^A)^2}$, i.e. scales quadratically with the adversarial advantage, or

• search game, where it is $\min_A \log_2 \frac{T(A)}{\mathsf{adv}^A}$, i.e. scales linearly with the adversarial advantage.

The $\min_A$ is minimizing over all adversaries attacking a primitive, and $T(A)$ is the running time of $A$. Note that advantage for search/decision games are defined differently (for search games, it is roughly the success probability, for decision games, it is $2\delta-1$, where $\delta$ is the success probability).

Anyway, in this framework you could try to prove something like

If $H(\cdot)$ is a hash function that is $\kappa$-bit pre-image resistant, then $H^{\circ k}(\cdot)$, the $k$-fold composition of $H$, is $(\log_2(k) + \kappa)$-bit pre-image resistant.

The proof roughly go as follows

1. Start with $\min_A \log_2 \frac{T(A)}{\mathsf{adv}_H^A}\geq \kappa$, where $\mathsf{adv}^A_H$ is the advantage of $A$ in a game defining pre-image resistance.

2. Establish some sort of advantage bound $\mathsf{adv}_{H^{\circ k}}^A \leq \mathsf{adv}_H^A$, keeping track of the running time of the new adversary $B$ one (implicitly) constructs as part of this. For simplicity, assume that $\mathsf{adv}_{H^{\circ k}}^B \leq \mathsf{adv}_H^A$, and $T(B) = kT(A)$ --- it is not clear to me this is true, but I think this assumption is implicit in your question.

3. Then, we have that $\min_B \frac{T(B)}{\mathsf{adv}_{H^{\circ k}}^B} \geq \min_A\frac{kT(A)}{\mathsf{adv}_{H}^A} = \log_2 k + \kappa$.

As #2 above points out, this really reduces to showing a (traditional) advantage bound of the form.

For any adversary $B$ against $SHA3^{\circ k}$, there is an adversary $A$ against $SHA3$ with

• $T(B) = kT(A)$, and
• $\mathsf{adv}^B_{SHA3^{\circ k}} \leq \mathsf{adv}^A_{SHA3}$.

This is to say that the MW framework allows one to discuss how much the higher running time of $B$ impacts security (which is your question), but one still needs to prove an advantage bound though.

A few thoughts on this, not really sure if I my answer will cover you and probably it has flaws.

First a few things about security. When we say that an cryptographic scheme has $λ$ bits of security what we usually mean is that the only way to break it is to brute force the trapdoor information and so to try $2^λ$ combinations. Of course we are not considering any other type of attacks, side channel attacks etc. Afterwards we consider an adversary model e.g. computationally bounded. And if we prove that the scheme is secure against this adversary then we say it has $λ$ bits of security.

Since you are referring to theoretical security the answer is no. It would probably be yes if you were referring to quantitative security. I will try to offer a very intuitive counter example.

Instead of considering a hash function consider Textbook RSA with proper padding for example. Let's define its security only in terms of semantic security. So it is secure, and thus we say it has $1^λ$ bits of security, if for any $PPT$ adversary (on the security parameter) any pair of same length messages $m_1, m_2$, their corespoding ciphertexts are computationally indistinguishable. If RSA assumption holds, we know RSA is semantically secure.

Now consider a new scheme where $c=Enc_k(Enc_k(x))$. If the last encryption scheme was more secure than the first one, this would mean that the adversary would be able to achieve non-negligible advantage in a game where it is given two ciphertexts each one encrypted with the two schemes, e.g. the distributions would need to be non-negligibly close. From the RSA assumption this cannot be the case.