Merge branch 'master' of ssh://taler.net/papers

1 files changed, 44 insertions, 35 deletions

diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex
index c415ec3..134d03f 100644
--- a/taler-fc19/paper.tex
+++ b/taler-fc19/paper.tex
@@ -818,7 +818,7 @@ Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange:
 

 We occasionally need these key generation algorithms separately, but

 we usually combine them into $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$. 

-%TODO: Eliminate this by fixing evrything below

+%TODO: Eliminate this by fixing evrything below.  Search for KeyGen.*CSK

 

 We require the following security properties to hold for $\textsc{CoinSignKx}$:

 \begin{itemize}

@@ -842,6 +842,7 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$:
   \item \emph{key exchange security}:  The output of $\algo{Kx}_{CSK}$ must be computationally

     indistinguishable from a random shared secret of the same length, for inputs that have been

     generated with $\algo{KeyGen}$.

+	%TODO: Isn't this just a PRF assumption???

 \end{itemize}

 

 We combine honest key generation and key exchange robustness in \emph{key exchange completeness} below.

@@ -934,13 +935,8 @@ Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instanti
     \begin{equation}

       \V{rid} := (\V{coin}_0, \V{pkD}_u, \V{nonce}, \{ s_i \}, \{ \overline{m}_i \}, \{r_i\}, \{\mathcal{T}_{(B*,i)}\} ).

     \end{equation}

-  % TODO: Move commitment into request refresh to handle aborts properly.

-

-  \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid}) \rightarrow \mathcal{T}$:

-    The customer looks up the refresh identifier $\V{rid}$ and recomputes the transfer key pairs,

-    transfer secrets and new coin key pairs.

 

-    Then customer sends the commitment $\pi_1 = (\V{pkCoin}_0, \V{pkD}_u, h_C)$ together with signature $\V{sig}_1

+    Now, the customer's wallet sends the commitment $\pi_1 = (\V{pkCoin}_0, \V{pkD}_u, h_C)$ together with signature $\V{sig}_1

     \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, \pi_1)$ to the exchange, where

     \begin{align*}

       h_T &:= H(T_1, \dots, T_\kappa)\\

@@ -959,7 +955,9 @@ Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instanti
         equivalent $\pi_1$.

     \end{enumerate}

 

-    In response, the customer sends the reveal message

+  \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid}) \rightarrow \mathcal{T}$:

+    The customer's wallet looks up the refresh identifier $\V{rid}$ and recomputes the transfer key pairs,

+    transfer secrets and new coin key pairs.  The customer sends the reveal message

     \begin{equation*}

       \pi_3 = T_\gamma, \overline{m}_\gamma,

       (s_1, \dots, s_{\gamma-1}, s_{\gamma+1}, \dots, s_\kappa)

@@ -969,7 +967,6 @@ Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instanti
       \V{sig}_{3'} \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, (\V{pkCoin}_0,

       \V{pkD}_u, \mathcal{T}_{(B*,\gamma)}, T_\gamma, \overline{m}_\gamma))

     \end{equation*} to the exchange.

-

     

     The exchange checks the signature $\V{sig}_{3'}$ and then computes for $i \ne \gamma$:

     \begin{align*}

@@ -1086,6 +1083,7 @@ with the generic instantiation.
 \begin{theorem}

   In the random oracle model, our instantiation satisfies anonymity.

 \end{theorem}

+% TODO: PRF suffices

 

 \begin{proof}

   We give a proof via a sequence of games $\mathbb{G}_0(b), \mathbb{G}_1(b),

@@ -1167,6 +1165,7 @@ with the generic instantiation.
   \V{pkCoin}_\gamma)$ and the execution of the blinding protocol is equivalent

   under the randeom oracle to using the non-determinized algorithms

   $\algo{KeyGen}_{CSK}$ and $\algo{Blind}_{BS}$.

+  % TODO: PRF suffices

 

   By the blindness of the $\textsc{BlindSign}$ scheme, the adversary is not

   able to distinguish blinded values from randomness.  Thus, the adversary is

@@ -1178,6 +1177,7 @@ with the generic instantiation.
   \kappa, b)$ is at most $1/2 + \epsilon(\lambda)$, where $\epsilon$ is a

   negligible function.

 \end{proof}

+% RSA ratios vs CDH in BLS below

 

 \subsection{Conservation}

 

@@ -1226,17 +1226,18 @@ Our instantiation satisfies {unforgeability}.
 \end{theorem}

 

 \begin{proof}

-The adversary must have produced at least one coin that was not blindly signed

-by the exchange.  In order to carry out a reduction from this adversary to a

-blind signature forgery, we inject the challenger's public key into one

-randomly chosen denomination.  Since we do not have access to the

-corresponding secret key of the challenger, signing operations for this

-denomination are replaced with calls to the challenger's signing oracle in

-\ora{WithdrawPickup} and \ora{RefreshPickup}.  For $n$ denominations, an

-adversary against the unforgeability game would produce a blind signature

-forgery with probability $1/n$.

+The adversary must have produced at least one coin that was not blindly

+signed by the exchange.  %TODO: Way too fasty here, resurect the chain

+In order to carry out a reduction from this adversary to a blind signature

+forgery, we inject the challenger's public key into one randomly chosen

+denomination.  Since we do not have access to the corresponding secret key

+of the challenger, signing operations for this denomination are replaced

+with calls to the challenger's signing oracle in \ora{WithdrawPickup} and

+\ora{RefreshPickup}.  For $n$ denominations, an adversary against the

+unforgeability game would produce a blind signature forgery with probability $1/n$.

 \end{proof}

 

+%TODO: RSA-KTI

 

 \subsection{Income Transparency}

 \begin{theorem}

@@ -1265,6 +1266,8 @@ Our instantiation satisfies {weak income transparency}.
   in this graph, where each refresh $R_i \in F$ either results in a coin in

   exclusive control of the adversary after step \ref{game:income:spend}, or the

   refresh operation does not result in a coin at all.

+  %TODO: The preceeding paragraph is basically nonsense.  We need to resurect 

+  % correct construction of F from games.tex

 

   During each $R_i \in F$, the adversary  must have submitted a blinded coin

   and transfer public key for which the linking protocol fails to produce the

@@ -1281,6 +1284,7 @@ Our instantiation satisfies {weak income transparency}.
 

   The last case can be excluded, because it would violate the key exchange

   completeness assumption.

+  % TODO: Wrong

 

   We shall prove

   \begin{equation}\label{eq:income-transparency-proof}

@@ -1289,7 +1293,8 @@ Our instantiation satisfies {weak income transparency}.
   where the expectation runs over

   any probability space used by the adversary and challenger.

 

-  We shall optimiz our adversary in ways that maximize $p \over b + p$.

+  We shall optimize our adversary in ways that maximize $p \over b + p$. 

+  %TODO: Explain.   % We cannot actually produce this optimize adversary ourselves, but its existence suffices to prove the inequality, and restrict our analysis to them.  This is not a reduction

 

   As a reminder, if a refresh operation is initiated using a false commitment

   that is detected by the exchange, then the new coin cannot be obtained, and

@@ -1330,13 +1335,11 @@ Our instantiation satisfies {weak income transparency}.
     b_i &= (\kappa - 1)v

   \end{align*}

   and thus $\kappa p_i = b_i + p_i$.  Now

-  \begin{align*}

-    \Exp{p} &= {1\over|F|} \sum_{R_i \in F} p_i\\

-    \Exp{b} &= {1\over|F|} \sum_{R_i \in F} b_i,

-  \end{align*}

-  so

   \begin{equation*}

-    \Exp{{p \over b + p} \middle| F \neq \emptyset} = {1\over\kappa},

+    \Exp{{p \over b + p} \middle| F \neq \emptyset}

+	= |F| \sum_{R_i\in F} {p_i \over b_i + p_i} 

+    = |F| \sum_{R_i\in F} {p_i \ovver \kappa p_i}

+	= {1\over\kappa},

   \end{equation*}

   which yields the equality (\ref{eq:income-transparency-proof}).

 

@@ -1400,20 +1403,26 @@ As for $F = \emptyset$, the return value of the game must be $0$, we conclude
 We now give a concrete instantiation that is used in our implementation

 for the schemes \textsc{BlindSign}, \textsc{CoinSignKx} and \textsc{Sign}.

 

-For \textsc{BlindSign}, we use RSA blind signatures~\cite{chaum1983blind}.  From

-the information theoretically secure blinding, the computational blindness property

-follows directly.  For the unforgeability property, we additionally rely on

-the RSA-KTI assumption as discussed in \cite{bellare2003onemore}.  Note

-that since the blinding step in RSA blind signatures is non-interactive,

-storage and verification of the transcript is omitted in refresh and link.

+For \textsc{BlindSign}, we use RSA-FDH blind signatures~\cite{chaum1983blind}

+with blinding factors produced by FD-PRF constructed from a hash

+function with range the full RSA domain $[0,pq)$.  An adversary who

+defeats the blindness property can recognise blinding factors,

+violating this PRF assumption.  For the unforgeability property,

+we require the RSA-KTI assumption as discussed in \cite{bellare2003onemore}. 

+%TODO: Jeff always cited multoiiple papers for RSA-KTI, but forgets why.

+As the blinding step in RSA blind signatures is non-interactive, storage

+and verification of the transcript is omitted in refresh and link.

+We envision BLS blind signatures working equally well.

 

 We instantiate \textsc{CoinSignKx} with signatures and key exchange operations

 on elliptic curves in Edwards form, where the same key is used for signatures

 and the Diffie--Hellman key exchange operations.  In practice, we use Ed25519

-\cite{bernstein2012high} / Curve25519 \cite{bernstein2006curve25519} for

-$\lambda=256$.  We caution that some other elliptic curve key exchange

-implementation might not satisfy the completeness property that we require, due

-to the lack of complete addition laws.

+signatures \cite{bernstein2012high} and scalar multiplication for the Edwards

+curve, which gives $\lambda=128$.  % Curve25519 \cite{bernstein2006curve25519} 

+We caution that some other elliptic curve key exchange implementations might

+not satisfy the robustness property that we require, due to the lack of

+complete addition laws. 

+% and that both robustness and honest key generation become tricky when ..

 

 For \textsc{Sign}, we use elliptic-curve signatures, concretely Ed25519.