Sequential squaring ⇒ FAC

Fully-black-box reduction · standard model · RSW96 · security loss: tight: one factoring call; the squaring adversary succeeds whenever the factoring algorithm does

Statement

If sequential squaring holds for with some gap , then factoring the moduli that outputs is hard, since the factors of give and with it in time — RSW96.

Sketch

Given , run the factoring algorithm on ; on a factor , set , compute with multiplications, and output , which equals because . The factoring algorithm has polynomial size, hence depth at most some polynomial , and the rest has depth ; for every polynomial with above this total, the adversary has depth at most and succeeds whenever factoring does.

Notes