Join Log in
Score:1
Dominic van der Zypen avatar Crypto

Inverses of the operation $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ for fixed bit length

br flag
Dominic van der Zypen

Background. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b \; \approx \; a \oplus b \oplus ((a \land b) \ll 1)$$ where $\oplus$ is bitwise XOR and $\land$ is bitwise AND, and $\ll$ is left-shift by 1 position. (The purpose of $((a \land b) \ll 1)$ is to simulate the "carry-bit" operation.)

Formulation of question. We can view this as an operation $+^{n}_\sim : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}^n$, defined by $(a, b) \mapsto a \oplus b \oplus ((a \land b) \ll 1)$. For $b\in \{0,1\}^n$ we get a map $s^n_b: \{0,1\}^n\to \{0,1\}^n$ defined by $$a \mapsto a +^{n}_\sim b.$$

Is $s^n_b$ injective (and therefore bijective) for all $n\in\mathbb{N}$ and $b\in \{0,1\}^n$?

57
0 + 0
kelalaka avatar
in flag
kelalaka
That's half-adder. To use it for n-bit you need Full-adder to propagate.
0
Reply
poncho avatar
my flag
poncho
Is this a homework question?
1
Reply
kelalaka avatar
in flag
kelalaka
Actually, the $s_b^n$ is not well defined. What does happen to the last carry?
0
Reply
Score:2
Daniel S avatar Crypto
ru flag
Daniel S

Yes, to see this note that $a$ can be computed bitwise from the least significant bit. We write $c$ for $a+^n_\sim b$ and $x_i$ for the $i$th bit of $x$. Observe that: $$a_0=b_0\oplus c_0$$ $$a_i=b_i\oplus c_i\oplus (a_{i-1}\wedge b_{i-1})$$ for $1\le i\le n-1$.

Sadly, there is not a nice 4-bit to 1 bit function bitwise inverse function $(b,c)\mapsto a$ e.g. $a_2$ is a function of $b_0$, $b_1$, $b_2$, $c_0$ and $c_1$.

0 + 0
ธงชาติไทย
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.