Paper 2026/2488

Yoshan: Algebraic-Circuit Co-Synthesis and Search Methodology of Hardware-Efficient S-Boxes

Abstract

Choosing a hardware S-box means balancing cryptanalytic strength (differential uniformity δ, linearity L, and algebraic degree) against circuit cost (AND count and AND depth D). Under masking, non-linear gates dominate silicon area, registers, and fresh randomness, while D sets pipeline latency. As a result, automated searches have largely retreated to quadratic permutations (D = 1), whose slow degree growth forces high cipher round counts. We present Yoshan, a co-synthesis engine that optimizes an S-box permutation and its gate-level circuit together across n ∈ {5,6,7,8}. Inside a quality-diversity archive, Yoshan seeds search with subfield towers, Feistel/Misty/MM networks, affine wrappers, CCZ graph automorphisms, and bilinear or shear constructions. It then evolves circuits via cryptographically guided DAG rewrites and exploratory differentiable Piling-Up seeding and crossover with Hungarian LSAP projection, before compressing them with SMT sub-DAG shaving, stage-preserving CSE, exact depth-1 SAT, and four-tier inverse compilation. Every archived circuit is exported gate for gate to SystemVerilog and certified by exhaustive simulation and a Z3 miter. Across 31,337 certified netlists (30,986 distinct permutations) in 56 (n,δ,L,deg) profiles, EA invariants and an exact affine-equivalence solver against a 712-entry catalogue (power maps, 5- and 6-bit quadratic/quartic classifications, Feistel/MISTY/Bridge structures, two-point-swapped power maps, and cipher S-boxes) partition the archive into known catalogue classes (Category A, 2,681 permutations) and permutations certified EAseparated from it (Category B, 28,305 permutations; 12 benchmark classes YSHn,i). All 30 benchmark S-boxes and their explicit inverses are synthesized gate-exactly in 45nm CMOS (unmasked and pipelined d = 2 DOM) and traced from seed to final netlist. For known classes, we obtain a gate-exact depth-3 AES-class pair (42 AND, 101 XOR; inverse 42 AND, 106 XOR at D = 3) and a provably AND-optimal 5-AND, D =1 circuit for the 5-bit Q71 class (δ = 4,L = 16). When the lookup table can vary, we find a 12-AND 6-bit degree-5 S-box YSH6,5 (δ = 6,L = 24,β = 14), a 5-AND, D =2 5-bit quartic S-box YSH5,2 in both directions, and 28- and 18-AND 8-bit degree-7 S-boxes, all compared against the best published circuits.