Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2304.08718 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914700300648448 |
|---|---|
| author | Feng, Yansong Nitaj, Abderrahmane Pan, Yanbin |
| author_facet | Feng, Yansong Nitaj, Abderrahmane Pan, Yanbin |
| contents | The Implicit Factorization Problem was first introduced by May and Ritzenhofen at PKC'09. This problem aims to factorize two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$ when their prime factors share a certain number of least significant bits (LSBs). They proposed a lattice-based algorithm to tackle this problem and extended it to cover $k>2$ RSA moduli. Since then, several variations of the Implicit Factorization Problem have been studied, including the cases where $p_1$ and $p_2$ share some most significant bits (MSBs), middle bits, or both MSBs and LSBs at the same position.
In this paper, we explore a more general case of the Implicit Factorization Problem, where the shared bits are located at different and unknown positions for different primes. We propose a lattice-based algorithm and analyze its efficiency under certain conditions. We also present experimental results to support our analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_08718 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generalized Implicit Factorization Problem Feng, Yansong Nitaj, Abderrahmane Pan, Yanbin Cryptography and Security The Implicit Factorization Problem was first introduced by May and Ritzenhofen at PKC'09. This problem aims to factorize two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$ when their prime factors share a certain number of least significant bits (LSBs). They proposed a lattice-based algorithm to tackle this problem and extended it to cover $k>2$ RSA moduli. Since then, several variations of the Implicit Factorization Problem have been studied, including the cases where $p_1$ and $p_2$ share some most significant bits (MSBs), middle bits, or both MSBs and LSBs at the same position. In this paper, we explore a more general case of the Implicit Factorization Problem, where the shared bits are located at different and unknown positions for different primes. We propose a lattice-based algorithm and analyze its efficiency under certain conditions. We also present experimental results to support our analysis. |
| title | Generalized Implicit Factorization Problem |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2304.08718 |