[Taler] Post-quantum Taler

[Jeff Burdges]

We were asked about the NSA's recent comments on quantum cryptography
during Florian's trial run of his talk where he mentioned RSA blind
signing.  We'll probably be asked about it again, so..

Flippant answer : 

Actually the NSA suggested a move away from ECC and towards RSA
temporarily, so this does not concern the RSA parts.  

Serious answer : 

Almost all the ECC in Taler pertains only to individual coins in a non-privacy 
sensitive way.  It's therefore not a high enough value target for an quantum 
attacks unless quantum computers go from impossible to stupidly cheap 
incredibly fast.

There are however two avenues for relevant quantum attacks on Taler :

(0) There are no know quantum attacks on the blinding process itself,
as the customer never reveals any public key.  A quantum adversary
therefore cannot look back into the recorded past to deanonymize a
coin.  They can of course look back into the past to deanonymize the
transaction itself, like with all other online communication.

(1) Attacks on the mint's denomination key could be used to rob or
bankrupt the mint.  These are not realistic because the mint's
denomination keys come with a relatively short expiration date, like a
year or so.   A nation would not gamble exposing an advantage in
quantum computing to rob or destroy a bank.  They'd just murder us if
they cared that much.

(2) There is a quantum attack against the refresh cut-choose protocol
whereby the attacker can look back into the recorded past to associate
coins with previously spent coins.

Ridiculous answer : 

We could actually modify Taler to be post-quantum, but it's not
desirable to do so unless real progress is made on quantum computation.
 How you ask?  

First, any signing algorithms and keys could be replaced by post
-quantum signature algorithms, maybe hash based ones like say Sphincs. 
 This consumes considerable of bandwidth and storage.

Second, I'd imagine most encryption based upon a Diffie-Hellman
operation like (2) could be replaced by a Diffie-Hellman-like operation
using either a Ring-LWE or super-singular isogenies, or maybe even
NTRU.

Third, we could continue to using RSA blind singing for issuing coins
but the mint no longer reveals the denomination key.  Instead, we could
create a withdrawal-refund protocol where you can refund a coin that
nobody ever spent.  A peer-to-peer protocol could then coordinate
random withdrawal-refund operations with identical coins by different
blinding factors, thereby verifying that the mint was not
systematically targeting anyone by assigning them custom denomination
keys.  

There are probably better ways to do this third part that do not make
users machine's actively work to guard their privacy, maybe even crazy
hash based stuff, but it's an answer if anyone ever presses the post
-quantum issue to ridiculous levels.

Best,
Jeff

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