Certifying Variant of RSA with Generalized Moduli

摘要

Let N be an arbitrary integer with unknown factorization. In Asiacrypt 2012, Kakvi et al. proposed an algorithm that, given prime e ≥ N~(1/4) + ε, certifies whether the RSA function RSA_(N,e)(x) := x~e mod N defines a permutation over Z_N~* or not. In this paper, we extend Kakvi et al.'s work by considering the case with generalized moduli N = Π_(i=1)~n p_i~(z_i). Surprisingly, when min{z_1,..., z_n} ≥ 2, we show that it can be efficiently decided whether the RSA function defines a permutation over Z_N~* or not even for the prime e < N~(1/4). Our result can be viewed as an extension of Kakvi et al.'s result.