KORD: Breaking the Key-Generation Bottleneck in Dealerless FSS via Protocol--Hardware Co-Design

Abstract

Function secret sharing (FSS) has become a core primitive in privacy-preserving computation. However, each FSS invocation requires a fresh pair of function keys generated by a trusted dealer , expands the system's trust boundary and hinders practical deployment. Existing dealerless protocols eliminate this dependency, but incur substantial communication and a number of interaction rounds that grows linearly with the input bit-width, making key generation a major bottleneck. This paper present KORD, a protocol--hardware co-design that dramatically reduces the cost of dealerless FSS key generation. At its core is a pair of special-purpose chips that establish a common root of trust through mutual attestation and, within it, reconstruct FSS keys---eliminating the need for a dealer. This root of trust further forms a security boundary within which KORD restructures the generation protocol, collapsing the interaction of prior dealerless protocols into a single round, independent of GGM depth. A cross-key scheduling scheme then interleaves independent GGM-tree traversals, sustaining high computational throughput. KORD reduces per-key-generation communication by 7,633--70,274$\times$ over the state-of-the-art distributed FSS protocol across a comprehensive suite of FSS building blocks. Post-route analysis projects 12.75 million 32-bit DPF keys per second at 204 MHz using 21.5K LUTs, with 99.8% AES lane utilization. On private ResNet-18 inference, KORD cuts the share of end-to-end time spent on key generation from over 96% to 11.9%.