Binary Permutation Polynomial Inversion and Application to Obfuscation Techniques

Whether it is for conditional statement, constant, opaque predicate or equation obfuscation, Mixed Boolean Arithmetics (MBA) technique is a powerful tool providing concrete ways to achieve obfuscation. Recent papers ([22,1]) presented ways to mix such tools with permutation polynomials modulo 2n in order to make them more resilient to SMT solvers. However, because of limitations regarding the inversion of such permutations, the set of permutation polynomials presented suffer some restrictions. Such restrictions bring several methods of arithmetic simplification, decreasing their effectiveness at hiding information. In this work, we present general methods for permutation polynomials inversion. Those methods allow us to remove some of the restrictions presented in the literature, making simplification methods less effective. We discuss complexity and limits of these methods, and conclude that not only current simplification methods may not be as effective as we thought, but they are still many uses of polynomial permutations in obfuscation that are yet to be explored.