A New Blind ECDSA Scheme for Bitcoin Transaction Anonymity

Xun Yi, Kwok-Yan Lam, Dieter Gollmann

Abstract

Bitcoin's pseudonymity often fails to protect user privacy when transactions are linked to real-world identities through liquidity providers. While blind signatures offer a theoretical solution, implementing them within Bitcoin's Elliptic Curve Digital Signature Algorithm (ECDSA) framework has historically faced compatibility and efficiency challenges. This paper presents a novel blind signature scheme based on a modified Paillier cryptosystem that produces standard ECDSA signatures. The protocol achieves high efficiency, with a total computation time of 175 milliseconds and minimal communication overhead, making it a viable solution for enhancing transaction anonymity without requiring changes to the Bitcoin protocol.

Introduction

While Bitcoin is frequently characterized as an anonymous currency, it is more accurately described as pseudonymous. A significant privacy vulnerability exists at the interface between the traditional financial system and the blockchain. When a user purchases bitcoin from a liquidity provider using a bank transfer or credit card, the provider can link the user’s legal identity to their specific blockchain address. This "doxing" allows the provider—and potentially any entity they share data with—to track the user’s future financial activity on the public ledger.

To mitigate this, cryptographers utilize blind signatures. In a blind signature scheme, a signer (the provider) signs a message without being able to see its contents. Once the signature is "unblinded" by the recipient, it remains valid but cannot be linked back to the specific signing session by the provider. However, most established blind signature schemes, such as those based on RSA, are incompatible with ECDSA, the cryptographic standard used by Bitcoin. Previous attempts to bridge this gap have often resulted in signatures that standard Bitcoin nodes cannot verify or protocols that lack formal security proofs.

Methodology: The Modified Paillier Cryptosystem

The authors propose a new protocol that leverages a modified version of the Paillier cryptosystem to facilitate blind ECDSA signatures.

1. Architectural Modifications

Standard Paillier encryption typically utilizes a modulus $N = pq$. The authors introduce a modified version where $N = pqt$ (the product of three primes). This structural change allows the cryptosystem to interact more effectively with the mathematical requirements of the elliptic curve operations used in ECDSA.

2. The Four-Step Interaction

The protocol follows a structured interaction between the Recipient (client) and the Signer (provider):

  • Commitment: The signer initiates the process by providing a cryptographic commitment.
  • Blinding: The recipient uses the modified Paillier system to blind the transaction data, ensuring the signer cannot see the underlying message.
  • Homomorphic Signing: Utilizing the additive homomorphic properties of the Paillier system, the signer applies their private key to the encrypted data. This allows the signer to contribute to the signature generation without ever seeing the plaintext transaction.
  • Unblinding: The recipient unblinds the resulting data to produce a standard, valid ECDSA signature.

3. Security via Zero-Knowledge Proofs (ZKP)

To ensure the integrity of the process, the protocol incorporates an interactive Zero-Knowledge Proof. This prevents a malicious recipient from submitting malformed blinded data in an attempt to extract the signer's private key. The ZKP ensures that the recipient has followed the protocol rules without revealing the transaction details.

Key Insights and Results

Full Bitcoin Compatibility

The most significant achievement of this scheme is that the final output is a standard ECDSA signature. Unlike previous research that required modified nodes or "hard forks" to the Bitcoin protocol, this scheme is fully compatible with the existing network. Any signature generated through this process can be verified by any standard Bitcoin miner or wallet software today.

Performance Benchmarks

The authors evaluated the scheme using Crypto++ 6.0.0 benchmarks on a standard Skylake Core-i5 (2.7GHz) hardware setup. The results demonstrate that the protocol is ready for commercial application:

  • Computation Speed: A single blind signature is completed in approximately 175 milliseconds.
  • Throughput: A provider could feasibly process 100 different client requests in roughly 8.75 seconds.
  • Data Efficiency: The total communication overhead is less than 28 kbytes per transaction, ensuring the protocol remains accessible for users on low-bandwidth connections.
  • Optimized Modulus: By utilizing a smaller modulus ($|N^2| = 2560$ bits) compared to previous attempts (which often required $>3328$ bits), the scheme reduces both computational load and data transmission requirements.

Security Foundations

The security of the scheme is formally grounded in the Decisional Composite Residuosity Assumption (DCRA). The authors provide proofs demonstrating that if the DCRA remains a hard mathematical problem, the scheme is both "blind" (the signer cannot link the signature to the user) and "unforgeable" (the user cannot create a valid signature without the signer's involvement).

Limitations and Future Directions

While the current protocol is highly efficient, the interactive Zero-Knowledge Proof in the second step introduces a degree of communication complexity. The authors have identified a potential modification that could eliminate the need for the ZKP, which would significantly increase processing speeds for high-volume providers. However, they note that a rigorous security proof for this streamlined version is still required. Future research will focus on validating this ZKP-less approach to further optimize the trade-off between security and performance in Bitcoin anonymity tools.

Conclusion

This research provides a practical path forward for Bitcoin privacy. By combining a modified Paillier cryptosystem with standard ECDSA requirements, the authors have developed a tool that allows users to interact with liquidity providers without sacrificing their long-term transaction privacy. The scheme's efficiency and immediate compatibility make it a strong candidate for real-world implementation in the Bitcoin ecosystem.

Summary updated

Abstract

In this paper, we consider a scenario where a bitcoin liquidity provider sells bitcoins to clients. When a client pays for a bitcoin online, the provider is able to link the client's payment information to the bitcoin sold to that client. To address the privacy concerns of clients, we require that the bitcoin provider cannot tell the relationship between the real identities of clients and the sold bitcoins in the blockchain. This requirement can be effectively achieved by using blind signatures. However, existing blind signature schemes are incompatible with the Elliptic Curve Digital Signature Algorithm (ECDSA) which is used by most of the existing bitcoin protocol, thus cannot be applied directly in Bitcoin. In this paper, we propose a new blind signature scheme that allows generating a blind signature compatible with the standard ECDSA. Afterwards, we make use of the new scheme to achieve bitcoin transaction anonymity. The new scheme is built on a variant of the Paillier cryptosystem and its homomorphic properties. As long as the modified Paillier cryptosystem is semantically secure, the new blind signature scheme has blindness and unforgeability.
BibTeX
@article{yi2018new,
  author = {Xun Yi and Kwok-Yan Lam and Dieter Gollmann},
  title = {{A New Blind ECDSA Scheme for Bitcoin Transaction Anonymity}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
  url = {https://openreview.net/forum?id=PJPH__59cPY},
}
Figure