Much expanded. And now compiles.

1 files changed, 168 insertions, 180 deletions

diff --git a/doc/paper/postquantum_melt.tex b/doc/paper/postquantum_melt.tex
index 2740fd37a..5d93e58e0 100644
--- a/doc/paper/postquantum_melt.tex
+++ b/doc/paper/postquantum_melt.tex
@@ -135,34 +135,18 @@ 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 retain their post-quantum security.
-
-Second, we propose a hash based scheme that 
-
-Merkle tree based scheme that provides a
- query complexity bound suitable for current deployments, and
- depends only upon the strength of the hash function used.
-
-
-
-
-much smaller 
-
-
-
-but these all
-incur significantly larger key sizes, requiring more badwidth and
-storage space for the exchange, and take longer to run.
-In addition, the established post-quantum key exchanges based on
-Ring-LWE, like New Hope \cite{}, require that both keys be
-ephemeral.  
-Super-singular isogenies \cite{,} would work ``out of the box'',
-if it were already packeged in said box.
-
-Instead, we observe that 
-
+scheme remains secure; however, these schemes youth leaves them
+relatively untested.
 
+Second, we propose a hash based scheme whose anonymity garentee needs
+only the one-way assumption on our hash function.  In this scheme,
+the vible security paramater 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 in
+parallel with the 
+As is the practice with hash based signature schemes 
 
 
 
@@ -192,20 +176,39 @@ proofs they employ.
 
 \section{Taler's refresh protocol}
 
-We first describe Taler's refresh protocol adding 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 symetric key resulting from the key exchange
-between them.  
+\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.
 
-We require there be effeciently computable
+\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 symetric key resulting from the key exchange between them.
+
+We need effeciently 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)$ and $\Lambda = \LPK(t,\mu)$
-       for a random bitstring $t$, and
+\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
@@ -217,10 +220,6 @@ to Taler's existing refresh protocol.
 
 \smallskip
 
-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.
-
 A coin $(C,\Mu,S)$ consists of 
   a Ed25519 public key $C = c G$,
   a post-quantum public key $\Mu$, and
@@ -235,16 +234,16 @@ 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(\textr{"Ed25519"} || s)
+$$ c = H(\textrm{"Ed25519"} || s)
 \qquad \mu = \CSK(s)
-\qquad b = H(\textr{"Blind"} || 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 sitaution, our coin $(C,M,S)$ was partially spent and 
+In the change sitaution, 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$.
@@ -255,8 +254,8 @@ we let $x_{j,i}$ denote the value normally denoted $x$ of
 % 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.
-So as above $c'$, $\mu'$, and $b_j$ are derived from $s_j$,
+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.}
@@ -265,10 +264,10 @@ So as above $c'$, $\mu'$, and $b_j$ are derived from $s_j$,
    \begin{itemize}
    \item  Create random $\zeta_j$ and $l_j$.
    \item  Also compute $L_j = l_j G$.
-   \item  Generate $\lambda_j$, $\Lambda_j$, and
-            $\eta_j = \KEX_2(\lambda,\Mu)$ as appropriate
-            using $\mu$. % or possibly $\Mu$.
-   \item  Set the linking commitment $\Gamma_{j,0} = (L_j,\Lambda_j)$. 
+   \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$:
@@ -277,8 +276,8 @@ So as above $c'$, $\mu'$, and $b_j$ are derived from $s_j$,
       \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 $\Eta_{j,i} = E_{k_j}(s')$. 
-      \item  Set the coin commitments $\Gamma_{j,i} = (\Eta_{j,i},B_{j,i})$
+      \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}
@@ -314,11 +313,11 @@ So as above $c'$, $\mu'$, and $b_j$ are derived from $s_j$,
 \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(???)$
+   \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}(\Eta_{j,i})$.
+     \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')$.
@@ -333,13 +332,29 @@ replacing $\Gamma_*$ with both $\Gamma_{\gamma,0}$ and
 It's clear this requires the wallet send that signature in some phase,
 but also the wallet must accept a phase 2 responce 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)$ consisting of
+ the user's reserve key \cite[??]{Taler} and
+ a post-quantum public key $\Mu$.
+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}
 
-In \cite{SIDH}, 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 \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
@@ -348,11 +363,22 @@ This rigidity makes constructing signature schemes with SIDH hard
 \cite{}, but does not impact our use case.  
 
 We let $\mu$ and $\Mu$ be the SIDH 2-torsion private and public keys,
-repectively.  We simlarly let $\lambda_j$ and $\Lambda_j$ be the
+repectively.  We simlarly let $\lambda$ and $\Lambda$ be the
 SIDH 3-torsion private and public keys.  
-% DO IT :
-We define $\CPK$, $\CSK$, $\LPK$, $\LSK$, $\KEX_2$ and $\KEX_3$
- as appropriate from \cite{SIDH} too.  
+
+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[\S6]{SIDH16}, \cite[??]{SIDH?15?}, and
+% \cite[]{SIDH?11?} for further discussion of the implementation.
+
+There is no relationship between $\mu$ and $\lambda$ in SIDH, so
+$\Lambda$ cannot itself leak any information about $C$.
 
 \smallskip
 
@@ -360,21 +386,34 @@ Ring-LWE based key exchanges like \cite{Peikert14,NewHope} 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
-problematic\cite{}.
+harder than with discrete log schemes\cite{}.
 
 We observe however that the Taler wallet controls both sides during 
 the refresh protocol, so the wallet can ensure that the key exchange 
 always succeeds.  In fact, the Ring-LWE paramaters could be tunned to
-make the probability of failure arbitrarily high, saving the exchange
-bandwidth, storage, and verification time.
-
+leave the probability of failure rather high, saving the exchange
+bandwidth, storage, and verification time.  
 
 We let $\mu$ and $\Mu$ be Alice (initator) side the private and public
 keys, repectively.  We simlarly let $\lambda_j$ and $\Lambda_j$ 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}.  % DO IT
+can be defined from \cite{Peikert14,NewHope}.  
+
+\smallskip
+
+At present, the SIDH implemention in \cite{SIDH16} requires about
+one third the key material and 100?? times as much CPU time as the
+Ring-LWE implemention in \cite{NewHope}.
+As noted above, Ring-LWE admits significant optimizations for the
+Taler refresh situation.
+
+We observe however that the Ring-LWE public key $\Lambda$ has a risk
+of leaking information about $\Mu$.  In particular, if polynomial $a$
+depends upon $\Mu$, like in \cite{NewHope}, then anonymity explicity
+depends upon the Ring-LWE problem\cite{}.  
+...
 
 
 \section{Hashed-based one-sided public keys}
@@ -383,50 +422,76 @@ We now define our hash-based encryption scheme.
 Let $\delta$ denote our query security paramater 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,t} = H(\mu || "YeyCoins!" || t || j)$
- for $t \le 2^\delta$.
-Let $\Lambda_j$ denote the root of $T_j$, making
- $\LPK(j,\mu)$ the Merkle tree root function.
-Set $\Mu = H(\Lambda_1 || \cdots || \Lambda_\kappa)$,
+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,t}$ consist of $(j,t,\eta_{j,t})$ along with
-both the Merkle tree path that proves $\eta_{j,i}$ is a leaf of $T_j$,
-and $(\Lambda_1,\ldots,\Lambda_\kappa)$,
- making $\LSK(t,\mu)$ an embelished Merkle tree path function.
+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,t},\Mu) = \eta_{j,t}$
- if $\lambda_{j,t}$ proves that $\eta_{j,t}$ is a leaf for $\Mu$,
+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.
 
-$\Mu = H(\Lambda_1 || \cdots || \Lambda_\kappa)$
+... proofs ...
 
-$\KEX_3(\Lambda,\mu)$
+\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 paramater whose 
+optimial setting depends upo nthe strength of the overall protocoll. 
 
+\smallskip
 
-$H(\eta_{j,i})$ along with a path 
+We can magnify the effective $\delta$ by using multiple $\eta_j$.
 
-$\eta$, $\lambda$, $\Lambda$, $\mu$, and $\Mu$ for key material 
+... analysis ...
+% multiple withdrawals
 
+We believe this provides sufficent post-quantum security for
+refreshing change.  
 
-We require there be effeciently computable
-  $\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)$ and $\Lambda = \LPK(t,\mu)$
-       for a random bitstring $t$, 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.
 
-\begin{itemize}
-\item 
-\item 
-\end{itemize}
+\section{Hash and Ring-LWE hybrid}
+
+We noted above in \S\ref{subsec:withdrawal} that exchange might
+require a refresh-like operation when coins are initially withdrawn.
+
+...
+% Use birthday about on Alice vs Bob keys
+
+\section{Conclusions}
 
 
 \bibliographystyle{alpha}
@@ -441,99 +506,22 @@ In particular, if $\KEX_3(\Lambda,\mu)$ would fail
 
 \end{document}
 
+\begin{itemize}
+\item 
+\item 
+\end{itemize}
 
 
 
 
 
 
-Let $\kappa$ and $\theta$ denote
- the exchange's security parameter and
- the maximum number of coins returned by a refresh, respectively. 
-
-We define a Merkle tree/sequence function 
-  $\mlink(m,i,j) = H(m || "YeyCoins!" || i || j)$ 
-        Actual linking key for jth cut of ith target coin
-  $\mhide(m,i,j) = H( \mlink(m,i,j) )$
-        Linking key hidden for Merkle
-  $\mcoin(m,i) = H( \mhide(m,i,1) || \ldots || \mhide(m,i,\kappa) )$
-        Merkle root for refresh into the ith coin
-  $\mroot(m) = M( \m_coin(m,1), \ldots, \mcoin(m,\theta) )$
-        Merkle root for refresh of the entire coin
-  $mpath(m,i)$ is the nodes adjacent to Merkle path to $\mcoin(m,i)$
-If $\theta$ is small then $M(x[1],\ldots,x[\theta])$ could be simply be
-the concatenate and hash function $H( x[1] || ... || x[\theta] )$ like
-in $\mcoin$, giving $O(n)$ time.  If $\theta$ is large, then $M$ should
-be a hash tree to give $O(\log n)$ time.  We could use $M$ in $\mcoin$
-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 = \mroot(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's signature $S$.
-In addition, there was a value $s$ such that 
-  $c = H(\textr{"Ed25519"} || s)$,
-  $m = H(\textr{"Merkle"} || s)$, and
-  $b = H(\textr{"Blind"} || s)$,
-but we try not to retain $s$ if possible.
-
-
-
-We have a tainted coin $(C,M,S)$ that we wish to
- refresh into $n \le \theta$ untained coins.  
-For simplicity, we allow $x'$ to stand for the component
- normally denoted $x$ of the $i$th new coin being created.  
-So $C' = c' G$, $M' = \mroot(m')$, and $b'$ must be derived from $s'$.
-For $j=1\cdots\kappa$,
- we allow $x^j$ to denote the $j$th cut of the $i$th coin.  
-So again
- $C^j = c^j G$, $M^j = \mroot(m^j)$, and $b^j$ must be derived from $s^j$.
-
-Wallet phase 1.
-  For $j=1 \cdots \kappa$:
-    Create random $s^j$ and $l^j$.
-    Compute $c^j$, $m^j$, and $b^j$ from $s^j$ as above.
-    Compute $C^j = c^j G$ and $L^j = l^j G$ too.
-    Compute $B^j = B_{b^j}(C^j || \mroot(m^j))$.
-    Set $k = H(\mlink(m,i,j) || l^j C)$
-    Encrypt $E^j = E_k(s^j,l^j)$.
-  Send commitment $S' = S_C( (L^j,E^1,B^1), \ldots, (E^\kappa,B^\kappa) )$
-%  Note : If $\mlink$ were a stream cypher then $E()$ could just be xor.
-
-Exchange phase 1.
-  Pick random $\gamma \in \{1 \cdots \kappa\}$.
-  Mark $C$ as spent by saving $(C,gamma,S')$.
-  Send gamma and $S(C,gamma,...)$
-
-Wallet phase 2.
-  Save ...
-  Set $\Beta_gamma = \mhide(m,i,gamma) = H( \mlink(m,i,gamma) )$ and
-      $\beta_i = \mlink(m,i,j)$ for $j=1\cdots\kappa$ not $\gamma$
-  Prepare a responce tuple $R^j$ consisting of 
-    $Beta_gamma$,  $(beta_j,l^j)$ for $j=1\cdots\kappa$ not $\gamma$,  
-    and  $\mpath(m,i)$, including $\mcoin(m,i)$,
-  Send $S_C(R^j)$.
-
-Exchange phase 2.
-  Set $Beta_j = H(beta_j)$ for $j=1\ldots\kappa$ except $\gamma$,
-    keep $Beta_gamma$ untouched.
-  Verify $M$ with $\mpath(m,i)$ including $\mcoin(m,i)$.
-  Verify $\mcoin(m,i) = H( Beta_1 || .. || Beta_kappa )$.
-  For $j=1 \cdots \kappa$ except $\gamma$:
-    Decrypt $s^j$ from $E^i$ using $k = H(beta_j || l^j C)$
-    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 || \mroot(m^j))$.
-  If verifications pass then send $S_{d_i}(B^\gamma)$.
-
-
-\section{Withdrawal}
-
+Crazy pants ideas : 
 
+Use a larger Mrkle tree with start points seeded throughout 
 
+Use a Merkle tree of SWIFFT hash functions becuase
+ their additive homomorphic property lets you keep the form of a polynomial