10
$\begingroup$

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, $x\leftarrow\mathbb{Z}_N^*$, and $T\in\mathbb{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^N\bmod{N^2}$ for $v\leftarrow\mathbb{Z}_N^*$ and, $T\in\mathbb{N}$ is the time parameter

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

Question: Is the hardness of these problems related? Are these problems reducible to one another?

Why should they be related? Intuitively speaking, the RSA group is embedded in the Paillier 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 $$x\bmod{N}\mapsto x^N\bmod{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 $$x\bmod{N^2}\mapsto x\bmod{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, $x\leftarrow\mathbb{Z}_{N^2}^*$, and $T\in\mathbb{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

Improve this question
$\endgroup$
3
  • $\begingroup$ Either you basically gave the answer, or the following has a flaw. Write $Z_{N^2}$ elements as $x_0 (1+N)^{x_1} \equiv x_0 + x_0 x_1 N$, the map $Z_{N^2} \to Z_N$ amounts to setting $x_1 = 0$. Suppose $y_0 \equiv x_0^t \; (N)$ (say for $t = 2^T$). To compute a compatible $y_1$ for a $Z_{N^2}$ representative, solve $y_0 + y_0 y_1 N \equiv x_0^t + t x_0 x_1 N$, i.e. let $y_1 N\equiv t x_0^{-t} x_0 x_1 N\mod N^2$. If $x_0$ is not invertible, we factor $N$ and can trivially solve. That gives you $(y_0, y_1)$ which is the $t$-th power of $(x_0, x_1)$. Any mistake? (Computing $y_1$ is fast!?) $\endgroup$
    – mk.
    Commented May 27, 2020 at 22:06
  • $\begingroup$ Not sure I follow. As per the first formulation of the problem, the $\mathbb{Z}_N$ component (which you call $(1+N)^{x_1}$) is already set to $1$. Could you rephrase your answer with that in mind? (This should be a simpler task as I feel you are trying to show that even the second formulation reduces to IS.) $\endgroup$
    – ckamath
    Commented May 28, 2020 at 12:58
  • $\begingroup$ I missed the power $N$ for the canonical embedding... what I described doesn't work. Perhaps letting $t=2^T N$ helps, although it changes the question? (Perhaps I'm overlooking something again.) $\endgroup$
    – mk.
    Commented May 29, 2020 at 0:03

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.