Skip to main content

2021 | OriginalPaper | Buchkapitel

Finding Effective SAT Partitionings Via Black-Box Optimization

verfasst von : Alexander Semenov, Oleg Zaikin, Stepan Kochemazov

Erschienen in: Black Box Optimization, Machine Learning, and No-Free Lunch Theorems

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the present chapter we study one method for partitioning hard instances of the Boolean satisfiability problem (SAT). It uses a subset of a set of variables of an original formula to partition it into a family of subproblems that are significantly easier to solve individually. While it is usually very hard to estimate the time required to solve a hard SAT instance without actually solving it, the partitionings of the presented kind make it possible to naturally construct such estimations via the well-known Monte Carlo method. We show that the problem of finding a SAT partitioning with minimal estimation of time required to solve all subproblems can be formulated as the problem of minimizing a special pseudo-Boolean black-box function. The experimental part of the paper clearly shows that in the context of the proposed approach relatively simple black-box optimization algorithms show good results in application to minimization of the functions of the described kind even when faced with hard SAT instances that encode problems of finding preimages of cryptographic functions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
2.
Zurück zum Zitat Babenko, L.K., Maro, E.A., Anikeev, M.V.: Application of algebraic cryptanalysis to MAGMA and PRESENT block encryption standards. In: Proceedings of IEEE 11th International Conference on Application of Information and Communication Technologies (AICT), pp. 1–7 (2017). https://doi.org/10.1109/ICAICT.2017.8686954 Babenko, L.K., Maro, E.A., Anikeev, M.V.: Application of algebraic cryptanalysis to MAGMA and PRESENT block encryption standards. In: Proceedings of IEEE 11th International Conference on Application of Information and Communication Technologies (AICT), pp. 1–7 (2017). https://​doi.​org/​10.​1109/​ICAICT.​2017.​8686954
5.
Zurück zum Zitat Bessiere, C., Katsirelos, G., Narodytska, N., Walsh, T.: Circuit complexity and decompositions of global constraints. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence - IJCAI’09, pp. 412–418 (2009) Bessiere, C., Katsirelos, G., Narodytska, N., Walsh, T.: Circuit complexity and decompositions of global constraints. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence - IJCAI’09, pp. 412–418 (2009)
6.
Zurück zum Zitat Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009) Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009)
7.
Zurück zum Zitat Biryukov, A., Shamir, A., Wagner, D.A.: Real time cryptanalysis of A5/1 on a PC. In: Schneier, B. (ed.) Fast Software Encryption, 7th International Workshop, FSE 2000. Lecture Notes in Computer Science, vol. 1978, pp. 1–18. Springer, Berlin (2000). https://doi.org/10.1007/3-540-44706-7_1 Biryukov, A., Shamir, A., Wagner, D.A.: Real time cryptanalysis of A5/1 on a PC. In: Schneier, B. (ed.) Fast Software Encryption, 7th International Workshop, FSE 2000. Lecture Notes in Computer Science, vol. 1978, pp. 1–18. Springer, Berlin (2000). https://​doi.​org/​10.​1007/​3-540-44706-7_​1
9.
Zurück zum Zitat Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway, P. (ed.) Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference. Lecture Notes in Computer Science, vol. 6841, pp. 169–187. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-22792-9_10 CrossRef Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway, P. (ed.) Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference. Lecture Notes in Computer Science, vol. 6841, pp. 169–187. Springer, Berlin (2011). https://​doi.​org/​10.​1007/​978-3-642-22792-9_​10 CrossRef
10.
Zurück zum Zitat Cannière, C.D., Preneel, B.: Trivium. In: Robshaw, M.J.B., Billet, O. (eds.) New Stream Cipher Designs - The eSTREAM Finalists. Lecture Notes in Computer Science, vol. 4986, pp. 244–266. Springer, Berlin (2008)CrossRef Cannière, C.D., Preneel, B.: Trivium. In: Robshaw, M.J.B., Billet, O. (eds.) New Stream Cipher Designs - The eSTREAM Finalists. Lecture Notes in Computer Science, vol. 4986, pp. 244–266. Springer, Berlin (2008)CrossRef
11.
Zurück zum Zitat Carter, K., Foltzer, A., Hendrix, J., Huffman, B., Tomb, A.: SAW: the software analysis workbench. In: Boleng, J., Taft, S.T. (eds.) Proceedings of the 2013 ACM SIGAda Annual Conference on High Integrity Language Technology, HILT, pp. 15–18. ACM, New York (2013). https://doi.org/10.1145/2527269.2527277 CrossRef Carter, K., Foltzer, A., Hendrix, J., Huffman, B., Tomb, A.: SAW: the software analysis workbench. In: Boleng, J., Taft, S.T. (eds.) Proceedings of the 2013 ACM SIGAda Annual Conference on High Integrity Language Technology, HILT, pp. 15–18. ACM, New York (2013). https://​doi.​org/​10.​1145/​2527269.​2527277 CrossRef
12.
Zurück zum Zitat Chang, C.L., Lee, R.C.T.: Symbolic Logic and Mechanical Theorem Proving, 1st edn. Academic Press, Cambridge (1997)MATH Chang, C.L., Lee, R.C.T.: Symbolic Logic and Mechanical Theorem Proving, 1st edn. Academic Press, Cambridge (1997)MATH
13.
Zurück zum Zitat Clarke, E.M., Kroening, D., Lerda, F.: A tool for checking ANSI-C programs. In: Jensen, K., Podelski, A. (eds.) Tools and Algorithms for the Construction and Analysis of Systems, 10th International Conference, TACAS 2004. Lecture Notes in Computer Science, vol. 2988, pp. 168–176. Springer, Berlin (2004). https://doi.org/10.1007/978-3-540-24730-2_15 Clarke, E.M., Kroening, D., Lerda, F.: A tool for checking ANSI-C programs. In: Jensen, K., Podelski, A. (eds.) Tools and Algorithms for the Construction and Analysis of Systems, 10th International Conference, TACAS 2004. Lecture Notes in Computer Science, vol. 2988, pp. 168–176. Springer, Berlin (2004). https://​doi.​org/​10.​1007/​978-3-540-24730-2_​15
14.
Zurück zum Zitat Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158 (1971) Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158 (1971)
15.
Zurück zum Zitat Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. In: Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 35, pp. 1–18. American Mathematical Society, Providence (1996) Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. In: Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 35, pp. 1–18. American Mathematical Society, Providence (1996)
17.
Zurück zum Zitat Courtois, N.T., Gawinecki, J.A., Song, G.: Contradiction immunity and guess-then-determine attacks on GOST. Tatra Mt. Math. Publ. 53(1), 2–13 (2012)MathSciNetMATH Courtois, N.T., Gawinecki, J.A., Song, G.: Contradiction immunity and guess-then-determine attacks on GOST. Tatra Mt. Math. Publ. 53(1), 2–13 (2012)MathSciNetMATH
19.
Zurück zum Zitat Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Log. Program. 1(3), 267–284 (1984)MathSciNetMATHCrossRef Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Log. Program. 1(3), 267–284 (1984)MathSciNetMATHCrossRef
20.
Zurück zum Zitat Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Selected Revised Papers. Lecture Notes in Computer Science, vol. 2919, pp. 502–518. Springer, Berlin (2003). https://doi.org/10.1007/978-3-540-24605-3_37 MATH Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Selected Revised Papers. Lecture Notes in Computer Science, vol. 2919, pp. 502–518. Springer, Berlin (2003). https://​doi.​org/​10.​1007/​978-3-540-24605-3_​37 MATH
21.
Zurück zum Zitat Eén, N., Sörensson, N.: Temporal induction by incremental SAT solving. Electr. Notes Theor. Comput. Sci. 89(4), 543–560 (2003)MATHCrossRef Eén, N., Sörensson, N.: Temporal induction by incremental SAT solving. Electr. Notes Theor. Comput. Sci. 89(4), 543–560 (2003)MATHCrossRef
22.
Zurück zum Zitat Eibach, T., Pilz, E., Völkel, G.: Attacking Bivium using SAT solvers. In: Büning, H.K., Zhao, X. (eds.) Theory and Applications of Satisfiability Testing - SAT 2008, 11th International Conference, SAT 2008. Lecture Notes in Computer Science, vol. 4996, pp. 63–76. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-79719-7_7 MATH Eibach, T., Pilz, E., Völkel, G.: Attacking Bivium using SAT solvers. In: Büning, H.K., Zhao, X. (eds.) Theory and Applications of Satisfiability Testing - SAT 2008, 11th International Conference, SAT 2008. Lecture Notes in Computer Science, vol. 4996, pp. 63–76. Springer, Berlin (2008). https://​doi.​org/​10.​1007/​978-3-540-79719-7_​7 MATH
23.
Zurück zum Zitat Feller, W.: An Introduction to Probability Theory and Its Applications, Volume II. Wiley, New York (1971) Feller, W.: An Introduction to Probability Theory and Its Applications, Volume II. Wiley, New York (1971)
24.
Zurück zum Zitat Franco, J., Martin, J.: A history of satisfiability. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 3–74. IOS Press, Amsterdam (2009) Franco, J., Martin, J.: A history of satisfiability. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 3–74. IOS Press, Amsterdam (2009)
25.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, New York (1979)MATH Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, New York (1979)MATH
26.
27.
Zurück zum Zitat Gomes, C.P., Sabharwal, A.: Exploiting runtime variation in complete solvers. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 271–288. IOS Press, Amsterdam (2009) Gomes, C.P., Sabharwal, A.: Exploiting runtime variation in complete solvers. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 271–288. IOS Press, Amsterdam (2009)
28.
Zurück zum Zitat Günther, C.G.: Alternating step generators controlled by de Bruijn sequences. In: Chaum, D., Price, W.L. (eds.) Advances in Cryptology - EUROCRYPT’87, Workshop on the Theory and Application of Cryptographic Techniques. Lecture Notes in Computer Science, vol. 304, pp. 5–14. Springer, Berlin (1987). https://doi.org/10.1007/3-540-39118-5_2 Günther, C.G.: Alternating step generators controlled by de Bruijn sequences. In: Chaum, D., Price, W.L. (eds.) Advances in Cryptology - EUROCRYPT’87, Workshop on the Theory and Application of Cryptographic Techniques. Lecture Notes in Computer Science, vol. 304, pp. 5–14. Springer, Berlin (1987). https://​doi.​org/​10.​1007/​3-540-39118-5_​2
29.
Zurück zum Zitat Hamadi, Y., Jabbour, S., Sais, L.: Manysat: a parallel SAT solver. J. Satisf. Boolean Model. Comput. 6(4), 245–262 (2009)MATH Hamadi, Y., Jabbour, S., Sais, L.: Manysat: a parallel SAT solver. J. Satisf. Boolean Model. Comput. 6(4), 245–262 (2009)MATH
31.
Zurück zum Zitat Hell, M., Johansson, T., Maximov, A., Meier, W.: The Grain family of stream ciphers. In: Robshaw, M.J.B., Billet, O. (eds.) New Stream Cipher Designs - The eSTREAM Finalists. Lecture Notes in Computer Science, vol. 4986, pp. 179–190. Springer, Berlin (2008)CrossRef Hell, M., Johansson, T., Maximov, A., Meier, W.: The Grain family of stream ciphers. In: Robshaw, M.J.B., Billet, O. (eds.) New Stream Cipher Designs - The eSTREAM Finalists. Lecture Notes in Computer Science, vol. 4986, pp. 179–190. Springer, Berlin (2008)CrossRef
32.
Zurück zum Zitat Heule, M., Kullmann, O., Wieringa, S., Biere, A.: Cube and conquer: guiding CDCL SAT solvers by lookaheads. In: Eder, K., Lourenço, J., Shehory, O. (eds.) Hardware and Software: Verification and Testing - 7th International Haifa Verification Conference, HVC 2011. Lecture Notes in Computer Science, vol. 7261, pp. 50–65. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-34188-5_8 Heule, M., Kullmann, O., Wieringa, S., Biere, A.: Cube and conquer: guiding CDCL SAT solvers by lookaheads. In: Eder, K., Lourenço, J., Shehory, O. (eds.) Hardware and Software: Verification and Testing - 7th International Haifa Verification Conference, HVC 2011. Lecture Notes in Computer Science, vol. 7261, pp. 50–65. Springer, Berlin (2011). https://​doi.​org/​10.​1007/​978-3-642-34188-5_​8
33.
Zurück zum Zitat Heule, M.J.H., Kullmann, O., Marek, V.W.: Solving and verifying the Boolean Pythagorean triples problem via cube-and-conquer. In: Creignou, N., Le Berre, D. (eds.) Theory and Applications of Satisfiability Testing – SAT 2016. Lecture Notes in Computer Science, vol. 9710, pp. 228–245. Springer, Berlin (2016)CrossRef Heule, M.J.H., Kullmann, O., Marek, V.W.: Solving and verifying the Boolean Pythagorean triples problem via cube-and-conquer. In: Creignou, N., Le Berre, D. (eds.) Theory and Applications of Satisfiability Testing – SAT 2016. Lecture Notes in Computer Science, vol. 9710, pp. 228–245. Springer, Berlin (2016)CrossRef
34.
Zurück zum Zitat Hyvärinen, A.E.J.: Grid based propositional satisfiability solving. Ph.D. Thesis, Aalto University (2011) Hyvärinen, A.E.J.: Grid based propositional satisfiability solving. Ph.D. Thesis, Aalto University (2011)
37.
38.
Zurück zum Zitat Järvisalo, M., Biere, A., Heule, M.: Simulating circuit-level simplifications on CNF. J. Autom. Reason. 49(4), 583–619 (2012)MathSciNetMATHCrossRef Järvisalo, M., Biere, A., Heule, M.: Simulating circuit-level simplifications on CNF. J. Autom. Reason. 49(4), 583–619 (2012)MathSciNetMATHCrossRef
39.
40.
Zurück zum Zitat Kochemazov, S., Zaikin, O.: ALIAS: a modular tool for finding backdoors for SAT. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) Theory and Applications of Satisfiability Testing - 21st International Conference, SAT 2018. Lecture Notes in Computer Science, vol. 10929, pp. 419–427. Springer, Berlin (2018). https://doi.org/10.1007/978-3-319-94144-8_25 MATHCrossRef Kochemazov, S., Zaikin, O.: ALIAS: a modular tool for finding backdoors for SAT. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) Theory and Applications of Satisfiability Testing - 21st International Conference, SAT 2018. Lecture Notes in Computer Science, vol. 10929, pp. 419–427. Springer, Berlin (2018). https://​doi.​org/​10.​1007/​978-3-319-94144-8_​25 MATHCrossRef
41.
Zurück zum Zitat Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385–482 (2003)MathSciNetMATHCrossRef Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385–482 (2003)MathSciNetMATHCrossRef
42.
Zurück zum Zitat Kroening, D.: Software verification. In: Biere et al. [6], pp. 505–532 Kroening, D.: Software verification. In: Biere et al. [6], pp. 505–532
44.
Zurück zum Zitat Levin, L.: Universal sequential search problems. Probl. Inf. Transm. 9, 265–266 (1973) Levin, L.: Universal sequential search problems. Probl. Inf. Transm. 9, 265–266 (1973)
46.
Zurück zum Zitat Marques-Silva, J.P., Sakallah, K.A.: GRASP - a new search algorithm for satisfiability. In: Rutenbar, R.A., Otten, R.H.J.M. (eds.) Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996, pp. 220–227. IEEE Computer Society/ACM, New York (1996). https://doi.org/10.1109/ICCAD.1996.569607 Marques-Silva, J.P., Sakallah, K.A.: GRASP - a new search algorithm for satisfiability. In: Rutenbar, R.A., Otten, R.H.J.M. (eds.) Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996, pp. 220–227. IEEE Computer Society/ACM, New York (1996). https://​doi.​org/​10.​1109/​ICCAD.​1996.​569607
47.
Zurück zum Zitat Marques-Silva, J.P., Lynce, I., Malik, S.: Conflict-driven clause learning SAT solvers. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 131–153. IOS Press, Amsterdam (2009) Marques-Silva, J.P., Lynce, I., Malik, S.: Conflict-driven clause learning SAT solvers. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 131–153. IOS Press, Amsterdam (2009)
48.
Zurück zum Zitat Maximov, A., Biryukov, A.: Two trivial attacks on trivium. In: Adams, C.M., Miri, A., Wiener, M.J. (eds.) Selected Areas in Cryptography, 14th International Workshop, SAC 2007, Revised Selected Papers. Lecture Notes in Computer Science, vol. 4876, pp. 36–55. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-77360-3_3 Maximov, A., Biryukov, A.: Two trivial attacks on trivium. In: Adams, C.M., Miri, A., Wiener, M.J. (eds.) Selected Areas in Cryptography, 14th International Workshop, SAC 2007, Revised Selected Papers. Lecture Notes in Computer Science, vol. 4876, pp. 36–55. Springer, Berlin (2007). https://​doi.​org/​10.​1007/​978-3-540-77360-3_​3
49.
Zurück zum Zitat Mcdonald, C., Charnes, C., Pieprzyk, J.: Attacking Bivium with MiniSat. Tech. Rep. 2007/040, ECRYPT Stream Cipher Project (2007) Mcdonald, C., Charnes, C., Pieprzyk, J.: Attacking Bivium with MiniSat. Tech. Rep. 2007/040, ECRYPT Stream Cipher Project (2007)
50.
Zurück zum Zitat Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography, 1st edn. CRC Press, Boca Raton (1996)MATH Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography, 1st edn. CRC Press, Boca Raton (1996)MATH
51.
Zurück zum Zitat Metropolis, N., Ulam, S.: The Monte Carlo Method. J. Am. Stat. Assoc. 44(247), 335–341 (1949)MATHCrossRef Metropolis, N., Ulam, S.: The Monte Carlo Method. J. Am. Stat. Assoc. 44(247), 335–341 (1949)MATHCrossRef
52.
Zurück zum Zitat Mühlenbein, H.: How genetic algorithms really work: mutation and hillclimbing. In: Männer, R., Manderick, B. (eds.) Parallel Problem Solving from Nature 2, PPSN-II, pp. 15–26. Elsevier, Amsterdam (1992) Mühlenbein, H.: How genetic algorithms really work: mutation and hillclimbing. In: Männer, R., Manderick, B. (eds.) Parallel Problem Solving from Nature 2, PPSN-II, pp. 15–26. Elsevier, Amsterdam (1992)
53.
Zurück zum Zitat Otpuschennikov, I.V., Semenov, A.A., Gribanova, I., Zaikin, O., Kochemazov, S.: Encoding cryptographic functions to SAT using TRANSALG system. In: Kaminka, G.A., Fox, M., Bouquet, P., Hüllermeier, E., Dignum, V., Dignum, F., van Harmelen, F. (eds.) ECAI 2016 - 22nd European Conference on Artificial Intelligence. Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 1594–1595. IOS Press, Amsterdam (2016). https://doi.org/10.3233/978-1-61499-672-9-1594 Otpuschennikov, I.V., Semenov, A.A., Gribanova, I., Zaikin, O., Kochemazov, S.: Encoding cryptographic functions to SAT using TRANSALG system. In: Kaminka, G.A., Fox, M., Bouquet, P., Hüllermeier, E., Dignum, V., Dignum, F., van Harmelen, F. (eds.) ECAI 2016 - 22nd European Conference on Artificial Intelligence. Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 1594–1595. IOS Press, Amsterdam (2016). https://​doi.​org/​10.​3233/​978-1-61499-672-9-1594
54.
Zurück zum Zitat Pavlenko, A., Buzdalov, M., Ulyantsev, V.: Fitness comparison by statistical testing in construction of SAT-based guess-and-determine cryptographic attacks. In: Auger, A., Stützle, T. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 312–320 (2019). https://doi.org/10.1145/3321707.3321847 Pavlenko, A., Buzdalov, M., Ulyantsev, V.: Fitness comparison by statistical testing in construction of SAT-based guess-and-determine cryptographic attacks. In: Auger, A., Stützle, T. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 312–320 (2019). https://​doi.​org/​10.​1145/​3321707.​3321847
55.
Zurück zum Zitat Pavlenko, A., Semenov, A.A., Ulyantsev, V.: Evolutionary computation techniques for constructing SAT-based attacks in algebraic cryptanalysis. In: Kaufmann, P., Castillo, P.A. (eds.) Applications of Evolutionary Computation - 22nd International Conference, EvoApplications 2019. Lecture Notes in Computer Science, vol. 11454, pp. 237–253. Springer, Berlin (2019). https://doi.org/10.1007/978-3-030-16692-2_16 Pavlenko, A., Semenov, A.A., Ulyantsev, V.: Evolutionary computation techniques for constructing SAT-based attacks in algebraic cryptanalysis. In: Kaufmann, P., Castillo, P.A. (eds.) Applications of Evolutionary Computation - 22nd International Conference, EvoApplications 2019. Lecture Notes in Computer Science, vol. 11454, pp. 237–253. Springer, Berlin (2019). https://​doi.​org/​10.​1007/​978-3-030-16692-2_​16
56.
Zurück zum Zitat Posypkin, M., Semenov, A.A., Zaikin, O.: Using BOINC desktop grid to solve large scale SAT problems. Comput. Sci. (AGH) 13(1), 25–34 (2012) Posypkin, M., Semenov, A.A., Zaikin, O.: Using BOINC desktop grid to solve large scale SAT problems. Comput. Sci. (AGH) 13(1), 25–34 (2012)
59.
Zurück zum Zitat Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Prentice Hall, Upper Saddle River (2009) Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Prentice Hall, Upper Saddle River (2009)
60.
Zurück zum Zitat Semenov, A.: Decomposition representations of logical equations in problems of inversion of discrete functions. J. Comput. Syst. Sci. Int. 48, 718–731 (2009)MathSciNetMATHCrossRef Semenov, A.: Decomposition representations of logical equations in problems of inversion of discrete functions. J. Comput. Syst. Sci. Int. 48, 718–731 (2009)MathSciNetMATHCrossRef
61.
Zurück zum Zitat Semenov, A.A., Zaikin, O.: Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem. In: Malyshkin, V. (ed.) Parallel Computing Technologies - 13th International Conference, PaCT 2015. Lecture Notes in Computer Science, vol. 9251, pp. 222–230. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-21909-7_21 Semenov, A.A., Zaikin, O.: Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem. In: Malyshkin, V. (ed.) Parallel Computing Technologies - 13th International Conference, PaCT 2015. Lecture Notes in Computer Science, vol. 9251, pp. 222–230. Springer, Berlin (2015). https://​doi.​org/​10.​1007/​978-3-319-21909-7_​21
62.
Zurück zum Zitat Semenov, A.A., Zaikin, O.: On the accuracy of statistical estimations of SAT partitionings effectiveness in application to discrete function inversion problems. In: Kononov, A.V., Bykadorov, I.A., Khamisov, O.V., Davydov, I.A., Kononova, P.A. (eds.) Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016). CEUR Workshop Proceedings, vol. 1623, pp. 261–275. CEUR-WS.org (2016) Semenov, A.A., Zaikin, O.: On the accuracy of statistical estimations of SAT partitionings effectiveness in application to discrete function inversion problems. In: Kononov, A.V., Bykadorov, I.A., Khamisov, O.V., Davydov, I.A., Kononova, P.A. (eds.) Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016). CEUR Workshop Proceedings, vol. 1623, pp. 261–275. CEUR-WS.org (2016)
63.
Zurück zum Zitat Semenov, A., Zaikin, O.: Algorithm for finding partitionings of hard variants of Boolean satisfiability problem with application to inversion of some cryptographic functions. SpringerPlus 5(1), 1–16 (2016)CrossRef Semenov, A., Zaikin, O.: Algorithm for finding partitionings of hard variants of Boolean satisfiability problem with application to inversion of some cryptographic functions. SpringerPlus 5(1), 1–16 (2016)CrossRef
64.
Zurück zum Zitat Semenov, A.A., Zaikin, O., Bespalov, D., Posypkin, M.: Parallel logical cryptanalysis of the generator A5/1 in BNB-grid system. In: Malyshkin, V. (ed.) Parallel Computing Technologies - 11th International Conference, PaCT 2011. Lecture Notes in Computer Science, vol. 6873, pp. 473–483. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-23178-0_43 MATH Semenov, A.A., Zaikin, O., Bespalov, D., Posypkin, M.: Parallel logical cryptanalysis of the generator A5/1 in BNB-grid system. In: Malyshkin, V. (ed.) Parallel Computing Technologies - 11th International Conference, PaCT 2011. Lecture Notes in Computer Science, vol. 6873, pp. 473–483. Springer, Berlin (2011). https://​doi.​org/​10.​1007/​978-3-642-23178-0_​43 MATH
65.
Zurück zum Zitat Semenov, A.A., Zaikin, O., Otpuschennikov, I.V., Kochemazov, S., Ignatiev, A.: On cryptographic attacks using backdoors for SAT. In: McIlraith, S.A., Weinberger, K.Q. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), pp. 6641–6648. AAAI Press, Palo Alto (2018) Semenov, A.A., Zaikin, O., Otpuschennikov, I.V., Kochemazov, S., Ignatiev, A.: On cryptographic attacks using backdoors for SAT. In: McIlraith, S.A., Weinberger, K.Q. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), pp. 6641–6648. AAAI Press, Palo Alto (2018)
66.
Zurück zum Zitat Semenov, A., Otpuschennikov, I., Gribanova, I., Zaikin, O., Kochemazov, S.: Translation of algorithmic descriptions of discrete functions to SAT with applications to cryptanalysis problems. Log. Meth. Comput. Sci. 16, 29:1–29:42 (2020) Semenov, A., Otpuschennikov, I., Gribanova, I., Zaikin, O., Kochemazov, S.: Translation of algorithmic descriptions of discrete functions to SAT with applications to cryptanalysis problems. Log. Meth. Comput. Sci. 16, 29:1–29:42 (2020)
67.
Zurück zum Zitat Soos, M.: Grain of Salt - an automated way to test stream ciphers through SAT solvers. In: Tools’10: Proceedings of the Workshop on Tools for Cryptanalysis, pp. 131–144 (2010) Soos, M.: Grain of Salt - an automated way to test stream ciphers through SAT solvers. In: Tools’10: Proceedings of the Workshop on Tools for Cryptanalysis, pp. 131–144 (2010)
68.
Zurück zum Zitat Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) Theory and Applications of Satisfiability Testing - SAT 2009, 12th International Conference, SAT 2009. Lecture Notes in Computer Science, vol. 5584, pp. 244–257. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-02777-2_24 Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) Theory and Applications of Satisfiability Testing - SAT 2009, 12th International Conference, SAT 2009. Lecture Notes in Computer Science, vol. 5584, pp. 244–257. Springer, Berlin (2009). https://​doi.​org/​10.​1007/​978-3-642-02777-2_​24
69.
Zurück zum Zitat Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: A.O. Slisenko (ed.) Studies in Mathematics and Mathematical Logic, Part II, pp. 115–125. Steklov Mathematical Institute, Moscow (1968) Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: A.O. Slisenko (ed.) Studies in Mathematics and Mathematical Logic, Part II, pp. 115–125. Steklov Mathematical Institute, Moscow (1968)
70.
Zurück zum Zitat Wegener, I.: The Complexity of Boolean Functions. Wiley, Hoboken (1987)MATH Wegener, I.: The Complexity of Boolean Functions. Wiley, Hoboken (1987)MATH
71.
Zurück zum Zitat Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03, pp. 1173–1178. Morgan Kaufmann, Burlington (2003) Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03, pp. 1173–1178. Morgan Kaufmann, Burlington (2003)
72.
Zurück zum Zitat Zaikin, O.: SAT-based cryptanalysis: from parallel computing to volunteer computing. In: Voevodin, V.V., Sobolev, S. (eds.) Supercomputing - 5th Russian Supercomputing Days, RuSCDays 2019. Communications in Computer and Information Science, vol. 1129, pp. 701–712. Springer, Berlin (2019). https://doi.org/10.1007/978-3-030-36592-9_57 Zaikin, O.: SAT-based cryptanalysis: from parallel computing to volunteer computing. In: Voevodin, V.V., Sobolev, S. (eds.) Supercomputing - 5th Russian Supercomputing Days, RuSCDays 2019. Communications in Computer and Information Science, vol. 1129, pp. 701–712. Springer, Berlin (2019). https://​doi.​org/​10.​1007/​978-3-030-36592-9_​57
73.
Zurück zum Zitat Zaikin, O., Kochemazov, S.: An improved SAT-based guess-and-determine attack on the alternating step generator. In: Nguyen, P.Q., Zhou, J. (eds.) Information Security - 20th International Conference, ISC 2017. Lecture Notes in Computer Science, vol. 10599, pp. 21–38. Springer, Berlin (2017). https://doi.org/10.1007/978-3-319-69659-1_2 Zaikin, O., Kochemazov, S.: An improved SAT-based guess-and-determine attack on the alternating step generator. In: Nguyen, P.Q., Zhou, J. (eds.) Information Security - 20th International Conference, ISC 2017. Lecture Notes in Computer Science, vol. 10599, pp. 21–38. Springer, Berlin (2017). https://​doi.​org/​10.​1007/​978-3-319-69659-1_​2
74.
Zurück zum Zitat Zaikin, O., Kochemazov, S.: Pseudo-boolean black-box optimization methods in the context of divide-and-conquer approach to solving hard SAT instances. In: OPTIMA 2018 (Supplementary Volume), pp. 76–87. DEStech Publications, Lancaster (2018) Zaikin, O., Kochemazov, S.: Pseudo-boolean black-box optimization methods in the context of divide-and-conquer approach to solving hard SAT instances. In: OPTIMA 2018 (Supplementary Volume), pp. 76–87. DEStech Publications, Lancaster (2018)
Metadaten
Titel
Finding Effective SAT Partitionings Via Black-Box Optimization
verfasst von
Alexander Semenov
Oleg Zaikin
Stepan Kochemazov
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-66515-9_11

Premium Partner