[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Taler] post-quantum refresh

From: Jeff Burdges
Subject: [Taler] post-quantum refresh
Date: Thu, 31 Mar 2016 03:05:23 +0200

I noticed a refresh-like algorithm with post-quantum blinding by
replacing the public key encryption with a symmetric key encryption
using a key in a Merkle tree, similar to hash based signatures.

I'll first describe a scheme for taxability during initial issuing,
which currently Taler does not worry about :  A reserve consists of both
an Ed25519 public key and the root of a large Merkle tree of symmetric
keys.  In issuing a coin, the wallet proves the coin's private key was
encrypted with a symmetric key in the Merkle tree via cut n' choose. 

A refresh protocol works similarly :  A coin is not merely an Ed25519
public key but also a Merkle tree root of the symmetric keys one may use
to refresh it.  A refresh record's unencrypted part identifies the
location in the tree of the tree of the coin it was refreshed from.  A
refresh record's encrypted part holds the new coin's private tree
generator.  And verification now checks that the root of the new coins
Merkle tree appears in the blind signed hash too. 

Is there a "huge foot-cannon" here like with stateful hashed based
signature schemes?
Yes of course.  Can we make the above scheme stateless though?

Yes!  We can do the refresh stateless easily because it happens only
once or twice.  :)

Initial issuing taxability is harder to make stateless.  We replace the
"sign a subtree" trick of hashed based signatures with the idea: If the
refresh can be stateless, then one should "refresh" the reserve's
initial issuing tree." 

In other words, we replace the reserve's initial issuing Merkle tree
before every withdraw operation by treating it as an "issuing
pseudo-coin" with no value, no RSA component, and no anonymity, but
still refreshable like the Merkle tree component of an ordinary coin.

There are two important tricks that make this viable : 
- We keep an initial secret s that we hash with public values to create
deterministically create private tree generators.  In this way, if a
user restores from backup after replacing their Merkle root then they
can regenerate the current one.
- We cannot trust cut n' choose much here because iterating it wins
eventually and this "issuing pseudo-coin" costs little but enables
unlimited tax evasion with real coins.  Instead, we produce 128
candidate trees of which say k=128*p will survive cut n' choose.  We
demand encryptions from each of the previous k trees for all 128
candidates.  In a round, the bad user could win some bad merchant
controlled trees, but this does not grown because they must encrypt the
private generator of all new trees with all old ones.  Actually 128
sounds excessive here. 

Should we actually build this for Taler?  NO!  It's easier for us to
fuck up building crypto primitives from Merkle trees while working
within our budget, than it is for the NSA to build a quantum computer on
their budget.  

I think a hash-based post-quantum refresh protocol sounds like an
interesting paper though because we're replacing a public key encryption
operation with a hash based encryption operation.  That's rather


p.s.  There is no significant increase in the size of ordinary refresh
records, but if one wants taxability for initial issuing then that's k
refresh records per withdraw operation including k^2 encryptions, in
addition to refresh records for the withdrawn coins. 

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]