[RS20b] Generically Speeding-Up Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions

Authors: Lior Rotem, Gil Segev | Venue: CRYPTO 2020 | Source

Abstract

Despite the fundamental importance of delay functions, repeated squaring in RSA groups (Rivest, Shamir and Wagner ‘96) is the main candidate offering both a useful structure and a realistic level of practicality. Somewhat unsatisfyingly, its sequentiality is provided directly by assumption (i.e., the function is assumed to be a delay function).

We prove sharp thresholds on the sequentiality of all generic-ring delay functions relative to an RSA modulus based on the hardness of factoring in the standard model. In particular, we show that generically speeding-up repeated squaring (even with a preprocessing stage and any polynomial number parallel processors) is equivalent to factoring.

More generally, based on the (essential) hardness of factoring, we prove that any generic-ring function is in fact a delay function, admitting a sharp sequentiality threshold that is determined by our notion of sequentiality depth. Moreover, we show that generic-ring functions admit not only sharp sequentiality thresholds, but also sharp pseudorandomness thresholds.

BibTeX

@Inproceedings{C:RotSeg20,
  author = {Lior Rotem and Gil Segev},
  title = {Generically Speeding-Up Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions},
  pages = {481--509},
  editor = {Daniele Micciancio and Thomas Ristenpart},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2020, Part~III},
  volume = {12172},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~17--21},
  publisher = {Springer, Cham, Switzerland},
  year = {2020},
  doi = {10.1007/978-3-030-56877-1_17},
}