[Top][All Lists]

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

Re: [Taler] post-quantum refresh

From: Jeff Burdges
Subject: Re: [Taler] post-quantum refresh
Date: Mon, 04 Apr 2016 01:38:00 +0200

I've fixed one mistake in the description.  I've satisfied myself that
the system is not really more fragile than the existing system that
hides linking keys with curve25519 operations.  

I worried about fragility coming from either (a) tricks around gamma, or
(b) miss-using a linking key.  Any tricks around gamma apply equally to
the curve25519 linking keys.  We cannot miss-use a linking key because
their ordering is fixed with the initial commitment anyways.  

It's important however that a coin has zero value left on it after being
melted because it cannot be melted twice, not without either the wallet
keeping checking the state or the wallet retrieving the state from the
exchange.  I suppose this makes recovery from backup more fragile. 

I've integrated the common source s idea for all the private coin data
here too.  I've omitted the new coin subscript like int he paper, but
unlike in the spec or code.

Let kappa and theta denote the exchange's security parameter and maximum
number of coins returned by a refresh. 

We define a Merkle tree/sequence function 
  m_link(m,i,j) = H(m || "YeyCoins!" || i || j) 
        Actual linking key for jth cut of ith target coin
  m_hide(m,i,j) = H( m_link{i,j}(m) )
        Linking key hidden for Merkle
  m_coin(m,i) = H( m_hide(m,i,1) || ... || m_hide(m,i,kappa) )
        Merkle root for refresh into the ith coin
  m_root(m) = M( m_coin(m,1), ..., m_coin(m,theta) )
        Merkle root for refresh of the entire coin
  m_path(m,i) = nodes adjacent to Merkle path to m_coin(m,i)
If theta is small then M(x[1],..,x[theta]) can be simply be the
concatenate and hash function H( x[1] || ... || x[theta] ) like in
m_coin, giving O(n) time.  If otoh theta n is large, then M should be a
hash tree to give O(log n) time.  We'd use M in m_coin too if kappa were
large, but concatenate and hash wins for kappa=3.  All these hash
functions should have a purpose string.

A coin now consists of 
  a Ed25519 public key C = c G,
  a Merkle root M = m_commit(m), and 
  an RSA signature S = S_d(C || M) by a denomination key d.
There was a blinding factor b used in the creation of the coin.
In addition, there was a value s such that 
  c = H("Ed25519" || s),
  m = H("Merkle" || s), and
  b = H("Blind" || s),
but we try not to retain s if possible.

We've a tainted coin (C,M,S) that we wish to refresh into n <= theta
untained coins.  For simplicity, we allow x' to stand for component
normally denoted x element of the ith new coin being created.  So 
  C' = c' G, M' = m_root(m'), and b' must be derived from s'.
for j=1..kappa, we allow x^j to denote the jth cut of the ith coin.  So
  C^j = c^j G, M^j = m_root(m^j), and b^j must be derived from s^j.
Wallet phase 1.
  For j=1..kappa:
    Create s^j.
    Compute c^j, m^j, and b^j from s^j.
    Compute C^j = c^j G too.
    Compute B^j = B_{b^j}(C^j || m_root(m^j)).
    Encrypt E^j = E_{m_link(m,i,j)}(s^j)
  Send commitment S' = S_C( (E^1,B^1), .. (E^kappa,B^kappa) )
  Note : If m_link were a stream cypher then E() could just be xor.

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 = m_hide(m,i,gamma) = H( m_link(m,i,gamma) ) and
      beta_i = m_link(m,i,j) j=1..kappa not gamma
  Send S_C(m_path(m,i) including m_coin(m,i) || 
           Beta_gamma || beta_j for j=1..kappa not gamma).

Exchange phase 2.
  Set Beta_j = H(beta_j) for j=1..k except gamma, keep Beta_gamma.
  Verify M with m_path(m,i) including m_coin(m,i).
  Verify m_coin(m,i) = H( Beta_1 || .. || Beta_kappa ).
  For j=1..kappa except gamma:
    Decrypt s^j from E^i using beta_i.
    Compute c^j, m^j, and b^j from s^j.
    Compute C^j = c^j G too.
    Verify B^i = B_{b^j}(C^j || m_root(m^j)).
  If verifications pass then send S_{d_i}(B^gamma).

As I mentioned, E can simply be xor if m_link were the output of a
stream cypher, so maybe that's worth doing.  

Aside from securely generating s, etc., we only care about m_link and E
being post-quantum, so m_link should be at least 256 bits, but all the
remaining m_hide, m_coin, and m_root need only be 128 bits.  I kinda
like m_link being larger than m_hide anyways because this makes that H
more resemble an information theoretically secure operation.  

It's harmless to double all these numbers if we're at all worried about
our stream cypher that produces m_link, so m_link and s could be 512
bits each, while the remaining hashes could be 256 bits each. 


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

reply via email to

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