*Bounty: 50*

*Bounty: 50*

The (computational) problem of *iterated squaring* (IS) in the RSA group is defined as follows, where $leftarrow$ denotes sampling uniformly at random:

Input: $(N,x,T)$, where $N$ is the RSA modulus, $xleftarrowmathbb{Z}_N^*$, and $Tinmathbb{N}$ is the time parameter

Solution: $x^{2^T}bmod{N}$.

This problem can be traced back to [C+] and used by [RSW] for constructing time-lock puzzles. More recently, it has been used to build verifiable delay functions [P,W]. It is not hard to see that the problem is at most as hard as factoring $N$. My question concerns the analogous problem in the Paillier group (ISP, for short), as used in [LM] and defined as follows*:

Input: $(N,x,T)$, where $N$ is the RSA modulus, $x=v^Nbmod{N^2}$ for $vleftarrowmathbb{Z}_N^*$ and, $Tinmathbb{N}$ is the time parameter

Solution: $x^{2^T}bmod{N^2}$.

*Question.* Is the hardness of these problems related, i.e., whether they are reducible to one another.

*Why should they be related?* Intuitively speaking, the RSA group is embedded in the Pailler group and constitutes its component of unknown order (which is necessary for iterated squaring to be hard). More formally:

$$(mathbb{Z}_{N^2}^*,times)cong (mathbb{Z}_N^*,times)times(mathbb{Z}_N,+),$$

and since iterated squaring in the $(mathbb{Z}_N,+)$ component is easy (as it is a group of known order), one could conjecture that hardness of solving ISP boils down to solving IS.

However, I could not find a reduction in either direction. For instance, to reduce IS to ISP one could try the canonical embedding of $mathbb{Z}*N^*$** in $mathbb{Z}*{N^2}^*$ defined as
$$xbmod{N}mapsto x^Nbmod{N}^2,$$
but this runs into the RSA problem when trying to map the solution back. In the other direction, one could try the canonical projection defined as
$$xbmod{N^2}mapsto xbmod{N},$$
but it is now not possible to lift the solution back to $mathbb{Z}_{N^2}^*$. Any ideas?

*Another way to define it would be as follows:

Input: $(N,x,T)$, where $N$ is the RSA modulus, $xleftarrowmathbb{Z}_{N^2}^*$, and $Tinmathbb{N}$ is the time parameter

Solution: $x^{2^T}bmod{N^2}$.

But it seems less natural than the formulation above.

*References.*

[C+]: Cai et al, Towards uncheatable benchmarks, CCC’93 (behind a paywall unfortunately)

[LM]: Lai and Malavolta Homomorphic Time-Lock Puzzles and Applications, Crypto’19

[P]: Pietzak, Simple verifiable delay functions, ITCS’19

[RSW]: Rivest, Shamir and Wagner, Time-lock puzzles and timed-release crypto, MIT Report

[W]: Wesolwski, Efficient verifiable delay functions, Eurocrypt’19