# 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.

## 1 Answer

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):
res.add(u)
return sorted(res)

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

n = 4
# GIFT GS
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:
dppt[u].add(v)

# 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