PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yijing Peng, Lin Liu, Yujie Xue, Shaojing Fu, Shaoqing Li, Yaohua Wang, Rongmao Chen, Yang Guo

arXiv:2608.30379v1cs.CRcs.AR

TL;DR

KORD addresses the communication and interaction costs of dealerless FSS key generation by combining mutually attested hardware with a restructured protocol and cross-key scheduling. It reduces communication by 7,633–70,274× and projects 12.75 million 32-bit DPF keys per second, while lowering ResNet-18 key-generation time from over 96% to 11.9%.

  • Problem

    Dealerless FSS key generation incurs substantial communication and interaction rounds that grow with input bit-width, while FSS workloads require sustained streams of fresh key pairs.

  • Method

    KORD uses a mutually attested pair of special-purpose chips as a hardware root of trust, restructures generation into one round, and interleaves independent GGM-tree traversals.

  • Results

    KORD reduces per-key-generation communication by 7,633–70,274× over distributed FSS, projects 12.75 million 32-bit DPF keys per second, and reaches 99.8% AES lane utilization.

  • Takeaways & Limitations

    On private ResNet-18 inference, KORD reduces the share of end-to-end time spent on key generation from over 96% to 11.9%.

  • Takeaways & Limitations

    KORD relocates rather than eliminates trust, requiring each party to trust and audit the remote chip and exposing both parties’ keys if either chip is compromised.

Abstract

from arXiv · show

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%.

I. INTRODUCTION

KORD addresses dealer trust and scaling bottlenecks in dealerless FSS by combining a protected key-generation boundary with hardware-aware GGM traversal. It removes per-level interaction, reduces computation to the special path, and sustains high throughput across keys.

  • Dealer-based FSS key generation creates trust risks, single-point failures, and deployment restrictions, while key synchronization remains a system bottleneck.
  • Existing dealerless DPF and DCF schemes either lack arithmetic-shared input or output support or require interaction and communication at every GGM level.
  • KORD establishes a common root of trust in paired chips, reconstructs key parameters inside the boundary, and expands only the special path, reducing computation from exponential to linear in ℓ.
  • KORD fixes per-key communication at a single round independent of input length and cuts computation from full-tree expansion to a linear special-path walk.
  • 99.8% AES lane utilization replaces 8.3% utilization by interleaving independent GGM traversals through shared hardware.
  • Across nine FSS building blocks, communication falls by 7,633–70,274×, projected throughput reaches 12.75 million DPF-32 keys/s, and ResNet-18 key-generation time falls to 11.9%.

B. Threat Model and Security Boundary

KORD assumes semi-honest parties and networks by default, with malicious parties outside scope. Its security boundary contains paired chips and their logical channel, while hosts and the physical network remain outside.

  • KORD’s analyses and reported results use the semi-honest model; extending the design to malicious parties remains future work.
  • The default network may read messages but must deliver faithfully, whereas KORD-mac adds integrity and replay protection against modified, reordered, dropped, or replayed messages.
  • Mutual attestation establishes shared root material and counters during one-time setup, after which both chips derive identical keys without further communication.
  • Plaintext inputs, seed chains, and root seeds exist only inside the two-chip boundary; chips authenticate requests, reconstruct and expand keys, emit shares, and zeroize intermediate state.
  • Compromising either chip exposes both parties’ keys and masks, so KORD relocates trust to auditable hardware rather than eliminating the trust assumption.

III. MOTIVATION

FSS applications consume a sustained stream of fresh keys, making key-generation throughput a deployment requirement rather than a startup cost. KORD targets this workload by requiring dealerless, width-independent interaction and application-matched supply rate.

  • Each comparison, lookup, ReLU, truncation, or oblivious access consumes fresh key pairs, creating a sustained key stream for large workloads.
  • In the evaluated dealerless ResNet-18 workload, key generation accounts for at least 96.9% of end-to-end time.
  • A deployable key source must avoid a dealer, use per-key interaction rounds independent of input width ℓ, and match the application’s key-consumption rate.

B. Existing Key Sources Trade Trust for Communication

Existing FSS key sources trade among dealer removal, depth-independent interaction, and application-rate supply. KORD addresses these tensions by confining joint state to paired hardware, using one exchange, and exploiting cross-key parallelism.

  • Dealer-based sources provide low interaction but make the dealer an additional trusted principal and compromise point.
  • Dealerless 2PC removes the dealer but incurs GGM-depth-dependent rounds and Θ(λℓ) communication per key.
  • At ℓ=16, the reproduced dealerless DPF generator transfers roughly 80 KB per party across hundreds of messages.
  • An isolated key occupies KORD’s AES lanes in only 8.31% of issue cycles because GGM levels are depth-serial.
  • KORD maps the three requirements to a minimal protected boundary, depth-independent interaction, and cross-key scheduling.

B. One-Round Key Generation

KORD reconstructs shared FSS inputs inside paired chips after one encrypted exchange, then locally performs the dealer-like GGM generation. The resulting standard key shares remain compatible with existing evaluation software.

  • A DPF/DCF key depends deterministically on reconstructed (α, β), two roots, and the PRG.
  • One simultaneous exchange gives both chips identical inputs, after which each independently computes correction words and emits only its own key share.
  • The paired chips derive identical roots from attested shared state and per-key counters without transmitting those roots.
  • The generation loop walks the special path in Θ(ℓ) time rather than expanding the full tree, while independent keys interleave in hardware.
  • KORD emits bit-exact standard DPF/DCF shares, allowing unchanged online binaries and key semantics.
  • Fixed-key AES-128 in MMO mode produced identical keys across RTL, reference software, and LLAMA in 101,334 field checks with zero mismatches.

C. Design Rationale

KORD’s default design transmits additive shares to preserve generality, compatibility, and like-for-like semi-honest accounting. Its hardened KORD-mac tier adds authenticated encryption for malicious-network settings at fixed per-frame overhead.

  • The default deployment transmits (α, β) shares because joint secrets arise in workloads and must be combined inside the reconstruction zone.
  • True-share input and standard key-share output make KORD a drop-in key source, unlike self-chosen masks that alter FSS protocol semantics.
  • The default comparison assumes a semi-honest network and parties, while KORD-mac prices the malicious-network upgrade separately.
  • Shared per-key roots remain inside attested chip boundaries and are identical by deterministic derivation, leaving no network view of the roots.
  • KORD-mac wraps each frame in a fixed 36-byte authenticated-encryption envelope and tolerates a fully malicious network at O(λ + ℓ) communication.

V. HARDWARE ARCHITECTURE AND IMPLEMENTATION

The reported cycle-level hardware results come from cycle-accurate simulation of the RTL later synthesized in the implementation evaluation.

  • All cycle-level results reported here come from cycle-accurate simulation of the same RTL synthesized in Section VII-E.

A. Realizing the Security Boundary

KORD places joint key-generation state inside a minimal trusted hardware boundary, where authenticated inputs are reconstructed and FSS keys are expanded before only the local share exits. DPF and DCF share the same pipeline, with DCF adding value-correction processing.

  • Trust boundary: KORD’s trusted perimeter contains the SCU, reconstruction zone, GGM fabric, and assembler; no principal outside it handles the counterparty’s material.The design is dealerless under a minimal hardware root, not trust-free.
  • Authenticated admission: The SCU authenticates both encrypted frames and checks counter freshness before permitting decryption, reconstruction, or fabric dispatch.Authentication failure produces no decryption, dispatch, or observable engine state.
  • Key reconstruction: After double authentication, the reconstruction zone combines the two shares of α and β in registers, which are zeroized after consumption.The reconstructed plaintext exists only inside the protected reconstruction path.
  • Key generation: The root-derivation unit obtains both initial seed pairs from (kr, ctr), after which the scheduler advances each admitted key through the GGM fabric.The assembler emits the serialized key stream through the SCU egress.
  • DPF and DCF: DCF uses the same eight-stage flow as DPF but enables value lanes, a Vα accumulator, and per-level value corrections.No other chip component distinguishes DPF from DCF.

C. Host Integration: Software–Hardware Co-Design

KORD keeps flexible orchestration on the host while confining secret-dependent generation to the chip, where cross-key scheduling hides GGM dependency bubbles. The resulting design combines high utilization, compact state, unified DPF/DCF support, and an explicit direct-generation scope boundary.

  • Host integration: The host sees four memory-mapped operations and handles message relay, batching, retries, and integration with the unchanged FSS stack.Secret-dependent processing remains inside the chip boundary.
  • Scope boundary: KORD’s verified prototype supports direct generation; binding is not implemented, so previously modeled bind-versus-expand ratios are withdrawn.The direct path remains the experimentally verified path.
  • State cost: 52.6 B of implemented state per key yields a saturated M = 16 working set of 0.82 KiB.Keys stream out without a landing buffer.
  • Cross-key scheduling: 8.31% single-key utilization rises to 99.84% with cross-key interleaving, while the analytical model tracks RTL within 0.3% across swept configurations.Independent in-flight keys fill dependency bubbles in the shared AES array.
  • Frequency limit: The correction-word extraction logic limits full-engine frequency, while pipelining it would raise fmax but require more in-flight slots.The AES lanes themselves close timing at higher extrapolated frequencies.
  • Unified datapath: A unified DPF/DCF engine uses 20,654 LUTs and 583 RAMB18, saving 50.8% of LUTs and 50.3% of BRAMs versus separate engines.The unified engine’s fmax is 154.6 MHz versus 154.9 MHz for the DCF-only datapath.

VI. SECURITY ANALYSIS

KORD’s security analysis models dealerless generation through a minimal trusted-chip abstraction and simulatable views, while explicitly bounding claims by hardware trust, multi-instance PRF security, channel assumptions, persistence, and unevaluated physical side channels.

  • Security claim: KORD is dealerless under a minimal hardware root: no principal acts as dealer, and plaintext is confined to a zeroized register-level zone.The trusted object is special-purpose hardware and its authenticated channel, not a general-purpose software stack.
  • Simulation argument: The adversarial view is computationally simulatable from a party’s own shares, public parameters, message count, and timing, rather than the true joint inputs.The proof composes pairing, exchange, and chip simulators.
  • Scope of proof: The security claim is conditional on the trusted-chip abstraction and, across requests, on multi-instance PRF security for derivation from Kch.Single-key FSS security alone does not cover the correlated stream.
  • Channel assumptions: The default network tier assumes relay integrity, while KORD-mac provides authentication and fail-closed rejection of unauthenticated messages.The default keystream protects confidentiality but is malleable against tampering relays.
  • Persistence: Rollback-protected persistence is required for counters and pairing secrets because reused keystream pads leak the XOR of two messages.The FPGA prototype implements only in-session monotonicity.
  • Physical leakage: No empirical side-channel evaluation was performed, so the register-level zeroization design does not establish leakage freedom.The mitigation is by construction rather than experimentally validated.

B. Building Blocks and Input-Width Scaling

Across nine FSS building blocks and input widths, KORD makes dealerless key generation single-round with nearly fixed communication, while the baseline scales linearly in input width and incurs full-tree expansion.

  • Building Blocks: 7,633×–70,274× lower per-key communication: KORD reduces interaction from 154–38,659 one-way messages to a single round across nine FSS building blocks.KORD’s modeled generation latency is 0.45–5.49 µs, compared with 37.8 ms–7.14 s measured localhost baseline generation.
  • Building Blocks: KORD’s key-generation message remains nearly flat at 2–512 bytes per operation, while its single-round protocol is independent of input length.The nine-building-block evaluation uses ℓ∈{8,16,18}; KORD’s ratio is reported using caliber B.
  • Input-Width Scaling: At ℓ=32, KORD’s per-key communication is 1,169×–18,290× lower for DPF and 1,132×–67,611× lower for DCF than extrapolated baseline values.At ℓ=64, the DCF gap reaches 1,146×–66,807×; KORD remains at one round with 4→16 B messages.
  • Input-Width Scaling: The baseline’s key-generation communication grows strictly linearly with input width: 4,168.2 B/bit for DPF and 16,500.7 B/bit for DCF.Measured residuals are 0.00% for DPF and 0.01% for DCF across ℓ∈{8,...,18}.
  • Input-Width Scaling: The baseline’s reported generation latency is a lower bound because full GGM-tree expansion costs Θ(2^ℓ) PRG evaluations and is omitted from timing.KORD instead expands only the special path, making per-key computation linear in ℓ.

C. End-to-End: Private ResNet-18

KORD substantially reduces modeled ResNet-18 key-generation overhead and sustains high hardware throughput, while its online evaluation remains unchanged because it emits standard keys.

  • End-to-End Impact: 1.542 s and 11.9%: KORD’s modeled ResNet-18 key generation is far below the dealerless baseline’s ≥363.6 s and ≥96.9% end-to-end share at ℓ=32.The model excludes host-side key-delivery I/O and sums generation with transfer without overlap credit.
  • Beyond the LAN: 519×–520× WAN latency reduction for one DCF key at ℓ=32 and 100 ms RTT grows to 1,031× at ℓ=64.The ratio is essentially flat across bandwidth and RTT because KORD uses one round while the baseline’s round count scales with depth.
  • The Hardware: 12.75 M DPF-32 keys/s at 204.0 MHz uses 21,540 LUTs, while cross-key pipelining raises AES-array utilization from 8.31% to 99.84%.These headline DPF-only throughput figures are reported for the hardware engine; saturation was confirmed on silicon.
  • The Hardware: The unified engine supplies 4.83 M keys/s for all-DPF or all-DCF streams and uses roughly half the resources of two separate engines.It occupies 20,654 LUTs and saves 50.8% of LUTs and 50.3% of BRAMs relative to separate engines.
  • Beyond the LAN: A DPF-only engine supplies 20.40 M keys/s for DORAM at d=20, exceeding a 40 Mbps link’s drain rate by 24×.This highlights a delivery-path constraint outside the prototype’s generation fabric.

VIII. RELATED WORK

KORD addresses dealerless FSS deployment by combining a minimal hardware trust root with single-round key generation and cross-key hardware pipelining.

  • FSS Systems and Their Key Sources: KORD targets MPC settings where FSS points are secret-shared, avoiding both dealer or helper-party key sources and point-knowing clients.The design exposes neither masks nor key shares to any principal outside the intended setting.
  • Dealerless Key Generation: Existing dealerless approaches either lack arithmetic-shared inputs or retain linear interaction and full-tree expansion costs.Floram and Half-tree do not support arithmetic-shared inputs or outputs, while Xing supports them but scales in rounds and computation.
  • Conclusion: KORD relocates trust from an online principal to minimal, auditable special-purpose hardware rather than eliminating the trust assumption.The paper explicitly identifies the hardware operations that must be trusted and the cost of compromise.
  • Conclusion: Cross-key interleaving saturates a shared AES array, complementing the protocol’s one-round and few-byte communication design.Depth-serial GGM expansion leaves hardware idle for one key at a time; independent keys fill those dependency bubbles.
Loading 2608.30379v1…