Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

  • What are some good methods to solve them?
  • What are some software packages or libraries that implement this?
  • 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.
share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.