Polybori: A framework for Gröbner-basis computations with Boolean polynomials

DOI10.1016/j.jsc.2008.02.017zbMath1186.68571OpenAlexW2071596701MaRDI QIDQ1030264

Michael Brickenstein, Alexander Dreyer

Publication date: 1 July 2009

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2008.02.017

zbMATH Keywords

formal verificationsatisfiabilityBoolean Gröbner basisalgebraic cryptoanalysis

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items

Narrow Proofs May Be Maximally Long, Conditional Differential Cryptanalysis of Trivium and KATAN, Boolean polynomials, BDDs and CRHS equations -- connecting the dots with CryptaPath, Gröbner bases of neural ideals, Mutant Differential Fault Analysis of Trivium MDFA, Space Complexity in Polynomial Calculus, A characteristic set method for solving Boolean equations and applications in cryptanalysis of stream ciphers, A signature based border basis algorithm, Characteristic set algorithms for equation solving in finite fields, On the relation between the MXL family of algorithms and Gröbner basis algorithms, Optimising Gröbner bases on Bivium, Obtaining and solving systems of equations in key variables only for the small variants of AES, Representing the integer factorization problem using ordered binary decision diagrams, Model checking in the modal \(\mu \)-calculus and generic solutions, Boolean Gröbner bases, On the efficiency of solving Boolean polynomial systems with the characteristic set method, Slimgb: Gröbner bases with slim polynomials, An algebraic model for implementing expert systems based on the knowledge of different experts, A natural language for implementing algebraically expert systems, An algebraic approach for detecting nearly dangerous situations in expert systems, A logic-algebraic approach to decision taking in a railway interlocking system, Algebraic Attacks Galore!, Solving non-linear Boolean equation systems by variable elimination, Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach, PolyBoRi, On conversions from CNF to ANF, Short Proofs Are Hard to Find, Polynomial semantics for modal logics, A white-box speck implementation using self-equivalence encodings, Boolean ideals and their varieties

Uses Software

• FGb
• Magma
• MiniSat
• SINGULAR
• slimgb
• SATLIB
• CUDD
• Python

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characteristic set method for solving Boolean equations and applications in cryptanalysis of stream ciphers
• New developments in the theory of Gröbner bases and applications to formal verification
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• The Magma algebra system. I: The user language
• Converting bases with the Gröbner walk
• Algebraic Attacks on the Courtois Toy Cipher
• Graph-Based Algorithms for Boolean Function Manipulation
• Advanced Encryption Standard – AES
• Theory and Applications of Satisfiability Testing
• Advances in Cryptology - CRYPTO 2003
• Interpolants and Symbolic Model Checking
• Fast Software Encryption