Paper 2023/1562 Original: eprint.iacr.org/2023/1562 ↗
Generalized Implicit Factorization Problem
Abstract
The Implicit Factorization Problem (IFP) was first introduced by May and Ritzenhofen at PKC'09, which concerns the factorization of two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$, where $p_1$ and $p_2$ share a certain consecutive number of least significant bits. Since its introduction, many different variants of IFP have been considered, such as the cases where $p_1$ and $p_2$ share most significant bits or middle bits at the same positions. In this paper, we consider a more generalized case of IFP, in which the shared consecutive bits can be located at $any$ positions in each prime, not necessarily required to be located at the same positions as before. We propose a lattice-based algorithm to solve this problem under specific conditions, and also provide some experimental results to verify our analysis.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2024-03-04: last updated
- 2023-10-11: published
- Short URL
- https://ia.cr/2023/1562
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/1562,
author = {Yansong Feng and Abderrahmane Nitaj and Yanbin Pan},
title = {Generalized Implicit Factorization Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1562},
year = {2023},
url = {https://eprint.iacr.org/2023/1562}
}