Short factoring proofs: Addition of phi(N)

[uncomputable]

In the short factoring proof, there is the line $y = r + (N - \varphi(N))e$. In the vanilla protocol, the verifier checks $x \overset{?}{\equiv} z^{y - eN} \mod N$. Because $\varphi(N)$ is the order of the multiplicative group of integers modulo $N$, taking the exponent of a multiple of $\varphi(N)$ gives you the identity 1 for all group elements, so $z^{\varphi(N)e} \equiv 1 \mod N$. This is my understanding how the protocol works.

I was wondering, can we define $y = r + (N + \varphi(N))e$ instead? The minus sign seems redundant to me and the above argument should still work, shouldn't it?

[fcasal]

Hi @uncomputable, Changing the operation from $N - \varphi(N)$ to $N + \varphi(N)$ would increase the bit-length of that term, which would require increasing the bit-length of the other terms $r$ and $e$. Failing to do so would probably lead to leaking some of $\varphi(N)$ bits. This would also slightly impact performance since you'd have to sample more bits, and compute a larger $y$.

In terms of completeness, as you say, the verification equation should still work, yes.

You can also find a (more complete) variant of the protocol in section 6 of the paper in the references, [PS00] Short proofs of knowledge for factoring (2000).

[uncomputable]

I see. Adding $\varphi(N)$ increases the maximum possible integers used, which increases the required bit length. Subtracting $\varphi(N)$ is an optimization to keep the bit length short.

I assumed $y$ to be in a finite group like $\mathbb{Z}_N$ or something (not in $\mathbb{N}$). In this case, the bit length would be constant. At least in an elliptic curve there are as many scalars as curve points. I have less experience with multiplicative groups like $\mathbb{Z}_N^*$ so I don't know if exponents can be bounded like that.

Thanks for linking the paper. I will read it over the next few days.