SAT and Lattice Reduction for Integer Factorization

• URL: http://arxiv.org/abs/2406.20071v1
• Date: Fri, 28 Jun 2024 17:30:20 GMT
• Title: SAT and Lattice Reduction for Integer Factorization
• Authors: Yameen Ajani, Curtis Bright,
• Abstract summary: 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.
• Score: 5.035245337299788
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The difficulty of factoring large integers into primes is the basis for cryptosystems such as RSA. Due to the widespread popularity of RSA, there have been many proposed attacks on the factorization problem such as side-channel attacks where some bits of the prime factors are available. When enough bits of the prime factors are known, two methods that are effective at solving the factorization problem are satisfiability (SAT) solvers and Coppersmith's method. The SAT approach reduces the factorization problem to a Boolean satisfiability problem, while Coppersmith's approach uses lattice basis reduction. Both methods have their advantages, but they also have their limitations: Coppersmith's method does not apply when the known bit positions are randomized, while SAT-based methods can take advantage of known bits in arbitrary locations, but have no knowledge of the algebraic structure exploited by Coppersmith's method. In this paper we describe a new hybrid SAT and computer algebra approach to efficiently solve random leaked-bit factorization problems. Specifically, Coppersmith's method is invoked by a SAT solver to determine whether a partial bit assignment can be extended to a complete assignment. Our hybrid implementation solves random leaked-bit factorization problems significantly faster than either a pure SAT or pure computer algebra approach.

Related papers

• A Summation-Based Algorithm For Integer Factorization [0.0]
  This paper introduces a new method that converts an integer into a sum in base-2. It plays a crucial role in modern cryptography, notably, in the security of RSA encryption.
  arXiv  Detail & Related papers  (2025-04-29T20:35:43Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• 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)
• Self-Satisfied: An end-to-end framework for SAT generation and prediction [0.7340017786387768]
  We introduce hardware accelerated algorithms for fast SAT problem generation and a geometric SAT encoding. These advances allow us to scale our approach to SAT problems with thousands of variables and tens of thousands of clauses. A fundamental aspect of our work concerns the very nature of SAT data and its suitability for training machine learning models.
  arXiv  Detail & Related papers  (2024-10-18T22:25:54Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  We introduce the notion of decomposition hardness (d-hardness) We show that the d-hardness expresses an estimate of the hardness of $C$ w.r.t.
  arXiv  Detail & Related papers  (2023-12-16T12:44:36Z)
• Machine Learning for SAT: Restricted Heuristics and New Graph Representations [0.8870188183999854]
  SAT is a fundamental NP-complete problem with many applications, including automated scheduling. To solve large instances, SAT solvers have to rely on Booleans, e.g., choosing a branching variable in DPLL and CDCL solvers. We suggest a strategy of making a few initial steps with a trained ML model and then releasing control to classical runtimes.
  arXiv  Detail & Related papers  (2023-07-18T10:46:28Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  We show that the hardness of SAT encodings for LEC instances can be estimated textitw.r.t some SAT partitioning. The paper proposes several methods for constructing partitionings, which, when used in practice, allow one to estimate the hardness of SAT encodings for LEC with good accuracy.
  arXiv  Detail & Related papers  (2022-10-04T09:19:13Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
  optimisation algorithms designed to work on quantum computers have been of research interest in recent years. Many of these solver can only optimise problems that are in binary and quadratic form. There are many optimisation problems that are naturally represented as permutations. We propose new static methods of calculating penalty weights which lead to more promising results.
  arXiv  Detail & Related papers  (2022-06-20T22:00:38Z)
• Integer Factorization with Compositional Distributed Representations [5.119801391862319]
  We present an approach to integer factorization using distributed representations formed with Vector Symbolic Architectures. The approach formulates integer factorization in a manner such that it can be solved using neural networks and potentially implemented on parallel neuromorphic hardware.
  arXiv  Detail & Related papers  (2022-03-02T08:09:17Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems. In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
  arXiv  Detail & Related papers  (2021-07-15T04:47:35Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  We introduce LAW, a new efficient batch acquisition method based on the determinantal point process. We provide a regret analysis for our method to gain insight in its theoretical properties. We evaluate the method on several standard problems involving permutations such as quadratic assignment.
  arXiv  Detail & Related papers  (2021-02-26T10:15:57Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.