In their paper about the AEAD scheme NORX, the authors mention that $a+b$ can be "well approximated" (this is a bit a hand-wavy statement) by $$a+b \; "="\; a\oplus b \oplus ((a\land b) \ll 1).$$

(Note that the purpose of $((a \land b) \ll 1)$ is to simulate the "carry bit operation.")

Is there such a neat approximation for multiplication $a\cdot b$?

  • $\begingroup$ While I can recommend the whole paper by Aumasson et al linked in the question, let me add that the approximation of $+$ is mentioned at the top of page 2. $\endgroup$ May 30, 2021 at 17:53
  • 2
    $\begingroup$ While I have no literature references, it looks like that approximation comes from representing $a+b$ via an adder (via something like $a + b = (a\oplus b) + ((a\land b)\gg 1)$, and then approximating $+\mapsto \oplus$. To derive something similar for $a\cdot b$ I would try to apply some similar process to a binary multiplier, and then try to approximate the resulting expression. $\endgroup$
    – Mark
    May 30, 2021 at 22:41
  • 2
    $\begingroup$ I can't think of anything that wouldn't result in a lot of operations. Even using $\mathbb{F}_2[x]$ multiplication as a primitive, there doesn't seem to be some simple relation between the two operations to make a useful compromise. The obvious thing is to do shift-and-add multiplication using the NORX operation as the "add", but that's not exactly "neat". $\endgroup$ May 31, 2021 at 4:10
  • $\begingroup$ Thanks to both commenters; the way @Mark suggests is the natural thing to do. I wondered whether there is some nifty shortcut I keep missing $\endgroup$ May 31, 2021 at 8:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.