A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Computer Science > Cryptography and Security [Submitted on 10 Sep 2024 (v1), last revised 15 Apr 2026 (this version, v2)] A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions Gregory Morse, Tamás Kozsik, Oskar Mencer, Peter Rakyta We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around 30 thousands of logical variables. Comments: 16 pages, 3 tables, 48 equations Subjects: Cryptography and Security (cs.CR); Mathematical Physics (math-ph); Quantum Physics (quant-ph) MSC classes: 68Q25 (Primary) 68R05, 94A60, 90C20 (Secondary) ACM classes: F.2.2; G.2.1; E.3; F.1.2 Cite as: arXiv:2409.07501 [cs.CR]   (or arXiv:2409.07501v2 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2409.07501 Focus to learn more Submission history From: Gregory Morse [view email] [v1] Tue, 10 Sep 2024 18:46:26 UTC (102 KB) [v2] Wed, 15 Apr 2026 14:35:35 UTC (102 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2024-09 Change to browse by: cs math math-ph math.MP quant-ph References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)