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
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
We call
We call
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.
- ADD
-
is the common addition in , e.g. is in - SUB
-
is subtraction in , e.g. is in - MUL
-
is the common multiplication in , e.g. is in - DIV
-
is division in with the result in special case , e.g. is in - XOR
-
is a bitwise XOR, e.g. is - AND
-
is a bitwise AND, e.g. is - OR
-
is a bitwise OR, e.g. is - IF
-
is an implication between two bits, e.g. if a then (b) else (false) - XNOR
-
is the negation of bitwise XOR, e.g. 1 and 1 gives 1 - NAND
-
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
↓ 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 .
For example, ADD is not distributive over XOR because -
MUL is distributive over MUL because
and in . 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
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.
-
The tables don’t seem to change beyond n>2.
-
If n=2 …
-
{DIV, MUL, AND} lose most distributivity properties
-
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.
-
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.
-
The table n=2 is not a subset of n=1 because the properties of IF change a lot.
-
-
If n>2 …
-
DIV loses right-distributivity over AND
-
MUL is not distributive over XOR anymore
-
Update 2021-08-26: I fixed formatting issues and a bug in the python script.