Paper 2021/963

Post-Quantum Key-Blinding for Authentication in Anonymity Networks

Edward Eaton, Douglas Stebila, and Roy Stracovsky


Anonymity networks, such as the Tor network, are highly decentralized and make heavy use of ephemeral identities. Both of these characteristics run in direct opposition to a traditional public key infrastructure, so entity authentication in an anonymity network can be a challenge. One system that Tor relies on is key-blinded signatures, which allow public keys to be transformed so that authentication is still possible, but the identity public key is masked. This is used in Tor during onion service descriptor lookup, in which a .onion address is resolved to a rendezvous point through which a client and an onion service can communicate. The mechanism currently used is based on elliptic curve signatures, so a post-quantum replacement will be needed. We consider four fully post-quantum key-blinding schemes, and prove the unlinkability and unforgeability of all schemes in the random-oracle model. We provide a generic framework for proving unlinkability of key-blinded schemes by reducing to two properties, signing with oracle reprogramming and independent blinding. Of the four schemes, two are based on Round 3 candidates in NIST's post-quantum signature standardization process, Dilithium and Picnic. The other two are based on much newer schemes, CSI-FiSh and LegRoast, which have more favourable characteristics for blinding. CSI-FiSh is based on isogenies and boasts a very small public key plus signature sizes, and its group action structure allows for key-blinding in a straightforward way. LegRoast uses the Picnic framework, but with the Legendre symbol PRF as a symmetric primitive, the homomorphic properties of which can be exploited to blind public keys in a novel way. Our schemes require at most small changes to parameters, and are generally almost as fast as their unblinded counterparts, except for blinded Picnic, for which signing and verifying is roughly half as fast.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. Latincrypt 2021
Contact author(s)
eeaton @ uwaterloo ca
dstebila @ uwaterloo ca
rstracovsky @ uwaterloo ca
2021-07-22: received
Short URL
Creative Commons Attribution


      author = {Edward Eaton and Douglas Stebila and Roy Stracovsky},
      title = {Post-Quantum Key-Blinding for Authentication in Anonymity Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2021/963},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.