# What are the algebraic normal forms for each bit of $z$, where $z = (x \oplus y) \oplus ((x \wedge y) \ll 1)$ (a non-linear operation in NORX)?

Let $$x, y, z$$ denote three $$n$$-bit words such that $$z = (x \oplus y) \oplus ((x \land y) \ll 1).$$

The NORX paper contains the generalized description of the algebraic normal forms for each bit of $$x$$ given $$y$$ and $$z$$: $$\begin{array}{l} x_0 = (z_0 \oplus y_0),\\ x_1 = (z_1 \oplus y_1) \oplus (x_0 \land y_0),\\ \vdots\\ x_i = (z_i \oplus y_i) \oplus (x_{i-1} \land y_{i-1}),\\ \vdots\\ x_{n-1} = (z_{n-1} \oplus y_{n-1}) \oplus (x_{n-2} \land y_{n-2}), \end{array}$$

where $$w_i$$ denotes an $$i$$-th bit of the word $$w \in \{x, y, z\}$$.

What is the corresponding generalized description of the algebraic normal forms for each bit of $$z$$ given $$x$$ and $$y$$?

From $$x_i = z_i \oplus y_i \oplus (x_{i-1} \land y_{i-1})$$ we get $$z_i = x_i \oplus y_i \oplus (x_{i-1} \land y_{i-1}).$$
• It seems that the inverse of H function in NORX is triangular, but the H function itself is not triangular because the algebraic normal form for $z_i$ does not depend on every single less significant bit. Is it true? – lyrically wicked Jun 11 at 9:30