Division property table of SBox In Table 12 (page 23) of the GIFT paper, the &quot;Division property&quot; table is given. I could not understand how it has been computed.
My questions:

May I have an algorithm on how to compute the table?
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 &amp; 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 &amp; 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 &amp; 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 &amp; u1 == u2:  # u2 \prec u1
            dppt[u2] = dppt[u2] | dppt[u1]

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

# or include all redundant ones
print(&quot;All:&quot;)
dppt = [expand(lst) for lst in dppt]
for u, lst in enumerate(dppt):
    print(f&quot;{u:x}:&quot;, *[f&quot;{v:x}&quot; 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