Paper 2026/2277

Non-Interactive Atomic Swaps from Standard Signatures: Lower Bounds and Constructions

Abstract

Atomic swaps are the prototypical application of adaptor signatures. Practical constructions settle with two ordinary on-chain signatures and require no scripting, but they need two sequential online rounds: Alice samples a hard statement and sends its pre-signature, and Bob follows with his own pre-signature using the same statement. We ask whether the protocol can be compressed into a single online round (from Bob to Alice), which we call a non-interactive atomic swap, without relying on impractical universal adaptor signatures. In particular, we require that both parties continue to use standard signature schemes with unmodified verification algorithms. Our main result is a lower bound: for statistically unlinkable adaptors with negligible faithfulness failure, Bob's valid-signature space per message must be superpolynomially larger than the relation's witness space. This (1) reaffirms the impossibility result by Erwig et al. [PKC 2021] for unique signatures as a trivial corollary, and (2) excludes non-interactive swaps using the same signature scheme on both sides. However, the bound does leave room for asymmetric instantiations. We give one in which Alice signs with BLS and Bob uses a pairing-Schnorr adaptor whose witness is Alice's BLS signature, and prove its security under the native unforgeability of BLS in the random oracle model. To support more signature schemes in our non-interactive swap framework, we introduce atomic signature swaps with preprocessing: Alice publishes message-independent public data before the messages are chosen. These data, together with her public key and the messages, later determine a statement whose witnesses assemble into her native signature. The protocol requires a single online round carrying a pre-signature by Bob and falls into our non-interactive framework. We prove a Schnorr/Schnorr instantiation under the OMDL assumption in the random oracle model, and give a conditional ECDSA/Schnorr instantiation.