Formal Verification of Modular Multipliers using Symbolic Computer Algebra and Boolean Satisfiability

Description

Modular multipliers are the essential components in cryptography and Residue Number System (RNS) designs. Especially, 2n − 1 and 2n + 1 modular multipliers have gained more attention due to their regular structures and a wide variety of applications. However, there is no automated formal verification method to prove the correctness of these multipliers. As a result, bugs might remain undetected after the design phase. In this paper, we present our modular verifier that combines Symbolic Computer Algebra (SCA) and Boolean Satisfiability (SAT) to prove the correctness of 2n − 1 and 2n + 1 modular multipliers. Our verifier takes advantage of three techniques, i.e. coefficient correction, SAT-based local vanishing removal, and SAT-based output condition check to overcome the challenges of SCA-based verification. The efficiency of our verifier is demonstrated using an extensive set of modular multipliers with up to several million gates.

Period	14 Jul 2022
Event title	Design Automation Conference 2022
Event type	Conference
Location	United StatesShow on map