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

Thursday, March 30, 2023 - 14:00 to 15:30


The School of Computer Science is pleased to present...

MSc Thesis Proposal by: Yameen Ajani 

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

MSc Thesis Proposal Announcement

Vector Institute in Artificial Intelligence, artificial intelligence approved topic logo

5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716