#StackBounty: #factoring #complexity #hardness-assumptions Hardness of iterated squaring in Pailler group

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.


[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

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.