On the distributivity of arithmetic and boolean operations in 2ⁿ

✍️ Written on 2021-08-24 in 4846 words.
Part of cs IT-Security pqcrypto

Motivation

In the field of hardware security, you often need to convert between boolean and arithmetic masking (e.g. Coron et al, CHES 2014). As a result, you often need to verify an algorithm mixing arithmetic and boolean operations. One specific usecase I had, was verifying whether \(a \oplus (b \land c) == (a \oplus b) \land (a \oplus c)\) holds true in \(\mathbb{Z}/{16}\mathbb Z\).

Mixing such operations essentially means you don’t know these laws by heart and resort to generating truthtables to verify your claims. In this blogpost, we do it systematically. It answers questions like:

  • Is XOR distributive over AND?

  • Is AND distributive over XOR?

  • Is OR distributive over XOR?

The law of distributivity

The law of distributivity is easy to state: Let x and y be any two elements of a given set S. Let \(\odot\) and \(\oplus\) be two binary operations. We call \(\odot\) left-distributive over \(\oplus\) if and only if …

\[x \odot (y \oplus z) = (x \odot y) \oplus (x \odot z)\]

We call \(\odot\) right-distributive over \(\oplus\) if and only if …

\[(y \oplus z) \odot x = (y \odot x) \oplus (z \odot x)\]

We call \(\odot\) distributive over \(\oplus\) if it is left-distributive and right-distributive.

Usually, you know this property from rings which establish distributivity between addition and multiplication.

A set of operations

Let us denote all numbers in binary, e.g. \(10_2\) for decimal 2. Let \(n\) define \(2^n\) as the number of elements in the set. Now, we consider various operations:

ADD

\(a + b\) is the common addition in \(\mathbb Z/2^n \mathbb Z\), e.g. \(2 + 3\) is \(5\) in \(\mathbb Z/2^3 \mathbb Z\)

SUB

\(a - b\) is subtraction in \(\mathbb Z/2^n \mathbb Z\), e.g. \(2 - 3\) is \(7\) in \(\mathbb Z/2^3 \mathbb Z\)

MUL

\(a \cdot b\) is the common multiplication in \(\mathbb Z/2^n \mathbb Z\), e.g. \(2 \cdot 3\) is \(6\) in \(\mathbb Z/2^3 \mathbb Z\)

DIV

\(a / b\) is division in \(\mathbb Z/2^n \mathbb Z\) with the result \(0\) in special case \(b = 0\), e.g. \(6 / 3\) is \(2\) in \(\mathbb Z/2^3 \mathbb Z\)

XOR

\(a \oplus b\) is a bitwise XOR, e.g. \(5 \cdot 1\) is \(4\)

AND

\(a \land b\) is a bitwise AND, e.g. \(5 \land 1\) is \(1\)

OR

\(a \lor b\) is a bitwise OR, e.g. \(6 \lor 1\) is \(7\)

IF

\(a \rightarrow b\) is an implication between two bits, e.g. if a then (b) else (false)

XNOR

\(\neg (a \oplus b)\) is the negation of bitwise XOR, e.g. 1 and 1 gives 1

NAND

\(\neg (a \land b)\) is the negation of bitwise AND, e.g. 1 and 1 gives 0

You can think of {ADD, SUB, MUL, DIV} as arithmetic operations and {XOR, AND, OR, IF, XNOR, NAND} as boolean operations.

Evaluation

Now, we generate a table for \(n = 1\) where l stands for left-distributivity and r stand for right-distributivity. We always consider the row operation to be distributive over the column operation.

↓ is distributive over → ADD SUB MUL DIV XOR AND OR IF XNOR NAND

ADD

SUB

MUL

l,r

l,r

l,r

l,r

l,r

l,r

l,r

DIV

l,r

l,r

l,r

l,r

l,r

l,r

l,r

XOR

AND

l,r

l,r

l,r

l,r

l,r

l,r

l,r

OR

l,r

l,r

l,r

l,r

l,r

l,r

IF

l

l

l

l

l

l

XNOR

NAND

Apparently, …

  • {ADD, SUB, XOR, XNOR, NAND} is not distributive over any other operation.
    For example, ADD is not distributive over ADD because \(x + (y + z) \neq (x + y) + (x + z)\).
    For example, ADD is not distributive over XOR because \(x 1 + (1 \oplus 1) = 1 \neq 0 = (1 + 1) \oplus (1 + 1)\)

  • MUL is distributive over MUL because \(x \cdot (y \cdot z) = (x \cdot y) \cdot (x \cdot z)\) and \((y \cdot z) \cdot x = (y \cdot x) \cdot (z \cdot x)\) in \(\mathbb Z/2\mathbb Z\). Why? Because either all values are one (then both sides are one) or one value is zero (then both sides are zero).

  • I call IF “left-biased” because IF returns 0 whenever the left argument is 0. This the reason why IF is left-distributive, but never right-distributive.

… in \(\mathbb Z/2\mathbb Z\).

So, what about other n?

n == 2

↓ is distributive over → ADD SUB MUL DIV XOR AND OR IF XNOR NAND

ADD

SUB

MUL

l,r

l,r

l,r

DIV

r

XOR

AND

l,r

l,r

l,r

OR

l,r

l,r

IF

l

r

r

r

XNOR

NAND

l,r

l,r

l,r

n == 3

↓ is distributive over → ADD SUB MUL DIV XOR AND OR IF XNOR NAND

ADD

SUB

MUL

l,r

l,r

DIV

XOR

AND

l,r

l,r

l,r

OR

l,r

l,r

IF

l

r

r

r

XNOR

NAND

l,r

l,r

l,r

n == 4

↓ is distributive over → ADD SUB MUL DIV XOR AND OR IF XNOR NAND

ADD

SUB

MUL

l,r

l,r

DIV

XOR

AND

l,r

l,r

l,r

OR

l,r

l,r

IF

l

r

r

r

XNOR

NAND

l,r

l,r

l,r

n == 5

↓ is distributive over → ADD SUB MUL DIV XOR AND OR IF XNOR NAND

ADD

SUB

MUL

l,r

l,r

DIV

XOR

AND

l,r

l,r

l,r

OR

l,r

l,r

IF

l

r

r

r

XNOR

NAND

l,r

l,r

l,r

python3 source code

The following source code was used to generate these results:

#!/usr/bin/env python3

import itertools
import collections


# convenience utilities
bit = lambda bits, i: (bits >> i) & 1

def op_per_bit(op, n):
    """Apply a binary operation to the i-th bits ∀i in i-bits vectors"""
    def per_bit(a, b):
        acc = 0
        for i in range(n):
            acc |= op(bit(a, i), bit(b, i))
        return acc
    return per_bit

# definition of operations
OP = collections.namedtuple('OP', 'name func')
OPS = lambda n: [
    OP('ADD ', lambda a, b: (a + b) % 2**n),
    OP('SUB ', lambda a, b: (a - b) % 2**n),
    OP('MUL ', lambda a, b: (a * b) % 2**n),
    OP('DIV ', lambda a, b: (a // b) % 2**n if b != 0 else 0),
    OP('XOR ', lambda a, b: a ^ b),
    OP('AND ', lambda a, b: a & b),
    OP('OR  ', lambda a, b: a | b),
    OP('IF  ', op_per_bit(lambda bit1, bit2: int(not bit1 or bit2), n)),
    OP('XNOR', op_per_bit(lambda bit1, bit2: int(not (bit1 ^ bit2)), n)),
    OP('NAND', op_per_bit(lambda bit1, bit2: int(not (bit1 & bit2)), n))
]


def result_repr(left, right):
    if left and right:
        return "l,r  "
    elif left:
        return "l    "
    elif right:
        return "r    "
    return "     "

def print_human_readable_table(tbl_left, tbl_right, n):
    ops = OPS(n)

    print(" " * 5 + "│", end='')
    for op in ops:
        print(op[0] + "│", end='')
    print()
    print("–" * 56)

    for op_1 in ops:
        print(op_1[0] + " │", end='')
        for op_2 in ops:
            print(result_repr(tbl_left[op_1[0] + op_2[0]], tbl_right[op_1[0] + op_2[0]]), end='')
        print()

if __name__ == "__main__":
    for n in range(1, 6):
        print("\n## n == {}\n".format(n))

        # evaluation data
        left_distributivity = {}
        right_distributivity = {}

        # evaluation
        for op1, op2 in itertools.product(OPS(n), repeat=2):
            left_dist, right_dist = True, True

            for arg1, arg2, arg3 in itertools.product(range(2**n), repeat=3):
                lhs = op1.func(arg1, op2.func(arg2, arg3))
                rhs = op2.func(op1.func(arg1, arg2), op1.func(arg1, arg3))
                left_dist = left_dist and (lhs == rhs)

                lhs = op1.func(op2.func(arg2, arg3), arg1)
                rhs = op2.func(op1.func(arg2, arg1), op1.func(arg3, arg1))
                right_dist = right_dist and (lhs == rhs)

            left_distributivity[op1.name + op2.name] = left_dist
            right_distributivity[op1.name + op2.name] = right_dist

        print_human_readable_table(left_distributivity, right_distributivity, n)

Conclusion

It is interesting to see how the operation change with increasing n.

  1. The tables don’t seem to change beyond n>2.

  2. If n=2 …

    1. {DIV, MUL, AND} lose most distributivity properties

    2. MUL is not distributive over MUL anymore, because it does not only matter whether one argument is zero, but x occurs two times on the right-hand side. Thus for values like 2, we get a first-order expression on the left-hand side and a second-order expression on the right-hand side.

    3. IF was sometimes left-distributive in the case of n=1. In n=2, it is only right-distributive over IF and XNOR. Right-distributivity over NAND is a new property.

    4. The table n=2 is not a subset of n=1 because the properties of IF change a lot.

  3. If n>2 …

    1. DIV loses right-distributivity over AND

    2. MUL is not distributive over XOR anymore

Update 2021-08-26: I fixed formatting issues and a bug in the python script.