International Association
for Cryptologic Research

Since the invention of Bitcoin, cryptocurrencies have gained huge popularity. Crypto wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency funds. Deterministic wallet is an advanced wallet mecha- nism that has been proposed to achieve some appealing virtues, such as low-maintenance, easy backup and recovery, supporting functionalities required by cryptocurrencies, and so on. However, the existing deter- ministic wallet schemes especially in the quantum world still have a long way to be practical. The first barrier is how to build a deterministic wallet scheme without relying on the state, i.e., stateless. The stateful deterministic wallet scheme must internally maintain and keep refreshing synchronously a parameter named state which makes the implementa- tion in practice become more complex. And once one of the states is leaked, thereafter the security notion of unlinkability is cannot be guar- anteed (referred to as the weak security notion of forward unlinkability). The second barrier is how to derive the session secret keys from the master secret key in one-way. There are security shortfalls in previous works, they suffer a fatal vulnerability when a minor fault happens (say, one derived key is compromised somehow), then the damage is not lim- ited to the leaked derived key, instead, it spreads to the master key and the whole system collapses. The third barrier is how to build a post- quantum secure deterministic wallet scheme supporting hot/cold setting, which is important since nearly all popular cryptocurrencies relied on the hardness problems that can be broken by quantum adversaries, and the hot/cold setting is a widely adopted method to effectively reduce the exposure chance of secret keys and hence improving the security of the system. The last barrier is how to build a deterministic wallet scheme with standard security notion of unforgeability. It is motivated by pre- vious works which are based on a weaker/nonstandard unforgeability notion, in which the adversary is only allowed to query and forge the signatures w.r.t. the public keys that were assigned by the challenger.

In this work, we present a new deterministic wallet scheme in quantum world, which is stateless, supports hot/cold setting, satisfiies stronger security notions, and is more efficient. In particular, we reformalize the syntax and security models for deterministic wallets, capturing the func- tionality and security requirements (including full unlinkability and stan- dard unforgeability) imposed by the practice in cryptocurrency. Then we propose a deterministic wallet construction and prove its security in the quantum random oracle model. Finally, we show our wallet scheme is more practicable by analyzing an instantiation of our wallet scheme based on the signature scheme Falcon.