INFLUENCE OF BRANCHING DEGREE IN SIGNATURE TREES BASED ON ONE-TIME SIGNATURES ON THE EFFICIENCY OF THEIR USE

Abstract

The article provides a comprehensive study of the influence of the branching degree N on the performance of many-time tree-based digital signatures built on one-time digital signatures . Two main types of structures are considered: stateful sequential trees and full (stateless) trees that dynamically reconstruct the signature .  It is theoretically substantiated and empirically confirmed that traditional binary trees (N = 2) are not optimal across most metrics, with the exception of initial signing speed in sequential structures . It was established that for both types of structures, the optimal balance between reconstruction time, signature size, and verification speed is achieved at N = 3 and N = 4 . However, for sequential trees within the studied intervals, the branching degree N = 3 demonstrates slightly higher efficiency terms of signature size and construction time, contrary to theoretical assumptions . It is proved that a further increase in N leads to an insignificant acceleration of the verification process, while causing a significant linear increase in signature generation costs . The results of the work allow to select the architecture of quantum-resistant authentication systems with optimization based on performance priorities and device resource constraints .