Reversible crypto systems for use in the Grover's algorithm

Question

I'm working on some papers (here and here) that use the Grover algorithm to crack krypto systems like AES and SHA.

I had already asked a first question here. Now, however, a new question has arisen for me.

So to my knowledge, AES uses a key and a clear text and generates a cipher from this. If AES is reversibly implemented in the paper, then one could read the plaintext and the key, because the circuit is reversible. Does it make sense? How do you prevent that? Reversible means that I can make the input from an output. In this context, that means that I could read the key directly. Why then use the Grover algorithm at all?

For example in the paper here pages 3-4 it is said:

Let $f : \{0, 1\}^k → \{0, 1\}^k$ be an efficiently function. For a fixed $y ∈ \{0, 1\}^k$, the value $x$ such that $f(x) = y$ is called a pre-image of $y$. In the worst case, the only way to compute a pre-image of $y$ is to systematically search the space of all inputs to f. A function that must be searched in this way is known as a one-way function. The Grover iteration has two subroutines. The first, $U_g$, implements the predicate $g : \{0, 1\}^k \rightarrow \{0, 1\}$ that maps $x$ to $1$ if and only if $f(x) = y$. Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a comparison circuit that checks whether $f(x) = y$.

Then the hash function is a sub-call of the oracle. Which means that the hash function must be reversible. But if the has-function is reversible, I can directly read the plaintext, because I have the cryptotext (the hash). Do I understand something wrong here? Why do you need the Grover algorithm at all?

I also have to ask the question, why in the first paper $AES$ and $AES^{-1}$ are executed once and in the second paper $f$ and $f^{-1}$ in the oracle part? Why is not just $AES$ and only $f$ executed as a call?

Answer 1

I think there are two meanings of "reversible" at work. These may be causing confusion.

1. Initially, even in the classical world, when we say that a function $f(x)$ is irreversible without any other qualifications, we mean that, given $y$, it is computationally difficult to find an $x$ such that $y=f(x)$

2. In other contexts, when talking about quantum circuits, when we say that a function $f$ is implemented in reversible gates, we mean that the gates come from our favorite set of universal unitaries, e.g. $\mathsf{CCNOT}$'s, etc.

We believe SHA is irreversible in the first sense; that does not mean it cannot be implemented with reversible gates as in the second sense.

If we were to use Grover's algorithm to get a polynomial speedup on SHA, then given an output $y_0$, we would find a way to implement the SHA function $f(x)$ with a set of reversible gates to create a unitary $U_f$, prepare a first register $\vert x \rangle$ into a uniform superposition, apply $U_f$ to a second register $\vert y \rangle$ conditioned on the values of the first register, and repeatedly apply the Grover rotations conditioned on the value of the second register $\vert y \rangle$ being $y_0$.

When we implement $f(x)$, we could also implement it with all of our lossy/irreversible gates $\mathsf{AND}$, $\mathsf{NOR}$, etc., as long as we keep a copy of $x$ in some of the outputs. We apply the Grover rotations to the entire superposition.