{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T06:22:58Z","timestamp":1768717378400,"version":"3.49.0"},"reference-count":24,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using the generic solvers for mixed-integer linear programming problems (MILP), but they require transforming expressions with Boolean functions to linear equations or inequalities. Here, we present two methods of such a transformation which applies to any Boolean function defined by explicit rules giving values of the Boolean function for all combinations of its Boolean variables. The first method represents the Boolean function as a linear equation in the original binary variables and, possibly, binary ancillaries, which become additional variables of the MILP problem being composed. The second method represents the Boolean function as a set of linear inequalities in the original binary variables and one additional continuous variable (representing the value of the function). The choice between the first or second method is a trade-off between the number of binary variables and number of linear constraints in the emerging MP problem. The advantage of the proposed approach is that both methods reduce important cryptanalysis problems, such as the preimaging of hash functions or breaking symmetric ciphers as the MILP problems, which are solved by the generic MILP solvers. Furthermore, the first method enables to reduce the binary linear equations to quadratic unconstrained binary optimization (QUBO), by the quantum annealer, e.g., D-Wave.<\/jats:p>","DOI":"10.3390\/a15020033","type":"journal-article","created":{"date-parts":[[2022,1,23]],"date-time":"2022-01-23T20:32:52Z","timestamp":1642969972000},"page":"33","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2639-4899","authenticated-orcid":false,"given":"Aleksey I.","family":"Pakhomchik","sequence":"first","affiliation":[{"name":"Terra Quantum AG, 9400 Rorschach, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1441-6117","authenticated-orcid":false,"given":"Vladimir V.","family":"Voloshinov","sequence":"additional","affiliation":[{"name":"Terra Quantum AG, 9400 Rorschach, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0977-3515","authenticated-orcid":false,"given":"Valerii M.","family":"Vinokur","sequence":"additional","affiliation":[{"name":"Terra Quantum AG, 9400 Rorschach, Switzerland"}]},{"given":"Gordey B.","family":"Lesovik","sequence":"additional","affiliation":[{"name":"Terra Quantum AG, 9400 Rorschach, Switzerland"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02591796","article-title":"Nonlinear 0\u20131 programming: I. Linearization techniques","volume":"30","author":"Balas","year":"1984","journal-title":"Math. Program."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Milano, M., and Trick, M. (2004). Constraint and integer programming. Constraint and Integer Programming, Springer.","DOI":"10.1007\/978-1-4419-8917-8"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Hooker, J.N. (2006). Logic-based modeling. Handbook on Modelling for Discrete Optimization, Springer.","DOI":"10.1007\/0-387-32942-0_3"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bian, Z., Chudak, F., Israel, R., Lackey, B., Macready, W.G., and Roy, A. (2016). Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. arXiv.","DOI":"10.3389\/fict.2016.00014"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"56","DOI":"10.3389\/fphy.2014.00056","article-title":"Discrete optimization using quantum annealing on sparse Ising models","volume":"2","author":"Bian","year":"2014","journal-title":"Front. Phys."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/s11128-021-03118-9","article-title":"Quantum search for scaled hash function preimages","volume":"20","author":"Bellini","year":"2021","journal-title":"Quantum Inf. Processing"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 24\u201326). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing\u2014STOC \u201996, New York, NY, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T. (1970). Convex Analysis, Princeton University Press.","DOI":"10.1515\/9781400873173"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF02293050","article-title":"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra","volume":"8","author":"Avis","year":"1992","journal-title":"Discret. Comput. Geom."},{"key":"ref_10","unstructured":"Fukuda, K. (2020). Polyhedral Computation, Department of Mathematics, Institute of Theoretical Computer Science ETH Zurich."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Avis, D., Fukuda, K., and Picozzi, S. (2002). On canonical representations of convex polyhedra. Mathematical Software, World Scientific.","DOI":"10.1142\/9789812777171_0037"},{"key":"ref_12","unstructured":"Fukuda, K. (2021, July 12). cdd, cddplus and cddlib Homepage. Swiss Federal Institute of Technology. Available online: http:\/\/www.inf.ethz.ch\/personal\/fukudak\/cddhome\/index.html."},{"key":"ref_13","unstructured":"Avis, D. (2021, July 12). lrs Homepage. McGill University. Available online: http:\/\/cgm.cs.mcgill.ca\/~avis\/C\/lrs.htm."},{"key":"ref_14","first-page":"71","article-title":"Reduction of bivalent maximization to the quadratic case","volume":"17","author":"Rosenberg","year":"1975","journal-title":"Cah. Cent. D\u2019etudes Rech. Oper."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Sasaki, Y., and Aoki, K. (2009). Finding Preimages in Full MD5 Faster Than Exhaustive Search. Advances in Cryptology\u2014EUROCRYPT 2009, Springer.","DOI":"10.1007\/978-3-642-01001-9_8"},{"key":"ref_16","unstructured":"(2017). Preimage Attack on MD4 Hash Function as a Problem of Parallel Sat-Based Cryptanalysis. Bull. South Ural State Univ. Ser. Comput. Math. Softw. Eng., 6, 16\u201327."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Mironov, I., and Zhang, L. (2006). Applications of SAT Solvers to Cryptanalysis of Hash Functions. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/11814948_13"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Dobbertin, H. (1998). The First Two Rounds of MD4 are Not One-Way. Fast Software Encryption, Springer.","DOI":"10.1007\/3-540-69710-1_19"},{"key":"ref_19","unstructured":"RFC (1992). The MD5 Message-Digest Algorithm, IETF. RFC 1321."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Dang, Q.H. (2015). Secure Hash Standard, Technical Report, National Institute of Standards and Technology.","DOI":"10.6028\/NIST.FIPS.180-4"},{"key":"ref_21","unstructured":"Daor, J., Daemen, J., and Rijmen, V. (2021, June 24). AES Proposal: Rijndael. Available online: https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.36.640."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Canright, D. (2005). A Very Compact S-Box for AES. Cryptographic Hardware and Embedded Systems\u2014CHES 2005, Springer.","DOI":"10.1007\/11545262_32"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Courtois, N.T. (2005). General Principles of Algebraic Attacks and New Design Criteria for Cipher Components. Advanced Encryption Standard\u2014AES, Springer.","DOI":"10.1007\/11506447_7"},{"key":"ref_24","unstructured":"Cai, J., Macready, W.G., and Roy, A. (2014). A practical heuristic for finding graph minors. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/33\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:05:39Z","timestamp":1760133939000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,21]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020033"],"URL":"https:\/\/doi.org\/10.3390\/a15020033","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,21]]}}}