A Verifiably Encrypted Signature (VES) scheme encrypts a digital signature in a way that allows the public to verify the validity of the encrypted signature. Recently, several practical VES schemes for ECDSA have been proposed to enable escrowed transactions with cryptocurrencies. However, these schemes are inefficient in terms of both communication and computation, or require a large lookup table. In this paper, we present two efficient VES schemes for ECDSA that improve upon previous work. The first scheme is based on Castagnos-Laguillaumie (CL) encryption, while the second is based on modified Joye-Libert (JL) encryption. Our benchmark shows that our schemes outperform existing constructions by a factor of at least 2 in both computation and communication. Additionally, our solution does not rely on any lookup table. We demonstrate that these schemes can also be generalized to design VES for Schnorr signature scheme and EdDSA. The main technical contribution of this paper, which is of independent interest, is a zero-knowledge proof for the equality of the discrete log of an elliptic-curve point and that of a JL ciphertext. Importantly, the security of our proof does not rely on any non-standard assumptions.

Verifiably encrypted signature (VES) allows a signer to encrypt a signature under the public key of a trusted third party (aka adjudicator) in a verifiable manner. Recently, Yanget al.proposed a practical verifiably encrypted signature scheme for ECDSA and initiated the study of escrow protocol for Bitcoin via VES. This paper generalizes and improves the VES scheme of Yanget al., such that it covers a family of signatures with similar structures, including ECDSA, Schnorr and their variants. Our construction is very efficient: comparing with Yanget al.’s construction, the size of the resulting VES (for ECDSA) is reduced by more than 25 times. The only caveat is that the adjudicator is required to store a look-up table of size around 270MB. Our scheme naturally gives rise to escrow protocols for mainstream cryptocurrencies that employ ECDSA-like signatures to authorise transaction, including Bitcoin, Ethereum, Cardano, Chainlink, etc.

An escrow protocol for Bitcoin allows fair trading using bitcoins. To ensure fairness, the existing proposals made various trade-offs between trust, privacy, and efficiency. In this work, we evaluate the existing escrow protocols for cryptocurrency and propose a practical escrow protocol for Bitcoin that is: (a) computationally efficient; (b) round efficient; and (c) privacy-preserving. The core component of our escrow protocol for Bitcoin is a new verifiably encrypted ECDSA scheme, which may be of independent interest. Furthermore, we implement the escrow protocol for Bitcoin in Bitcoin mainnet, demonstrating the feasibility of our protocol.