Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis
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 pr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/2/33 |
| _version_ | 1827657787499347968 |
|---|---|
| author | Aleksey I. Pakhomchik Vladimir V. Voloshinov Valerii M. Vinokur Gordey B. Lesovik |
| author_facet | Aleksey I. Pakhomchik Vladimir V. Voloshinov Valerii M. Vinokur Gordey B. Lesovik |
| author_sort | Aleksey I. Pakhomchik |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T22:49:53Z |
| format | Article |
| id | doaj.art-f2bb94224c654b8e9f730b4de45ffa3b |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T22:49:53Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-f2bb94224c654b8e9f730b4de45ffa3b2023-11-23T18:23:55ZengMDPI AGAlgorithms1999-48932022-01-011523310.3390/a15020033Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for CryptanalysisAleksey I. Pakhomchik0Vladimir V. Voloshinov1Valerii M. Vinokur2Gordey B. Lesovik3Terra Quantum AG, 9400 Rorschach, SwitzerlandTerra Quantum AG, 9400 Rorschach, SwitzerlandTerra Quantum AG, 9400 Rorschach, SwitzerlandTerra Quantum AG, 9400 Rorschach, SwitzerlandThere 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.https://www.mdpi.com/1999-4893/15/2/33constrained programmingquadratic unconstrained binary optimizationhash functioncryptanalysis |
| spellingShingle | Aleksey I. Pakhomchik Vladimir V. Voloshinov Valerii M. Vinokur Gordey B. Lesovik Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis Algorithms constrained programming quadratic unconstrained binary optimization hash function cryptanalysis |
| title | Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis |
| title_full | Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis |
| title_fullStr | Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis |
| title_full_unstemmed | Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis |
| title_short | Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis |
| title_sort | converting of boolean expression to linear equations inequalities and qubo penalties for cryptanalysis |
| topic | constrained programming quadratic unconstrained binary optimization hash function cryptanalysis |
| url | https://www.mdpi.com/1999-4893/15/2/33 |
| work_keys_str_mv | AT alekseyipakhomchik convertingofbooleanexpressiontolinearequationsinequalitiesandqubopenaltiesforcryptanalysis AT vladimirvvoloshinov convertingofbooleanexpressiontolinearequationsinequalitiesandqubopenaltiesforcryptanalysis AT valeriimvinokur convertingofbooleanexpressiontolinearequationsinequalitiesandqubopenaltiesforcryptanalysis AT gordeyblesovik convertingofbooleanexpressiontolinearequationsinequalitiesandqubopenaltiesforcryptanalysis |