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

Beschreibung

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.

Zeitraum	14 Juli 2022
Ereignistitel	Design Automation Conference 2022
Veranstaltungstyp	Konferenz
Ort	USA/Vereinigte StaatenAuf Karte anzeigen