The Multi-User Constrained Pseudorandom Function Security of Generalized GGM Trees for MPC and Hierarchical Wallets

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 GGM tree that stems from the pseudorandom generator to pseudorandom function 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 pseudorandom function 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 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-p-based Bip32 variants reduce the communication cost of MPC-based implementations by 73.3% to 93.8%, whereas our AES-based function secret sharing substantially improves mu security while reducing computations by 50%.