exchange

postquantum.tex (21751B)

---

 \documentclass{llncs}
 %\usepackage[margin=1in,a4paper]{geometry}
 \usepackage[T1]{fontenc}
 \usepackage{palatino}
 \usepackage{xspace}
 \usepackage{microtype}
 \usepackage{tikz,eurosym}
 \usepackage{amsmath,amssymb}
 \usepackage{enumitem}
 \usetikzlibrary{shapes,arrows}
 \usetikzlibrary{positioning}
 \usetikzlibrary{calc}
 
 % Relate to:
 % http://fc14.ifca.ai/papers/fc14_submission_124.pdf
 
 % Terminology:
 % - SEPA-transfer -- avoid 'SEPA transaction' as we use
 %       'transaction' already when we talk about taxable
 %        transfers of Taler coins and database 'transactions'.
 % - wallet = coins at customer
 % - reserve = currency entrusted to exchange waiting for withdrawal
 % - deposit = SEPA to exchange
 % - withdrawal = exchange to customer
 % - spending = customer to merchant
 % - redeeming = merchant to exchange (and then exchange SEPA to merchant)
 % - refreshing = customer-exchange-customer
 % - dirty coin = coin with exposed public key
 % - fresh coin = coin that was refreshed or is new
 % - coin signing key = exchange's online key used to (blindly) sign coin
 % - message signing key = exchange's online key to sign exchange messages
 % - exchange master key = exchange's key used to sign other exchange keys
 % - owner = entity that knows coin private key
 % - transaction = coin ownership transfer that should be taxed
 % - sharing = coin copying that should not be taxed
 
 
 \title{Post-quantum anonymity in Taler}
 
 \begin{document}
 \mainmatter
 
 \author{Jeffrey Burdges}
 \institute{Inria / GNUnet / Taler}
 
 
 \maketitle
 
 \begin{abstract}
 David Chaum's original RSA blind sgnatures provide information theoretic
 anonymity for customers' purchases.  In practice, there are many schemes
 that weaken this to provide properties, such as offline transactions or
 taxability in Taler.  We describe a refresh protocol for Taler that
 provides customers with post-quantum anonymity.  It replaces an elliptic
 curve Diffe-Hellman operation with a hash-based encryption scheme for
 the proof-of-trust via key knoledge property that Taler requires to
 distinguish untaxable operations from taxable purchases. 
 \end{abstract}
 
 
 \section{Introduction}
 
 David Chaum's RSA blind sgnatures \cite{} can provide financial
 security for the exchange, or traditionally mint,
  assuming RSA-CTI \cite{,}. 
 
 A typical exchange deployment must record all spent coins to prevent
 double spending.  It would therefore rotate ``denomination'' signing
 keys every few weeks or months to keep this database from expanding
 indefinitely \cite{Taler??}.  As a consequence, our exchange has
 ample time to respond to advances in cryptgraphy by increasing their
 key sizes, updating wallet software with new algorithms, or
 even shutting down.
 
 In particular, there is no chance that quantum computers will emerge
 and become inexpensive within the lifetime of a demonination key.
 Indeed, even a quantum computer that existed only in secret posses
 little threat because the risk of exposing that secret probably exceeds
 the exchange's value. 
 
 \smallskip
 
 We cannot make the same bold pronouncement for the customers' anonymity
 however.  We must additionally ask if customers' transactions can be
 deanonymized in the future by the invention of quantum computes, or
 mathematical advances. 
 
 David Chaum's original RSA blind sgnatures provide even information
 theoretic anonymity for customers, giving the desired negative answer.
 There are however many related schemes that add desirable properties
 at the expense of customers' anonymity.  In particular, any scheme
 that supports offline merchants must add a deanonymization attack
 when coins are double spent \cite{B??}.  
 
 Importantly, there are reasons why exchanges must replace coins that
 do not involve actual financial transactons, like to reissue a coin
 before the exchange rotates the denomination key that signed it, or
 protect users' anonymity after a merchant receives a coin, but fails
 to process it or deliver good.
 
 In Taler, coins can be partially spent by signing with the coin's key
 for only a portion of the value determined by the coin's denomination
 key.  This allows precise payments but taints the coin with a
 transaction,  which frequently entail user data like a shipng address.  
 To correct this, a customer does a second transaction with the exchange
 where they sign over the partially spent coin's risidual balance
 in exchange for new freshly anonymized coins.  
 Taler employs this {\em refresh} or {\em melt protocol} for
 both for coins tainted through partial spending or merchant failures,
 as well as for coin replacement due to denomination key roration.
 
 If this protocol were simply a second transaction, then customers
 would retain information theoreticaly secure anonymity.  
 In Taler however, we require that the exchange learns accurate income
 information for merchants.  If we use a regular transaction, then
 a customer could conspire to help the merchant hide their income
 \cite[]{Taler??}.
 To prevent this, the refresh protocol requires that a customer prove
 that they could learn the private key of the resulting new coins.
 
 At this point, Taler employs an elliptic curve Diffie-Hellman key
 exchange between the coin's signing key and a new linking key 
 \cite[??]{Taler??}.  As the public linking key is exposed,
 an adversary with a quantum computer could trace any coins involved
 in either partial spending operations or aborted transactions.
 A refresh prompted by denomination key rotation incurs no anonymity
 risks regardless.
 
 \smallskip
 
 We propose two variations on Taler's refresh protocol that offer
 resistane to a quantum adversary.
 
 First, we describe attaching contemporary post-quantum key exchanges,
 based on either super-singular eliptic curve isogenies \cite{SIDH} or
 ring learning with errors (Ring-LWE) \cite{Peikert14,NewHope}.
 These provide strong post-quantum security so long as the underlying
 scheme remains secure; however, these schemes' youth leaves them
 relatively untested.
 
 Second, we propose a hash based scheme whose anonymity guarantee needs
 only the one-way assumption on our hash function.  In this scheme,
 the vible security parameter is numerically far smaller than in the
 key exchange systems, but covers query complexity which we believe
 suffices.
 
 We describe this hash based proof-of-encryption-to-self scheme to
 align the description of all our schemes.
 
 ...
 
 \smallskip
 
 %TODO : What is this part for?
 
 We observe that several elliptic curve blind signature schemes provide
 information theoreticly secure blinding as well, but 
  Schnorr sgnatures require an extra round trip \cite{??}, and
  pairing based schemes offer no advnatages over RSA \cite{??}.
 
 There are several schemes like Anonize \cite{} in Brave \cite{}, 
 or Zcash \cite{} used in similar situations to blind signatures. 
 % https://github.com/brave/ledger/blob/master/documentation/Ledger-Principles.md
 In these systems, anonymity is not post-quantum due to the zero-knowledge
 proofs they employ.
 
 
 \section{Taler's refresh protocol}
 
 \def\Mu{M}
 \def\Eta{}
 \def\newmathrm#1{\expandafter\newcommand\csname #1\endcsname{\mathrm{#1}}}
 \newmathrm{CPK}
 \newmathrm{CSK}
 \newmathrm{LPK}
 \newmathrm{LSK}
 \newmathrm{KEX}
 
 
 We shall describe Taler's refresh protocol in this section.
 All notation defined here persists throughout the remainder of
  the article.
 
 We let $\kappa$ denote the exchange's taxation security parameter,
 meaning the highest marginal tax rate is $1/\kappa$.  Also, let 
 $\theta$ denote the maximum number of coins returned by a refresh.
 
 \smallskip
 
 We label place holders $\eta$, $\lambda$, $\Lambda$, $\mu$, and $\Mu$
 for key material involved in post-quantum operations.  
 We view $\Lambda$ and $\Mu$ as public keys with respective
  private keys $\lambda$ and $\mu$, and
 $\eta$ as the symmetric key resulting from the key exchange between them.
 
 We need efficiently computable functions
   $\CPK$, $\CSK$, $\LPK$, $\LSK$, $\KEX_2$ and $\KEX_3$  such that 
 \begin{itemize}
 \item  $\mu = \CSK(s)$ for a random bitstring $s$,
        $\Mu = \CPK(\mu)$,
 \item  $\lambda = \LSK(t,\mu)$ for a bitstring $t$, 
        $\Lambda = \LPK(\lambda)$, and
 \item $\eta = \KEX_2(\lambda,\Mu) = \KEX_3(\Lambda,\mu)$.
 \end{itemize}
 In particular, if $\KEX_3(\Lambda,\mu)$ would fail
  then $\KEX_2(\lambda,\Mu)$ must fail too.
 
 % Talk about assumption that if KEX_2 works then KEX_3 works?
 If these are all read as empty, then our description below reduces
 to Taler's existing refresh protocol. 
 
 \smallskip
 
 A coin $(C,\Mu,S)$ consists of 
   a Ed25519 public key $C = c G$,
   a post-quantum public key $\Mu$, and
   an RSA-FDH signature $S = S_d(C || \Mu)$ by a denomination key $d$.
 A coin is spent by signing a contract with $C$.  The contract must
 specify the recipient merchant and what portion of the value denoted
 by the denomination $d$ they receive.
 If $\Mu$ is large, we may replace it by $H(C || \Mu)$ to make signing
 contracts more efficient.
 
 There was of course a blinding factor $b$ used in the creation of
 the coin's signature $S$.  In addition, there was a private seed $s$
 used to generate $c$, $b$, and $\mu$, but we need not retain $s$
 outside the refresh protocol.
 $$ c = H(\textrm{"Ed25519"} || s)
 \qquad \mu = \CSK(s)
 \qquad b = H(\textrm{"Blind"} || s) $$
 
 \smallskip
 
 We begin refresh with a possibly tainted coin $(C,\Mu,S)$ that
 we wish to refresh into $n \le \theta$ untainted coins.  
 
 In the change situation, our coin $(C,\Mu,S)$ was partially spent and 
 retains only a part of the value determined by the denominaton $d$.
 There is usually no denomination that matchets this risidual value
 so we must refresh from one coin into $n \le \theta$.
 
 For $x$ amongst the symbols $c$, $C$, $\mu$, $\Mu$, $b$, and $s$,
 we let $x_{j,i}$ denote the value normally denoted $x$ of
  the $j$th cut of the $i$th new coin being created. 
 % So $C_{j,i} = c_{j,i} G$, $\Mu_{j,i}$, $m_{j,i}$, and $b^{j,i}$
 %  must be derived from $s^{j,i}$ as above.
 We need only consider one such new coin at a time usually, 
 so let $x'$ denote $x_{j,i}$ when $i$ and $j$ are clear from context.
 In other words, $c'$, $\mu'$, and $b_j$ are derived from $s_j$,
  and both $C' = c' G$ and $\Mu' = \CSK(s')$.
 
 \paragraph{Wallet phase 1.}
 \begin{itemize}
 \item  For $j=1 \cdots \kappa$:
    \begin{itemize}
    \item  Create random $\zeta_j$ and $l_j$.
    \item  Also compute $L_j = l_j G$.
    \item  Generate $\lambda_j = \LSK((j,i),\mu)$,
           $\Lambda_j = \LPK(\lambda_j)$, and
             $\eta_j = \KEX_2(\lambda_j,\Mu)$.
    \item  Set the linking commitment $\Gamma_{j,0} = (L_j,E_{l_j C}(\Lambda_j))$. 
    \item  Set $k_j = H(l_j C || \eta_j)$.
 \smallskip
    \item  For $i=1 \cdots n$:
       \begin{itemize}
       \item  Set $s' = H(\zeta_j || i)$.
       \item  Derive $c'$, $m'$, and $b'$ from $s'$ as above.
       \item  Compute $C' = c' G$ and $\Mu' = \CPK(m')$ too.
       \item  Compute $B_{j,i} = B_{b'}(C' || \Mu')$.
       \item  Encrypt $\Gamma'_{j,i} = E_{k_j}(s')$. 
       \item  Set the coin commitments $\Gamma_{j,i} = (\Gamma'_{j,i},B_{j,i})$
 \end{itemize}
 \smallskip
 \end{itemize}
 \item  Send $(C,\Mu,S)$ and the signed commitments
    $\Gamma_* = S_C( \Gamma_{j,i} \quad\textrm{for}\quad j=1\cdots\kappa, i=0 \cdots n )$.
 \end{itemize}
 
 \paragraph{Exchange phase 1.}
 \begin{itemize}
 \item  Verify the signature $S$ by $d$ on $(C || \Mu)$.
 \item  Verify the signatures by $C$ on the $\Gamma_{j,i}$ in $\Gamma_*$.
 \item  Pick random $\gamma \in \{1 \cdots \kappa\}$.
 \item  Mark $C$ as spent by saving $(C,\gamma,\Gamma_*)$.
 \item  Send $\gamma$ as $S(C,\gamma)$.
 \end{itemize}
 
 \paragraph{Wallet phase 2.}
 \begin{itemize}
 \item  Save $S(C,\gamma)$.
 \item  For $j = 1 \cdots \kappa$ except $\gamma$:
    \begin{itemize}
    \item  Create a proof $\lambda_j^{\textrm{proof}}$ that
           $\lambda_j$ is compatible with $\Lambda_j$ and $\Mu$.
    \item  Set a response tuple
           $R_j = (\zeta_j,l_j,\lambda_j,\lambda_j^{\textrm{proof}})$.
    \end{itemize}
 \item  Send $S_C(R_j \quad\textrm{for}\quad j \ne \gamma )$.
 \end{itemize}
 
 \paragraph{Exchange phase 2.}
 \begin{itemize}
 \item  Verify the signature by $C$.
 \item  For $j = 1 \cdots \kappa$ except $\gamma$:
    \begin{itemize}
    \item  Compute $\eta_j = \KEX_2(\lambda_j,\Mu)$.
    \item  Verify that $\Lambda_j = \LPK(\lambda_j)$
    \item  Set $k_j = H(l_j C || \eta_j)$.
    \item  For $i=1 \cdots n$:
      \begin{itemize}
      \item  Decrypt $s' = D_{k_j}(\Gamma'_{j,i})$.
      \item  Compute $c'$, $m'$, and $b'$ from $s_j$.
      \item  Compute $C' = c' G$ too.
      \item  Verify $B' = B_{b'}(C' || \Mu')$.
      \end{itemize}
    \end{itemize}
 \item  If verifications all pass then send $S_{d_i}(B_\gamma)$.
 \end{itemize}
 
 We could optionally save long-term storage space by
 replacing $\Gamma_*$ with both $\Gamma_{\gamma,0}$ and
  $S_C(\Eta_{j,i} \quad\textrm{for}\quad j \ne \gamma )$.
 It's clear this requires the wallet send that signature in some phase,
 but also the wallet must accept a phase 2 response to a phase 1 request.
 
 \smallskip
 
 There is good reason to fear tax evasion committed during the
 initial withdrawal of a coin as well.  A merchant simply provides
 the customer with a blinded but unpurchased coin and asks them to
 pay to withdraw it.
 
 \subsection{Withdrawal}\label{subsec:withdrawal}
 
 In Taler, we may address tax fraud on initial withdrawal by turning
 withdrawal into a refresh from a pseudo-coin $(C,\Mu)$ in which 
  $C$ is the user's reserve key \cite[??]{Taler} and
  $\Mu$ s a post-quantum public key kept with $C$.
 We see below however that our public key algorithm has very different
 security requirements in this case, impacting our algorithm choices.
 
 
 \section{Post-quantum key exchanges}
 
 % \subsection{Isogenies between super-singular elliptic curves}
 
 In \cite{SIDH?,SIDH16}, there is a Diffie-Helman like key exchange
 (SIDH) based on computing super-singular eliptic curve isogenies 
 which functions as a drop in replacement, or more likely addition,
 for Taler's refresh protocol.
 
 In SIDH, private keys are the kernel of an isogeny in the 2-torsion
 or the 3-torsion of the base curve.  Isogenies based on 2-torsion can
 only be paired with isogenies based on 3-torsion, and visa versa.  
 This rigidity makes constructing signature schemes with SIDH hard
 \cite{??SIDHsig??}, but does not impact our use case.  
 
 We let $\mu$ and $\Mu$ be the SIDH 2-torsion private and public keys,
 respectively.  We similarly let $\lambda$ and $\Lambda$ be the
 SIDH 3-torsion private and public keys.  
 
 We envision the 2-torsion secret key generation function $\CSK(s)$
 for $\mu$ being deterministic with seed $s$, but the 3-torsion secret
 key generation function $\LSK()$ ignores the arguments given above 
 Our 2-torsion and 3-torsion public key derivation functions
 $\CPK(\mu)$ and $\LPK(\lambda)$ along with our two key derivation
 functions $\KEX_2$ and $\KEX_3$, all work as described in
 \cite[\S6]{SIDH16}.
 % We refer to \cite[??]{SIDH?15?} and \cite[]{SIDH?11?} for further background.
 
 If using SIDH, then we naturally depend upon the security assumption
 used in SIDH, but combining this with ECDH is stronger than either
 alone.  
 
 ... proof ...
 
 At least, there is no relationship between $\mu$ and $\lambda$ in
 SIDH though, so $\Lambda$ cannot itself leak any information about
 $(C,\Mu,S)$.  
 
 % \smallskip
 
 We note that $\Lambda$ contains two points used by $\KEX_3$ to
 evaluate its secret isogeny but not used by $\KEX_2$.  We do not
 consider this a weakness for taxability because the cut and choose
 protocol already requires that the exchange verify the public
 key $\Lambda_j$ for $j \neq \gamma$. 
 
 \smallskip
 % \subsection{Ring Learning with Errors}
 
 In \cite{Peikert14,NewHope}, there is another key exchange based on
 a variant of the Ring-LWE problem.  Ring-LWE key exchange has a
 worrying relationship with this hidden subgroup problem on dihedral
 groups \cite{??,??}, but also a reasuring relationship with NP-hard
 problems.
 
 We again let $\mu$ and $\Mu$ denote the Alice (initator) side the
 private and public keys, respectively.  We likewise let $\lambda$
 and $\Lambda$ be the Bob (respondent) private and public keys. 
 % DO IT?
 Again now, $\CPK$, $\CSK$, $\LPK$, $\LSK$, $\KEX_2$ and $\KEX_3$
 can be defined from \cite{Peikert14,NewHope}.  
 
 A priori, one worried that unlinkability might fail even without
 the Ring-LWE key exchange itself being broken because $\lambda_j$
 and $\Lambda_j$ are constructed using the public key $\Mu$. 
 
 First, the polynomial $a$ commonly depends upon $\Mu$, like in
 \cite{NewHope}, so unlinkability explicitly depends upon the Ring-LWE
 problem\cite{}.  [[ PROOF ??? ]]
 
 Second, the reconciliation information in $\Lambda$ might leak
 additional information about $\lambda$.  
 [[ LITERATURE ADDRESSES THIS POINT ??? ]]
 
 Ring-LWE key exchanges require that both Alice and Bob's keys be
 ephemeral because the success or failure of the key exchange
 leaks one bit about both keys\cite{}.  As a result, authentication
 with Ring-LWE based schemes remains harder than with discrete log
 schemes\cite{??RLWEsig??}, and this situation impacts us as well.
 
 A Taler wallet should control both sides during the refresh protocol,
  which produces an interesting connundrum.
 An honest wallet could ensure that the key exchange always succeeds.
 If wallets were honest, then one could tune the Ring-LWE parameters
 to leave the probability of failure rather high,
  saving the exchange bandwidth, storage, and verification time.
 A dishonest wallet and merchant could conversely search the key space
 to find an exchange that fails, meaning the wallet could aid the
 merchant in tax evasion. 
 
 [[ IS THE FOLLOWING IMPOSSIBLE ??? ]]
 
 If possible, we should  tune the Ring-LWE parameters to reduce costs
 to the exchange, and boost the unlinkability for the users, while 
 simultaniously
 
 % \smallskip
 % \subsection{Comparson}
 
 At present, the SIDH implementation in \cite{SIDH16} requires about
 one third the key material and 100?? times as much CPU time as the
 Ring-LWE implementation in \cite{NewHope}.
 [[ We believe this provides a strong reason to continue exploring 
 parameter choices for Ring-LWE key exchange along with protocol tweaks.  
 ... ]]
 
 
 \section{Hashed-based one-sided public keys}
 
 We now define our hash-based encryption scheme.
 Let $\delta$ denote our query security parameter and
  let $\mu$ be a bit string.
 For $j \le \kappa$, we define a Merkle tree $T_j$ of height $\delta$
 with leaves $\eta_j = H(\mu || "YeyCoins!" || t || j)$
  for some leaf index $t \le 2^\delta$. 
 Let $t_j$ denote the root of $T_j$.
 Set $\Mu = H(t_1 || \cdots || t_\kappa)$,
  which defines $\CPK(\mu)$.
 
 Now let $\lambda_j = \LSK((t,j),\mu)$ consist of
 $(t,j,\eta_j)$ along with both
  the Merkle tree path that proves $\eta_j$ is a leaf of $T_j$,
 and $(t_1,\ldots,t_\kappa)$,
  making $\LSK$ an embelished Merkle tree path function.
 Also let $\Lambda_j = \LPK(\lambda_j)$ be $(t,j)$
 
 We define $\KEX_2(\lambda_j,\Mu)$ to be $\eta_j$
  if $\lambda_j$ proves that $\eta_j$ is the $t$ leaf for $\Mu$,
 or empty otherwise.
 $\KEX_3(\Lambda_j,\mu)$ simply recomputes $\eta_j$ as above.
 If $\KEX_2$ works then so does $\KEX_3$.
 
 As $\Lambda_j = (t,j)$, it matters that $\lambda_j$ actually
 demonstrates the position $t$ in the Merkle tree.
 
 ... proofs ...
 
 \smallskip
 
 We observe that $\CPK$ has running time $O(2^\delta)$, severely
 limiting $\delta$.  We lack the time-space trade offs resolve
 this issue for hash-based signature (see \cite{SPHINCS}).
 
 Imagine that $\delta = 0$ so that $T_j = H(\eta_j)$.
 In this scenario, a hostile exchange could request two different
 $\gamma$ to learn all $\eta_j$, if the wallet reruns its second
 phase.  In principle, the wallet saves the exchange's signed 
 choice of $\gamma$ before revealing $\eta_j$ for $j \neq \gamma$.
 It follows that even $\delta = 0$ does technically provides
 post-quantum anonymity,
 
 We must worry about attacks that rewind the wallet from phase 2 to
 phase 1, or even parallelism bugs where the wallet answer concurrent
 requests.  We cannot remove the curve25519 exchange $l_j C$ from the
 refresh protocol becausenn such attacks would represent serious risks
 without it.  With our $l_j C$ component, there is little reason for
 an attacker to pursue $\eta_j$ alone unless they expect to break
 curve25519 in the future, either through mathematical advances or
 by building a quantum computer.  
 
 We therefore view $\delta$ as a query complexity parameter whose 
 optimial setting depends upo nthe strength of the overall protocol. 
 
 \smallskip
 
 We can magnify the effective $\delta$ by using multiple $\eta_j$.
 
 ... analysis ...
 % multiple withdrawals
 
 We believe this provides sufficient post-quantum security for
 refreshing change.  
 
 
 \section{Hash and Ring-LWE hybrid}
 
 We noted in \S\ref{subsec:withdrawal} above that exchange might
 require that initial withdrawals employs a refresh-like operation.
 In this scenario, we refresh from a pseudo-coin $(C,\Mu)$ where
  $C$ is the user's reserve key \cite[??]{Taler} and
  $\Mu$ s a post-quantum public key kept with $C$.
 As a result, our hash-based scheme should increase the security
 parameter $\delta$ to allow a query for every  withdrawal operation.
 
 Instead, ...
 [[ ??? we propose using a Merkle tree of Alice side Ring-LWE keys,
 while continuing to invent the Bob side Ring-LWE key. ??? ]]
 
 % Use birthday about on Alice vs Bob keys?
 
 \section{Conclusions}
 
 ...
 
 
 \bibliographystyle{alpha}
 \bibliography{taler,rfc}
 
 % \newpage
 % \appendix
 
 % \section{}
 
 
 
 \end{document}
 
 \begin{itemize}
 \item 
 \item 
 \end{itemize}
 
 \begin{itemize}
 \item 
 \item 
 \end{itemize}
 
 
 
 
 
 Crazy pants ideas : 
 
 Use a larger Mrkle tree with start points seeded throughout 
 
 Use a Merkle tree of SWIFFT hash functions because
  their additive homomorphic property lets you keep the form of a polynomial