[Taler] Against post-quantum blind signature schemes in Taler (for now)

[Jeff Burdges]

As I've been digging into post-quantum public key schemes for my mix
network research, Christian asked that I review the current state of
post-quantum blind signature schemes.  We would not deploy this anytime
soon of course, but it's nice to know the options.  

I've actually managed to find relatively solid answers after a
remarkably thin review of the literature :

  At present, there do not appear to be any post-quantum blind
  signature schemes that one could deploy without weakening real
  world security. 

There is a scheme based on supersingular isogenies Diffie-Hellman (SIDH)
described in https://eprint.iacr.org/2016/148 but it requires that the
signer participate in the verification.  At first blush, this sounds
okay for Taler since the merchant immediately contacts the exchange.
And indeed the protocol could probably be adapted.  I fear however that
the result would be more fragile.  And customers would probably need to
run the signature verification protocol during withdrawal and refresh,
adding round trips. 

In that same paper, they comment that lattice-based blind signature
schemes still use the Fiat-Shamir transform, which seems vulnerable to a
quantum attacker by https://eprint.iacr.org/2013/245 [1].  There are a
bunch of lattice-base blind signature articles though, so who knows if
they got everything.

In addition, I fear any current post-quantum blind signature scheme
would actually weaken customer anonymity, at least formally.

RSA blind signatures offer information theoretically secure anonymity
because you simply multiply your message's hash by an RSA encrypted
random number, and then divide by that number afterwards.  Although
maybe one should drag out the Chinese remainder theorem or something
here to be precise.  Also, it looks like the Schnorr and pairing-based
blind signatures were information theoretically secure too. 

In the blind signature scheme based on SIDH, you blind with a random
isogeny and unblind with it's dual, but the isogeny is uniquely
determined by the message and blinded curve.  I strongly suspect this
produces a confirmation attack *if* the underlying SIDH scheme were
broken:  Just check the guide points for any prime besides the blinding
prime. Alternatively, use the extra bit added in key compression.  In
other words, the consumer's anonymity rests on the underlying
cryptographic assumptions of SIDH, not information theoretic security.  

As I said, I have not examined the lattice-based schemes, as maybe none
are post-quantum currently.  If however a suitable one appears, then I'd
expect a similar situation where the customer's anonymity depends upon
the lattice-based cryptographic assumptions.

Imho, we should not weaken anonymity, even if only formally, to bolster
the exchange's financial security against an adversary that does not yet
exist.  In fact, there are good odds the first usable quantum computers
might be built by the sort of adversaries who could easily shutdown an
exchange using more conventional means.  

Best,
Jeff

[1] There are some subtleties here I should check, like verifying that
their "quantum random oracle model" attacks represent realistic
adversaries, as some quantum query attacks on symmetric crypto do not
represent realistic adversaries, but I'm assume the adversary would be
realistic since we're talking about public key crypto.

signature.asc
Description: This is a digitally signed message part