SAT Solving Using XOR-OR-AND Normal Forms
Open Access
- 24 October 2024
- journal article
- research article
- Published by Springer Nature in Mathematics in Computer Science
- Vol. 18 (4) , 1-26
Abstract
This paper introduces the XOR-OR-AND normal form (XNF) for logical formulas. It is a generalization of the well-known Conjunctive Normal Form (CNF) where literals are replaced by XORs of literals. As a first theoretic result, we show that every CNF formula is equisatisfiable to a formula in 2-XNF, i.e., a formula in XNF where each clause involves at most two XORs of literals. Subsequently, we present an algorithm which converts Boolean polynomials efficiently from their Algebraic Normal Form (ANF) to formulas in 2-XNF. Experiments with the cipher ASCON-128 show that cryptographic problems, which by design are based strongly on XOR-operations, can be represented using far fewer variables and clauses in 2-XNF than in CNF. In order to take advantage of this compact representation, new SAT solvers based on input formulas in 2-XNF need to be designed. By taking inspiration from graph-based 2-CNF SAT solving, we devise a new DPLL-based SAT solver for formulas in 2-XNF. Among others, we present advanced pre- and in-processing techniques. Finally, we give timings for random 2-XNF instances and instances related to key recovery attacks on round reduced ASCON-128, where our solver outperforms state-of-the-art alternative solving approaches.Keywords
All Related Versions
Funding Information
- Universität Passau
This publication has 34 references indexed in Scilit:
- CaDiCaL 2.02024
- An Efficient Key Recovery Attack on SIDH2023
- Autoguess: A Tool for Finding Guess-and-Determine Attacks and Key Bridges2022
- XOR Local Search for Boolean Brent Equations2021
- Parity (XOR) Reasoning for the Index Calculus Attack2020
- Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC2019
- Extending SAT Solvers to Cryptographic Problems2009
- Applications of SAT Solvers to Cryptanalysis of Hash Functions2006
- Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations2000
- Computational Commutative Algebra 12000