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

Lior Rotem and Gil Segev

##### 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2020
Keywords
RSAfactoringdelay functionsgeneric ring model
Contact author(s)
lior rotem @ cs huji ac il
History
2021-03-21: revised
See all versions
Short URL
https://ia.cr/2020/812

CC BY

BibTeX

@misc{cryptoeprint:2020/812,
author = {Lior Rotem and Gil Segev},
title = {Generically Speeding-Up Repeated Squaring is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions},
howpublished = {Cryptology ePrint Archive, Paper 2020/812},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/812}},
url = {https://eprint.iacr.org/2020/812}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.