Accepted Paper at CCS 2020 „Deterministic Wallets in a Quantum World“

10.09.2020

The authors of this paper are: Nabil Alkeilani Alkadri, Poulami Das, Andreas Erwig, Sebastian Faust, Juliane Krämer, Siavash Riahi, Patrick Struck.

Here is the abstract of our paper:

Most blockchain solutions are susceptible to quantum attackers as they rely on cryptography that is known to be insecure in the presence of

quantum adversaries. In this work we advance the study of quantum resistant blockchain solutions by giving a quantum resistant construction

of a deterministic wallet scheme. Deterministic wallets are frequently used in practice in order to secure funds by storing the

sensitive secret key on a so-called cold wallet that is not connected to the Internet. Recently, Das et al. (CCS'19) developed a formal model for the

security analysis of deterministic wallets and proposed a generic construction from certain types of signature schemes that exhibit key

rerandomization properties. We revisit the proposed classical construction in the presence of quantum adversaries, and obtain the following

results.

First, we give a generic wallet construction with security in the quantum random oracle model (QROM) if the underlying signature

scheme is secure in the QROM. We next design the first post-quantum secure signature scheme with rerandomizable public keys by giving a

construction from generic lattice-based Fiat-Shamir signature schemes. Finally, we show and evaluate the practicality by analyzing an

instantiation of the wallet scheme based on the signature scheme qTESLA (ACNS'20).