pith. sign in

arxiv: 2409.07501 · v2 · submitted 2024-09-10 · 💻 cs.CR · math-ph· math.MP· quant-ph

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

Gregory Morse , Tam\'as Kozsik , Oskar Mencer , Peter Rakyta This is my paper

Pith reviewed 2026-05-23 20:30 UTC · model grok-4.3

classification 💻 cs.CR math-phmath.MPquant-ph
keywords QUBO encodingcryptographyAESinteger linear programmingboolean logicquantum annealingvariable reductionnormal forms
0
0 comments X

The pith

ILP solutions for normal-form coefficients produce QUBO encodings with thousands fewer variables for AES and other cryptos.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a systematic way to convert logic formulas such as ANF and DNF into QUBO form by solving integer linear programs for their integer coefficients, including substitutions for multi-input gates. Applied to full AES-128/192/256, MD5, SHA1 and SHA256 circuits, the resulting QUBO instances contain thousands fewer binary variables than earlier published encodings while remaining sparse and using small coefficients. A sympathetic reader would care because the size reduction directly lowers the hardware threshold at which a quantum annealer could embed and attack these standard cryptographic constructions.

Core claim

Solving ILP problems to obtain minimal integer coefficients for ANF/DNF representations or multi-input AND/OR/XOR substitutions yields valid QUBO encodings. For AES-256 this produces more than an 8x reduction in the number of logical variables compared with prior results, with comparable large savings for the other listed algorithms, while the QUBO matrix stays sparse and coefficient magnitudes remain low.

What carries the argument

Integer linear programming solutions for the integer coefficients of algebraic normal form, disjunctive normal form, or multi-input gate substitutions that directly define the quadratic terms of a QUBO matrix.

If this is right

  • AES-256 requires more than eight times fewer binary variables than previous QUBO encodings.
  • MD5, SHA1 and SHA256 each lose thousands of logical variables in their QUBO forms.
  • The resulting matrices remain sparse with low-magnitude coefficients.
  • Cryptographic functions become solvable by quantum annealers limited to roughly 30,000 embeddable variables.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same ILP coefficient search can be applied to any boolean constraint set that appears in combinatorial optimization.
  • Classical branch-and-bound or SAT solvers may also run faster on the reduced-variable QUBOs for medium-sized crypto instances.
  • If annealing hardware capacity grows, the demonstrated size reductions would accelerate the timeline for practical attacks on these algorithms.

Load-bearing premise

The ILP-derived coefficients produce QUBO encodings that faithfully represent the original logic formulas without introducing extra solutions or requiring later corrections.

What would settle it

Solve the new compact QUBO instance for a single known AES S-box or round function on a classical solver or annealer and verify that every solution matches an input-output pair permitted by the original boolean circuit.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims that minimal QUBO encodings for boolean logic (ANF, DNF, and multi-input AND/OR/XOR substitutions) can be obtained by solving ILP problems for integer coefficients of quadratic penalty terms, and applies this to produce compact QUBO formulations of AES-128/192/256, MD5, SHA1 and SHA256. It reports reductions of thousands of logical variables relative to prior published encodings (including >8x for AES-256), while preserving sparsity and bounded coefficient magnitudes, thereby increasing the feasibility of attacking these constructions on quantum annealers limited to ~30k variables.

Significance. If the ILP-derived encodings are shown to be correct (i.e., their ground states coincide exactly with the solutions of the original boolean formulae), the reported size reductions would be a concrete advance for quantum-annealing cryptanalysis and for general QUBO modeling of circuit constraints. The approach of treating coefficient search as an external ILP against standard logic specifications is a methodological strength that could be reused beyond cryptography.

major comments (2)
  1. [Abstract] Abstract: the central claim of 'valid' minimal encodings that achieve >8x variable reduction for AES-256 (and thousands of variables for the other primitives) rests on ILP solutions, yet the manuscript supplies no verification data, error bounds, comparison tables, or independent checks (exhaustive enumeration on small gates, symbolic equivalence, or explicit positivity constraints on invalid assignments). Without such evidence it is impossible to confirm that the obtained quadratic forms introduce no extraneous solutions.
  2. [Method section (ILP formulation)] The ILP formulation (described in the method for ANF/DNF and multi-input gate substitutions) minimizes variable count and coefficient magnitude but, on the evidence of the abstract, does not state an explicit constraint that the resulting quadratic form equals zero on all valid assignments and is strictly positive on all invalid ones; this constraint is load-bearing for the correctness of every reported reduction.
minor comments (1)
  1. [Abstract] The abstract would benefit from a brief statement of the largest benchmark instance size and the solver used for the ILP step.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and for identifying the need to strengthen the presentation of correctness guarantees. We agree that explicit verification and formulation details are essential for the claims regarding minimal QUBO encodings. Below we respond point-by-point to the major comments and outline the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim of 'valid' minimal encodings that achieve >8x variable reduction for AES-256 (and thousands of variables for the other primitives) rests on ILP solutions, yet the manuscript supplies no verification data, error bounds, comparison tables, or independent checks (exhaustive enumeration on small gates, symbolic equivalence, or explicit positivity constraints on invalid assignments). Without such evidence it is impossible to confirm that the obtained quadratic forms introduce no extraneous solutions.

    Authors: We acknowledge that the current manuscript does not provide explicit verification data, error bounds, or independent checks (such as exhaustive enumeration on small gates or symbolic equivalence) to confirm that the ILP-derived quadratic forms are zero on valid assignments and strictly positive on invalid ones. This is a substantive gap. In the revised manuscript we will add a new subsection on verification that includes: (i) exhaustive enumeration results for small ANF/DNF instances and multi-input gates, (ii) explicit tables comparing variable counts and coefficient magnitudes against prior encodings, and (iii) a description of how the ILP objective and constraints ensure no extraneous solutions. We will also report any numerical tolerances or bounds used in the ILP solver. revision: yes

  2. Referee: [Method section (ILP formulation)] The ILP formulation (described in the method for ANF/DNF and multi-input gate substitutions) minimizes variable count and coefficient magnitude but, on the evidence of the abstract, does not state an explicit constraint that the resulting quadratic form equals zero on all valid assignments and is strictly positive on all invalid ones; this constraint is load-bearing for the correctness of every reported reduction.

    Authors: The referee is correct that the ILP formulation, as currently described, does not explicitly articulate the constraints enforcing that the quadratic penalty equals zero on valid assignments and is strictly positive on invalid assignments. While the overall approach relies on these properties, they are not stated as formal ILP constraints in the method section. We will revise the method section to present the complete ILP model, explicitly including the equality and positivity constraints (or their equivalent penalty-term conditions) for each logic form (ANF, DNF, and multi-input substitutions). This will make the correctness argument self-contained and directly address the load-bearing requirement. revision: yes

Circularity Check

0 steps flagged

No significant circularity; ILP-based QUBO derivation is independent computation

full rationale

The paper presents QUBO encodings as the output of an external ILP solver applied to standard ANF/DNF representations of boolean logic in crypto primitives. This is a computational minimization against fixed logic specifications rather than any self-definitional loop, fitted input renamed as prediction, or load-bearing self-citation chain. No equations or steps in the abstract reduce the claimed variable-count reductions to tautological inputs or prior author results by construction. The method remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review prevents exhaustive ledger; the approach rests on standard ILP solvability and the assumption that QUBO equivalence can be certified by coefficient search alone.

axioms (1)
  • domain assumption Integer linear programming can be solved to global optimality for the coefficient search problems arising from logic normal forms.
    Invoked when the paper states that minimal QUBO encodings emerge as solutions of ILP problems.

pith-pipeline@v0.9.0 · 5745 in / 1172 out tokens · 23464 ms · 2026-05-23T20:30:47.399944+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

84 extracted references · 84 canonical work pages · 5 internal anchors

  1. [1]

    S. A. Cook, The complexity of theorem-proving proce- dures, in: Proceedings of the Third Annual ACM Sym- posium on Theory of Computing, STOC ’71, Association for Computing Machinery, New Y ork, NY , USA, 1971, p. 151–158. URL: https://doi.org/10.1145/800157.805047. doi:10.1145/800157.805047

    work page doi:10.1145/800157.805047 1971

  2. [2]

    Applegate, R

    D. Applegate, R. Bixby, V . Chv´ atal, W. Cook, The Travel- ing Salesman Problem: A Computational Study, Princeton Ser ies in Applied Mathematics, Princeton University Press, 2011. URL: https://books.google.hu/books?id=zfIm94nNqPoC

    work page 2011

  3. [3]

    A. L. Blum, R. L. Rivest, Training a 3-node neural network is np-complete, Neural Networks 5 (1992) 117–127. URL: https://www.sciencedirect.com/science/article/pii/S0893608005800103. doi:https://doi.org/10.1016/S0893-6080(05)80010-3

    work page doi:10.1016/s0893-6080(05)80010-3 1992

  4. [4]

    Dasgupta, The Hardness of K-means Clustering, Techni cal re- port (University of California, San Diego

    S. Dasgupta, The Hardness of K-means Clustering, Techni cal re- port (University of California, San Diego. Department of Co m- puter Science and Engineering), Department of Computer Sci ence and Engineering, University of California, San Diego, 2008 . URL: https://books.google.hu/books?id=riJuAQAACAAJ

    work page 2008

  5. [5]

    Glover, Future paths for integer programming and link s to artificial in- telligence, Computers & Operations Research 13 (1986) 533– 549

    F. Glover, Future paths for integer programming and link s to artificial in- telligence, Computers & Operations Research 13 (1986) 533– 549. URL: https://www.sciencedirect.com/science/article/pii/0305054886900481. doi:https://doi.org/10.1016/0305-0548(86)90048-1, applica- tions of Integer Programming

    work page doi:10.1016/0305-0548(86)90048-1 1986

  6. [6]

    M. L. Fred Glover, Extending SA T solvers to cryptographi c problems, in: Tabu Search, Springer New Y ork, NY , 1997. URL: https://doi.org/10.1007/978-1-4615-6089-0 . doi:doi.org/10.1007/978-1-4615-6089-0

    work page doi:10.1007/978-1-4615-6089-0 1997

  7. [7]

    Kirkpatrick, B

    S. Kirkpatrick, B. Selman, Critical behavior in the sati sfiability of random boolean expressions, Science 264 (1994) 1297–1301. URL: https://www.science.org/doi/abs/10.1126/science.264.5163.1297. doi:10.1126/science.264.5163.1297. arXiv:https://www.science.org/doi/pdf/10.1126/science.264.5163.1297

    work page doi:10.1126/science.264.5163.1297 1994

  8. [8]

    T. Graß, D. Ravent´ os, B. Juli´ a-D´ ıaz, C. Gogolin, M. Lewenstein, Quan- tum annealing for the number-partitioning problem using a t unable spin glass of ions, Nat Commun 7 (2016) 11524

    work page 2016

  9. [9]

    Quantum Annealing Implementation of Job-Shop Scheduling

    D. V enturelli, D. J. J. Marchand, G. Rojo, Quantum anneal ing implemen- tation of job-shop scheduling, 2016. arXiv:1506.08479

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  10. [10]

    Rosenberg, P

    G. Rosenberg, P . Haghnegahdar, P . Goddard, P . Carr, K. W u, M. L. de Prado, Solving the optimal trading trajectory probl em using a quantum annealer, in: Proceedings of the 8th Work- shop on High Performance Computational Finance, WHPCF ’15, Association for Computing Machinery, New Y ork, NY , USA,

    work page

  11. [11]

    doi:10.1145/2830556.2830563

    URL: https://doi.org/10.1145/2830556.2830563. doi:10.1145/2830556.2830563

    work page doi:10.1145/2830556.2830563

  12. [12]

    Dridi, H

    R. Dridi, H. Alghassi, Prime factorization using quant um an- nealing and computational algebraic geometry, Scientific R e- ports 7 (2017) 43048. URL: https://doi.org/10.1038/srep43048. doi:10.1038/srep43048

    work page doi:10.1038/srep43048 2017

  13. [13]

    Quantum Annealing for Prime Factorization

    S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, S. Kai s, Quantum annealing for prime factorization, 2018. arXiv:1804.02733

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  14. [14]

    Perdomo-Ortiz, J

    A. Perdomo-Ortiz, J. Fluegemann, S. Narasimhan, R. Bis was, V . N. Smelyanskiy, A quantum annealing approach for fault detection and diagnosis of graph-based systems, The Eu- ropean Physical Journal Special Topics 224 (2015) 131–148. URL: https://doi.org/10.1140/epjst/e2015-02347-y. doi:10.1140/epjst/e2015-02347-y

    work page doi:10.1140/epjst/e2015-02347-y 2015

  15. [15]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgre n, D. Preda, A quantum adiabatic evolution algorithm applied to random i n- stances of an np-complete problem, Science 292 (2001) 472–4 75. URL: https://www.science.org/doi/abs/10.1126/science.1057726. doi:10.1126/science.1057726. arXiv:https://www.science.org/doi/pdf/10

    work page doi:10.1126/science.1057726 2001

  16. [16]

    ˇS˚ ucha, Z

    P . ˇS˚ ucha, Z. Hanz´ alek, Scheduling of a lq con- trol algorithm for e fficient fpga implementation, IFAC Proceedings V olumes 41 (2008) 5770–5775. URL: https://www.sciencedirect.com/science/article/pii/S14746670163986 doi:https://doi.org/10.3182/20080706-5-KR-1001.00973 , 17th IFAC World Congress

    work page doi:10.3182/20080706-5-kr-1001.00973 2008

  17. [17]

    W.-K. Mak, Modern fpga constrained placement, in: Proc eedings of the 2005 Asia and South Pacific Design Automation Conference, AS P-DAC ’05, Association for Computing Machinery, New Y ork, NY , USA , 2005, p. 779–784. URL: https://doi.org/10.1145/1120725.1121016. doi:10.1145/1120725.1121016

    work page doi:10.1145/1120725.1121016 2005

  18. [18]

    Rakhshanfar, J

    A. Rakhshanfar, J. H. Anderson, An integer programming placement approach to fpga clock power reduction, in: 16th Asia and Sou th Pacific Design Automation Conference (ASP-DAC 2011), 2011, pp. 831 –836. doi:10.1109/ASPDAC.2011.5722305

    work page doi:10.1109/aspdac.2011.5722305 2011

  19. [19]

    D. Abts, J. Ross, J. Sparling, M. Wong-V anHaren, M. Bake r, T. Hawkins, A. Bell, J. Thompson, T. Kahsai, G. Kimmell, J. Hwang, R. Lesl ie-Hurd, M. Bye, E. Creswick, M. Boyd, M. V enigalla, E. Laforge, J. Purdy, P . Ka- math, D. Maheshwari, M. Beidler, G. Rosseel, O. Ahmad, G. Gag arin, R. Czekalski, A. Rane, S. Parmar, J. Werner, J. Sproch, A. Mac ias, B...

    work page doi:10.1109/isca45697.2020.00023 2020

  20. [20]

    D. Abts, G. Kimmell, A. Ling, J. Kim, M. Boyd, A. Bitar, S. Par- mar, I. Ahmed, R. DiCecco, D. Han, J. Thompson, M. Bye, J. Hwan g, J. Fowers, P . Lillian, A. Murthy, E. Mehtabuddin, C. Tekur, T . Sohmers, K. Kang, S. Maresh, J. Ross, A software-defined tensor stream ing mul- tiprocessor for large-scale machine learning, in: Proceed ings of the 49th Annual...

    work page doi:10.1145/3470496.3527405 2022

  21. [21]

    The unconstrained binary quadratic programming problem: a survey.Journal of Combinatorial Optimization, 28:58–81, 2014

    G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. L ¨ u, H. Wang, Y . Wang, The unconstrained binary quadratic programming pr ob- lem: a survey, Journal of Combinatorial Optimization 28 (20 14) 58–81. URL: https://doi.org/10.1007/s10878-014-9734-0 . doi:10.1007/s10878-014-9734-0

    work page doi:10.1007/s10878-014-9734-0

  22. [22]

    Glover, G

    F. Glover, G. Kochenberger, R. Hennig, Y . Du, Quantum bridge analytics i: a tutorial on formulating and using qubo models, Annals of Operations Research 314 (2022) 141–183. URL: https://doi.org/10.1007/s10479-022-04634-2 . doi:10.1007/s10479-022-04634-2

    work page doi:10.1007/s10479-022-04634-2 2022

  23. [23]

    A tutorial on formulating and using qubo models

    F. Glover, G. Kochenberger, Y . Du, A tutorial on formula ting and using qubo models, 2019. arXiv:1811.11538

    work page arXiv 2019

  24. [24]

    G. J. Mooney, S. U. Tonetto, C. D. Hill, L. C. L. Hollen- berg, Mapping np-hard problems to restricted adiabatic qua n- tum architectures, arXiv: Quantum Physics (2019). URL: https://api.semanticscholar.org/CorpusID:207863414

    work page 2019

  25. [25]

    Chancellor, S

    N. Chancellor, S. Zohren, P . A. Warburton, S. C. Benjami n, S. Roberts, A direct mapping of max k-sat and high order parity checks to a chimera graph, Scientific Reports 6 (2016) 37107. URL: https://doi.org/10.1038/srep37107. doi: 10.1038/srep37107

    work page doi:10.1038/srep37107 2016

  26. [26]

    C. C. McGeoch, Adiabatic quantum computation and quan- tum annealing: Theory and practice, in: Adiabatic Quan- tum Computation and Quantum Annealing, 2014. URL: https://api.semanticscholar.org/CorpusID:13341621

    work page 2014

  27. [27]

    C. C. Chang, C.-C. Chen, C. Koerber, T. S. Humble, J. Ostr owski, Integer programming from quantum annealing and open quantum system s, 2020. arXiv:2009.11970

    work page arXiv 2020

  28. [28]

    N¨ ußlein, T

    J. N¨ ußlein, T. Gabor, C. Linnhoff-Popien, S. Feld, Algorithmic qubo for- mulations for k-sat and hamiltonian cycles, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22, Association for Computing Machinery, New Y ork, NY , USA, 202 2, p. 2240–2246. URL: https://doi.org/10.1145/3520304.3533952. doi:10.1145/3520304.3...

    work page doi:10.1145/3520304.3533952

  29. [29]

    Z. Bian, F. Chudak, W. Macready, A. Roy, R. Sebas- tiani, S. V arotti, Solving sat (and maxsat) with a quan- tum annealer: Foundations, encodings, and preliminary re- sults, Information and Computation 275 (2020) 104609. URL: https://www.sciencedirect.com/science/article/pii/S0890540120300973. doi:https://doi.org/10.1016/j.ic.2020.104609

    work page doi:10.1016/j.ic.2020.104609 2020

  30. [30]

    H. N. Djidjev, G. Chapuis, G. Hahn, G. Rizk, E fficient combinatorial op- timization using quantum annealing, 2018. arXiv:1801.08653

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  31. [31]

    V . S.-N. Choi, Adiabatic quantum algorithms for the np- complete maximum-weight independent set, exact cover and 3sat problems, ArXiv abs /1004.2226 (2010). URL: https://api.semanticscholar.org/CorpusID:18906380

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  32. [32]

    H. N. Djidjev, Quantum annealing with inequality const raints: the set cover problem, 2023. arXiv:2302.11185

    work page arXiv 2023

  33. [33]

    Lucas, Frontiers in Physics2 (2014), 10.3389/fphy.2014.00005, arXiv:1302.5843

    A. Lucas, Ising formulations of many np prob- lems, Frontiers in Physics 2 (2014). URL: https://www.frontiersin.org/articles/10.3389/fphy.2014.00005. doi:10.3389/fphy.2014.00005

    work page doi:10.3389/fphy.2014.00005 2014

  34. [34]

    Zhang, G

    J. Zhang, G. Lo Bianco, J. C. Beck, Solving job-shop scheduling problems with qubo-based specialized hard- ware, Proceedings of the International Conference on Au- tomated Planning and Scheduling 32 (2022) 404–412. URL: https://ojs.aaai.org/index.php/ICAPS/article/view/19826. doi:10.1609/icaps.v32i1.19826

    work page doi:10.1609/icaps.v32i1.19826 2022

  35. [35]

    Encoding Cryptographic Functions to SAT Using Transalg System

    I. Otpuschennikov, A. Semenov, I. Gribanova, O. Zaikin , S. Kochema- zov, Encoding cryptographic functions to sat using transalg system, 2016. arXiv:1607.00888

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  36. [36]

    Burek, M

    E. Burek, M. Wro´ nski, K. Ma´ nk, M. Misztal, Algebraic attacks on block ciphers using quantum annealing, IEEE Transactions on Emerging Topics in Computing 10 (2022) 678–689. doi: 10.1109/TETC.2022.3143152

    work page doi:10.1109/tetc.2022.3143152 2022

  37. [37]

    A. I. Pakhomchik, V . V . V oloshinov, V . M. Vinokur, G. B. Lesovik, Converting of boolean expression to linear equati ons, inequalities and qubo penalties for cryptanalysis, Algori thms 15 (2022). URL: https://www.mdpi.com/1999-4893/15/2/33. doi:10.3390/a15020033

    work page doi:10.3390/a15020033 2022

  38. [38]

    Lafitte, Cryptosat: a tool for sat-based cryptanaly- sis, IET Information Security 12 (2018) 463–474

    F. Lafitte, Cryptosat: a tool for sat-based cryptanaly- sis, IET Information Security 12 (2018) 463–474. URL: https://ietresearch.onlinelibrary.wiley.com/doi/abs/10.1049/iet-ifs.2017.0176. doi:https://doi.org/10.1049/iet-ifs.2017.0176. arXiv:https://ietresearch.onlinelibrary.wiley.com/doi/pdf/10.1049/iet-ifs.2017.0176

    work page doi:10.1049/iet-ifs.2017.0176 2018

  39. [39]

    Massacci, L

    F. Massacci, L. Marraro, Logical cryptanalysis as a sat problem, Journal of Automated Reasoning 24 (2000) 165–

    work page 2000

  40. [40]

    doi:10.1023/A:1006326723002

    URL: https://doi.org/10.1023/A:1006326723002. doi:10.1023/A:1006326723002

    work page doi:10.1023/a:1006326723002

  41. [41]

    Lafitte, J

    F. Lafitte, J. Nakahara Jr, D. V an Heule, Applications of sat solvers in cryptanalysis: Finding weak keys and preimages, Journal on Sat- isfiability, Boolean Modeling and Computation 9 (2014) 1–25 . URL: https://doi.org/10.3233/SAT190099. doi: 10.3233/SAT190099, 1

    work page doi:10.3233/sat190099 2014

  42. [42]

    S. A. Cook, The complexity of theorem-proving procedur es, Proceedings of the third annual ACM symposium on Theory of computing (197 1). URL: https://api.semanticscholar.org/CorpusID:7573663

    work page

  43. [43]

    G. S. Tseitin, On the complexity of deriva- tion in propositional calculus, 1983. URL: https://api.semanticscholar.org/CorpusID:123007433

    work page 1983

  44. [44]

    Mironov, L

    I. Mironov, L. Zhang, Applications of sat solvers to cry ptanalysis of hash functions, in: A. Biere, C. P . Gomes (Eds.), Theory and Appli cations of Satisfiability Testing - SA T 2006, Springer Berlin Heidel berg, Berlin, Heidelberg, 2006, pp. 102–115

    work page 2006

  45. [45]

    Legendre, G

    F. Legendre, G. Dequen, M. Krajecki, Logical reasoning to detect weaknesses about sha-1 and md4 /5, Cryptology ePrint Archive, Pa- per 2014 /239, 2014. URL: https://eprint.iacr.org/2014/239, https://eprint.iacr.org/2014/239

    work page 2014

  46. [46]

    D. De, A. Kumarasubramanian, R. V enkatesan, Inversion attacks on se- cure hash functions using sat solvers, in: J. Marques-Silva, K. A. Sakallah (Eds.), Theory and Applications of Satisfiability Testing – SA T 2007, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 377–382

    work page 2007

  47. [47]

    M. Soos, K. Nohl, C. Castelluccia, Extending SA T solver s to cryp- tographic problems, in: O. Kullmann (Ed.), Theory and Appli ca- tions of Satisfiability Testing - SA T 2009, 12th International Conference, SA T 2009, Swansea, UK, June 30 - July 3, 2009. Proceedings, vo lume 5584 of Lecture Notes in Computer Science , Springer, 2009, pp. 244–

    work page 2009

  48. [48]

    doi:10.1007/978-3-642-02777-2\_24

    URL: https://doi.org/10.1007/978-3-642-02777-2_24 . doi:10.1007/978-3-642-02777-2\_24

    work page doi:10.1007/978-3-642-02777-2_24

  49. [49]

    D. Choo, M. Soos, K. M. A. Chai, K. S. Meel, Bosphorus: Bri dg- ing anf and cnf solvers, in: 2019 Design, Automation & Test in Europe Conference & Exhibition (DA TE), 2019, pp. 468–473 . doi:10.23919/DATE.2019.8715061

    work page doi:10.23919/date.2019.8715061 2019

  50. [50]

    Kurin, S

    V . Kurin, S. Godil, S. Whiteson, B. Catanzaro, Improv- ing sat solver heuristics with graph networks and rein- forcement learning, ArXiv abs /1909.11830 (2019). URL: https://api.semanticscholar.org/CorpusID:202888711

    work page arXiv 1909

  51. [51]

    Zielinski, J

    S. Zielinski, J. N¨ ußlein, J. Stein, T. Gabor, C. Linnho ff-Popien, S. Feld, Influence of di fferent 3sat-to-qubo transformations on the solution quality of quantum annealing: A benchmark study, in: Proceedings of the Companion Conference on Ge- netic and Evolutionary Computation, GECCO ’23 Companion, A s- sociation for Computing Machinery, New Y ork, NY , ...

    work page doi:10.1145/3583133.3596330 2023

  52. [52]

    Glover, G

    F. Glover, G. Kochenberger, B. Alidaee, M. Amini, Solv- ing Quadratic Knapsack Problems by Reformulation and Tabu Search: Single Constraint Case, ????, pp. 111–121. URL: https://www.worldscientific.com/doi/abs/10.1142/9789812778215_000 doi:10.1142/9789812778215_0008. arXiv:https://www.worldscientific.com

    work page doi:10.1142/9789812778215_000

  53. [53]

    V erma, M

    A. V erma, M. Lewis, Penalty and partitioning tech- niques to improve performance of qubo solvers, Discrete Optimization 44 (2022) 100594. URL: https://www.sciencedirect.com/science/article/pii/S15725286203002 doi:https://doi.org/10.1016/j.disopt.2020.100594, quadratic Combinatorial Optimization Problems

    work page doi:10.1016/j.disopt.2020.100594 2022

  54. [55]

    P . Codognet, Encoding the at-most-one constraint for q ubo and quantum annealing: Experiments with the n-queens prob- lem, in: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, GECCO ’23 Companion, Associ a- tion for Computing Machinery, New Y ork, NY , USA, 2023, p. 2195–2202. URL: https://doi.org/10.1145/3583133.3596394. ...

    work page doi:10.1145/3583133.3596394 2023

  55. [56]

    N¨ ußlein, S

    J. N¨ ußlein, S. Zielinski, T. Gabor, C. Linnho ff-Popien, S. Feld, Solv- ing (max) 3-sat via quadratic unconstrained binary optimiz ation, in: J. Mikyˇ ska, C. de Mulatier, M. Paszynski, V . V . Krzhizhanov skaya, J. J. Dongarra, P . M. Sloot (Eds.), Computational Science – I CCS 2023, Springer Nature Switzerland, Cham, 2023, pp. 34–47

    work page 2023

  56. [57]

    A. Wolf, C. Grozea, Automatic conversion of minizinc pr ograms to qubo,

    work page

  57. [58]

    Karimi, P

    S. Karimi, P . Ronagh, Practical integer-to-binary map ping for quan- tum annealers, Quantum Information Processing 18 (2017). U RL: https://api.semanticscholar.org/CorpusID:22888234

    work page 2017

  58. [59]

    Cimatti, A

    A. Cimatti, A. Franz´ en, A. Griggio, R. Sebastiani, C. S tenico, Satisfiabil- ity modulo the theory of costs: Foundations and application s, in: J. Es- parza, R. Majumdar (Eds.), Tools and Algorithms for the Cons truction and Analysis of Systems, Springer Berlin Heidelberg, Berli n, Heidelberg, 2010, pp. 99–113

    work page 2010

  59. [60]

    Sebastiani, S

    R. Sebastiani, S. Tomasi, Optimization modulo theorie s with lin- ear rational costs, ACM Trans. Comput. Logic 16 (2015). URL: https://doi.org/10.1145/2699915. doi: 10.1145/2699915

    work page doi:10.1145/2699915 2015

  60. [61]

    Kucera, P

    P . Kucera, P . Savick´ y, V . V orel, A lower bound on cnf encodings of the at-most-one constraint, Theor. Comput. Sci. 762 (2017) 51– 73. URL: https://api.semanticscholar.org/CorpusID:5910836

    work page 2017

  61. [62]

    Zielinski, J

    S. Zielinski, J. N¨ ußlein, J. Stein, T. Gabor, C. Linnho ff- Popien, S. Feld, Pattern qubos: Algorithmic construc- tion of 3sat-to-qubo transformations, Electronics 12 (202 3). URL: https://www.mdpi.com/2079-9292/12/16/3492. doi:10.3390/electronics12163492

    work page doi:10.3390/electronics12163492 2079

  62. [63]

    V erma, M

    A. V erma, M. W. Lewis, V ariable reduction for quadratic uncon- strained binary optimization, ArXiv abs /2105.07032 (2021). URL: https://api.semanticscholar.org/CorpusID:234741995

    work page arXiv 2021

  63. [64]

    Morse, T

    G. Morse, T. Kozsik, On optimal qubo encoding of boolean logic, (max-)3-sat and (max-)k-sat with integer programmi ng, in: Proceedings of the 7th International Conference on Al- 15 gorithms, Computing and Systems, ICACS ’23, Association for Computing Machinery, New Y ork, NY , USA, 2024, p. 145–153. URL: https://doi.org/10.1145/3631908.3631929. doi:10.114...

    work page doi:10.1145/3631908.3631929 2024

  64. [65]

    W. Peng, B. Wang, F. Hu, Y . Wang, X. Fang, X. Chen, C. Wang,Factoring larger integers with fewer qubits via quantum annealing wit h optimized parameters, Science China Physics, Mechanics & Astronomy 6 2 (2019) 60311. URL: https://doi.org/10.1007/s11433-018-9307-1 . doi:10.1007/s11433-018-9307-1

    work page doi:10.1007/s11433-018-9307-1 2019

  65. [66]

    Mandal, A

    A. Mandal, A. Roy, S. Upadhyay, H. Ushijima-Mwesigwa, C ompressed quadratization of higher order binary optimization proble ms, 2020. arXiv:2001.00658

    work page arXiv 2020

  66. [67]

    Domino, A

    K. Domino, A. Kundu, ¨O. Salehi, K. Krawiec, Quadratic and higher- order unconstrained binary optimization of railway resche duling for quantum computing, Quantum Information Processing 21 (202 2)

    work page

  67. [68]

    doi:10.1007/s11128-022-03670-y

    URL: https://doi.org/10.1007/s11128-022-03670-y . doi:10.1007/s11128-022-03670-y

    work page doi:10.1007/s11128-022-03670-y

  68. [69]

    I. G. Rosenberg, Reduction of bivalent maximization to the quadratic case, Cahiers du Centre d’Etudes de Recherche Operationnel le 17 (2020) 71–74

    work page 2020

  69. [70]

    R. S. Barr, T. Huskinson, Binary integer reformula- tions for adiabatic quantum annealing hardware (2023). doi:10.21203/rs.3.rs-3471221/v1

    work page doi:10.21203/rs.3.rs-3471221/v1 2023

  70. [71]

    Soeken, Determining the multiplicative complexity of boolean func- tions using sat, 2020

    M. Soeken, Determining the multiplicative complexity of boolean func- tions using sat, 2020. arXiv:2005.01778

    work page arXiv 2020

  71. [72]

    Daemen, V

    J. Daemen, V . Rijmen, The block cipher rijndael, in: J.- J. Quisquater, B. Schneier (Eds.), Smart Card Research and Applications, S pringer Berlin Heidelberg, Berlin, Heidelberg, 2000, pp. 277–284

    work page 2000

  72. [73]

    Daemen, V

    J. Daemen, V . Rijmen, The Design of Rijndael: AES - The Ad vanced Encryption Standard (Information Security and Cryptograp hy), 1 ed., Springer, 2002

    work page 2002

  73. [74]

    Soeken, Determining the multiplicative complexity of boolean functions using sat, Cryptology ePrint Archive, Pa per 2020/530, 2020

    M. Soeken, Determining the multiplicative complexity of boolean functions using sat, Cryptology ePrint Archive, Pa per 2020/530, 2020. URL: https://eprint.iacr.org/2020/530, https://eprint.iacr.org/2020/530

    work page 2020

  74. [75]

    Canright, A very compact s-box for aes, in: J

    D. Canright, A very compact s-box for aes, in: J. R. Rao, B . Sunar (Eds.), Cryptographic Hardware and Embedded Systems – CHES 2005, Springer Berlin Heidelberg, Berlin, Heidelberg, 2005, pp. 441–455

    work page 2005

  75. [76]

    Boyar, R

    J. Boyar, R. Peralta, A small depth-16 circuit for the ae s s-box, in: D. Gritzalis, S. Furnell, M. Theoharidou (Eds.), Informati on Security and Privacy Research, Springer Berlin Heidelberg, Berlin, Hei delberg, 2012, pp. 287–298

    work page 2012

  76. [77]

    Reyhani-Masoleh, M

    A. Reyhani-Masoleh, M. Taha, D. Ashmawy, Smashing the i m- plementation records of aes s-box, IACR Transactions on Cry pto- graphic Hardware and Embedded Systems 2018 (2018) 298–336. URL: https://tches.iacr.org/index.php/TCHES/article/view/884. doi:10.13154/tches.v2018.i2.298-336

    work page doi:10.13154/tches.v2018.i2.298-336 2018

  77. [78]

    Burek, K

    E. Burek, K. Ma´ nk, M. Wro´ nski, Searching for an e fficient system of equations defining the aes sbox for the qubo prob- lem, Journal of Telecommunications and Information Techno logy 4 (2023) 30–37. URL: https://jtit.pl/jtit/article/view/1340. doi:10.26636/jtit.2023.4.1340

    work page doi:10.26636/jtit.2023.4.1340 2023

  78. [79]

    URL: https://github.com/GregoryMorse/CryptoQUBO

    Qubo instances of cryptography constructions, https://github.com/GregoryMorse/CryptoQUBO, 2024. URL: https://github.com/GregoryMorse/CryptoQUBO

    work page 2024

  79. [80]

    R. L. Rivest, The MD5 Message-Digest Algorithm, RFC 132 1,

    work page

  80. [81]

    doi:10.17487/RFC1321

    URL: https://www.rfc-editor.org/info/rfc1321. doi:10.17487/RFC1321

    work page doi:10.17487/rfc1321

Showing first 80 references.