# Division property table of SBox

In Table 12 (page 23) of the GIFT paper, the "Division property" table is given. I could not understand how it has been computed.

My questions:

1. May I have an algorithm on how to compute the table?
2. Is there any public implementation available? For example, Sage seems to have several SBox related implementations, but not this one.

Here's a simple Python implementation.

def anf(s):
s = list(s)
for i in range(n):
for j in range(0, 2**n, 2*2**i):
for o in range(2**i):
s[j+o+2**i] ^= s[j+o]
return s

def size_reduce(lst):
res = set()
for u in lst:
if not any(u != v and u & v == v for v in lst):
return sorted(res)

def expand(lst):
res = set()
for v in range(2**n):
if any(v & u == u for u in lst):
return sorted(res)

n = 4
sbox = 0x1, 0xa, 0x4, 0xc, 0x6, 0xf, 0x3, 0x9, 0x2, 0xd, 0xb, 0x7, 0x5, 0x0, 0x8, 0xe

# calculate ANFs of products
dppt = [set() for u in range(2**n)]
for v in range(2**n):
a = anf([int(y & v == v) for y in sbox])
for u, take in enumerate(a):
if take:

# propagate larger monomials to smaller ones
for u1 in range(2**n):
for u2 in range(u1):
if u2 & u1 == u2:  # u2 \prec u1
dppt[u2] = dppt[u2] | dppt[u1]

# remove redundant ones
dppt = [size_reduce(lst) for lst in dppt]
print("Reduced:")
for u, lst in enumerate(dppt):
print(f"{u:04b}:", *[f"{v:04b}" for v in lst])

# or include all redundant ones
print("All:")
dppt = [expand(lst) for lst in dppt]
for u, lst in enumerate(dppt):
print(f"{u:x}:", *[f"{v:x}" for v in lst])


Output:

Reduced:
0000: 0000
0001: 0001 0010 0100 1000
0010: 0001 0010 0100 1000
0011: 0001 0010 1100
0100: 0001 0010 0100 1000
0101: 0010 0101 1000
0110: 0011 0100 1001 1010
0111: 0101 1011 1110
1000: 0001 0010 0100 1000
1001: 0011 0100 1000
1010: 0011 0100 1000
1011: 0110 1011 1101
1100: 0011 0100 1000
1101: 0011 0101 1000
1110: 0100 1001 1010
1111: 1111
All:
0: 0 1 2 3 4 5 6 7 8 9 a b c d e f
1: 1 2 3 4 5 6 7 8 9 a b c d e f
2: 1 2 3 4 5 6 7 8 9 a b c d e f
3: 1 2 3 5 6 7 9 a b c d e f
4: 1 2 3 4 5 6 7 8 9 a b c d e f
5: 2 3 5 6 7 8 9 a b c d e f
6: 3 4 5 6 7 9 a b c d e f
7: 5 7 b d e f
8: 1 2 3 4 5 6 7 8 9 a b c d e f
9: 3 4 5 6 7 8 9 a b c d e f
a: 3 4 5 6 7 8 9 a b c d e f
b: 6 7 b d e f
c: 3 4 5 6 7 8 9 a b c d e f
d: 3 5 7 8 9 a b c d e f
e: 4 5 6 7 9 a b c d e f
f: f

• Would you mind giving a textual description on how is it computed or how to interpret the table...?
– hola
Feb 19 at 16:12
• Also, would be great if you consider making a pull request to Sage :-)
– hola
Feb 19 at 16:22