Paper 2023/1148

Post Quantum Fuzzy Stealth Signatures and Applications

Sihang Pu, Helmholtz Center for Information Security
Sri AravindaKrishnan Thyagarajan, NTT Research
Nico Döttling, Helmholtz Center for Information Security
Lucjan Hanzlik, Helmholtz Center for Information Security

Private payments in blockchain-based cryptocurrencies have been a topic of research, both academic and industrial, ever since the advent of Bitcoin. Stealth address payments were proposed as a solution to improve payment privacy for users and are, in fact, deployed in several major cryptocurrencies today. The mechanism lets users receive payments so that none of these payments are linkable to each other or the recipient. Currently known stealth address mechanisms either (1) are insecure in certain reasonable adversarial models, (2) are inefficient in practice or (3) are incompatible with many existing currencies. In this work, we formalize the underlying cryptographic abstraction of this mechanism, namely, stealth signatures with formal game-based definitions. We show a surprising application of our notions to passwordless authentication defined in the Fast IDentity Online (FIDO) standard. We then present SPIRIT, the first efficient post-quantum secure stealth signature construction based on the NIST standardized signature and key-encapsulation schemes, Dilithium and Kyber. The basic form of SPIRIT is only secure in a weak security model, but we provide an efficiency-preserving and generic transform, which boosts the security of SPIRIT to guarantee the strongest security notion defined in this work. Compared to state-of-the-art, there is an approximately 800x improvement in the signature size while keeping signing and verification as efficient as 0.2 ms. We extend SPIRIT with a fuzzy tracking functionality where recipients can outsource the tracking of incoming transactions to a tracking server, satisfying an anonymity notion similar to that of fuzzy message detection (FMD) recently introduced in [CCS 2021]. We also extend SPIRIT with a new fuzzy tracking framework called scalable fuzzy tracking that we introduce in this work. This new framework can be considered as a dual of FMD, in that it reduces the tracking server's computational workload to sublinear in the number of users, as opposed to linear in FMD. Experimental results show that, for millions of users, the server only needs 3.4 ms to filter each incoming message which is a significant improvement upon the state-of-the-art.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. CCS 2023
post-quantumstealth addressstealth signaturesfuzzy message detection
Contact author(s)
sihang pu @ cispa de
t srikrishnan @ gmail com
doettling @ cispa de
hanzlik @ cispa de
2023-07-27: approved
2023-07-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sihang Pu and Sri AravindaKrishnan Thyagarajan and Nico Döttling and Lucjan Hanzlik},
      title = {Post Quantum Fuzzy Stealth Signatures and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1148},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.