# 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$$?

## 1 Answer

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}).$$

• Then I am wondering why the paper claims that this function "is not obviously invertible at a first glance". Is it true that it is a triangular T-function (as well as addition and subtraction)? – lyrically wicked Jun 11 at 2:32
• It is triangular, but there is no word-based expression for inversion like for addition/subtraction. Probably that's the reason. – Fractalice Jun 11 at 8:48
• 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
• That is correct; not having an inverse with a similar number of word operations as the forward direction is why we called it "not obvious". Both the forward and backward directions are T-functions; a T-function does not need to involve every previous bit to be triangular, it just needs to involve exclusively previous bits. – Samuel Neves Jun 11 at 22:14
• @SamuelNeves: "a T-function does not need to involve every previous bit to be triangular" — it depends on what is meant by the word "involve". According to this Wikipedia article, "if every single less significant bit is included in the update of every bit in the state, such a T-function is called triangular." Note the phrasing: "every single less significant bit". [1/2] – lyrically wicked 2 days ago