End-to-end Algorithm for Optimizing the S-box Circuit

Artifact for the paper “An Efficient End-to-end Algorithm for Optimizing the S-box Circuit” by Yao Sun, Min Zhang, and Ting Li.

The package contains the C++17 optimizer, its eight input instances, the circuits corresponding to the Full column of paper Table 6, the circuits and reference values used in Table 7, and deterministic validation scripts.

1. Quick evaluation

From the artifact root:

make env
make quick

The quick test does not require Gurobi, Yosys, or OpenSTA. A successful run ends with:

TABLE 6 CHECK: PASS (39 paper rows)
TABLE 7 STRUCTURAL CHECK: PASS (6 entries)
QUICK TEST: PASS

2. Requirements

Circuit validation

• Linux or macOS
• Python 3.8 or newer
• Bash
• GNU Make

Only the Python standard library is used.

C++ optimizer

• C++17 compiler
• Gurobi Optimizer with the C++ interface
• Valid Gurobi license
• POSIX threads

The final package has been tested with:

• Ubuntu 24.04
• Python 3.12.3
• GCC/G++ 13.3.0
• Gurobi 13.0

The paper experiments used Ubuntu 20.04 LTS on an AMD Threadripper 3970X (32 cores) with 128 GB RAM.

Gurobi license setup

Install the full Gurobi distribution with its C++ headers and libraries, then configure a valid license. See the official license overview and Academic Named-User setup guide. Follow the instructions for your license type; WLS licenses use a different setup from Named-User licenses. Set GUROBI_HOME to the platform directory containing include/ and lib/, as shown below.

Optional ADP flow

• Yosys 0.65+71
• ABC invoked through Yosys
• OpenSTA 3.1.0
• Nangate 45 nm Open Cell Library

These optional tools and the cell library are not included.

3. Evaluation commands

Deterministic quick test

make quick

This performs exhaustive functionality tests for representative AES, SNOW3G, and Saturnin circuits and checks all Table 6 and Table 7 mappings.

All published circuits

make full

This statically checks all 46 included circuit files. It exhaustively verifies the 44 standalone circuits over their complete input spaces. The two JBKK25 SNOW3G files are serial components and are checked structurally.

C++ optimizer smoke test

Set the Gurobi installation directory, for example:

export GUROBI_HOME=/opt/gurobi1300/linux64
make algorithm-smoke

The default smoke test uses:

instance                 aes10_ops
depth bound              28
target strategy          1 (AT)
seed                      12345
successful-round limit   1
time limit               120 seconds

A successful run ends with RUN SUMMARY and at least one successful round. This configuration was tested successfully by the authors with Gurobi 13.0.

A custom bounded run can be selected with environment variables:

OPS_NAME=aes10v2_ops \
DEPTH_LIMIT=22 \
TARGET_STRATEGY=1 \
SEED=2026 \
MAX_SUCCESSFUL_ROUNDS=3 \
MAX_SECONDS=600 \
make algorithm-smoke

Supported instances are:

aes10_ops   aes10v2_ops   aes10v3_ops
aes12_ops   aes12v2_ops   aes12v3_ops
snow_ops    saturnin_ops

Target strategies 0, 1, and 2 correspond to NONE, AT, and ST. The optimizer is randomized; a smoke test checks functionality and is not expected to rediscover every best result from the long search campaigns.

Optional Verilog and ADP flow

make verilog

Detailed commands for Yosys/ABC and OpenSTA are in synthesis/README.md. The paper uses:

normalized_area = mapped_cell_area / area(NAND2_X1)
ADP             = normalized_area × critical_path_delay

For the Nangate library revision used in the experiments, area(NAND2_X1) = 0.798.

4. Interpreting validation output

Example:

D=22, AD=5, #L=82, #NL=32, functional=PASS

• D: total Boolean-circuit depth
• AD: nonlinear depth
• #L: XOR count; output negation by XOR with constant 1 is not counted
• #NL: number of AND and OR gates
• functional=PASS: exhaustive truth-table comparison succeeded

In Circuits_MinXORs/, H<number> is the imposed depth upper bound. The actual derived depth may therefore be smaller than H<number>.

5. Paper-result mapping

Paper result	Files	Check
Table 6, Full column	Circuits_MinXORs/, results/table6_full_results.csv	make table6
Table 7 circuits and ADP values	Circuits_MinADP/, results/table7_adp.csv	make table7
C++ end-to-end optimizer	e2e_code/	make algorithm-smoke
Optional synthesis flow	synthesis/	make verilog

The long randomized timing and comparison campaigns are not included in this package.

6. Package structure

.
├── README.md
├── LICENSE
├── THIRD_PARTY_NOTICES.md
├── Makefile
├── docs/                  Developer guide
├── e2e_code/              C++ source, input instances, and S-box tables
├── Circuits_MinXORs/      39 Table 6 Full-column circuits
├── Circuits_MinADP/       Table 7 circuits and comparison circuits
├── scripts/               Environment and validation scripts
├── results/               Table 6 and Table 7 machine-readable mappings
└── synthesis/             Optional Verilog/Yosys/OpenSTA flow

7. License

The authors' artifact is released under the MIT License in LICENSE. Third-party notices and the applicable license text are in THIRD_PARTY_NOTICES.md.

8. Developer documentation

See the developer guide in docs/DEVELOPMENT.md for source organization, data structures, input formats, and extension points.