4
$\begingroup$

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.
$\endgroup$
2
2
+25
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ Would you mind giving a textual description on how is it computed or how to interpret the table...? $\endgroup$ – hola Feb 19 at 16:12
  • $\begingroup$ Also, would be great if you consider making a pull request to Sage :-) $\endgroup$ – hola Feb 19 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.