diff options
author  Florian Dold <florian.dold@gmail.com>  20180925 16:03:18 +0200 

committer  Florian Dold <florian.dold@gmail.com>  20180925 16:03:18 +0200 
commit  ec02729cee5d9a3df253d090e9834c18603e63fc (patch)  
tree  f8502e8b2d7bb6d3c7fa74e35733cc56111a95c1  
parent  6c335f33558b79293ed30bec6fd805ee17f1e206 (diff)  
download  papersec02729cee5d9a3df253d090e9834c18603e63fc.tar.gz papersec02729cee5d9a3df253d090e9834c18603e63fc.tar.bz2 papersec02729cee5d9a3df253d090e9834c18603e63fc.zip 
enhanced key exchange completeness, no more honest key generation
rwrr  talerfc19/paper.tex  88 
1 files changed, 40 insertions, 48 deletions
diff git a/talerfc19/paper.tex b/talerfc19/paper.tex index f9f40a5..1200ae7 100644  a/talerfc19/paper.tex +++ b/talerfc19/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 pseudorandom function family (PRF).
+exchange, a collisionresistant hash function and a pseudorandom 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 (EUFCMA).
 \item \emph{honest key generation}:
 Any probabilistic polynomialtime 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 polynomialtime 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 polynomialtime 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 (SUFCMA).
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
bitstring.

Let $\V{PRF}$ be a pseudorandom function family.
+Let $\V{PRF}$ be a pseudorandom function family and $H : \{0,1\}^* \rightarrow \{0,1\}^\lambda$
+a collisionresistant hash function.
Using these primitives, we now instantiate the syntax:
+Using these primitives, we now instantiate the syntax of our incometransparent ecash 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'_{\gamma1}, T_\gamma, T_{\gamma+1}', \dots, T_\kappa')
+ h_T' &:= H(T'_1, \dots, T'_{\gamma1}, 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}_{\gamma1}', \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}_{\gamma1}', \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 noncorrupted 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,
