Paper 2024/572
Split Gröbner Bases for Satisfiability Modulo Finite Fields
Abstract
Satisfiability modulo finite fields enables automated verification for cryptosystems. Unfortunately, previous solvers scale poorly for even some simple systems of field equations, in part because they build a full Gröbner basis (GB) for the system. We propose a new solver that uses multiple, simpler GBs instead of one full GB. Our solver, implemented within the cvc5 SMT solver, admits specialized propagation algorithms, e.g., for understanding bitsums. Experiments show that it solves important bitsum-heavy determinism benchmarks far faster than prior solvers, without introducing much overhead for other benchmarks.
Note: Update 1: badges & camera-ready revisions. Update 2: acknowledge CBR.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Minor revision. CAV'24
- Keywords
- zero knowledgeSMTverificationfinite fields
- Contact author(s)
- aozdemir @ cs stanford edu
- History
- 2024-08-26: last of 2 revisions
- 2024-04-15: received
- See all versions
- Short URL
- https://ia.cr/2024/572
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/572,
author = {Alex Ozdemir and Shankara Pailoor and Alp Bassa and Kostas Ferles and Clark Barrett and Işil Dillig},
title = {Split Gröbner Bases for Satisfiability Modulo Finite Fields},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/572},
year = {2024},
url = {https://eprint.iacr.org/2024/572}
}
