Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Signature Scheme, Publicly Derived Public Key, Key-Insulated Security, Privacy

Date: received 8 Oct 2018, last revised 10 Oct 2018

Contact author: liuzhen at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20181010:094519 (All versions of this report)

Short URL: ia.cr/2018/956


[ Cryptology ePrint archive ]