Sequential Squaring Assumption

The sequential squaring assumption states that for an RSA modulus of unknown factorization and a random , for a gap and every sufficiently large polynomial , every polynomial-size circuit of depth at most computes with negligible probability, although sequential squarings compute it.

Assumption

The assumption is parameterized by a modulus generator that on input outputs with for distinct -bit primes (uniform, as in the factoring assumption, unless stated otherwise), and by a gap ; the game additionally takes a difficulty , a polynomial, over which the definition quantifies. Adversaries are non-uniform families of polynomial-size circuits; the depth of is its parallel running time.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ssq}}_{\GrGen,T,\calA}(\secpar)$}
\begin{algorithmic}
\State $(N, p, q) \gets \GrGen(1^\secpar)$; $x \getsr \ZZ_N^*$
\State $y \gets \calA_\secpar(N, T(\secpar), x)$
\Comment{$\calA_\secpar$ has depth at most $T(\secpar)^\varepsilon$}
\Return $[y = x^{2^{T(\secpar)}} \bmod N]$
\end{algorithmic}
\end{algorithm}

Sequential squaring holds for with gap if there is a polynomial such that for every polynomial and every polynomial-size of depth at most ,

is negligible.

The depth bound is necessary because successive squarings modulo are a polynomial-size circuit of depth that computes . The quantifiers follow the definition of time-lock puzzles with gap of BGJ+16.

Known Results

  • Trapdoor. Given , the exponent takes multiplications modulo , and for every , so is computable in time — RSW96. Hence Sequential squaring ⇒ FAC.
  • Generic ring model. Against algorithms that treat as a generic ring, speeding up repeated squaring, even after a preprocessing stage and with polynomially many parallel processors, is equivalent to factoring (FAC ⇒ Sequential squaring (generic ring model)); more generally, every generic-ring function relative to an RSA modulus has a sharp sequentiality threshold, assuming factoring is hard in the standard model — RS20b.
  • Known-order groups. No generic-group delay function exists in a cyclic group of known order: for every delay function that does not use the representation of the group, an attacker given the group order breaks its sequentiality, even when the group carries a -linear map for a constant — RSS20.
  • Time-lock puzzles. The RSW puzzle masks a key with ; RSW96 conjecture that without the factorization of repeated squaring cannot be sped up by parallel computation, and hence that the puzzle is secure, and give no reduction (Sequential squaring ⇒ TLP (RSW puzzle)) — RSW96.
  • Verifiable delay functions. Proofs that make repeated squaring a VDF in the group of signed quadratic residues modulo a product of two safe primes — Pie19 — and in groups of unknown order such as RSA groups and class groups of imaginary quadratic fields — Wes19. Wesolowski’s proof is sound in groups satisfying the adaptive root assumption — BBF18; the assumption fails in itself, since satisfies for every odd prime — standard.

Variations

Decisional sequential squaring

The decisional form asks to distinguish from a uniform element of .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{dssq}}_{\GrGen,T,\calA}(\secpar)$}
\begin{algorithmic}
\State $(N, p, q) \gets \GrGen(1^\secpar)$; $x \getsr \J_N$; $b \getsr \bits$
\State $y_0 \gets x^{2^{T(\secpar)}} \bmod N$; $y_1 \getsr \J_N$
\State $b' \gets \calA_\secpar(N, T(\secpar), x, y_b)$
\Comment{$\calA_\secpar$ has depth at most $T(\secpar)^\varepsilon$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

Decisional sequential squaring holds for with gap if, with the quantifiers above,

is negligible. MT19 state the sequential squaring assumption in this decisional form over , against polynomial-size adversaries of bounded depth, for a product of two equal-length safe primes.

Strong sequential squaring

The strong form, for outputting a product of two equal-length safe primes (so that is cyclic), splits the adversary into a preprocessing stage , a polynomial-size circuit of unrestricted depth that receives , and a generator of and outputs a state, and an online stage , of depth at most , that receives the state, and — MT19. MT19’s multiplicatively homomorphic time-lock puzzle is secure if strong sequential squaring holds over — MT19.

Groups of unknown order

The assumption generalizes from to a group generator that on input outputs the description of a finite abelian group with polynomial-time multiplication and canonical encodings of its elements, together with a polynomial-time sampler for . The game is the one above with in place of , drawn by that sampler and computed in . Sequential squaring holds for with gap under the same quantifiers. The assumption is parameterized by , and a result from it names its group generator. Pie19 formulates the assumption for arbitrary families of groups. Class groups of imaginary quadratic fields are a candidate without a trusted setup: for a random negative prime discriminant, the order of the class group is unknown — Wes19. If an efficient algorithm outputs, with non-negligible probability, a multiple of the exponent of of polynomial length, sequential squaring fails for , since is then computed in depth — standard, as for the trapdoor above.

Attacks

  • Factoring. An algorithm that factors yields , and from it in further time — RSW96; the RSW puzzle is therefore vulnerable to advances in factoring — MMV11.
  • Quantum. Shor’s algorithm factors in quantum polynomial time and so breaks the assumption in RSA groups — Shor97.

Participates in

Builds on Sequential Squaring Assumption

Produces Sequential Squaring Assumption