Polynomial-time algorithms for quadratic isomorphism of polynomials: The regular case

Jérémy Berthomieu, Jean-Charles Faugère, Ludovic Perret

TL;DR

This paper presents randomized polynomial-time algorithms for solving the Quadratic Isomorphism of Polynomials problem (IP1S) for quadratic forms. This is a significant step towards solving a fundamental problem in multivariate cryptography and computational algebra, particularly for the "regular" instances.

What Problem Does This Paper Address?

The Isomorphism of Polynomials (IP) problem, and its variant IP1S (Isomorphism of Polynomials with One Secret), are central to multivariate cryptography and have connections to problems in arithmetic complexity. The core challenge is to determine if two sets of polynomials are equivalent under an invertible linear transformation of variables. While IP1S for general polynomials is known to be hard, the case of quadratic forms has been particularly challenging. For $m=1$ (a single quadratic form), the problem is solved. However, for $m > 1$ (multiple quadratic forms), no polynomial-time algorithm existed for the general case, even for the "regular" instances where certain matrices associated with the polynomials are invertible. This paper aims to bridge this gap by providing efficient algorithms for this important sub-problem.

Methods

The authors employ a multi-pronged approach:

  • Reduction to Canonical Form: They show that IP1S for quadratic polynomials can be reduced to a canonical form. This involves transforming the problem into finding a D-orthogonal matrix that satisfies certain conjugacy conditions.
  • Linearization: The problem of finding an invertible matrix in a linear space of matrices is tackled. This is achieved by reducing it to testing the simultaneous similarity of symmetric matrices.
  • Matrix Square Root Computation: A key algorithmic component is the efficient computation of matrix square roots, particularly over algebraic extensions. They adapt existing methods and propose new ones to control bit complexity.
  • Field Extensions and Jordan Normal Form: To amplify success probabilities and handle cases where solutions might not exist in the base field, they leverage field extensions and the computation of Jordan normal forms.
  • Specialized Algorithms for Characteristic 2: The paper addresses the unique challenges posed by fields of characteristic 2, developing specific algorithms for this case.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their complexity, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Power of Canonical Forms: Reducing the complex IP1S problem to a canonical form significantly simplifies the algorithmic task, making it amenable to polynomial-time solutions for regular instances.
  • Linearizing Non-linear Problems: The ability to linearize the problem by transforming it into finding matrices within a specific subspace is a crucial algorithmic insight.
  • Matrix Square Roots as a Bottleneck: The paper highlights that computing matrix square roots, especially with controlled bit complexity, is a critical and challenging sub-problem in solving IP1S.
  • Characteristic 2 Peculiarities: The distinct behavior of matrices and their square roots in characteristic 2 necessitates specialized algorithmic treatments.

Key Results

  • Randomized Polynomial-Time Algorithm for Regular Quadratic IP1S: The paper presents a randomized polynomial-time algorithm for solving IP1S for regular quadratic homogeneous instances.
  • Deterministic Algorithms: Under certain non-degeneracy assumptions, the randomized algorithms can be turned into deterministic ones.
  • Handling Inhomogeneous Polynomials: A reduction from inhomogeneous polynomials with affine transformations to homogeneous polynomials with linear transformations is established.
  • Counting Solutions (#IP1S): The paper also addresses the counting problem, providing an upper bound on the number of solutions for quadratic-IP1S.
  • Special Case of IP: A randomized polynomial-time algorithm is presented for a specific case of the general IP problem involving power polynomials.

Limitations and Future Work

  • Irregular Cases: The paper explicitly acknowledges that its algorithms fail on "irregular" instances, where linear combinations of Hessian matrices are always singular. This remains an open and intriguing challenge.
  • Field Size Requirements: For certain algorithms, particularly those involving factorization, the size of the field K needs to be sufficiently large, which is a practical limitation.
  • General IP Problem: While progress is made on a special case of the general IP problem, a polynomial-time solution for all instances of IP remains an open question.
  • Efficiency for Large n: While polynomial-time, the complexity might still be high for very large dimensions $n$, especially in cryptographic applications where $n$ is typically constrained.

Summary updated

Abstract

Let $\mathbf{f}=(f\_1,\ldots,f\_m)$ and $\mathbf{g}=(g\_1,\ldots,g\_m)$ be two sets of $m\geq 1$ nonlinear polynomials over $\mathbb{K}[x\_1,\ldots,x\_n]$ ($\mathbb{K}$ being a field). We consider the computational problem of finding -- if any -- an invertible transformation on the variables mapping $\mathbf{f}$ to $\mathbf{g}$. The corresponding equivalence problem is known as {\tt Isomorphism of Polynomials with one Secret} ({\tt IP1S}) and is a fundamental problem in multivariate cryptography. The main result is a randomized polynomial-time algorithm for solving {\tt IP1S} for quadratic instances, a particular case of importance in cryptography and somewhat justifying {\it a posteriori} the fact that {\it Graph Isomorphism} reduces to only cubic instances of {\tt IP1S} (Agrawal and Saxena). To this end, we show that {\tt IP1S} for quadratic polynomials can be reduced to a variant of the classical module isomorphism problem in representation theory, which involves to test the orthogonal simultaneous conjugacy of symmetric matrices. We show that we can essentially {\it linearize} the problem by reducing quadratic-{\tt IP1S} to test the orthogonal simultaneous similarity of symmetric matrices; this latter problem was shown by Chistov, Ivanyos and Karpinski to be equivalent to finding an invertible matrix in the linear space $\mathbb{K}^{n \times n}$ of $n \times n$ matrices over $\mathbb{K}$ and to compute the square root in a matrix algebra. While computing square roots of matrices can be done efficiently using numerical methods, it seems difficult to control the bit complexity of such methods. However, we present exact and polynomial-time algorithms for computing the square root in $\mathbb{K}^{n \times n}$ for various fields (including finite fields). We then consider \\#{\tt IP1S}, the counting version of {\tt IP1S} for quadratic instances. In particular, we provide a (complete) characterization of the automorphism group of homogeneous quadratic polynomials. Finally, we also consider the more general {\it Isomorphism of Polynomials} ({\tt IP}) problem where we allow an invertible linear transformation on the variables \emph{and} on the set of polynomials. A randomized polynomial-time algorithm for solving {\tt IP} when \(\mathbf{f}=(x\_1^d,\ldots,x\_n^d)\) is presented. From an algorithmic point of view, the problem boils down to factoring the determinant of a linear matrix (\emph{i.e.}\ a matrix whose components are linear polynomials). This extends to {\tt IP} a result of Kayal obtained for {\tt PolyProj}.
BibTeX
@article{berthomieu2015polynomial,
  author = {Jérémy Berthomieu and Jean-Charles Faugère and Ludovic Perret},
  title = {{Polynomial-time algorithms for quadratic isomorphism of polynomials: The regular case}},
  journal = {J. Complex},
  year = {2015},
  doi = {10.1016/j.jco.2015.04.001},
}
Figure