Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-24T21:25:50.382Z Has data issue: false hasContentIssue false
  • English
  • Français

Phase transition of multivariate polynomial systems

Published online by Cambridge University Press:  01 February 2009

GIORDANO FUSCO  and
ERIC BACH
GIORDANO FUSCO
Affiliation:
Computer Sciences Department, Stony Brook University, Stony Brook, NY 11794 Email: [email protected]
ERIC BACH
Affiliation:
Computer Sciences Department, University of Wisconsin-Madison, Madison, WI 53706 Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A random multivariate polynomial system with more equations than variables is likely to be unsolvable. On the other hand, if there are more variables than equations, the system has at least one solution with high probability. In this paper we study in detail the phase transition between these two regimes, which occurs when the number of equations equals the number of variables. In particular, the limiting probability for no solution is 1/e at the phase transition, over a prime field.

We also study the probability of having exactly s solutions, with s ≥ 1. In particular, the probability of a unique solution is asymptotically 1/e if the number of equations equals the number of variables. The probability decreases very rapidly if the number of equations increases or decreases.

Our motivation is that many cryptographic systems can be expressed as large multivariate polynomial systems (usually quadratic) over a finite field. Since decoding is unique, the solution of the system must also be unique. Knowing the probability of having exactly one solution may help us to understand more about these cryptographic systems. For example, whether attacks should be evaluated by trying them against random systems depends very much on the likelihood of a unique solution.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 9 - 23
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Biryukov, A. and De Cannière, C. (2003) Block ciphers and systems of quadratic equations. Proc. FSE 2003. Springer-Verlag Lecture Notes in Computer Science 2887 274–289.CrossRefGoogle Scholar
Beame, P., Impagliazzo, R., Krajíček, J., Pitassi, T. and Pudlák, P. (1996) Lower bounds on Hilbert's Nullstellensatz and propositional proofs. Proc. London Math. Soc. 73 1–26.CrossRefGoogle Scholar
Buss, S., Impagliazzo, R., Krajíček, J., Razborov, A. A. and Sgall, J. (1997) Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Comput. Complex. 6 256–298.CrossRefGoogle Scholar
Clegg, M., Edmonds, J. and Impagliazzo, R. (1996) Using the Groebner basis algorithm to find proofs of unsatisfiability. Proc. 28th Ann. ACM Symp. Theory Comput. 174–183.CrossRefGoogle Scholar
Courtois, N., Klimov, A., Patarin, J. and Shamir, A. (2000) Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Proc. Eurocrypt 2000. Springer-Verlag Lecture Notes in Computer Science 1807 392–407.CrossRefGoogle Scholar
Courtois, N. and Pierpzyk, J. (2002) Cryptanalysis of block ciphers with overdefined systems of equations. In: Proc. Asiacrypt 2002. Springer-Verlag Lecture Notes in Computer Science 2501 267–287.CrossRefGoogle Scholar
Dickson, L. E. (1899) Determination of the structure of all linear homogeneous groups in a Galois field which are defined by a quadratic invariant. Amer. J. Math. 21 193–256.CrossRefGoogle Scholar
Friegut, E. (1999) Necessary and sufficient conditions for sharp thresholds of graph properties and the k-SAT problem. Amer. J. Math. 12 1017–1054.CrossRefGoogle Scholar
Franco, J. (2001) Results related to threshold phenomena research in satisfiability: lower bounds. Theoret. Comput. Sci. 265 (1-2)147–157.CrossRefGoogle Scholar
Franco, J. (2005) Typical case complexity of satisfiability algorithms and the threshold phenomenon. Disc. Appl. Math. 153 (1-3)89–123.CrossRefGoogle Scholar
Gerth, F. (1986) Limit probabilities for coranks of matrices over GF(q). Lin. Multilin. Alg. 19 79–93.CrossRefGoogle Scholar
Håstad, J., Phillips, S. and Safra, S. (1993) A well-characterized approximation problem. Inf. Proc. Lett. 47 (6)301–305.CrossRefGoogle Scholar
Jordan, C. (1872) Sur la forme canonique des congruences du second degré et le nombre de leurs solutions. J. Math. Pures. Appls. 17 (2)368–402. (Abstract of results in C. R. Acad. Sci. (1872) 74 1093–1095.)Google Scholar
Pitassi, T. (1997) Algebraic propositional proof systems. In: Immerman, N. and Kolaitis, P. G. (eds.) Descriptive Complexity and Finite Models, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 31 215–244.CrossRefGoogle Scholar
Valiant, L. G. (1979) The complexity of enumeration and reliability problems. SIAM J. Comput. 8 4120–421.CrossRefGoogle Scholar
Woods, A. R. (1998) Unsatisfiable systems of equations, over a finite field. Proc. 39th Ann. Symp. Found. Comput. Sci. 202–211.CrossRefGoogle Scholar