[Solved]: Complexity of GF(2) and applications to cryptography

Problem Detail: 

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.

Asked By : user6824

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9678

 Ask a Question

 Download Related Notes/Documents