FAC ⇒ Sequential squaring (generic ring model)

Free reduction · non-standard model · RS20b

Statement

If factoring the moduli output by is hard, then for every efficient algorithm that treats as a generic ring, even with a polynomial-time preprocessing stage and polynomially many parallel processors, the probability that it outputs for a uniform using fewer than sequential rounds of ring operations is negligible — RS20b. Against generic-ring algorithms this gives sequential squaring with every gap . Algorithms that use the representation of ring elements are not covered.

Notes

  • RS20b prove more generally that every generic-ring delay function relative to an RSA modulus has a sharp sequentiality threshold, given by its sequentiality depth, assuming factoring is hard in the standard model — RS20b.
  • The converse holds in the standard model: factoring gives in time (Sequential squaring ⇒ FAC) — RSW96.
  • In cyclic groups of known order no generic-group delay function exists — RSS20.