Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes

Vitto, Giuseppe

Reference : Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes


	Document type :	E-prints/Working papers : Already available on another site
	Discipline(s) :	Engineering, computing & technology : Computer science
	Focus Areas :	Computational Sciences
	To cite this reference:	http://hdl.handle.net/10993/49472

Title :	Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes
Language :	English
Author, co-author :	Vitto, Giuseppe [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux >]
Publication date :	2021
Peer reviewed :	No
Keywords :	[en] elliptic curves ; complex-multiplication ; backdoor ; semiprime ; certificate ; MPC ; RSA ; ECM
Funders :	Fonds National de la Recherche - FnR
Target :	Researchers
Permalink :	http://hdl.handle.net/10993/49472
Commentary :	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 B, can efficiently retrieve it from N. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes p associated to B-smooth order elliptic curves over Fp. 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 ZN, and with no knowledge other than N and 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.
source URL :	https://eprint.iacr.org/2021/1610
FnR project :	FnR ; FNR11684537 > Alex Biryukov > FinCrypt > Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts > 01/08/2018 > 31/07/2021 > 2017

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Open access	factoring_primes.pdf		Author preprint	464.65 kB	View/Open

All documents in ORBi^lu are protected by a user license.

University of Luxembourg Library | Feedback | Legal notices