summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--taler-fc19/paper.tex88
1 files changed, 40 insertions, 48 deletions
diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex
index f9f40a5..1200ae7 100644
--- a/taler-fc19/paper.tex
+++ b/taler-fc19/paper.tex
@@ -741,7 +741,7 @@ deterrent, after all our purpose of the game is to characterize tax evasion.
We give an instantiation of our protocol syntax that is generic over
a blind signature scheme, a signature scheme, a combined signature scheme / key
-exchange, a commitment scheme and a pseudo-random function family (PRF).
+exchange, a collision-resistant hash function and a pseudo-random function family (PRF).
%\subsection{Generic Instantiation}
Let $\textsc{BlindSign}$ be a blind signature scheme with the following syntax, where the party $\mathcal{S}$
@@ -803,19 +803,16 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$:
\item \emph{unforgeability}: The signature scheme $(\algo{KeyGen}_{CSK}, \algo{Sign}_{CSK}, \algo{Verify}_{CSK})$
must satisfy existential unforgeability under chosen message attacks (EUF-CMA).
- \item \emph{honest key generation}:
- Any probabilistic polynomial-time adversary has only negligible chance
- to produce a public key $\V{pk}$ and a valid signature $\sigma$,
- i.e.\ $\algo{Verify}_{CSK}(\V{pk}, m, \sigma) = 1$, without also producing
- some secret key $\V{sk}$ such that $\V{pk} = \algo{KeyGenPub}_{CSK}(\V{sk})$.
-
\item \emph{key exchange completeness}:
- Any probabilistic polynomial-time adversary has only negligible chance to find
- $(\V{sk}_x, \V{pk}_x) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ for $x \in \{A,B\}$
- such that the key exchange fails:
+ Any probabilistic polynomial-time adversary has only negligible chance to find
+ a degenerate key pair $(\V{sk}_A, \V{sk}_B)$ such that for some
+ honestly generated key pair
+ $(\V{sk}_B, \V{pk}_B) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$
+ the key exchange fails, that is
\begin{equation*}
- \algo{Kex}_{CSK}(\V{sk}_A, \V{pk}_B) \neq \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A).
+ \algo{Kex}_{CSK}(\V{sk}_A, \V{pk}_B) \neq \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A),
\end{equation*}
+ but the adversary can still produce a pair $(m, \sigma)$ such that $\algo{Verify}_{BS}(\V{pk}_A, m, \sigma) = 1$.
\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
@@ -825,20 +822,15 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$:
Let $\textsc{Sign} = (\algo{KeyGen}_{S}, \algo{Sign}_{S}, \algo{Verify}_{S})$ be a signature
scheme that satisfies selective unforgeability under chosen message attacks (SUF-CMA).
-Let $(\algo{Setup}, H_{pck})$ be a computationally hiding and binding
-commitment scheme, where $\algo{Setup}$ generates the public commitment key
-$pk$ and $H_{pck} : \{0,1\}^* \rightarrow \{0,1\}^\lambda$ deterministically commits to a
-bit-string.
-
-Let $\V{PRF}$ be a pseudo-random function family.
+Let $\V{PRF}$ be a pseudo-random function family and $H : \{0,1\}^* \rightarrow \{0,1\}^\lambda$
+a collision-resistant hash function.
-Using these primitives, we now instantiate the syntax:
+Using these primitives, we now instantiate the syntax of our income-transparent e-cash scheme:
\begin{itemize}
\item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \mathfrak{D})$:
- Generate the exchange's signing key pair $\V{skESign} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$ and public
- commitment key $\V{pck} \leftarrow \algo{Setup}(1^\lambda)$.
+ Generate the exchange's signing key pair $\V{skESign} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$.
For each element in the sequence $\mathfrak{D} = d_1,\dots,d_n$, generate
denomination key pair $(\V{skD}_i, \V{pkD}_i) \leftarrow \algo{KeyGen}_{BS}(1^\lambda)$.
@@ -925,9 +917,9 @@ Using these primitives, we now instantiate the syntax:
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_{pck}(T_1, \dots, T_\kappa)\\
- h_{\overline{m}} &:= H_{pck}(\overline{m}_1, \dots, \overline{m}_\kappa)\\
- h_C &:= H_{pck}(h_T \Vert h_{\overline{m}})
+ h_T &:= H(T_1, \dots, T_\kappa)\\
+ h_{\overline{m}} &:= H(\overline{m}_1, \dots, \overline{m}_\kappa)\\
+ h_C &:= H(h_T \Vert h_{\overline{m}})
\end{align*}
The exchange checks the signature $\V{sig}_1$, and aborts if invalid. Otherwise,
@@ -960,7 +952,7 @@ Using these primitives, we now instantiate the syntax:
x_i' &\leftarrow \algo{Kx}(t_i, \V{pkCoin}_0)\\
(\V{skCoin}_i', \V{pkCoin}_i') &\leftarrow
\algo{KeyGen}^*_{CSK}(x_i', 1^\lambda) \\
- h_T' &:= H_{pck}(T'_1, \dots, T'_{\gamma-1}, T_\gamma, T_{\gamma+1}', \dots, T_\kappa')
+ h_T' &:= H(T'_1, \dots, T'_{\gamma-1}, T_\gamma, T_{\gamma+1}', \dots, T_\kappa')
\end{align*}
and simulates the blinding protocol with recorded transcripts (without signing each message,
as indicated by the dot ($\cdot$) instead of a signing secret key), obtaining
@@ -970,8 +962,8 @@ Using these primitives, we now instantiate the syntax:
\end{align*}
and finally
\begin{align*}
- h_{\overline{m}}' &:= H_{pck}(\overline{m}_1', \dots, \overline{m}_{\gamma-1}', \overline{m}_\gamma, \overline{m}_{\gamma+1}',\dots, \overline{m}_\kappa')\\
- h_C' &:= H_{pck}(h_T' \Vert h_{\overline{m}}').
+ h_{\overline{m}}' &:= H(\overline{m}_1', \dots, \overline{m}_{\gamma-1}', \overline{m}_\gamma, \overline{m}_{\gamma+1}',\dots, \overline{m}_\kappa')\\
+ h_C' &:= H(h_T' \Vert h_{\overline{m}}').
\end{align*}
Now the exchange checks if $h_C = h_C'$, and aborts the protocol if the check fails.
@@ -1223,20 +1215,20 @@ Our instantiation satisfies {weak income transparency}.
\end{theorem}
\begin{proof}
-In our refresh operation, the commitment phase sends only the hash
-of blinded coins and transfer public keys to reduce bandwidth.
-We therefore first convert our adversary into an adversary for a
-variant protocol in which these commitments contain the full values:
-We rewind the adversary to try two distinct $\gamma \in 1,\dots,\kappa$
-during each refresh operation, so that we obtain all values.
-We need only try two choices because the adversary reveals all but
-one planchet in each run. We now witness a hash collision if the
-transfer secret the adversary reveals does not yield the correct coins.
-
-If Taler satisfies unforgeability then this variant protocol does so too,
-because an adversary against the protocol with commitment to full planchets
-can trivially be replaced by an adversary against the protocol with hash
-commitments.
+%In our refresh operation, the commitment phase sends only the hash
+%of blinded coins and transfer public keys to reduce bandwidth.
+%We therefore first convert our adversary into an adversary for a
+%variant protocol in which these commitments contain the full values:
+%We rewind the adversary to try two distinct $\gamma \in 1,\dots,\kappa$
+%during each refresh operation, so that we obtain all values.
+%We need only try two choices because the adversary reveals all but
+%one planchet in each run. We now witness a hash collision if the
+%transfer secret the adversary reveals does not yield the correct coins.
+%
+%If Taler satisfies unforgeability then this variant protocol does so too,
+%because an adversary against the protocol with commitment to full planchets
+%can trivially be replaced by an adversary against the protocol with hash
+%commitments.
We consider the directed forest on coins induced by the refresh protocol.
It follows from unforgeability that any coin must originate from some
@@ -1249,7 +1241,7 @@ commitments.
via the linking protocol, but no non-corrupted user could obtain the
coin provided by the refresh, as otherwise $\V{coin}_i$ gets marked as
spent in step step \ref{game:income:spend}.
- Set $F := \{ R_i \mid i \leq l \}$. %TODO: Not ellegant, clean up below.
+ Set $F := \{ R_i \mid i \leq l \}$. %TODO: Not elegant, clean up below.
During each $R_i \in F$, our adversary must have submitted a blinded
coin and transfer public key for which the linking protocol fails to
@@ -1259,18 +1251,18 @@ commitments.
\begin{enumerate}
\item the execution of the refresh protocol is incomplete,
\item the commitment for the $\gamma$-th blinded coin and transfer
- public key was wrong,
+ public key does not match the revealed value,
\item a commitment for a blinded coin and transfer public key other
- than the $\gamma$-th was wrong,
+ than the $\gamma$-th does not match the revealed value,
\end{enumerate}
We show these to be exhaustive by assuming their converses all hold:
- As the commitment is signed, our our honest key generation assumption
+ As the commitment is signed by $\V{skCoin}_0$, our our honest key generation assumption
of $\textsc{CoinSignKx}$ applies to the coin public key.
- We assumed the $\gamma$-th transfer public key is honest too, so
- our key exchange completeness assumption of $\textsc{CoinSignKx}$
- yields $t C' \neq c' T$ where $T = t G$ is the transfer key,
- so the customer obtains the correct transfer secret.
+ We assumed the $\gamma$-th transfer public key matches the commitment
+ too, so our key exchange completeness assumption of $\textsc{CoinSignKx}$
+ yields $\algo{Kex}_{CSK}(t,C') = \algo{Kex}_{CSK}(c',T)$ where $T = \algo{KeyGenPub}_{CSK}(t)$ is the transfer key, so the customer
+ obtains the correct transfer secret.
We assumed the refresh concluded and all submissions besides the
$\gamma$-th were honest, so the exchange correctly reveals the signed
blinded coin. We assumed the $\gamma$-th blinded coin is correct too,