Factoring ⇒ Forward-secure signature (Bellare–Miner)
Statement
If factoring Blum integers is hard, then for every polynomially bounded the Bellare–Miner scheme with key components (and -bit challenges) is a forward-secure signature scheme with periods in the random-oracle model — BM99. The scheme is a Fiat–Shamir-type scheme modulo a Blum integer : the secret key is a vector of elements of , and squares each component, so the key of period determines the keys of all later periods, while computing an earlier one requires square roots modulo — BM99. Honest signatures satisfy its verification equation in every period, so it is perfectly correct, and the random oracle hashes the message, so it signs bit strings — standard.