Instantiation section

1 files changed, 51 insertions, 37 deletions

diff --git a/games/games.tex b/games/games.tex
index 31556c6..abf57f9 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -169,7 +169,7 @@ protocol.
 
     % pkDenom needs to appear in ExchangeKeygen
 
-  \item \algo{Spend}(contract, \V{f}, \V{pkUser}, \V{skCoin}, pkReceiver):
+  \item \algo{Spend}(contract, \V{f}, \V{pkUser}, \V{skCoin}, \V{pkReceiver}):
     Algorithm to produce and sign a deposit permission \V{depositPermission}
     for a particular contract.  The fraction $0 < \V{f} \le 1$ determines the
     fraction of the coin's value that will be spent.
@@ -185,7 +185,7 @@ protocol.
     On success, we mark $\V{pkCoin}$ spent in $\V{deposited}[\V{pkCoin}]$ and
     return the exchange's signature over the request.
 
-  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{skCoin})):
+  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{skCoin}, \V{pkDenom})):
     Interactive protocol between exchange and user.
 
     If $\V{pkCoin}$ (derived from \V{skCoin}) is being overspent, then
@@ -364,14 +364,14 @@ Let \oraSet{Anon} stand for access to the oracles
   \item $(\V{pkU}_0, \V{pkU}_1, \V{contract}_0, \V{contract}_1) \leftarrow {\prt{A}}^{\oraSet{Anon}}()$ \\
     The adversary creates two users and selects two contract identifiers.
   \item Return 0 if $\V{pkU}_0$ or $\V{pkU}_1$ are not uncorrupted registered users.
-  \item Select distinct fresh coins $\V{pkC}_0$ and $\V{pkC}_1$
+  \item Select distinct fresh coins $\V{pkCoin}_0$ and $\V{pkCoin}_1$
     from the wallets of $\V{pkU}_0$ and $\V{pkU}_1$ respectively.%
     \footnote{In principle, we might anonymously refresh coins before
     or concurrently with spending them, but if our adversary directs a
     non-anonymous refresh then they can mark coins with it}
     Return 0 if either $\V{pkU}_0$ or $\V{pkU}_1$ has insufficient unspent unrefreshed coins.
-  \item $\V{dp_0} \leftarrow \algo{Spend}(\V{contract}_0, \V{pkU}_b, \V{pkC}_b, \V{pkM})$, \\
-      $\V{dp_1} \leftarrow \algo{Spend}(\V{contract}_1, \V{pkU}_{1-b}, \V{pkC}_{1-b}, \V{pkM})$ \\
+  \item $\V{dp_0} \leftarrow \algo{Spend}(\V{contract}_0, \V{pkU}_b, \V{pkCoin}_b, \V{pkM})$, \\
+      $\V{dp_1} \leftarrow \algo{Spend}(\V{contract}_1, \V{pkU}_{1-b}, \V{pkCoin}_{1-b}, \V{pkM})$ \\
       Spend these two coins without revealing the mapping between users and coins.
   \item $r_0 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_0))$, \\
     $r_1 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_1))$ \\
@@ -607,50 +607,64 @@ but the condition restricts it to games in which $p \over b + p$ is defined.
   Christian agrees with Jeff on using an abstract key exchange.
 \end{mdframed}
 
-Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coordinates).  
+Let $G \in \mathbb{E}$ be the generator of an Edwards curve in which the DDH problem yields $\lambda$ bits of security, like Ed25519 if $\lambda = 128$.
 
 \begin{itemize}
-  \item \algo{ExchangeKeygen}():  Generate an RSA key pair of length $\lambda$ and return it.
-  \item \algo{UserKeygen}():  Generate an EdDSA key pair and return it.
-  \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU})):
+  \item \algo{ExchangeKeygen}():  Generate and return denomination RSA key pair of a length that yields $\lambda$ bits of security, as well as the exchange signing key.
+  \item \algo{UserKeygen}():  Generate and return merchant EdDSA key pair, which doubles as a reserve key for our purposes.
+  \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{pkDenom})):
     \begin{enumerate}
-      \item \prt{U} selects blinding factor $r \randsel \Z_N^*$, coin secret $\V{skC} \randsel \Z_{|\mathbb{E}|}$, computes
-        $\V{pkC} = \V{skC} \cdot G$, $\overline{M} = r \cdot H(\V{pkC})$ and sends $\overline{M}$ to $\prt{E}$.
+      \item \prt{U} selects blinding factor $r \randsel \Z_N^*$, coin secret $\V{skCoin} \randsel \Z_{|\mathbb{E}|}$, computes
+        $\V{pkCoin} = \V{skCoin} \cdot G$, $\overline{M} = r \cdot \textrm{FDH}_{\V{pkDenom}}(\V{pkCoin})$ and sends $\overline{M}$ to $\prt{E}$.
       \item \prt{E} receives $\overline{M}$ and sends back $\overline{M}^d \bmod N$ to \prt{U}.
     \end{enumerate}
 
     Thus the protocol transcript is $(\overline {M}, \overline{M}^d \bmod N)$.
-  \item \algo{Spend}(contract, skCoin, pkReceiver):  TODO
-
-    The deposit permission is computed as
+  \item \algo{Spend}(contract, \V{f}, \V{pkUser}, \V{skCoin}, \V{pkReceiver}):
+  
+    The deposit permission is computed as $(\V{sig}, \V{pkCoin})$ where $\V{pkCoin} = \V{skCoin} \cdot G$ and
     \begin{equation*}
-      (\V{sig}, \V{pkCoin}) = (\algo{Sign}(skCoin, (contract, pkReceiver)), \V{skCoin} \cdot G)
+      \V{sig} = \algo{Sign}(skCoin, (contract, pkReceiver))
     \end{equation*}
 
   \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
-    Exchange checks signatures, adds contribution $f$ of each coin to database of spent coins.
-  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{\overrightarrow{skCoinList}})):
-    The protocol transcript is 
-    \begin{equation*}
-      (\V{pkCoin}, sig, T_1, \dots, T_\kappa, \overline{M}_1, \dots, \overline{M}_\kappa, \gamma, \tilde{t}_1, \dots, \tilde{t}_\kappa, \tilde{n}_1, \dots, \tilde{n}_i \overline{M}_\gamma)
-    \end{equation*}
+   
+    Exchange checks signatures, records contribution $f$ of each coin to database of spent coins.
+
+  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{skCoin}, \V{pkDenom})):
 
-    with
+	First the user samples a verification nonce $\V{nonce} \randsel U$ and, for each $i<\kappa$, computes the $i$th commitment data:
+    \begin{itemize}
+	\item Transfer private key $t_i \randsel U$
+	\item Transfer public key $T_i = t_i \cdot G$A
+	\item $\V{linkSecret}_i = H(\V{nonce} \mathbin{\|} \V{skCoin} \mathbin{\|} i)$
+	\item Transfer secret $s_i = ECDH(t_i, pkCoin) \mathbin{\|} \V{linkSecret}_i$
+	\item Blinding factor $r_i = \textrm{FD-PRF}_{pkDenom}(s_i)$
+	\item Coin private key $m_i = \textrm{PRF}_{\V{pkCoin}}(s_i)$
+	\item Coin public key $M_i = m_i \cdot G$
+	\item Planchet $\overline{M}_i = r_i^e \cdot \textrm{FDH}_{\V{pkDenom}}(M_i) \bmod \V{pkDenom}$
+	\end{itemize}
+	The user aggregates this commitment data
     \begin{itemize}
-      \item Refresh confirmation signature $sig = Sign(skCoin, "refresh", \V{pkCoin})$
-      \item Verification nonce $n_i \randsel U$
-      \item Transfer private key $t_i \randsel U$
-      \item Transfer public key $T_i = t_i \cdot G$A
-      \item Transfer secret $s_i = ECDH(t_i, pkCoin)$
-      \item Blinding factor $r_i = PRF_{pkCoin}(s_i)$
-      \item Coin private key $m_i = PRF_{pkCoin+1}(s_i \mathbin{\|} n_i)$
-      \item Coin public key $M_i = m_i \cdot G$
-      \item Planchet $\overline{M}_i = (r_i \cdot M_i)^d \bmod N$
-      \item (tide denotes item at index $\gamma$ set to zero)
-    \end{itemize}
-  \item \algo{Link}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{linkSecret}, \V{skCoin})):
-    The user obtains the protocol transcript for the Refresh with coin public key derived from \V{skCoin}.
-    The refresh protocol is then used to withdraw the planchet $\overline{M}_\kappa$.
+	\item $h_M = H(\overline{M}_1, \dots, \overline{M}_\kappa)$,
+	\item $h_T = H(T_1, \dots, T_\kappa)$,
+	\end{itemize}
+	and send the commitment $(\pi_1, \V{sig})$ where $\pi_1 = (\V{pkCoin}, \V{nonce}, h_T, h_M)$ and $\V{sig} = Sign_{\V{skCoin}}(\pi_1)$.
+	
+	Second, the exchange chooses a $0 \le \gamma < \kappa$ and signs this choice along with ???
+
+	Third, the user reveals $T_\gamma$ and $\overline{M}_\gamma$ along with 
+	$$ t_1, \dots, t_{\gamma-1}, t_{\gamma+1}, \dots, t_\kappa \quad\textrm{and}\quad
+	     \V{linkSecret}_1, \dots, \V{linkSecret}_{\gamma-1}, \V{linkSecret}_{\gamma+1}, \dots, \V{linkSecret}_i \mathcomma $$
+	 again signing this message with $\V{skCoin}$.
+
+    Finally the exchange returns the signed planchet $\overline{M}_\gamma^d \bmod \V{pkDenom}$, which the user unblinds and verifies.
+
+  \item \algo{Link}(\prt{E}(\V{skE}), \prt{U}(\V{skU}, \V{pkE}, \V{skCoin})):
+  
+    For each completed refresh of $\V{skCoin}$:
+    The user obtains the verification nonce $\V{nonce}$, the new denomination $\V{pkDenom}$, the transfer public key $T_\gamma$, and the signed planchet $\overline{M}_\gamma^d \bmod \V{pkDenom}$ from the protocol transcript for the Refresh with coin public key derived from \V{skCoin}.  The user computes the $\V{linkSecret}_\gamma$ using $\V{nonce}$, computes both the blinding factor $r_i$ and the coin private key $m_i$ using $T_\gamma$, unblinds the signed planchet and verifies the result is the RSA signature for the new coin.
+
 \end{itemize}
 
 \section{Proofs}
@@ -689,7 +703,7 @@ then Taler satisfies {anonymity}.
   must fake a link secret that causes the oracle to return random data leading
   to incorrect behavior by the customer.  We recall however that link secrets
   were constructed as $(\V{nonce}, \V{linkSecret})$ where
-    $\V{linkSecret} = H(\V{nonce}, \V{skOldCoin})$,
+    $\V{linkSecret} = H(\V{nonce} \mathbin{\|} \V{skOldCoin})$,
   with the customer rejecting link secrets that fail this test.
   So our adversary must either find a hash collision or find the coin's private key.