Quantum Implementation of S-Boxes: A Memory Optimized Approach

Abstract

Substitution boxes (S-boxes) serve as fundamental non-linear components in symmetric cryptography, and their quantum circuit implementation is critical for quantum security. This work addresses the dual challenges of quantum circuit depth optimization and computational intractability in S-box synthesis. We introduce memory-optimized data structures, a pointer-efficient RandomAccessSet and a dynamic devector, that reduce memory overhead by 12 times per element, thereby mitigating the computational complexity associated with Pauli representation. Our enhanced Meet-in-the-Middle framework achieves exhaustive depth optimization for standardized S-boxes, demonstrating up to 8.5% depth reduction over DORCIS baselines at equivalent T-depth. The approach scales to 5-8-bit primitives, establishing memory efficiency as an independent resource dimension in quantum circuit synthesis. Comparative analysis under varied cost parameters provides new insights for resource-efficient cryptographic implementations on quantum hardware. © 2025 IEEE.