upTPM: Unbounded Preprocessing for Schnorr Multi-Signatures on TPM

Abstract

Schnorr-based multi-signature schemes support offline preprocessing of nonce commitments to reduce online signing to a single round. However, preprocessing is inherently bounded: each preprocessed nonce pair consumes signer-side storage, and once exhausted, an interactive commitment round is required to refill. This limitation is particularly severe for TPM~2.0 devices, where usable NVRAM is typically 6--16\,KB and connectivity is intermittent. This paper presents upTPM, a framework that achieves unbounded preprocessing with constant signer storage. Each TPM stores a single 32-byte secret seed from which an unlimited sequence of nonce commitments is deterministically derived. Commitments are published to an untrusted coordinator before use; nonce scalars never leave the TPM. We formalize three properties not provided by existing schemes: (1)~unbounded deterministic preprocessing with constant storage; (2)~asynchronous commitment refill, allowing any signer to unilaterally extend its commitment pool; and (3)~TPM-attested commitments, a hardware-backed authenticity and state-binding mechanism that strengthens resistance to host-software compromise. We prove EU-CMA security in the random oracle model under the discrete logarithm assumption and Pseudo Random Function (PRF) security, with a one-time-use invariant enforced by TPM hardware state. We extend the construction to $(t,n)$-threshold signatures and provide a detailed analysis of coordinator trust, crash recovery, and performance evaluations.

This version substantially revises the earlier PiTPM design. The protocol and security model were redesigned to remove the earlier dependences and security flaws