TY - JOUR A1 - Kreuzer, Martin A1 - Long, Le Ngoc A1 - Robbiano, Lorenzo T1 - Re-embeddings of affine algebras via Gröbner fans of linear ideals JF - Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry N2 - 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ö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ã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öbner fan of the linear part of  I . Then we describe a method to compute the Grö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. KW - Re-embedding KW - Optimal embedding KW - Gröbner fan KW - Cotangent space KW - Border basis scheme Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024041316352253862922 SN - 0138-4821 SN - 2191-0383 VL - 65 IS - 4 SP - 827 EP - 851 PB - Springer Berlin Heidelberg CY - Berlin/Heidelberg ER - TY - THES A1 - Danner, Julian T1 - SAT Solving Using XOR-OR-AND Normal Forms and Cryptographic Fault Attacks N2 - 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ö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. Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19171 ER -