<p>Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ and blue variables ${v_b}_0, {v_b}_1, ..., {v_b}_m$ (all in $\mathbb{F}_2$).</p>

<p>Suppose also that you are given a description of $P*$, a polynomial defined over the collection $P_0, P_1, ..., P_n$.</p>

<p>Blue variables are 'mutable' and public, and may be set to any constant term ${0, 1}$ or to dynamically represent a polynomial combination of other red and blue variables. Red variables are static and are 'unknown'.</p>

<p>Here are some problems I would like to automate. Each bulletpoint below represents a slightly different optimization problem. Given $P*$, $P_0, P_1, ..., P_n$, $z$ and $k$ and $n$ and $m$ and $d$, how should I set the value of blue variables in order that:</p>

<ul>
<li>The number of red variables in the largest degree term of $P*$ is minimized.</li>
<li>The number of polynomials $P_0, P_1, ..., P_n$ forced to the value 0 is maximized.</li>
</ul>

<p>Both problems are subject to the constraints that:</p>

<ul>
<li>There will only be one term of the highest degree in $P*$ with red variables.</li>
<li>$P*$ is of degree $d$ or less (viewed as a polynomial over red and blue variables).</li>
</ul>

<p>I'm looking to understand the complexity of finding solutions which optimize one of the two first goals in the list. Additionally, I'd like to know how hard it is to find <em>some</em> satisfying assignment (or prove that none exist) - without considering the optimization in either problem above.</p>

<p>Does anyone have a reference to a similar problem that might be adaptable to these scenarios? A hunch or intuition about the correct way to approach the problem? Or (ideally) an answer to these questions with referenced papers or solid proof?</p>

CC BY-SA 2.5
2010-09-01T13:58:02.433Z
I cannot understand the problem at all, and I hope that the questioner or those who voted the question up will clarify the question.  Here are several things I cannot understand.  How is one supposed to optimize two things at the same time?  How is ∑P_i+1 (why +1?) computed without knowing the values of “red variables”?  If you assign values in F_2 to variables, ∑P_i+1 evaluates to a value in F_2; how do you compare the values in F_2?  By the degree of P*, do you mean the degree in v_{ri}’s and v_{bi}’s or the degree in P_0,…,P_n?  What on earth does the third bullet mean?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-01T17:23:56.683Z
The second goal is auxilary. Really the the number of red variables should be minimized. However, this second auxilary goal isn't strictly _required_ for the problem. In fact, this is where the "some problems" in the title comes from.

The motivation for the problem is the automation of dynamic cube attacks. Maximizing the sum over P_i + 1 (due to F2) means maximizing the number of polynomials that evaluate to 0. It's very difficult to compute the value of the polynomials without knowing the red values, but it is often the case the changing the blue variables forces evaluation.
Ross Snider
CC BY-SA 2.5
2010-09-01T17:24:32.140Z
By degree of P* I mean the degree on a red/blue variable level. The third bullet I hoped was clear. Suppose P* is xy + yz and x is red and y, z are blue. This is a 'good' polynomial. Now, suppose y is red and x,z are blue. This is a 'bad' polynomial. Split the polynomial into several terms and order them by degree. Of the terms of the highest degree, there ought be only one with red variables (and there should be fewer than d of them).
Ross Snider
CC BY-SA 2.5
2010-09-01T23:33:57.757Z
What do you mean by satisfying assignments?  Also, if “Of the terms of the highest degree, there ought be only one with red variables” is satisfied, it seems obvious to me that there are fewer than d of them, because there is only one.  I think I am missing something.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-01T23:52:51.940Z
A satisfying assignment in this case would be an assignment of values to blue variables such that the two constraints (lower bullet list) are met. The second confusion is entirely my fault. I meant "there will only be one term of the highest degree with red variables and there will be fewer than or equal to d red variables in that term (which is obvious because the highest term has to be of degree d or lower)." The way I tried to communicate that was really confusing.
Ross Snider
CC BY-SA 2.5
2010-09-02T00:03:35.107Z
Now I understand the second point.  Can I suggest you to replace the bullet in the question with what you wrote in the comment?  I think that the way you wrote it in the comment is much better than the way you stated in the question and, honestly speaking, I still cannot parse that sentence in the question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T00:04:30.127Z
As for the meaning of satisfying assignments, I still do not understand.  The two constraints are, as you stated, not constraints on an assignment but constraints on the problem (called “promises”).  For example, it does not make sense to me to speak of something like “an assignment such that the degree of P* in red and blue variables is at most d” because P* is given as part of the input and changing assignments does not affect (the degree of) P*.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T00:08:47.440Z
By the way, I do not think I can answer the question even if you answer all my questions (sorry).  But at least I am trying to help you improve the statement of the question so that people can understand it more easily.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T00:17:02.740Z
Thank you Tsuyoshi for helping me to clarify what I mean. A description of P* is given as input to the problem. I'll give an example in the problem statement.
Ross Snider
CC BY-SA 2.5
2010-09-02T00:35:06.643Z
Thanks for revising the question.  After reading the revised question, I noticed a few more points.  First, as for the first optimization problem, suppose that the only highest-degree term containing red variables contains r red variables.  Then it seems to me that the value to minimize is either 0 or r (depending on whether that particular term vanishes or not).  It is quite unnatural to speak of a minimization problem if there are only two possible values for the objective function, so I guess I am missing something.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T00:39:14.877Z
As for the second optimization problem, this may show my lack of knowledge, but what do you mean by a polynomial “forced to the value 0”?  More concretely, does the polynomial x^2−x count as a polynomial forced to the value 0 (assuming the variable x is a red variable)?  It is a nonzero polynomial but it evaluates to 0 if you substitute x with any element of F_2.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T00:44:37.633Z
@Tsuyoshi I am responding to your question about the second optimization problem. Suppose P_0 = r1 * b1. If I set b1 = 0, P_0 is forced to be 0. In a similar way, if I could manipulate blue varibles so that a polynomial (taking assignments of blue variables into account) reduces to x^2 - x (where x is a red variable) then I have also forced the polynomial to be equal to 0.
Ross Snider
CC BY-SA 2.5
2010-09-02T00:47:54.100Z
@Tsuyoshi I am responding to your question about the first optimization problem. I do not understand how the first problem is not an optimization problem. It is my understanding that the polynomial could take on a highest degree term with many to few to 0 red variables.
Ross Snider
CC BY-SA 2.5
2010-09-02T01:21:49.100Z
Let me clarify my concern about the first optimization problem.  According to the first promise, only one of the highest-degree terms in P* (in red and blue variables) contains red variables.  Call it T, and let r be the number of red variables in T.  Now suppose that we assign values to the blue variables.  If T vanishes, the highest-degree term T no longer contains red variables.  If T does not vanish, the highest-degree term T contains r red variables.  Therefore, the value of objective function is either 0 or r.  What am I missing?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T01:28:36.850Z
As for the second optimization problem, you should be careful about the wording because the polynomial x^2−x is a different polynomial from the polynomial 0 (that is why I wrote “It is a nonzero polynomial”), although they define the same _function_ from F_2 to F_2.  How about defining the phrase “forced to the value 0” explicitly?  An example: A polynomial P_i is said to be forced to the value 0 (by an assignment to blue variables) if the polynomial evaluates to 0 for every assignment of values in F_2 to red variables.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T01:30:30.747Z
(My understanding is that stating the right question is sometimes more difficult than answering it….)
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T01:38:12.090Z
You are missing the fact that setting blue variables so that T disappears could introduce another highest term U with y red variables. Specifically "Blue variables are 'mutable' and public, and may be set to any constant term ${0, 1}$ or to dynamically represent a polynomial combination of other red and blue variables." Blue variables can take on values other than 0 or 1. They can take on the function of other variables.
Ross Snider
CC BY-SA 2.5
2010-09-02T01:40:13.677Z
With respect to "A polynomial P_i is said to be forced to the value 0 (by an assignment to blue variables) if the polynomial evaluates to 0 for every assignment of values in F_2 to red variables." Yes. That is what I am (failing at?) asking.
Ross Snider
CC BY-SA 2.5
2010-09-02T01:59:18.593Z
“You are missing the fact that …”  Oh, I see!  Now a new question: I do not understand which values each blue variable can take.  You say that a blue variable can take a polynomial combination of other red and blue variables.  For example, what happens if b_1 is substituted with b_2 and b_2 is substituted with b_1?  It sounds like an infinite loop.  If this kind of cycle is not allowed, then it is equivalent to allowing polynomials consisting of only red variables.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T02:03:38.387Z
Also, how are P_0, …, P_n, P* represented in the input to an algorithm?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T12:42:44.133Z
As for “forced,” my point is that the terminology “(polynomials are) forced to the value 0” in the question is ambiguous unless it is already an established terminology, because a polynomial being 0 is very different from a polynomial evaluating to 0 at all the points in F_2^d (where d is the number of variables), as demonstrated by the example x^2−x.
Tsuyoshi Ito
<cc.complexity-theory><cr.crypto-security><polynomials>
Some problems involving polynomials of public and private variables over GF(2).
Ross Snider
# Some problems involving polynomials of public and private variables over GF(2).

(Asked by: username_0 on 2010-09-01)

Suppose there are a set of low degree (less than some degree $z$) polynomials $P\_0, P\_1, ..., P\_k$ each of which is defined over two types of variables, red variables ${v\_r}\_0, {v\_r}\_1, ..., {v\_r}\_n$ and blue variables ${v\_b}\_0, {v\_b}\_1, ..., {v\_b}\_m$ (all in $\mathbb{F}\_2$).

Suppose also that you are given a description of $P\*$, a polynomial defined over the collection $P\_0, P\_1, ..., P\_n$.

Blue variables are 'mutable' and public, and may be set to any constant term ${0, 1}$ or to dynamically represent a polynomial combination of other red and blue variables. Red variables are static and are 'unknown'.

Here are some problems I would like to automate. Each bulletpoint below represents a slightly different optimization problem. Given $P\*$, $P\_0, P\_1, ..., P\_n$, $z$ and $k$ and $n$ and $m$ and $d$, how should I set the value of blue variables in order that:

* The number of red variables in the largest degree term of $P\*$ is minimized.
* The number of polynomials $P\_0, P\_1, ..., P\_n$ forced to the value 0 is maximized.

Both problems are subject to the constraints that:

* There will only be one term of the highest degree in $P\*$ with red variables.
* $P\*$ is of degree $d$ or less (viewed as a polynomial over red and blue variables).

I'm looking to understand the complexity of finding solutions which optimize one of the two first goals in the list. Additionally, I'd like to know how hard it is to find *some* satisfying assignment (or prove that none exist) - without considering the optimization in either problem above.

Does anyone have a reference to a similar problem that might be adaptable to these scenarios? A hunch or intuition about the correct way to approach the problem? Or (ideally) an answer to these questions with referenced papers or solid proof?

**Tags:** cc.complexity-theory, cr.crypto-security, polynomials
> **Comments:**
> **username_1**: I cannot understand the problem at all, and I hope that the questioner or those who voted the question up will clarify the question.  Here are several things I cannot understand.  How is one supposed to optimize two things at the same time?  How is ∑P_i+1 (why +1?) computed without knowing the values of “red variables”?  If you assign values in F_2 to variables, ∑P_i+1 evaluates to a value in F_2; how do you compare the values in F_2?  By the degree of P*, do you mean the degree in v_{ri}’s and v_{bi}’s or the degree in P_0,…,P_n?  What on earth does the third bullet mean?  
> **username_0**: The second goal is auxilary. Really the the number of red variables should be minimized. However, this second auxilary goal isn't strictly _required_ for the problem. In fact, this is where the "some problems" in the title comes from.  The motivation for the problem is the automation of dynamic cube attacks. Maximizing the sum over P_i + 1 (due to F2) means maximizing the number of polynomials that evaluate to 0. It's very difficult to compute the value of the polynomials without knowing the red values, but it is often the case the changing the blue variables forces evaluation.  
> **username_0**: By degree of P* I mean the degree on a red/blue variable level. The third bullet I hoped was clear. Suppose P* is xy + yz and x is red and y, z are blue. This is a 'good' polynomial. Now, suppose y is red and x,z are blue. This is a 'bad' polynomial. Split the polynomial into several terms and order them by degree. Of the terms of the highest degree, there ought be only one with red variables (and there should be fewer than d of them).  
> **username_1**: What do you mean by satisfying assignments?  Also, if “Of the terms of the highest degree, there ought be only one with red variables” is satisfied, it seems obvious to me that there are fewer than d of them, because there is only one.  I think I am missing something.  
> **username_0**: A satisfying assignment in this case would be an assignment of values to blue variables such that the two constraints (lower bullet list) are met. The second confusion is entirely my fault. I meant "there will only be one term of the highest degree with red variables and there will be fewer than or equal to d red variables in that term (which is obvious because the highest term has to be of degree d or lower)." The way I tried to communicate that was really confusing.  
> **username_1**: Now I understand the second point.  Can I suggest you to replace the bullet in the question with what you wrote in the comment?  I think that the way you wrote it in the comment is much better than the way you stated in the question and, honestly speaking, I still cannot parse that sentence in the question.  
> **username_1**: As for the meaning of satisfying assignments, I still do not understand.  The two constraints are, as you stated, not constraints on an assignment but constraints on the problem (called “promises”).  For example, it does not make sense to me to speak of something like “an assignment such that the degree of P* in red and blue variables is at most d” because P* is given as part of the input and changing assignments does not affect (the degree of) P*.  
> **username_1**: By the way, I do not think I can answer the question even if you answer all my questions (sorry).  But at least I am trying to help you improve the statement of the question so that people can understand it more easily.  
> **username_0**: Thank you Tsuyoshi for helping me to clarify what I mean. A description of P* is given as input to the problem. I'll give an example in the problem statement.  
> **username_1**: Thanks for revising the question.  After reading the revised question, I noticed a few more points.  First, as for the first optimization problem, suppose that the only highest-degree term containing red variables contains r red variables.  Then it seems to me that the value to minimize is either 0 or r (depending on whether that particular term vanishes or not).  It is quite unnatural to speak of a minimization problem if there are only two possible values for the objective function, so I guess I am missing something.  
> **username_1**: As for the second optimization problem, this may show my lack of knowledge, but what do you mean by a polynomial “forced to the value 0”?  More concretely, does the polynomial x^2−x count as a polynomial forced to the value 0 (assuming the variable x is a red variable)?  It is a nonzero polynomial but it evaluates to 0 if you substitute x with any element of F_2.  
> **username_0**: @Tsuyoshi I am responding to your question about the second optimization problem. Suppose P_0 = r1 * b1. If I set b1 = 0, P_0 is forced to be 0. In a similar way, if I could manipulate blue varibles so that a polynomial (taking assignments of blue variables into account) reduces to x^2 - x (where x is a red variable) then I have also forced the polynomial to be equal to 0.  
> **username_0**: @Tsuyoshi I am responding to your question about the first optimization problem. I do not understand how the first problem is not an optimization problem. It is my understanding that the polynomial could take on a highest degree term with many to few to 0 red variables.  
> **username_1**: Let me clarify my concern about the first optimization problem.  According to the first promise, only one of the highest-degree terms in P* (in red and blue variables) contains red variables.  Call it T, and let r be the number of red variables in T.  Now suppose that we assign values to the blue variables.  If T vanishes, the highest-degree term T no longer contains red variables.  If T does not vanish, the highest-degree term T contains r red variables.  Therefore, the value of objective function is either 0 or r.  What am I missing?  
> **username_1**: As for the second optimization problem, you should be careful about the wording because the polynomial x^2−x is a different polynomial from the polynomial 0 (that is why I wrote “It is a nonzero polynomial”), although they define the same _function_ from F_2 to F_2.  How about defining the phrase “forced to the value 0” explicitly?  An example: A polynomial P_i is said to be forced to the value 0 (by an assignment to blue variables) if the polynomial evaluates to 0 for every assignment of values in F_2 to red variables.  
> **username_1**: (My understanding is that stating the right question is sometimes more difficult than answering it….)  
> **username_0**: You are missing the fact that setting blue variables so that T disappears could introduce another highest term U with y red variables. Specifically "Blue variables are 'mutable' and public, and may be set to any constant term ${0, 1}$ or to dynamically represent a polynomial combination of other red and blue variables." Blue variables can take on values other than 0 or 1. They can take on the function of other variables.  
> **username_0**: With respect to "A polynomial P_i is said to be forced to the value 0 (by an assignment to blue variables) if the polynomial evaluates to 0 for every assignment of values in F_2 to red variables." Yes. That is what I am (failing at?) asking.  
> **username_1**: “You are missing the fact that …”  Oh, I see!  Now a new question: I do not understand which values each blue variable can take.  You say that a blue variable can take a polynomial combination of other red and blue variables.  For example, what happens if b_1 is substituted with b_2 and b_2 is substituted with b_1?  It sounds like an infinite loop.  If this kind of cycle is not allowed, then it is equivalent to allowing polynomials consisting of only red variables.  
> **username_1**: Also, how are P_0, …, P_n, P* represented in the input to an algorithm?  
> **username_1**: As for “forced,” my point is that the terminology “(polynomials are) forced to the value 0” in the question is ambiguous unless it is already an established terminology, because a polynomial being 0 is very different from a polynomial evaluating to 0 at all the points in F_2^d (where d is the number of variables), as demonstrated by the example x^2−x.  

---

## 0 answers

