Paper 2026/987

Impact of Post-Quantum Signatures on InnoDB B+-Trees and Efficient Batch Signing

Min-Seo Kim, Hansung University

Ui-Jae Kim, Hansung University

Hui-Ju Kang, Hansung University

Hwa-Jeong Seo, Hansung University

Abstract

The transition to post-quantum cryptography (PQC) digital signatures poses an unexpected threat to the storage structure of relational databases. At the same security level, the AIMer-192f signature reaches 13,056\,B, which is more than 13 times that of RSA-7680 (960\,B). Storing it inline in MySQL InnoDB causes the B$^+$-Tree fan-out to collapse from the theoretically predicted value of 167 to a measured value of 1. This result experimentally reveals that the off-page storage model in the MySQL official manual has a factor of 167 error in this case. To address this problem, we propose an architecture that combines a split-table schema with a Merkle Tree-based batch signing approach. The proposed architecture ($B=512$) restores the collapsed fan-out to 41, reduces the number of leaf pages by 97\%, and improves insertion throughput by 28.1$\times$. It also reduces the per-document signature storage cost by up to 97.6\%. This study quantifies the limitations of the traditional single-table storage approach in a PQC migration environment and presents a practical mitigation architecture.

@misc{cryptoeprint:2026/987,
      author = {Seung-Won Lee and Min-Seo Kim and Ui-Jae Kim and Hui-Ju Kang and Hwa-Jeong Seo},
      title = {Impact of Post-Quantum Signatures on {InnoDB} B+-Trees and Efficient Batch Signing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/987},
      year = {2026},
      url = {https://eprint.iacr.org/2026/987}
}