GATOR implementation

This repository contains a Python and C++ implementation of the paper "GATOR: Group-Action AdapTOR Signatures via MPC-in-the-Head" by Nico Döttling, Manar Mohamed and Riccardo Zanotto. It is available on eprint at https://eprint.iacr.org/2026/1067.

The Python code provides the reference protocol structure, while native pybind11 modules provide faster action and adaptor-signature backends for benchmarking.

The original python implementation with the PPRF module, and the CSIDH and MEDS group actions has been written by Manar. The C++ protocol, and the modular bindings for the actions, and the additional LESS and ALTEQ actions have been implemented by Riccardo with the help of OpenAI's Codex.

Requirements

• Python 3
• pybind11
• CMake 3.17 or newer
• OpenSSL
• GMP, required by the native CSIDH and CSI-FiSh targets
• A C/C++ compiler with C++17 support

Install the Python-side build dependency with:

python3 -m pip install pybind11

On macOS with Homebrew, the Makefile tries to discover openssl@3 automatically through brew --prefix openssl@3. If OpenSSL is installed elsewhere, set OPENSSL_DIR or OPENSSL_ROOT_DIR.

Directory Structure

.
|-- AS.py                  # Main access point for running protocols and selecting implementations
|-- AdaptorSignature/      # Pure-Python signer, verifier, buyer, seller, and signature types
|-- AdaptorSignatureC/     # Native C++ adaptor-signature implementation and pybind11 bindings
|   |-- include/
|   `-- src/
|-- GroupActions/          # Generic group-action interfaces and concrete action packages
|   |-- ALTEQ/             # ALTEQ Python wrappers, C++ bindings, and reference C implementation
|   |-- CSIDH/             # CSIDH and CSI-FiSh Python wrappers, C++ bindings, and C implementation
|   |-- LESS/              # LESS Python wrappers, C++ bindings, and reference/optimized C code
|   |-- MEDS/              # MEDS Python wrappers, C++ bindings, and reference C code
|   `-- ZpStar/            # Small Zp* action used for default tests and examples
|-- Puncturable_PRF/       # Native puncturable PRF used by the signature scheme
|-- bench/                 # Benchmark, parameter-search, plotting, and table-formatting scripts
|-- benchmark_data/        # Generated and checked-in benchmark CSVs, plots, and tables
|-- cmake/                 # CMake helpers for shared native cores and generated params
|-- tests/                 # Unit, native-binding, and interop tests
|-- benchmark.py           # Dispatcher for scripts under bench/
|-- standard_params.json   # Standard parameter choices used by AS.py and standard benchmarks
|-- CMakeLists.txt         # Top-level native build
`-- Makefile               # Convenience targets for building, testing, and profiling

Build

The top-level CMake project builds all native extension modules into their package directories. The Makefile wraps the common targets and passes the selected Python executable to CMake.

Build only the PPRF module needed by the default Python tests:

make build

Build every native module:

make build-all

Build individual native modules:

make build-adaptor-c
make build-csidh
make build-meds
make build-less
make build-alteq

Run tests:

make test            # default ZpStar tests
make test-csidh
make test-csifish
make test-meds
make test-less
make test-alteq
make test-adaptor-c
make test-all

Select a specific Python interpreter with PYTHON:

make PYTHON=python3.11 build-all
make PYTHON=python3.11 test-all

Useful native build parameters:

make build-meds MEDS_PARAM=MEDS9923
make build-less LESS_CATEGORY=252 LESS_TARGET=192 LESS_IMPLEMENTATION=auto
make build-alteq ALTEQ_API=lp1
make build-csidh CSIDH_BITS=512 CSIDH_USE_ASM=auto

CSIDH_USE_ASM=auto uses the bundled optimized assembly when the selected parameter set and platform support it. Use CSIDH_USE_ASM=OFF to force generic C, or CSIDH_USE_ASM=ON to require assembly.

AS.py Access Point

AS.py is the main programmatic and command-line entry point. It centralizes:

• action selection: zpstar, meds, less, alteq, csidh, csifish
• implementation selection: python or native
• parameter construction, including standard parameters from standard_params.json
• one-shot protocol runs for the adaptor flow and the base signature scheme
• serialization and size measurement helpers used by the benchmarks

Run one adaptor-signature protocol:

python3 AS.py --action meds --impl native

Run the base signature scheme instead of the adaptor flow:

python3 AS.py --action meds --impl native --base

Override parameters manually:

python3 AS.py --action less --impl native --n 32 --R 20 --s 4

If --n and --R are omitted and a standard choice exists for the selected action and s, AS.py uses standard_params.json. The file stores the chosen N; R is derived for 128-bit security by ceil(128 / (log2(N) + log2(s))) unless an explicit R is present.

The same functionality is available from Python:

import AS

params = AS.make_standard_parameters("meds", "native", s=4)
result = AS.run_protocol("meds", "native", s=4)
base = AS.run_base_signature_scheme("meds", "native", s=4)
print(result["times"], result["sizes"])

Benchmarks

All benchmark scripts are dispatched through benchmark.py:

python3 benchmark.py --help

Parameter Sweeps and Standard Parameters

The standard parameters in standard_params.json were selected from presignature sweeps with the balanced-log heuristic. For each action and each s, the heuristic normalizes log(presignature size) and log(pSign time) to [0, 1] and minimizes their sum. This balances size and pSign runtime rather than optimizing only one metric.

Generate full sweep data for CSI-FiSh, LESS, MEDS, and ALTEQ:

python3 benchmark.py do-benchmark --action all --impl native --out-dir benchmark_data

This writes files such as:

• benchmark_data/meds_native_action.csv
• benchmark_data/meds_native_keygen.csv
• benchmark_data/meds_native_presign_sweep.csv
• benchmark_data/meds_native_table.csv
• benchmark_data/meds_native_table.tex

Print the balanced-log choices implied by the sweep files:

python3 benchmark.py standard-params --impl native --out-dir benchmark_data

Rewrite standard_params.json from those sweep files:

python3 benchmark.py standard-params --impl native --out-dir benchmark_data --write

Full Benchmark for Standard Parameters

Run the full protocol benchmark for all standard parameter choices:

python3 benchmark.py standard-benchmark --impl native --trials 100 --out-dir benchmark_data

This runs the adaptor flow and the base signature scheme for each standard s value and writes one full CSV per action:

• benchmark_data/csifish_standard_full.csv
• benchmark_data/less_standard_full.csv
• benchmark_data/meds_standard_full.csv
• benchmark_data/alteq_standard_full.csv

Run only one action or one subset of s values:

python3 benchmark.py standard-benchmark --action meds --impl native --s 1,2,4 --trials 100 --out-dir benchmark_data

Scatter Plots

Scatter plots use the sweep CSVs and matching keygen CSVs generated by do-benchmark. Generate a plot for one action:

python3 benchmark.py plot-presign-sweep \
  benchmark_data/meds_native_presign_sweep.csv \
  --log-x --log-y \
  --out benchmark_data/meds_native_presign_scatter_log.png

Generate a combined plot for all actions:

python3 benchmark.py plot-presign-sweep \
  benchmark_data/csifish_native_presign_sweep.csv \
  benchmark_data/less_native_presign_sweep.csv \
  benchmark_data/meds_native_presign_sweep.csv \
  benchmark_data/alteq_native_presign_sweep.csv \
  --log-x --log-y \
  --thin-n-step 2 \
  --thin-s-step 1 \
  --out benchmark_data/all_actions_native_presign_scatter_log.png

Use --pareto-only to plot only nondominated size/time points, and --label-points to annotate every point with its action, N, and s.

Standard Text Tables

Format the full standard benchmark CSVs into compact table CSVs and LaTeX table snippets:

python3 benchmark.py format-standard-tables \
  benchmark_data/csifish_standard_full.csv \
  benchmark_data/less_standard_full.csv \
  benchmark_data/meds_standard_full.csv \
  benchmark_data/alteq_standard_full.csv

This writes files such as:

• benchmark_data/meds_standard_table.csv
• benchmark_data/meds_standard_table.tex

The table CSVs report sizes in kB and times in ms. The .tex files are pgfplotstable snippets and expect LaTeX packages such as booktabs and pgfplotstable.

Quick Performance Meter

For a one-shot operation-level profile:

python3 benchmark.py performance-meter --action meds --impl native
python3 benchmark.py performance-meter --action meds --impl python --profile

Convenience make targets exist for common performance-meter runs:

make perf
make perf-meds
make perf-less
make perf-alteq
make perf-c-meds