Signing-Enhanced Forward-Secure Signatures by Leveraging SNARKs

Abstract

Forward-secure digital signatures protect the integrity of past signatures, even if the current signing key is compromised. Among forward-secure signature schemes, the method introduced by Lee et al. [1], based on zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), is particularly notable for achieving constant complexity across all metrics without requiring a predefined maximum time period. However, a naive approach to recursive proof composition results in an excessive amount of redundant computation being repeated for each signing process, which our method reduces significantly. In this paper, we advance a zk-SNARK-based forward-secure signature scheme by significantly improving the efficiency of its signing algorithm. By incorporating commit-and-prove SNARKs, we replace the inner verification process with commit verification within the signing circuit. Furthermore, we employ efficient recursive zk-SNARKs with accumulation and folding schemes to improve the setup and update algorithms. Our implementation demonstrates the practicality of our approach: the signing procedure completes in 0.18 seconds, achieving a 75-fold speedup over the previous scheme, setup time is reduced to 0.71 seconds - over 61 times faster, and public parameters are reduced to 25 MB, more than 16 times smaller.