Let $n \in \mathbb{N}$ be a predefined integer. Consider the following bijection (between the ring of integers modulo $2^n$ and finite field with $2^n$ elements: $$ \phi: \mathbb{Z}_{2^n} \to \mathbb{F}_{2^n},$$ where $\phi$ is given by the following rule: if basis $(e_1, \dots, e_n) \in \mathbb{F}_{2^n}$ is chosen and fixed, then the image of $\bar{x}$ is $\sum_{i=1}^{n} x_i e_i$, where $(x_0, x_1, \dots, x_n)$ is the bit decomposition of $x \in [0, 2^n-1]$ - the representative of $\bar{x}$.
Consider the following function $f: \mathbb{F}_{2^n} \times \mathbb{F}_{2^n} \to \mathbb{F}_{2^n},$ given by: $f(x, y) = \phi (\phi^{-1}(x) + \phi^{-1}(y))$, where $+$ denotes the ordinary addition in the ring $\mathbb{Z}_{2^n}$. Note, that this function $f$ is obviously different from $g: \mathbb{F}_{2^n} \times \mathbb{F}_{2^n} \to \mathbb{F}_{2^n}: g(x, y) = x+ y$, which will correspond to bitwise xor under our bijection.
As any function over the finite field, $f(x, y)$ may be represented as a polynomial in $(x, y)$, but apriori there is no bound on the degree of such a polynomial. The question I'm interested in is the following: what are the conditions on $n$ and the chosen basis, for which the corresponding polynomial for $f$ would be of low degree (where low-degree means being $\mathcal{O}(\log n)$ or even $\mathcal O(1)$).
The approach I've tried is to utilize the theory of permutation polynomials over finite fields (and $f$ is definitely a permutation polynomial). These polynomials are often of low degree and well studied, but it seems to me to be computationally infeasible to directly find the closed form for $f$.
PS: This question originates from arithmetization problem in modern zero-knowledge cryptography (zk-Snarks in particular), where the usual task is to represent some deterministic function (for example, hash computation) as a set of polynomial constraint over some finite field. For efficiency purposes we want the number of constraints and the degrees of polynomials to be as small as possible. The natural arithmetic for most modern processors is done $\mod 2^n$, for n = 32 or 64 (width of general-purpose registers) and the problem in question is about the efficient arithmetization of standard hardware-friendly addition.
