"Act natural!": Having a Private Chat on a Public Blockchain

Chats have become an essential means of interpersonal interaction. Yet untraceable private communication remains an elusive goal, as most messengers hide content, but not communication patterns. The knowledge of communication patterns can by itself reveal too much, as happened e.g., in the context of the Arab Spring. The subliminal channel in cryptographic systems - as introduced by Simmons in his pioneering works - enables untraceable private communication in plain sight. In this context, blockchains are a natural object for subliminal communication: accessing them is innocuous, as they rely on distributed access for verification and extension. At the same time, blockchain transactions generate hundreds of thousands transactions per day that are individually signed and placed on the blockchain. This significantly increases the availability of publicly accessible cryptographic transactions where subliminal channels can be placed. In this paper we propose a public-key subliminal channel using ECDSA signatures on blockchains and prove that our construction is undetectable in the random oracle model under a common cryptographic assumption. While our approach is applicable to any blockchain platform relying on (variants of) ECDSA signatures, we present a proof of concept of our method for the popular Bitcoin protocol and show the simplicity and practicality of our approach.