@article{KreuzerLongRobbiano2024, author = {Kreuzer, Martin and Long, Le Ngoc and Robbiano, Lorenzo}, title = {Re-embeddings of affine algebras via Gr{\"o}bner fans of linear ideals}, series = {Beitr{\"a}ge zur Algebra und Geometrie / Contributions to Algebra and Geometry}, volume = {65}, journal = {Beitr{\"a}ge zur Algebra und Geometrie / Contributions to Algebra and Geometry}, number = {4}, publisher = {Springer Berlin Heidelberg}, address = {Berlin/Heidelberg}, issn = {0138-4821}, doi = {10.1007/s13366-024-00733-2}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2024041316352253862922}, pages = {827 -- 851}, year = {2024}, abstract = {Given an affine algebra R=K[x1,⋯,xn]/Iover a field  K , where I is an ideal in the polynomial ring P=K[x1,⋯,xn], we examine the task of effectively calculating re-embeddings of  I , i.e., of presentations R=P′/I′such that P′=K[y1,⋯,ym]has fewer indeterminates. For cases when the number of indeterminates  n is large and Gr{\"o}bner basis computations are infeasible, we have introduced the method of Z -separating re-embeddings in Kreuzer et al. (J Algebra Appl 21, 2022) and Kreuzer, et al. (S{\~a}o Paulo J Math Sci, 2022). This method tries to detect polynomials of a special shape in  I which allow us to eliminate the indeterminates in the tuple  Z by a simple substitution process. Here we improve this approach by showing that suitable candidate tuples  Z can be found using the Gr{\"o}bner fan of the linear part of  I . Then we describe a method to compute the Gr{\"o}bner fan of a linear ideal, and we improve this computation in the case of binomial linear ideals using a cotangent equivalence relation. Finally, we apply the improved technique in the case of the defining ideals of border basis schemes.}, language = {en} } @phdthesis{Danner2025, author = {Danner, Julian}, title = {SAT Solving Using XOR-OR-AND Normal Forms and Cryptographic Fault Attacks}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19171}, school = {Universit{\"a}t Passau}, pages = {vi, 237 Seiten}, year = {2025}, abstract = {The Boolean satisfiability problem (SAT) lies at the core of computational logic and has found many applications in verification, cryptography, and artificial intelligence. While conflict-driven SAT solvers (CDCL) excel on large industrial instances, they struggle with XOR-rich instances arising frequently in cryptanalysis, due to the inefficiency of CNF encodings of linear constraints. Conversely, algebraic approaches can work with linear XOR constraints naturally but fail to scale to relevant sizes. Bridging these complementary paradigms with a focus on cryptographic problems is at the heart of this thesis. On one hand, this dissertation advances SAT solving by introducing the XOR-OR-AND normal form (XNF) as a generalization of the conjunctive normal form (CNF), where literals are replaced by XOR chains of literals. This allows for a native representation of XOR constraints. We generalize the CDCL architecture to the richer language of XNFs. The underlying reasoning based on the proof system SRES which is shown to be exponentially stronger than classical resolution. An implementation demonstrates competitive performance and often surpasses state-of-the-art algebraic and logic solvers on random and cryptographic benchmarks. Furthermore, we prove that every XNF formula can be converted in polynomial time to a formula in 2-XNF, enabling a graph-based approach similar to 2-SAT. Building on this, we propose advanced in- and pre-processing techniques, and construct a simple DPLL-based solving framework. Our implementation, 2-Xornado, outperforms modern algebraic and logic solving approaches on many random and some structured cryptographic problems. On the other hand, we apply combined algebraic and logical techniques to cryptanalysis of stream ciphers. We introduce a formal guess-and-determine (GD) framework using a logical abstraction of the information flow in the internal state. From an algebraic point of view, we can then find optimal GD attacks utilizing a Gr{\"o}bner basis. As a case study, we apply this method to aid in the construction of novel fault attacks on the ciphers KCipher-2 and Enocoro-128v2. Using ad hoc methods combining algebraic and logical approaches, we show that both ciphers are vulnerable to active side-channel attacks under rather weak fault models.}, language = {en} }