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?

  • $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Sep 1 '10 at 13:58
  • $\begingroup$ 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. $\endgroup$ – Ross Snider Sep 1 '10 at 17:23
  • $\begingroup$ 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). $\endgroup$ – Ross Snider Sep 1 '10 at 17:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 2 '10 at 0:08
  • 1
    $\begingroup$ (My understanding is that stating the right question is sometimes more difficult than answering it….) $\endgroup$ – Tsuyoshi Ito Sep 2 '10 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.