1
$\begingroup$

Given $f(x)$, a weak one-way permutation, how to prove that $f^T(x)$ is not a strong one-way function? Here $f^T$ denotes $T$ times self composition of $f$ and $T$ is a polynomial in input length.

$\endgroup$
1
$\begingroup$

Obviously, composing $T$-times a weak OWP can give a strong OWF: simply consider the case where $f$ is already a strong OWP (hence in particular a weak OWP). Now, what you want is to show that it is not necessarily the case; i.e., you want a function $f$ which is a weak OWP, but such that $f^T$ is not a strong OWF (i.e., an example where security does not "amplify through composition").

I'll give you such a candidate; I let you prove that it satisfies what you want, that is a quite simple exercise. Let $g: I \mapsto I$ be an arbitrary (strong or weak) OWP, and let $J$ be some arbitrary set such that $|J| = |I|$, and $I$ is disjoint from $J$. Consider the following function $f$:

$f:I \cup J \mapsto I \cup J$ is defined as follows: $f(x) = g(x)$ if $x \in I$, and $f(x) = x$ if $x\in J$.

Claim: $f$ is a permutation (that's quite obvious), and also a weak-OWP (you should be able to check that easily). Yet, $f^T$ is still a weak-OWP, but not a strong OWF. Can you see why?

(if you're stuck in the analysis, just ask for more hints in the comment section)

$\endgroup$
  • $\begingroup$ I am interested in the situation where $f$ is a weak OWF and not a strong OWF. In that case, $f^T$ will not be a strong OWF. But I don't know how to prove it. $\endgroup$ – Deevashwer Aug 9 '18 at 10:26
  • $\begingroup$ In my example, $f$ is obviously a weak one way function and not a strong one. Can you see why? Remember that a OWF is related to the hardness of inverting it on a random input of its domain. What happens if you take a random input in the domain of $f^T$? How often is it easy to invert? I can give you the full solution if you can't work it out, or just give you hints if you prefer, it's not so hard $\endgroup$ – Geoffroy Couteau Aug 9 '18 at 11:38
0
$\begingroup$

How do you define weak vs strong? We need to consider some kind of additional construction. By definition, a permutation is invertible. You may mean how distinguishable it is from a random permutation.

For a well constructed one, like Keccak-$f$, the inverse may be significantly more expensive to calculate. In any case, applying Keccak-$f$ 24 times is secure IF we only give $r$ bits of data after applying this (giving us claims for (1600 - r)/2-bit security). If we were to get access to the whole state, then it is obviously not secure.

As an important note though, since you are talking about applying the exact same permutation $T$ times, then you can't have different round constants. Thus, if you want a "strong" result, the initial permutation can't be completely vulnerable to rotational attacks. But this is a fairly low bar, since you can achieve this by including even a single "wide" add operation across your domain, and then $T$ linear in the length of $x$ is sufficient to address this. Of course, there are many different types of attacks. For example, you can't have a construction vulnerable to slide attacks, for which the number of rounds may become irrelevant (this is similar to a permutation which doesn't add anything against rotation attacks).

$\endgroup$
  • $\begingroup$ From a strong one-way function, I mean that the success probability of inverting $f$ is at most negligible. From a weak one-way function, I mean that the failure probability of inverting $f$ is at least noticeable. $\endgroup$ – Deevashwer Aug 5 '18 at 13:59
  • $\begingroup$ So I think what you're talking about is some kind of oracle here (i.e., $f$ is not known with certainty by the attacker). Basically, $f$ is to be selected from some known set of permutations, $S$, such that given access to a black-box implementation of $f$, the attacker has a relatively high chance of inverting it. However, by iterating over $f$, the attacker then has a relatively low chance of inverting it. Thus, $S$ must be large (so $f^T$ is strong), but have structure (so $f$ is weak). $\endgroup$ – MotiN Aug 6 '18 at 7:43
0
$\begingroup$

So, the question is are we after $n$-bit security (where $n=|x|$)? If the answer is yes (that this is strong), then the statement is correct.

For slide attacks; one indeed remains "vulnerable". Thus, indeed we won't be able to have better security than the birthday bound (i.e., for $n$-bits, $\frac{n}{2}$ security in terms of number of plaintext, cipher-text pairs).

Otherwise, if one is ok with this $\frac{n}{2}$ bound, then it is quite likely that one can achieve this. For example, consider defining $f = f_K$ using a reduced-round block cipher for some random $K$, such that $f$ itself is weak. $f^T$ may be strong.

A "silly" example of this could be to consider the Keccak permutation, where we need a fixed round constant. The fact that different rounds have different constants are supposed to provide protection against rotational and slide attacks. Rotational attacks can be dealt with by doing a $b$-wide addition to a random offset $O$. In this case, from a security perspective we need at least $b$ additions for the "strong" permutation (i.e., $T \geq b$ is necessary).

$\endgroup$
  • $\begingroup$ I'm not sure that answers/has any relation with the question. Unless I misunderstood it, OP asks whether for a weak OWP $f$, it does necessarily hold that $f^T$ is a strong OWF. I do not see how any of you considerations (with concrete attacks and the like) have anything to do with this purely theoretical question, where we do not care about concrete attacks, but only about (the existence or inexistence of) a polytime reduction between two primitives. $\endgroup$ – Geoffroy Couteau Aug 7 '18 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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