Given $n = pq$, where $p$ and $q$ are prime and $\phi(n^2) = (p^2-p)(q^2-q)$ (The Euler Totient function). Is there some combination of $n$s such that $\phi(n^2)|f(n)$
$f$ can be anything (greater than$\phi(n^2)$)given it only uses $n$ and not $p$ or $q$ separately and results in an integer for the input of $n$.
I have tried to find some such $f$ by manipulating $\phi(n^2)$ but haven't had any luck.
Anyway of showing such an $f$ doesn't exist would also be helpful Thanks
Edit: I am trying to adapt this answer here: https://crypto.stackexchange.com/questions/58047/equality-check-in-homomorphic-encryption
where I am taking$\mod n^2$ rather than$\mod p$ I am looking to replace the $p-1$ in $1 - (A - B)^{p-1}$ with $f(n)$ that still returns 0 if $A \neq B \mod n^2$. to do this I am applying:
Euler’s Theorem: Let $m \in N$. For any $a ∈ Z$ such that $hcf(a, m) = 1$, we have $a^ {\phi(m)} ≡ 1 \mod m$, where $φ(m)$ is the Euler totient function.
I understand that this will occasionally fail (i.e. if $A-B = p \mod n) which is ok for me
Since I will be applying this $f(n)$ to check if $A=B$ I need it to be computationally efficient (e.g. in time polynomial in $\log n$) without knowing $p$,$q$. so an $f$ requiring the decomposition of $n$ won't work as this would take too long/ completely remove the point of the encryption
One would hope that there is no efficient way to compute a nontrivial $f(n)$ without apriori knowledge of the factorization of $n$ (or some equivalent knowledge, such as the knowledge of $\phi(n)$)
The reason is that knowledge of any (nonhuge) multiple of $\phi(n)$ allows you to efficiently factor $n$; hence you would have just broken RSA (and Paillier).
The method to factor is fairly straight-forward; if you know a value $z = k \phi(n)$ (for some unknown $k > 0$); $z$ has the property that $g^z \equiv 1 \pmod n$ for any $g$ relatively prime to $n$.
What you do is compute the odd value $w = z / 2^{\lambda}$ (where $\lambda$ is number of factors of 2 within $z$; because $\phi(n)$ is even, we have $\lambda > 0$), and then for a random $g$, we compute $g^w \bmod n$; if that is neither 1 nor -1 (aka $n-1$), we repeatedly square the result $\lambda$ times. If one of the squarings results in a 1 but the previous value was not $-1$, then that gives the factorization, becaues if $g^2 \equiv 1 \bmod n$, and $g$ is neither $1$ nor $-1$, then $\gcd( g-1, n)$ and $\gcd( g+1, n)$ are nontrivial factors of $n$.
It is straight-forward to show that this yields nontrivial factors for at least half of the random $g$ values; this is also efficient, and so is a practical factorization method (assuming that we know $z$ in the first place)
Also, you are doing this in order to generate a Paillier based function that converts (most) nonzero values to 1 and zero values to 0. With such a function, Paillier would become a fully homomorphic function (that is, you can compute any [1] function homomorphically. We can see this because we could generate a two input NAND function homomorphically by, given $E_k(A)$ and $E_k(B)$ (where both $A, B \in \{0, 1\}$) by computing $E_k(2-A-B)$ (which Paillier allows us to do), and then applying your magic function to the result. And, since NAND is complete, that means we can express any circuit as a series of NAND functions.
A Paillier-based fully homomorphic encryption would be a big deal; it doesn't look likely in practice.
[1]: Well, anything that can be described with a bounded circuit, which turns out to be just about anything we care about in practice