Multivariate Cryptography and Polynomial System Solving Complexity

Explore multivariate cryptography and the complexity of polynomial system solving in this 47-minute seminar from the Society for Industrial and Applied Mathematics. Delve into the security of multivariate cryptographic primitives, focusing on the challenges of computing solutions for multivariate polynomial systems over finite fields. Learn about Gröbner bases computations and their impact on cryptographic security. Examine linear-algebra-based methods for computing Gröbner bases, considered the most efficient algorithms available. Investigate key invariants controlling complexity and explore the difficulty of solving "random" polynomial systems. Gain insights into post-quantum cryptography, the multivariate quadratic problem, and practical applications such as the MinRank problem and the ABC cryptosystem.

Intro
A CRYPTOGRAPHY PRIMER Main goal: Achieving privacy and security in communications
ONE-WAY TRAPDOOR FUNCTIONS M set of messages, set of cyphertexts Definition
POST-QUANTUM CRYPTOGRAPHY
MULTIVARIATE CRYPTOGRAPHY
THE MULTIVARIATE QUADRATIC PROBLEM AND GRÖNER BASES
THE IMPORTANCE OF BEING LEX Shape Lemma
LINEAR-ALGEBRA-BASED GB ALGORITHMS Built from an idea of Lazard, they are currently the most efficient They include F/5s, XL and its variants
COMPUTING A LEX GROBNER BASIS IN PRACTICE compute a drl Grobner basis using a linear algebra-based algorithm convertit into a lex one using the FGLM Algorithm For cryptographic system, the complexity is dominated by the first step
BOUNDING THE SOLVING DEGREE
EXAMPLE - THE COMPLEXITY OF MINRANK MinRank Problem
RANDOM POLYNOMIAL SYSTEMS
HILBERT SERIES AND REGULAR SEQUENCES
REGULAR AND SEMIREGULAR SEQUENCES
SOLVING DEGREE OF SEMIREGULAR SEQUENCES
(RANDOM) REGULAR SEQUENCES OF QUADRICS
THE ABC CRYPTOSYSTEM