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