# Complexity of GF(2) and applications to cryptography

If I have a system of N polynomial equations with N unknowns in GF(2):

• What are some good methods to solve them?
• What's the highest value of N that can be reasonable solved?

Now, my root interest isn't GF, it's crypto. Here's my reasoning:

1. Any function from a n-dimensional binary vector to {0,1} can be represented as a GF(2) polynomial function of n variables.
2. Thus, for instance, any cipher from (Plaintext, Key) to Ciphertext can be represented as a series of equations (one for each bit in the ciphertext), each a GF(2) polynomial of (p-bits + k-bits) variables.
3. Thus, if we know P and C, and we can solve systems of GF(2) equations, we can determine K.
-
This question could profit from less jargon, in particular "GF". – Raphael Feb 11 '13 at 17:34
GF=Galois Field or finite field. roughly, arithmetic mod 2. – vzn Sep 12 '13 at 1:08
another way of looking at this is that arithmetic operations mod 2 are very similar to binary gates, therefore a GF(2) expression can be converted to a circuit and vice versa (although this basic transform does not seem to be named...?) and therefore this does seem to be closely related to SAT in complexity. – vzn Sep 12 '13 at 1:11
I'm removing parts of the question that are offtopic here. I'm also not clear how the three bullets relate to the main question (other than background, which is okay). The tags seemed pretty haphazardly chosen, so I removed most; I'm open to suggestions. – Raphael Feb 7 at 18:07

The (meta) algorithm you're looking for is the Gröbner basis algorithm. In the last decade, the approach that you mention, called algebraic attacks, has gained momentum in the cryptological community. One person who has been developing efficient Gröbner basis algorithms in the context of cryptography is Faugère. He has some links to relevant papers on his web page, including applications.

Since SAT can also be written as a (small) system of polynomial equations, you shouldn't expect a general algorithm to work always, or even on average. The hope is that some systems of polynomial equations are easier. You have to find these "easy" systems in order to apply this method in cryptology.

-
In other words: This will work in theory. In practice, solving the nonlinear system of polynomial equations in n indeterminants is equiv. to solving n-SAT, which is hard. So, it's not a magic wand. The crypto approach is to look for ways to reduce ciphers to small systems, if possible. Is that it? – user6824 Feb 11 '13 at 16:17
Not exactly. Algebraic attacks are just one approach. Other approaches are statistical in nature, and they form the majority of cryptological attacks. – Yuval Filmus Feb 11 '13 at 16:21
Yes, I should have said "the crypto approach to use this observation". I'm not defining all crypto, just showing how practical crypto can use this observation. – user6824 Feb 11 '13 at 16:38
What's the highest value of N that can be reasonable solved? Also can you please fix your reference. – Ilya_Gazman Feb 7 at 10:08
@Ilya_Gazman The answer is probably in the papers of Faugere. If you find the correct link, please edit my answer and fix the broken one. – Yuval Filmus Feb 7 at 10:42

Gröbner bases are one approach, but you should also explore SAT solvers. For some problem instances, SAT solvers seem to be more effective. There's a straightforward translation of equations over GF(2) to SAT instances.

If you want to try out various SAT solvers, MiniSAT is a good starting point; it is a solid SAT solver that is pretty good. You might be especially intersted in CryptoMiniSAT, which is based upon MiniSAT but is extended to be especially useful for cryptographic problems. In particular, it was extended to be more effective at reasoning about XOR operations, which are common in cryptography (XOR corresponds to addition in GF(2)), though you may have to set a special configuration parameter to enable this support fully. STP is also a convenient tool for this, as it contains a built-in pre-processing that applies Gaussian elimination over GF(2), which can be convenient for some problem instances.

Finally, you could learn about linearization (converting non-linear equations into linear ones, over a larger set of variables) and re-linearization (applying this idea multiple times). This can sometimes be effective if you have a highly over-constrained set of equations over GF(2).

See also http://www.cryptosystem.net/aes/tools.html (but I make no guarantees whether anything there is accurate or useful).

-

Here is a good article that answer those questions.

What are some software packages or libraries that implement this?
What are some good methods to solve them?

Allan Steel in Magma, cubic Gaussian elimination implemented by Victor Shoup. And the two methods from the article I suggested.

What's the highest value of N that can be reasonable solved?

Base on the references I gave you, a cubic matrix with 100,000 rows would take hours to solve. You can look on the values from the article below.

Matrix Dimension        Cubic PLE        Algorithm 2
-----------------------------------------------------------------
10, 000 × 10, 000       1.478s              0.880s
16, 384 × 16, 384       5.756s              3.570s
20, 000 × 20, 000       8.712s              5.678s
32, 000 × 32, 000       29.705s             24.240s

-
This doesn't answer the question that was asked. The techniques you cite are only for systems of linear equations. The questions asks about systems of polynomials, which are much harder to solve (as in general polynomials need not be linear). – D.W. Feb 9 at 0:33