Related papers: Generalized Implicit Factorization Problem

Generalized Implicit Factorization Problem

URL: http://arxiv.org/abs/2304.08718v3
Date: Mon, 4 Mar 2024 02:56:04 GMT
Title: Generalized Implicit Factorization Problem
Authors: Yansong Feng, Abderrahmane Nitaj, Yanbin Pan,
Abstract summary: The Implicit Factorization Problem was first introduced by May and Ritzenhofen at PKC'09. We propose a lattice-based algorithm and analyze its efficiency under certain conditions.
Score: 29.650588509354606
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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.

Related papers

Quantum inspired factorization up to 100-bit RSA number in polynomial time [0.0]
We attack the RSA factorization building on Schnorr's mathematical framework. We factorize RSA numbers up to 256 bits encoding the optimization problem in quantum systems. Results do not currently undermine the security of the present communication infrastructure.
arXiv Detail & Related papers (2024-10-21T18:00:00Z)
Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
arXiv Detail & Related papers (2024-08-27T18:28:31Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
SAT and Lattice Reduction for Integer Factorization [5.035245337299788]
We describe a new hybrid SAT and computer algebra approach to solve random leaked-bit factorization problems. Our implementation solves random leaked-bit factorization problems significantly faster than either a pure SAT or pure computer algebra approach.
arXiv Detail & Related papers (2024-06-28T17:30:20Z)
Quantum and Classical Combinatorial Optimizations Applied to Lattice-Based Factorization [0.046040036610482664]
We show that lattice-based factoring does not scale successfully to larger numbers. We consider particular cases of the CVP, and opportunities for applying quantum techniques to other parts of the factorization pipeline.
arXiv Detail & Related papers (2023-08-15T14:31:25Z)
HUBO and QUBO models for Prime factorization [0.0]
The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers p and q satisfying N=p*q. This paper presents a prime factoriaation method using D-Wave quantum computer that can threaten the RSA cryptosystem.
arXiv Detail & Related papers (2023-01-17T07:49:10Z)
End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z)
An Algebraic-Geometry Approach to Prime Factorization [0.0]
New algorithms for prime factorization can have a practical impact on present implementations of cryptographic algorithms. We show that there are varieties whose points can be evaluated efficiently given a number of parameters not greater than n/2. In one case, we show that there are varieties whose points can be evaluated efficiently given a number of parameters not greater than n/2.
arXiv Detail & Related papers (2022-09-23T15:31:07Z)
Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
arXiv Detail & Related papers (2021-07-03T23:17:26Z)
Finite-Function-Encoding Quantum States [52.77024349608834]
We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
arXiv Detail & Related papers (2020-12-01T13:53:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.