Takunari Miyazaki (Trinity College, Hartford, Connecticut,)
The problem of finding a low-rank linear combination of matrices is a fundamental problem in linear algebra. In practice, the problem has also naturally arisen in cryptography (see, e.g., [Cou01a, Cou01b, FLP08,KS99]).
In this note, we consider the problem in the following decision version, which has become of some importance in computational complexity theory.
Let ${\bf F}_q$ denote a finite field of order $q > 0$.
Minimum rank ($q$) (MIN-RANK($q$))
- Instance: matrices $M_0, M_1, \ldots, M_\ell \in M_{m \times n}({\bf F}_q)$ and an integer $r \le m$.
- Question: Are there $\alpha_1, \ldots, \alpha_\ell \in {\bf F}_q$ such that
Buss, Frandsen and Shallit prove in [BFS99] that, in general, MIN-RANK is NP-complete, via an elegant reduction from SAT, inspired by Valiant’s (cf. [Val79, Section 2]).
On the other hand, the well-known Kipnis–Shamir attack on the Hidden Field Equations (HFE) protocol in [KS99] suggests that MIN-RANK may admit a polynomial-time solution when the target rank $r$ is bounded by a constant. In their cryptoanalysis [FLP08], Faug`ere, Levy-dit-Vehel and Perret also propose, using a Gr"obner-basis approach, a polynomial-time solution to MIN-RANK when the co-rank $m - r$ is bounded by a constant.
When an NP-complete problem has a polynomial-time solution for some special cases (e.g., 2-SAT), such a solution often exploits some inherent properties of the problem under the given constraints. While Faug`ere, Levy-dit-Vehel and Perret’s Gr"obner-basis approach is impressive, it is not obvious, at least to me, exactly what properties of the problem make it solvable in polynomial time. In my view, it is thus still worthwhile to ask if there is an ``elementary’’ solution to answer the following question.
Is
MIN-RANK($q$) solvable in polynomial time when the target rank $r$ or co-rank $m - r$ is bounded by a constant?
My interest in MIN-RANK originally arose while working with J. B. Wilson to investigate the complexity of testing singularity of bilinear maps (cf. [MW]).
-
[BFS99] J. F. Buss, G. S. Frandsen and J. O. Shallit, The computational complexity of some problems of linear algebra, J. Comput. System Sci. 58 (1999), 572–596.
-
[Cou01a] N. T. Courtois, La s'ecurit'e des primitives cryptographiques bas'ees sur des probl`emes alg'ebriques multivariables:
MQ,IP,MinRank,HFE, Th`ese de doctorat,Universit'e Pierre et Marie Curie (Paris VI), Paris, 2001. -
[Cou01b] - - - Efficient zero-knowledge authentication based on a linear algebra problem
MinRank, Advances in Cryptology – ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Dec. 9–13, 2001, Proceedings (C. Boyd, ed.), Lecture Notes in Comput. Sci., vol. 2248, Springer, Heidelberg, 2001, pp. 402–421. -
[FLP08] J.-C. Faug`ere, F. Levy-dit-Vehel and L. Perret, Cryptanalysis of
MinRank, Advances in Cryptology – CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, Aug. 17–21, 2008, Proceedings (D. Wagner, ed.), Lecture Notes in Comput. Sci., vol. 5157, Springer, Heidelberg, 2008, pp. 280–296. -
[MW] T. Miyazaki and J. B. Wilson, Linear-size reductions and completeness in algebra, preprint.
-
[KS99] A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology – CRYPTO ‘99, 19th Annual International Cryptology Conference, Santa Barbara, Aug. 15–19, 1999, Proceedings (M. Wiener, ed.), Lecture Notes in Comput. Sci., vol. 1666, Springer, Heidelberg, 1999, pp. 19–30.
-
[Val79] L. G. Valiant, Completeness classes in algebra, Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, Apr. 30–May 2, 1979, ACM, New York, 1979, pp. 249–261.
Additional Questions?
If you have additional questions, feel free to reach out to a maintainer / contributor on the contact page.
