Paper 2018/956

Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key

Zhen Liu and Guomin Yang and Duncan S. Wong and Khoa Nguyen and Huaxiong Wang

Abstract

Since the introduction of Bitcoin in 2008, cryptocurrency has been undergoing a quick and explosive development. At the same time, privacy protection, one of the key merits of cryptocurrency, has attracted much attention by the community. In this paper, we identify a security vulnerability of the privacy-preserving key derivation algorithm of Monero, which is one of the most popular privacy-centric cryptocurrencies. To provide a formal treatment for the problem, we introduce and formalize a new signature variant, called Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS), which forms a convenient and robust cryptographic tool for building privacy-preserving cryptocurrencies. Specifically, PDPKS allows anyone to derive new signature verification keys for a user, say Alice, based on her long-term public-key, while only Alice can derive the signing keys corresponding to those verification keys. In terms of privacy, given a derived verification key and valid signatures with respect to it, an adversary is not able to link them to the underlying long-term public key; and given two verification keys and corresponding valid signatures, an adversary cannot tell whether the verification keys are derived from the same long-term public key. A distinguishing security feature of PDPKS, with the above functionality and privacy features, is that the derived keys are independent/insulated from each other, namely, compromising the signing key associated with a verification key does not allow an adversary to forge a valid signature for another verification key, even if both verification keys are derived from the same long-term public key. We formalize the notion of PDPKS and propose a practical and proven secure construction, which fixes the identified security vulnerability in Monero and provides a more robust solution for implementing the so-called stealth addresses for cryptocurrencies. Also, our PDPKS scheme can be used to fix the similar vulnerability in the deterministic wallet algorithm for Bitcoin.