MSc Thesis Proposal Announcement of Yameen Ajani:"A Hybrid SAT and Lattice Reduction Approach for Integer Factorization"

 

Date: Thursday March 30, 2023 

Time:  2:00 PM - 3:30 PM 

Location: Essex Hall, Room 122 

Reminders: 1. Two-part attendance mandatory (sign-in sheet, QR Code) 

2. Arrive 5-10 minutes prior to event starting - LATECOMERS WILL NOT BE ADMITTED. Note that due to demand, if the room has reached capacity, even if you are "early" admission is not guaranteed. 

3. Please be respectful of the presenter by NOT knocking on the door for admittance once the door has been closed whether the presentation has begun or not (If the room is at capacity, overflow is not permitted (ie. sitting on floors) as this is a violation of the Fire Safety code). 

4. Be respectful of the decision of the advisor/host of the event if you are not given admittance. The School of Computer Science has numerous events occurring soon. 

 

 

Integer factorization is a very famous problem in the mathematics and computer science community. The difficulty of factoring large integers, especially semi-primes, is the basis for a lot of cryptosystems like RSA. Satisfiablity (SAT) based integer factorization has been used to factor relatively small integers. However, the search space of the SAT problem grows exponentially with the number of bits making it difficult to factorize large integers using SAT solvers. Nonetheless, the use of SAT in side-channel attacks on cryptosystems where some bits of the private key are available has shown promising results. Another powerful factorization method is Coppersmith’s algorithm which uses lattice basis reduction to factor the integer in polynomial time when enough high or low bits of one of the factors is known. While both methods have their own advantages, they also have limitations that restrict their applicability to specific scenarios. This research is the first attempt to explore the potential of using a novel hybrid approach in which SAT solvers are employed for situations where the leaked bit positions are randomized. Specifically, Coppersmith's algorithm is invoked by the SAT solver to determine whether a partial bit assignment can be extended to a complete assignment. The research also evaluates the approach’s effectiveness in comparison with other well-known factorization techniques. 

 

Keywords: Factoring, SAT, Lattice Reduction, Cryptography, RSA, Coppersmith 

 

MSc Thesis Committee:

Internal Reader: Dr. Ahmad Biniaz

External Reader: Dr. Ilya Shapiro    

Advisor: Dr. Curtis Bright