International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Generically Speeding-Up Repeated Squaring is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions

Authors:
Lior Rotem , Hebrew University of Jerusalem
Gil Segev , Hebrew University of Jerusalem
Download:
DOI: 10.1007/978-3-030-56877-1_17 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2020
Abstract: Despite the fundamental importance of delay functions, repeated squaring in RSA groups (Rivest, Shamir and Wagner '96) is the only 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.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30408,
  title={Generically Speeding-Up Repeated Squaring is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56877-1_17},
  author={Lior Rotem and Gil Segev},
  year=2020
}