Probabilistic Computing Tackles Closest Vector Problem, Enabling Lattice-Based Factoring with 100x Potential

The closest vector problem (CVP) lies at the heart of modern cryptography, forming the basis for the security of many encryption systems and underpinning Schnorr’s lattice-based factoring algorithm, a method that attempts to break RSA encryption. Max O. Al-Hasso and Marko von der Leyen, from Quantum Dice Ltd and the University of Oxford, investigate a novel approach to solving the CVP, leveraging the power of probabilistic computing, a hardware acceleration technique for randomised algorithms. Their work demonstrates that this method efficiently refines approximations to the CVP, achieving a speed-up that allows the team to factor semiprime numbers using significantly fewer computational steps than conventional techniques, potentially offering a substantial advance in the field of cryptographic factoring and lattice-based cryptography. The research establishes a linear relationship between processing time and problem size, and shows that this probabilistic computing approach can achieve up to a hundredfold reduction in the number of lattice instances required for factoring.

Furthermore, Schnorr’s lattice-based factoring algorithm reduces integer factoring, the foundation of current cryptosystems including RSA, to the closest vector problem (CVP). Recent work has investigated incorporating a heuristic CVP approximation ‘refinement’ step into the lattice-based factoring algorithm, using quantum variational algorithms to perform the optimization. This coincides with the emergence of probabilistic computing as a hardware accelerator for randomized algorithms, including tasks in combinatorial optimization. This research investigates applying probabilistic computing to the heuristic optimization task of CVP approximation refinement in lattice-based factoring.

Prime Lattices Enable Scalable CVP Solution

Scientists have achieved a breakthrough in solving the closest vector problem (CVP), a fundamental challenge in lattice-based cryptography and factoring, by applying probabilistic computing techniques. This work demonstrates a novel approach to heuristic optimization, crucial for Schnorr’s lattice-based factoring algorithm, which reduces integer factoring, the basis of current cryptosystems like RSA, to solving multiple instances of the CVP. The team designed a probabilistic computing algorithm capable of finding the maximal available CVP approximation refinement in time that scales linearly with problem size, representing a significant advancement in efficiency. Experiments reveal that this probabilistic computing method, when used with specifically defined ‘prime lattice’ parameters, can locate the composite prime factors of a semiprime number using up to 100times fewer lattice instances than comparable quantum and classical methods.

This improvement stems from the implementation of a virtually connected Boltzmann machine (VCBM), allowing for more expressive calculations than traditional Ising model approaches, while maintaining computational feasibility. The researchers successfully mapped the CVP to a network of probabilistic bits (p-bits), demonstrating the efficacy of probabilistic computing as a combinatorial solver. The team’s approach utilizes p-bits, which represent a state between classical bits and qubits, as random variables with controlled probabilities, enabling a more flexible and efficient search for solutions. The energy function used in the calculations is quadratic, allowing for a direct mapping between the VCBM and more traditional Ising model approaches. This work focuses on improvements to lattice-based factoring and does not claim to surpass the performance of the general number field sieve, the current leading classical algorithm for factoring large integers. However, the results demonstrate a promising pathway for accelerating lattice-based cryptography and potentially enhancing the security of future cryptosystems.

Probabilistic Computing Speeds Lattice-Based Factoring

This work demonstrates the successful application of probabilistic computing to a key challenge in lattice-based cryptography, specifically the closest vector problem (CVP) and its role in factoring numbers. Researchers developed a probabilistic computing algorithm capable of efficiently refining approximate CVP solutions in a time linear to the problem size, representing a significant advancement in this area. Experimental results indicate that this approach requires substantially fewer lattice instances, up to 100times fewer, compared to conventional methods when factoring numbers. The team acknowledges limitations in the lattice-based factoring method itself, noting that the number of lattices needed to find prime factors still increases exponentially with the size of the number being factored.

Future research directions include testing this method on dedicated probabilistic computing hardware, optimizing parameter scaling to minimize computational collisions, and extending the technique to more general instances of the CVP and potentially to lattice-based post-quantum cryptography. Further investigation into techniques for managing the computational cost of the probabilistic bias function as system size increases is also planned. These efforts aim to refine and broaden the applicability of probabilistic computing within the field of cryptographic computation.