# AES as Integer Program

I read that AES can be broken by solving a Linear Integer Program (IP).

1. From a given encrypted text, how can one construct this IP?
2. How big is the system?
• 2. Too big to be easier than just brute forcing AES. – Nova Mar 3 '15 at 14:31
• If I am correct, every symmetric algorithm can be described by a system. The problem is the whole system is too much big to be solved. – ddddavidee Mar 3 '15 at 14:42
• yes i know, but i am still interested how this system look like! – user3613886 Mar 3 '15 at 14:51
• @user3613886, to make simple, each output bit is a boolean function depending of the 128-bits of input message ${x_1, \cdots, x_{128}}$ with also their ONE-Complement and the n-bits of the key ${k_1, \cdots, k_n}$ with also their ONE complement. n=128, 192 or 256 depending of the required secutity. Then each output bit can be viewed as a huge sum of these monomials. After that you can allways try to optimize with KARNAUGH or Queen-Mac Cluskey. I however warn that these method are generally limited to few number of variables $\leq 10$. – Robert NACIRI Mar 3 '15 at 15:21
• Where did you read this? Did they not give any references? – mikeazo Mar 3 '15 at 15:23

First I find the question legitimate and trying to evaluate the complexity is not an easy problem. But regarding how it looks like, I would mention beforehand that AES or any other crypto algorithm could be written in many different ways.

BTW any crypto function appears like a map $\{0,1\}^n \times \{0,1\}^m \longrightarrow \;\{0,1\}^n$, with appropriate identification of message and key spaces. We then can mathematically modelize with the theory of boolean functions.

For a chosen m-bit key; $y_i=f_{k,i}(x_1,\cdots,x_n)=\sum_{(u_1,\cdots,u_n)}a_u.x_1^{u_1}\cdots x_n^{u_n}=\sum_u.a_ux^u$, with a compact representation where $u=(u_1,\cdots,u_n)$ and $u_i \in \{-1,0,+1\}$, and $u_i^{-1}=1-u_i$ represents the ONE-complement of the bit $u_i$.

This representation by the boolean function is to indicate the complexity of for synthetisation of a crypto algorithm (even in hardware we can easily build a circuit dedicated to DES, AES or even PKC).
The reduction methods employed in logic design analysis (KARNAUGH, QUEEN_McCLUSKEY,...) are generally limited to a restricted number of variables.
However, boolean functions is an active field of research in cryptography and attacks. See for example how Linear and Differantial cryptanalysis manage the question.

I hope this gives a general idea of this interesting question.