Re: [Taler] post-quantum refresh

[Jeff Burdges]

At this hour, the hashed based refresh protocol looks fairly simple.  I
think it saves space and eliminates kappa curve25519 operations on each
side too. 


Let kappa denote the exchange's security parameter.  

First, we define the Merkle line functions : 
  ml_j(m) = H(m || j)
  ML(m) = H( H(ml_1(m)) || .. || H(ml_kappa(m)) )


We've a tainted coin C = c G and M = ML(m) with a blind signature
        S_d(C || M) where d is the denomination key.  
We want to refresh it into a coin C' = c' G.


Wallet phase 1.
  For i=1..kappa:
    Create c^i and compute C^i = c^i G 
    Create blinding factor b^i.
    Create random m^i.
    Compute B^i = B_{b^i}(C^i || ML(m^i)).
    Encrypt E^i = E_{ml_i(m)}(c^i, b^i, m^i)
  Send commitment S' = S_C( (E^i,B^i) for i=1..kappa )
Exchange phase 1.
  Pick random gamma in 1..kappa.
  Mark C as spent by saving (C,gamma,S').
  Send gamma and S(C,gamma,...)
Wallet phase 2.
  Save ...
  Set Beta_gamma = H(ml_gamma(m)) and
      beta_i = ml_i(m) for i=1..kappa not gamma
  Send S_C(Beta_gamma || beta_i for i=1..kappa not gamma).
Exchange phase 2.
  Set Beta_i = H(beta_i) for i=1..k except gamma, keep Beta_gamma.
  Verify M = H( Beta_1 || .. || Beta_kappa ).
  For i=1..k except gamma:
    Decrypt c^i, b^i, and m^i from E^i using beta_i.
    Compute C^i = c^i G.
    Verify B^i = B_{b^i}(C^i || ML(m^i)).
  If verifications pass then send S_d(B^gamma).


We do not take m=c because that give an quantum attack on the blinding
factors.  We could let m, c, and even the b all be distinct hashes of
another secret value, shortening E but costing a few more hashes.  

We should be careful of attacks on ml_i(m) via E_{ml_i(m)} either by
using IVs properly, using an IV missuse resistant E, or by making c^i,
b^i, m^i deterministic. 


I'll need to check all this when I haven't been awake quite so long.  ;)

Best,
Jeff

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