The paper says that
The inversion $\alpha \mapsto \alpha^{-1} $ (where 0 is mapped to 0) can be seen as a permutation on $\mathbb F_{256}$. This permutation is odd, while quantum circuits with NOT, CNOT, and Toffoli gates on n > 3 qubits generate the full alternating group $A_{2n}$ of even permutations. Hence we have to use one ancilla qubit, i.e., nine qubits in total.
Why we restrict the gates only to NOT, CNOT, and Toffoli? As I know they does not generate the universal quantum gate set. Isn't It? For example n-qubit Toffoli is an odd permutation in $S_{2^n}$, but it can be constructed with out ancilla bit as shown in the page.
I think with out ancilla qubit we can construct any permutation in $S_{2^n}$ (in particular we can implement any S-box without ancilla). Am I wrong?