From ec02729cee5d9a3df253d090e9834c18603e63fc Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 16:03:18 +0200 Subject: enhanced key exchange completeness, no more honest key generation --- taler-fc19/paper.tex | 88 ++++++++++++++++++++++++---------------------------- 1 file 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, -- cgit v1.2.3