The Multi-user Constrained PRF Security of Generalized GGM Trees for MPC and Hierarchical Wallets

Chun Guo, Xiao Wang, Xiang Xie, Yu Yu

This paper, recently published in ACM Transactions on Privacy and Security, tackles a critical gap in modern cryptography: how do the "trees" of random numbers we use for Bitcoin wallets and secure multi-party computation (MPC) hold up when millions of people use them simultaneously?

TL;DR

The authors provide the first formal multi-user security analysis for generalized GGM trees, a cornerstone of hierarchical wallets and Function Secret Sharing (FSS). By establishing tighter security bounds, they propose new variants that slash the communication costs of MPC-based Bitcoin wallets by up to 93% while simultaneously hardening them against large-scale attackers.

What Problem Does This Paper Address?

At the heart of many cryptographic protocols is the GGM tree (named after Goldreich, Goldwasser, and Micali). It’s a method for turning a simple Pseudorandom Generator (PRG) into a complex Pseudorandom Function (PRF) with a hierarchical structure. This structure allows for "constrained" keys—for example, a parent key that can derive child keys for specific sub-branches, which is exactly how Bitcoin’s Bip32 hierarchical deterministic wallets work.

However, most security proofs for GGM trees are "single-user." They assume an attacker is targeting one specific key. In the real world, platforms like Exodus have millions of active users. An attacker doesn't need to break your specific wallet; they just need to break any wallet among millions. Standard theory suggests security degrades linearly with the number of users ($u$), but this "trivial bound" is often too pessimistic or fails to capture how specific protocol leakages (like public child keys) affect the system.

Methods

The authors introduce a Generalized GGM Tree model that moves beyond simple binary trees to support multiple branches and public "labels" (additional inputs to the underlying hash or cipher).

To analyze security, they use:

  • Multi-user Leakage CPRF Security: A new formal definition that accounts for multiple users and the "leakage" of intermediate values common in real-world protocols.
  • The H-coefficient Method: A sophisticated proof technique used to bound an adversary's advantage in the Random Oracle Model (ROM) and Ideal Cipher Model (ICM).
  • Primitive Replacement: They evaluate replacing the heavy HMAC-SHA512 used in Bip32 with more "MPC-friendly" primitives like SHACAL3 (the block cipher inside SHA-512) and Keccak-p (the permutation inside SHA-3).

Datasets

As a theoretical cryptography paper, it does not use traditional "training" datasets. Instead, it evaluates its findings through:

  • MPC Benchmarks: The authors implemented their proposed Bip32 variants using the EMP-Toolkit (a standard library for efficient MPC).
  • Performance Metrics: They measured the number of AND gates (a proxy for communication/computation cost in MPC), execution time, and communication volume (KB) across different tree depths.

Key Insights and Ideas

  • The "Label" Matters: Security in the multi-user setting is heavily dependent on the "concentration of labels." If different users' trees use the same public inputs (labels) for their internal hash calls, the attacker can batch their work. By ensuring labels are distinct (e.g., using a random Initialization Vector), the $log_2 u$ security degradation can be almost entirely eliminated.
  • Bip32 is Over-Engineered for MPC: The standard Bip32 uses HMAC-SHA512, which is computationally expensive to execute inside a secure MPC protocol (often used for institutional "threshold" wallets). The authors show that using the underlying block cipher (SHACAL3) directly provides equivalent security with a fraction of the overhead.
  • Multi-branch Trade-offs: For Function Secret Sharing (FSS), the authors found that moving from a binary tree to a 4-branch tree reduces computation by 50% at the cost of a slightly larger "punctured" key, offering a better efficiency frontier for private information retrieval.

Key Results

  • Communication Reduction: The SHACAL3-based Bip32 variant reduced MPC communication costs by 73.3%, while the Keccak-p-based variant reduced them by a staggering 93.8% compared to the standard HMAC-based implementation.
  • Concrete Security: They proved that Bip32 achieves roughly 247 bits of multi-user security (near the 256-bit ideal), providing a rigorous mathematical foundation for a standard that previously lacked a formal multi-user proof.
  • FSS Optimization: Their AES-based FSS improvement not only reduced computation but also significantly improved multi-user security by introducing random IVs to prevent cross-user birthday attacks.

Limitations and Future Work

  • Ideal Models: The proofs rely on the Random Oracle and Ideal Cipher Models. While standard in the field, these are mathematical abstractions; proving these bounds in the "Standard Model" (without such abstractions) remains an open, much harder challenge.
  • Full FSS Complexity: While the paper optimizes the GGM tree component of FSS, it does not provide a full characterization of the entire FSS protocol's security, which involves additional secret-sharing steps.
  • Signature Schemes: The authors note that while the key derivation is secure, the overall security of a wallet still depends on the underlying signature scheme (like ECDSA). They suggest that finding ECDSA variants with better multi-user bounds is a promising area for future research.

Summary updated

Abstract

Multi-user (mu) security considers large-scale attackers that, given access to a number of cryptosystem instances, attempt to compromise at least one of them. We initiate the study of mu security of the so-called GGMtree that stems from the PRG-to-PRF transformation of Goldreich, Goldwasser, and Micali, with a goal to provide references for its recently popularized use in applied cryptography. We propose a generalized model for GGM trees and analyze its mu prefix-constrained PRF security in the random oracle model. Our model allows to derive concrete bounds and improvements for various protocols, and we showcase on the Bitcoin-Improvement-Proposal standard Bip32 hierarchical wallets and function secret sharing (FSS) protocols. In both scenarios, we propose improvements with better performance and concrete security bounds at the same time. Compared with the state-of-the-art designs, our SHACAL3- and KeccaK-𝑝-based Bip32 variants reduce the communication cost of MPC-based implementations by 73.3%∼93.8%, while our AES-based FSS substantially improves mu security while reducing computations by 50%.
BibTeX
@article{guo2024multi,
  author = {Chun Guo and Xiao Wang and Xiang Xie and Yu Yu},
  title = {{The Multi-user Constrained PRF Security of Generalized GGM Trees for MPC and Hierarchical Wallets}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
  url = {https://openreview.net/forum?id=V8Wdv6TiWb},
}
Figure