## CryptoDB

### Paper: 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 DOI: http://dx.doi.org/10.1007/978-3-030-56877-1_17 (login may be required) Search ePrint Search Google CRYPTO 2020 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.
##### 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={http://dx.doi.org/10.1007/978-3-030-56877-1_17},
author={Lior Rotem and Gil Segev},
year=2020
}