Join Log in
Score:1
avatar Crypto

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)?

de flag
lyrically wicked

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

98
1 + 0
Score:2
Fractalice avatar Crypto
in flag
Fractalice

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

0 + 9
de flag
lyrically wicked
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](https://en.m.wikipedia.org/wiki/T-function) (as well as addition and subtraction)?
0
Reply
Fractalice avatar
in flag
Fractalice
It is triangular, but there is no word-based expression for inversion like for addition/subtraction. Probably that's the reason.
0
Reply
de flag
lyrically wicked
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?
0
Reply
pe flag
Samuel Neves
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.
1
Reply
de flag
lyrically wicked
@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](https://en.m.wikipedia.org/wiki/T-function), "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]
0
Reply
de flag
lyrically wicked
@SamuelNeves: The backward direction of H function matches the definition of "triangular", but the forward direction does not because the ANF for an $i$-th bit of the word $x$ (i.e. backward direction) contains $x_{i-1}$, but the ANF for an $i$-th bit of the word $z$ (i.e. forward direction) does not contain $z_{i-1}$. Is my understanding of "triangularity" correct? [2/2]
0
Reply
pe flag
Samuel Neves
It seems a bit silly to me to be talking about triangular T-functions, since the T already stands for triangular. I don't quite know where the wikipedia article got that definition from, since I don't recall seeing it in literature.
0
Reply
de flag
lyrically wicked
@SamuelNeves: Section 4 in the paper "A New Class of Invertible Mappings" [A. Klimov, A. Shamir] gives a description of what the name "T-function" refers to, and explains the difference between the implicit triangulation and the explicit triangulation... So maybe a "triangular T-function" implies a "T-function which has an explicit triangular shape"?
0
Reply
pe flag
Samuel Neves
OK, as far as I can tell Wikipedia has a much more restricted definition of a T-function, which forces it to be invertible (this is not necessarily the case). What it calls a T-function is what one would ordinarily call an invertible or bijective T-function, and what it calls a triangular T-function is what one would call a single-cycle T-function. So, the NORX op is a bijective T-function, but definitely not a single-cycle T-function (when fixing one of the arguments).
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.