Welcome to the resource topic for 2021/1610
Title:
Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes
Authors: Giuseppe Vitto
Abstract:We describe a technique to backdoor a prime factor of a composite odd integer N, so that an attacker knowing a possibly secret factor base \mathcal{B}, can efficiently retrieve it from N. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes p associated to \mathcal{B}-smooth order elliptic curves over \mathbb{F}_p. When such primes p divide an integer N, the latter can be efficiently factored using a generalization of Lenstra’s Factorization Method over rings bigger than \mathbb{Z}_N, and with no knowledge other than N and \mathcal{B}. We then formalize semiprimality certificates that, based on a result by Goldwasser and Kilian, allow to prove semiprimality of an integer with no need to reveal any of its factors. We show how our prime generation procedure can be used to efficiently produce semiprimality certificates, ultimately allowing us to sketch a multi-party distributed protocol to generate semiprimes with unknown factorisation, particularly relevant in the setting of distributed RSA modulus generation. We provide and discuss implementations of all proposed protocols and we address security of semiprimality certificates by showing that semiprimes generated within our methods result at least as secure as random semiprimes of same size.
ePrint: https://eprint.iacr.org/2021/1610
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .