Abstract
Modern cryptographic systems, ranging from Bitcoin’s hierarchical deterministic wallets to secure multi-party computation (MPC), rely heavily on the GGM tree construction to derive hierarchical keys. While these systems are often analyzed in a single-user setting, real-world deployments involve millions of concurrent users, creating a significant security analysis gap. This paper establishes the first formal multi-user security analysis for generalized GGM trees. By introducing a new security definition for Multi-user Leakage Constrained Pseudorandom Functions (CPRFs) and utilizing the H-coefficient method, the authors provide tighter security bounds. These theoretical insights lead to the proposal of new, MPC-friendly variants of the Bip32 standard that reduce communication costs by up to 93% while maintaining robust security against large-scale adversaries.
Introduction
The GGM tree, named after Goldreich, Goldwasser, and Micali, is a fundamental building block in symmetric cryptography. It allows a single seed to be expanded into a tree of pseudorandom values, where specific nodes can be revealed to provide "constrained" access to sub-branches without compromising the rest of the tree. This property is the backbone of Bitcoin’s Bip32 standard for hierarchical deterministic wallets and is increasingly critical for Function Secret Sharing (FSS) used in private information retrieval.
However, a critical discrepancy exists between cryptographic theory and practice. Most existing proofs for GGM-based constructions assume a single-user setting where an attacker targets one specific key. In reality, platforms like Exodus or Coinbase manage millions of users. An attacker succeeds if they break any user’s key, not necessarily a specific one. Standard security reductions suggest that security degrades linearly with the number of users ($u$), but this "trivial bound" is often too pessimistic for practical parameter selection or fails to account for the specific ways protocols leak intermediate values.
Formalizing Multi-User Security
To bridge this gap, the authors introduce a Generalized GGM Tree model. Unlike the classic binary GGM tree, this model supports arbitrary branching factors and incorporates public "labels"—additional inputs used during the derivation process.
Multi-user Leakage CPRF Security
The paper proposes a new formal security definition: Multi-user Leakage CPRF Security. This definition is designed to capture the realities of modern protocols where an adversary might see intermediate values (leakage) or public child keys. To analyze this, the authors employ the H-coefficient method, a sophisticated proof technique that bounds the statistical distance between a real-world execution and an ideal world by looking at the probability of "bad" events in the transcript of interactions.
The Role of Labels
A key insight from the analysis is that multi-user security is highly sensitive to "label concentration." If multiple users utilize the same public labels for their internal hash or cipher calls, an attacker can perform "batch" attacks, effectively attacking many users with the same computational effort. The authors demonstrate that by ensuring labels are distinct—for instance, by incorporating a random Initialization Vector (IV)—the $log_2 u$ security degradation can be mitigated, providing near-ideal security.
Optimizing Bip32 for MPC
One of the most practical applications of this research is the optimization of Bitcoin’s Bip32 standard for use in secure Multi-Party Computation. Institutional "threshold" wallets often require Bip32 key derivation to be performed inside an MPC protocol so that no single party ever holds the master seed.
The current Bip32 standard uses HMAC-SHA512 for key derivation. While secure, HMAC-SHA512 is extremely "heavy" for MPC, requiring a massive number of AND gates, which translates to high communication and computation costs. The authors evaluate two primary alternatives:
- SHACAL3: The underlying block cipher used within the SHA-512 compression function.
- Keccak-p: The permutation at the heart of the SHA-3 standard.
By applying their multi-user security proofs, the authors show that these simpler primitives can replace the full HMAC-SHA512 construction without sacrificing security in the multi-user setting.
Performance and Results
The theoretical findings were validated through implementation using the EMP-Toolkit, a standard library for efficient MPC. The results demonstrate a dramatic improvement in efficiency:
- Communication Efficiency: The SHACAL3-based variant of Bip32 reduced communication costs by 73.3%. The Keccak-p-based variant achieved a 93.8% reduction compared to the standard HMAC-SHA512 implementation.
- Concrete Security Bounds: The analysis proved that Bip32 achieves approximately 247 bits of multi-user security. This provides a rigorous mathematical foundation for a standard that, despite its ubiquity, previously lacked a formal multi-user proof.
- FSS Improvements: Beyond wallets, the authors optimized Function Secret Sharing. By moving from a binary tree to a 4-branch tree and introducing random IVs, they reduced computation by 50% and hardened the protocol against cross-user birthday attacks.
Conclusion and Future Work
This research provides the necessary theoretical framework to deploy GGM-based systems at scale with confidence. By proving that simpler, more efficient primitives can achieve high multi-user security, the authors pave the way for more performant institutional crypto-custody and private database queries.
However, some challenges remain. The current proofs rely on the Random Oracle Model (ROM) and Ideal Cipher Model (ICM). While these are standard abstractions in cryptography, future work could focus on achieving similar bounds in the "Standard Model." Additionally, while the key derivation process is now formally secured in the multi-user setting, the overall security of a digital asset still depends on the underlying signature scheme (e.g., ECDSA or Schnorr). Investigating the multi-user security of these signature schemes in conjunction with GGM trees remains a vital area for future exploration.
Summary updated