Cryptology ePrint Archive: Report 2020/812

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

Category / Keywords: foundations / RSA, factoring, delay functions, generic ring model

Original Publication (with major differences): IACR-CRYPTO-2020

Date: received 30 Jun 2020

Contact author: lior rotem at cs huji ac il

Available format(s): PDF | BibTeX Citation

Version: 20200630:130719 (All versions of this report)

Short URL: ia.cr/2020/812


[ Cryptology ePrint archive ]