0
$\begingroup$

This may not be a good question, but I am just start to learn cryptography. I would like to ask why a fix permutation is not one way.

An adversary is given y=f(x) and try to invert y, x and y are n bits

In my opinion, an efficient adversary could only make polynomials query to the permutation. And it could only succeed if it made a query of x to f().

So the probability of the adversary to success is only p(n)*(1/(2^n)) which is negligible Are there anything wrong with my statement?

[edit] Let me provide more details, this is the problem of 7.5(a) of Katz/Lindell Given a psuedurandom permutation F Show that f(x,y) = $F_x (y)$ is not one way.

$\endgroup$
1
  • $\begingroup$ The identity function is a permutation. How hard is it to invert the identity function? $\endgroup$
    – Maeher
    Commented Aug 4, 2021 at 14:05

1 Answer 1

3
$\begingroup$

I would like to ask why a fix permutation is not one way.

Whether it is one way depends on how you define the problem.

If your are given Oracle access to the one way permutation, that is, you are allowed to provide a number of queries $x$ and the Oracle provides you the evaluation of $F(x)$, well, we hope that (assuming the size is large) it is one-way. After all, if we define $F$ to be the AES block encryption based on a secret key (so $n = 2^{128}$), well, this Oracle paradigm is exactly a standard CPA attack, and we hope that AES is secure against it. And, indeed it can be formally proven that the success probability you gave for a random permutation is close (the actual upper bound probability is slightly higher because the attacker can guess an input he didn't provide to the Oracle, bumping his success probability slightly).

On the other hand, if you are given the description of $F$, it becomes more problematic. The easiest (and most common) way to generate a strong permutation is to take a series of weak permutations (rounds) and concatenate them together; this is the approach that Keccak (SHA-3) uses. This works, but is easy to invert (just compute the inverse of the weak permutations in the opposite order).

On the other hand, that's not the only way to define a permutation; an example of a different way is to define the permutation $F(x) = x^e \bmod n$ for an RSA modulus $n$ and a public exponent $e$. This is a permutation of $x \in [0 ... n-1]$, and if $n, e$ are well chosen, it is hard to invert even given the values $n, e$ (or so we hope; otherwise RSA is insecure)

$\endgroup$

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.