Publication Details
Abstract
Digital signatures based on the compact knapsack problem are attractive post-quantum candidates: they rely solely on integer arithmetic, require no algebraic ring structure, and rest on a hardness assumption distinct from the Module-LWE/Module-SIS problems that underlie the recently standardized ML-DSA (FIPS 204). The three-move identification scheme of Rizos and Draziotis (2023) and its Fiat–Shamir signature establish completeness, special soundness, special honest-verifier zero-knowledge, and EUF-CMA security in the random-oracle model. Its concrete parameters, however, were selected by hand, yielding a comparatively large signature (≈ 31.9 KB); the authors explicitly leave smarter parameter selection as future work. We close this gap. First, we provide an independent, fully reproducible re-implementation of the scheme's lattice attacks (the closest-vector and divide-and-conquer attacks) and of its signature-size accounting, validated against the original tables; our re-implementation reproduces the published success rates to within experimental noise. Second, we cast parameter selection as a constrained optimization problem and design an adaptive bit-allocation optimizer that minimizes signature size subject to soundness, completeness, commitment-unpredictability, key-entropy, and an empirical lattice-attack hardness gate. The optimizer exposes two honest sources of slack in the base parameters—an over-provisioned nonce space and an under-tightened secret space. The resulting configuration S = S1/4,1/3, S′ = S′1/8,1/8 shrinks the signature by 19.6% (to 25.6 KB) at identical security: equal soundness (2⁻⁸⁰), equal commitment-unpredictability (2⁻²⁴), equal completeness error (2.15 × 10⁻⁶), empirically equal closest-vector-attack hardness (50.0%), and equal-or-better divide-and-conquer hardness. All code, seeds, and numerical results are released for reproducibility.