Paper 2026/2549

Firebolt: Fast, Lightweight, Malicious Non-Interactive Vector-OLE

Abstract

We introduce a new maliciously-secure vector oblivious linear evaluation (VOLE), building upon a recent construction of (semi-honest) Paillier-based non-interactive VOLE. Our protocol is non-interactive (the sender can adaptively reveal entries of the VOLE using a single message to the receiver) and enjoys low communication (535 bytes for each VOLE entry) and low computation (around 5ms per party, single-threaded). Our protocol can be used as a drop-in replacement for less efficient VOLEs used in a variety of threshold schemes. We exemplify it by devising a new concurrently-secure two-round two-party ECDSA protocol that significantly improves over the state of the art. Along the way, we introduce several new strategies for proving shortness of plaintexts in Paillier ciphertexts or integer commitments, and we devise a modular framework for building threshold-ECDSA in a VOLE-hybrid model with concurrent security without requiring the use of (typically less efficient) UC-secure VOLE. All of these contributions are of independent interest.