From a48075c70499ce12da0ca96bdae3cdb484263cea Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 09:58:48 +0200 Subject: spell out SUF-CMA --- taler-fc19/paper.tex | 94 ++++++++++++++++++++++++++-------------------------- 1 file changed, 47 insertions(+), 47 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 8d48ead..3645f69 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -78,7 +78,7 @@ We consider a Chaum-style~\cite{chaum1983blind} payment system with an exchange (Chaum: mint) and multiple, -dynamically created customers and merchants. +dynamically created customers and merchants. We model withdrawing digital coins, spending them with merchants and subsequently depositing them at the exchange, as well as obtaining unlinkable change for partially spent coins with a @@ -214,7 +214,7 @@ of parties maintained by the challenger in the security games which we define la \item $\algo{WithdrawRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{pkD})) \mapsto (\mathcal{T}_{WR}, \V{wid})$: Interactive protocol between the exchange and a customer that - initiates withdrawing a single coin of a particular denomination. + initiates withdrawing a single coin of a particular denomination. The customer obtains a withdraw identifier $\V{wid}$ from the protocol execution and stores it in $\V{withdrawIds}[\V{pkCustomer}]$. @@ -390,7 +390,7 @@ adversary can send and receive messages. \item $\ora{SendMessage}(\mathcal{I}, P_1, P_2, m) \mapsto ()$: Send message $m$ on the channel from party $P_1$ to party $P_2$ in the - execution of interactive protocol $\mathcal{I}$. + execution of interactive protocol $\mathcal{I}$. \item $\ora{ReceiveMessage}(\mathcal{I}, P_1, P_2) \mapsto m$: Read message $m$ in the channel from party $P_1$ to party $P_2$ in the execution @@ -439,7 +439,7 @@ adversary can send and receive messages. Shares a coin (identified by handle $\mathcal{H}$) with the customer identified by $\V{pkCustomer}$, i.e. puts the coin identified by $\mathcal{H}$ into $\V{wallet}[\V{pkCustomer}]$. Intended to be used by the adversary in attempts to - violate income transparency. + violate income transparency. Note that this trivially violates anonymity (by sharing with a corrupted customer), thus the usage must be restricted in some games. @@ -447,7 +447,7 @@ adversary can send and receive messages. % the share oracle is the reason why we don't need a second withdraw oracle \item $\ora{CorruptCustomer}(\V{pkCustomer})\mapsto - \newline{}\qquad (\V{skCustomer}, \V{wallet}[\V{pkCustomer}],\V{acceptedContracts}[\V{pkCustomer}], + \newline{}\qquad (\V{skCustomer}, \V{wallet}[\V{pkCustomer}],\V{acceptedContracts}[\V{pkCustomer}], \newline{}\qquad \phantom{(}\V{refreshIds}[\V{pkCustomer}], \V{withdrawIds}[\V{pkCustomer}])$: Used by the adversary to corrupt a customer, giving the adversary access to @@ -465,7 +465,7 @@ adversary can send and receive messages. Returns an error if the deposit permission is addressed to a merchant that was not registered with $\ora{AddMerchant}$. - + This oracle does not give the adversary new information, but is used to model the situation where there might be multiple conflicting deposit permissions generated via $\algo{Spend}$, but only a limited number can be @@ -545,7 +545,7 @@ in $\mathfrak{R}$. \setlength\itemsep{0em} \item $(\V{sksE}, \V{pksE}, \V{skM}, \V{pkM}) \leftarrow {\prt{A}}()$ \item $(\V{pkCustomer}_0, \V{pkCustomer}_1, \V{transactionId}_0, \V{transactionId}_1, f) \leftarrow {\prt{A}}^{\oraSet{NoShare}}()$ - \item Select distinct fresh coins + \item Select distinct fresh coins \begin{align*} \V{coin}_0 &\in \V{wallet}[\V{pkCustomer}_0]\\ \V{coin}_1 &\in \V{wallet}[\V{pkCustomer}_1] @@ -589,7 +589,7 @@ money or privacy. \vspace{-0.5\topsep} \begin{enumerate} \setlength\itemsep{0em} - \item $(\V{sksE}, \V{pksE}) \leftarrow \mathrm{ExchangeKeygen}(1^\lambda, 1^\kappa, M)$ + \item $(\V{sksE}, \V{pksE}) \leftarrow \mathrm{ExchangeKeygen}(1^\lambda, 1^\kappa, M)$ \item $\V{pkCustomer} \leftarrow {\cal A}^{\oraSet{NoShare}}(\V{pksE})$ \item Return $0$ if $\V{pkCustomer}$ is a corrupted user. \item \label{game:conserv:run} Run $\algo{WithdrawPickup}$ for each withdraw identifier $\V{wid}$ @@ -635,7 +635,7 @@ they legitimately withdraw. \vspace{-0.5\topsep} \begin{enumerate} \setlength\itemsep{0em} - \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ + \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ \item $(C_0, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{All}}(pkExchange)$ \item Return $0$ if any $C_i$ is not of the form $(\V{skCoin}, \V{pkCoin}, \V{pkD}, \V{coinCert})$ or any $\V{coinCert}$ is not a valid signature by $\V{pkD}$ on the respective $\V{pkCoin}$. @@ -670,9 +670,9 @@ without being visible as income to the exchange. \vspace{-0.5\topsep} \begin{enumerate} \setlength\itemsep{0em} - \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ + \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ \item $(\V{coin}_1, \dots, \V{coin}_\ell) \leftarrow \mathcal{A}^{\oraSet{All}}(pkExchange)$ - + (The $\V{coin}_i$ must be coins, including secret key and signature by the denomination, for the adversary to win. However these coins need not be present in any honest or corrupted customer's wallet.) @@ -725,14 +725,14 @@ section. \begin{equation}\label{eq:income-transparency-expectation} E\left[\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)\right] \le {1\over\kappa} \mathperiod \end{equation} - In (\ref{eq:income-transparency-expectation}), the expectation runs over + In (\ref{eq:income-transparency-expectation}), the expectation runs over any probability space used by the adversary and challenger. \end{definition} For some instantiations, e.g. ones based on zero knowledge proofs, $\kappa$ might be a security parameter in the traditional sense. However for an e-cash scheme to be useful in practice, the adversary need not have only -negligible success probability in the income transparency game. +negligible success probability in the income transparency game. It suffices that the financial losses of the adversary in the game are a deterrent, after all our purpose of the game is to characterize tax evasion. @@ -812,21 +812,21 @@ Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange: \end{itemize} We occasionally need these key generation algorithms separately, but -we usually combine them into $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$. +we usually combine them into $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$. We require the following security properties to hold for $\textsc{CoinSignKx}$: \begin{itemize} \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}: + \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 find + \item \emph{key exchange completeness}: + Any probabilistic polynomial-time adversary has only negligible chance find $(\V{sk}_x, \V{pk}_x) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ for $x=A,B$ for which the key exchange fails, \begin{equation*} @@ -839,7 +839,7 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$: \end{itemize} Let $\textsc{Sign} = (\algo{KeyGen}_{S}, \algo{Sign}_{S}, \algo{Verify}_{S})$ be a signature -scheme that satisfies SUF-CMA. +scheme that satisfies selective unforgeability under chosen message attacks (SUF-CMA). Let $(\algo{Setup}_C, H_{pk})$ be a computationally hiding and binding commitment scheme, where $\algo{Setup}$ generates the public commitment key @@ -855,7 +855,7 @@ Using these primitive, we now instantiate the syntax: Generate the exchange's signing key pair $\V{skESign} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$ and public commitment key $\V{CK} \leftarrow Setup_C(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)$. \item $\algo{CustomerKeygen}(1^\lambda,1^\kappa)$: @@ -890,7 +890,7 @@ Using these primitive, we now instantiate the syntax: \end{enumerate} \item $\algo{Spend}(\V{transactionId}, f, \V{coin}, \V{pkMerchant})$: - + The deposit permission is computed as $\V{depositPermission} = (\V{pkCoin}, \sigma_D, m)$ where $m = (\V{transactionId}, f, \V{pkMerchant})$ and $\sigma_D = \algo{Sign}_{CSK}(skCoin, m)$. @@ -968,7 +968,7 @@ Using these primitive, we now instantiate the syntax: \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*} (t_i', T_i') &\leftarrow \algo{KeyGen}^*_{CSK}(s_i, 1^\lambda)\\ @@ -1052,7 +1052,7 @@ Using these primitive, we now instantiate the syntax: %private key being a multiple of the cofactor. % %In this vein, almost all post-quantum key exchanges suffer from key exchange -%failures that permit invalid key attacks against non-ephemeral keys. +%failures that permit invalid key attacks against non-ephemeral keys. %All these schemes support only one ephemeral party by revealing the %ephemeral party's private key to the non-ephemeral party, % ala the Fujisaki-Okamoto transform~\cite{fujisaki-okamoto} or similar. @@ -1149,7 +1149,7 @@ with the generic instantiation. (Modified anonymity game where the $\gamma$-th commitment in the refresh oracle is drawn uniformly from $D_b$ (using rewinding). Technically, we need to - draw from $D_b$ on withdraw for the coin secret key, write it to a table, look it up on refresh and + draw from $D_b$ on withdraw for the coin secret key, write it to a table, look it up on refresh and use the matching tuple, so that with $b=0$ we perfectly simulate $\mathbb{G}_1$.) \end{enumerate} @@ -1159,7 +1159,7 @@ with the generic instantiation. receives the result of the key exchange or real randomness. Thus $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| = \epsilon_{KX}$ is exactly the advantage of $\mathbb{G}_{1 \sim 2}$. - + We observe in $\mathbb{G}_2$ that as $x_\gamma$ is uniform random and not learned by the adversary, the generation of $(\V{skCoin}_\gamma, \V{pkCoin}_\gamma)$ and the execution of the blinding protocol is equivalent (under the PRF assumption) @@ -1245,41 +1245,41 @@ Our instantiation satisfies {weak income transparency}. \begin{proof} In our refresh operation, the commitment phase sends only the hash -of blinded coins and transfer public keys to reduce bandwidth. +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. +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. +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. + We consider the directed forest on coins induced by the refresh protocol. It follows from unforgeability that any coin must originate from some customer's withdraw in this graph. We may assume that all $\V{coin}_1, \dots, \V{coin}_l$ originate from - non-corrupted users, for some $l \leq \ell$. % So $\ell \leq w + |X|$. + non-corrupted users, for some $l \leq \ell$. % So $\ell \leq w + |X|$. For any $i \leq l$, there is a final refresh operation $R_i$ in which a non-corrupted user could obtain the coin $C'$ consumed in the refresh - 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}. + 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. 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 - produce the resulting coin correctly, otherwise the coin would have + produce the resulting coin correctly, otherwise the coin would have been spent in step \ref{game:income:spend}. In this case, we consider several non-exclusive cases \begin{enumerate} \item the execution of the refresh protocol is incomplete, - \item the commitment for the $\gamma$-th blinded coin and transfer + \item the commitment for the $\gamma$-th blinded coin and transfer public key was wrong, \item a commitment for a blinded coin and transfer public key other than the $\gamma$-th was wrong, @@ -1288,7 +1288,7 @@ commitments. We show these to be exhaustive by assuming their converses all hold: As the commitment is signed, 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 + 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. @@ -1371,18 +1371,18 @@ As for $F = \emptyset$, the return value of the game must be $0$, we conclude % $E(p/b) = {1 \over \kappa-1}$ %As it turns out, there is a simple hash-based solutions that provides -%post-quantum anonymity without additional assumptions though: -%% because the coin holder is encrypting to themselves: +%post-quantum anonymity without additional assumptions though: +%% because the coin holder is encrypting to themselves: %We extend the coin private key $c$ by a secret $m$ and extend the %coin signing key $C$ to be a pair $(C,R)$ in which $R$ is the root %of a Merkle tree whose $i$th leave is $H(m,i)$. -%In a refresh, the wallet first constructs the planchets from +%In a refresh, the wallet first constructs the planchets from %$H(t C', H(m,i))$ and commits to the index $i$ along with with each -%transfer public key $T$, and later when revealing $t$ also reveals -%$H(m,i)$ and the proof that it lives in the Merkle tree. +%transfer public key $T$, and later when revealing $t$ also reveals +%$H(m,i)$ and the proof that it lives in the Merkle tree. %In this scheme, our Merkle tree should be large enough to accommodate %some fixed number of refreshes per coin, possibly just one, while -%our wallet must avoid any fragility in committing its $i$ choices to disk. +%our wallet must avoid any fragility in committing its $i$ choices to disk. %\section{Standard Definitions} %\begin{definition}[One-more forgery] @@ -1390,7 +1390,7 @@ As for $F = \emptyset$, the return value of the game must be $0$, we conclude %a probabilistic polynomial time Turing machine $\mathcal{A}$ that can %compute, after $\ell$ interactions with the signer $\Sigma$, $\ell + 1$ signatures with non-negligible % probability. The ``one-more forgery'' is an $(\ell, \ell + 1)$-forgery for some -%integer $\ell$. +%integer $\ell$. %\end{definition} % %Taken from \cite{pointcheval1996provably}. This definition applies to blind signature schemes in general. @@ -1423,7 +1423,7 @@ 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}. +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. @@ -1433,10 +1433,10 @@ 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 signatures \cite{bernstein2012high} and scalar multiplication for the Edwards -curve, which gives $\lambda=128$. % Curve25519 \cite{bernstein2006curve25519} +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. +complete addition laws. % and that both robustness and honest key generation become tricky when .. For \textsc{Sign}, we use elliptic-curve signatures, concretely Ed25519. -- cgit v1.2.3 From 2b15d57fcd56676508506420be614972e74c51a5 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 10:00:12 +0200 Subject: C must die --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 3645f69..a5178eb 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -841,7 +841,7 @@ 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}_C, H_{pk})$ be a computationally hiding and binding +Let $(\algo{Setup}, H_{pk})$ be a computationally hiding and binding commitment scheme, where $\algo{Setup}$ generates the public commitment key $pk$ and $H_{pk} : \{0,1\}^* \rightarrow \{0,1\}^\lambda$ deterministically commits to a bit-string. -- cgit v1.2.3 From 3b3aabb726c343bd13cf30557a06a98acb4a8f7d Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 10:00:51 +0200 Subject: C must die --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index a5178eb..7515627 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -854,7 +854,7 @@ Using these primitive, we now instantiate the syntax: \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{CK} \leftarrow Setup_C(1^\lambda)$. + commitment key $\V{CK} \leftarrow \algo{Setup}(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)$. -- cgit v1.2.3 From ae923abfc9fca770b92c2fb2694244f01ae35110 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:02:52 +0200 Subject: missing subscripts --- taler-fc19/paper.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 7515627..f84f118 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -975,18 +975,18 @@ Using these primitive, 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(T'_1, \dots, T_{\gamma-1}, T_\gamma, T_{\gamma+1}', \dots, T_\kappa') + h_T' &:= H_{pk}(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 \begin{align*} (\overline{m}_i', r_i', \mathcal{T}_i) &\leftarrow - \algo{Blind}^*_{BS}(\mathcal{S}(\V{skD}_u), \mathcal{R}(H(x_i'), \cdot, \V{pkD}_u, \V{skCoin}_i))\\ + \algo{Blind}^*_{BS}(\mathcal{S}(\V{skD}_u), \mathcal{R}(x_i', \cdot, \V{pkD}_u, \V{skCoin}_i))\\ \end{align*} and finally \begin{align*} - h_{\overline{m}}' &:= H(\overline{m}_1', \dots, \overline{m}_\gamma, \dots, \overline{m}_\kappa')\\ - h_C &:= H(h_T' \Vert h_{\overline{m}}'). + h_{\overline{m}}' &:= H_{pk}(\overline{m}_1', \dots, \overline{m}_\gamma, \dots, \overline{m}_\kappa')\\ + h_C &:= H_{pk}(h_T' \Vert h_{\overline{m}}'). \end{align*} For each $i \ne \gamma$, the exchange computes -- cgit v1.2.3 From af67501b777f3caf32f278e2dab9ffcba346aead Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:14:11 +0200 Subject: Sign_BS is a protocol, fix subscript --- taler-fc19/paper.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index f84f118..56e04ce 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -753,10 +753,10 @@ is the signer and $\mathcal{R}$ is the signature requester: to blind a message $m$ that is to be signed later. The result is a blinded message $\overline{m}$ and a residual $r$ that allows to unblind a blinded signature on $m$ made by $\V{sk}$. \item $\algo{Sign}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\overline{m})) \mapsto - \overline{\sigma}$ is an algorithm to sign a blinded message $\overline{m}$. + \overline{\sigma}$ is a protocol to sign a blinded message $\overline{m}$. The result $\overline{\sigma}$ is a blinded signature that must be unblinded using the $r$ returned from the corresponding blinding operation before - verification. We restrict \algo{Sign} to be a two-move protocol, where the + verification. We restrict $\algo{Sign}_{BS}$ to be a two-move protocol, where the requester sends the first message, and the signer responds. \item $\algo{UnblindSig}_{BS}(r, m, \overline{\sigma}) \mapsto \sigma$ is an algorithm to unblind a blinded signature. -- cgit v1.2.3 From 6244246564a5fa6070f639b7f7d52c6b053d3c7c Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:14:56 +0200 Subject: G->H --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 56e04ce..9014e45 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -941,7 +941,7 @@ Using these primitive, we now instantiate the syntax: \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, \pi_1)$ to the exchange, where \begin{align*} h_T &:= H_{pk}(T_1, \dots, T_\kappa)\\ - h_{\overline{m}} &:= G_{pk}(\overline{m}_1, \dots, \overline{m}_\kappa)\\ + h_{\overline{m}} &:= H_{pk}(\overline{m}_1, \dots, \overline{m}_\kappa)\\ h_C &:= H_{pk}((h_T \Vert h_{\overline{m}}) \end{align*} -- cgit v1.2.3 From e50f9e20e39f64af5e95560b965f68e2c1206ae5 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:15:23 +0200 Subject: parens --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 9014e45..e69c073 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -942,7 +942,7 @@ Using these primitive, we now instantiate the syntax: \begin{align*} h_T &:= H_{pk}(T_1, \dots, T_\kappa)\\ h_{\overline{m}} &:= H_{pk}(\overline{m}_1, \dots, \overline{m}_\kappa)\\ - h_C &:= H_{pk}((h_T \Vert h_{\overline{m}}) + h_C &:= H_{pk}(h_T \Vert h_{\overline{m}}) \end{align*} The exchange checks the signature $\V{sig}_1$, and aborts if invalid. Otherwise, -- cgit v1.2.3 From 020ddeca0a98028a026a19ff3b9e524e5652c6e3 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 10:20:16 +0200 Subject: no unblinding for \sigma_x --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index e69c073..2d173b7 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -790,7 +790,7 @@ We require the following two security properties for $\textsc{BlindSign}$: m \randsel M, \\ \sigma \leftarrow \algo{UnblindSig}_{BS}(r, m, \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), m)) ) \\ x \randsel \overline{M}, \\ - \sigma_x \leftarrow \algo{UnblindSig}_{BS}(r, x, \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), x)) ) + \sigma_x \leftarrow \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), x)) \end{array} \right\}. \] \item \emph{unforgeability}: An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$ -- cgit v1.2.3 From 6318b2836fbee3c21e83a1c2d33a87981e34fe4a Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 10:22:29 +0200 Subject: undo no unblinding for \sigma_x -- x is also not blinded --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 2d173b7..e69c073 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -790,7 +790,7 @@ We require the following two security properties for $\textsc{BlindSign}$: m \randsel M, \\ \sigma \leftarrow \algo{UnblindSig}_{BS}(r, m, \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), m)) ) \\ x \randsel \overline{M}, \\ - \sigma_x \leftarrow \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), x)) + \sigma_x \leftarrow \algo{UnblindSig}_{BS}(r, x, \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), x)) ) \end{array} \right\}. \] \item \emph{unforgeability}: An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$ -- cgit v1.2.3 From 5ded568f83b7eb405c4e74c3a9142e7b25d718b6 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:29:22 +0200 Subject: blindness --- taler-fc19/paper.tex | 18 ++---------------- 1 file changed, 2 insertions(+), 16 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index e69c073..e863d19 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -775,24 +775,10 @@ We require the following two security properties for $\textsc{BlindSign}$: \begin{itemize} \item \emph{blindness}: Let $M$ be the set of all possible messages and $\overline{M}$ be the set of all possible blinded messages. Then the distribution of - \[ \left\{ (m, \sigma, \overline{m}, \overline{\sigma}) \,\middle| - \begin{array}{c} - m\, \randsel M, \\ - \overline{m} \leftarrow \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), m), \\ - \overline{\sigma} \leftarrow \algo{Sign}_{BS}(\V{sk}, \overline{m}), \\ - \sigma \leftarrow \algo{UnblindSig}_{BS}(r, m, \overline{\sigma}) - \end{array} - \right\} \] + \[ \left\{ (m, \overline{m}) \,\middle| m\, \randsel M, \overline{m} \leftarrow \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), m) \right\} \] must be computationally indistinguishable from - \[ \left\{ (m, \sigma, x, \sigma_x) \,\middle|\, - \begin{array}{c} - m \randsel M, \\ - \sigma \leftarrow \algo{UnblindSig}_{BS}(r, m, \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), m)) ) \\ - x \randsel \overline{M}, \\ - \sigma_x \leftarrow \algo{UnblindSig}_{BS}(r, x, \algo{Sign}_{BS}(\V{sk}, \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), x)) ) - \end{array} - \right\}. \] + \[ \left\{ (m, x) \,\middle|\, m \randsel M, x \randsel \overline{M} \right\}. \] \item \emph{unforgeability}: An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$ is unable to produce $k+1$ valid signatures with non-negligible probability. \end{itemize} -- cgit v1.2.3 From 45c81d9e0376a0a8831a65266fe7400992c40111 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 10:31:07 +0200 Subject: must be ZK --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index e863d19..a5f1b0f 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -749,7 +749,7 @@ is the signer and $\mathcal{R}$ is the signature requester: \begin{itemize} \item $\algo{KeyGen}_{BS}(1^\lambda) \mapsto (\V{sk}, \V{pk})$ is the key generation algorithm for the signer of the blind signature protocol. - \item $\algo{Blind}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\V{pk}, m)) \mapsto (\overline{m}, r)$ is a possibly interactive protocol + \item $\algo{Blind}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\V{pk}, m)) \mapsto (\overline{m}, r)$ is a possibly interactive zero-knowledge protocol to blind a message $m$ that is to be signed later. The result is a blinded message $\overline{m}$ and a residual $r$ that allows to unblind a blinded signature on $m$ made by $\V{sk}$. \item $\algo{Sign}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\overline{m})) \mapsto -- cgit v1.2.3 From d6c16a25a7c03cb243a8c1504309fa89d751454e Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 10:42:56 +0200 Subject: minor fixes --- taler-fc19/paper.tex | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index a5f1b0f..2241039 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -785,7 +785,7 @@ We require the following two security properties for $\textsc{BlindSign}$: For more generalized notions of the security of blind signatures, see e.g. \cite{fischlin2009security,schroder2017security}. -Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange: +Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange protocol: \begin{itemize} \item $\algo{KeyGenSec}_{CSK}(1^\lambda) \mapsto \V{sk}$ is a secret key generation algorithm. @@ -812,16 +812,16 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$: 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 find - $(\V{sk}_x, \V{pk}_x) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ for $x=A,B$ - for which the key exchange fails, + 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: \begin{equation*} \algo{Kex}_{CSK}(\V{sk}_A, \V{pk}_B) \neq \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A). \end{equation*} \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}$. + generated with $\algo{KeyGen}_{CSK}$. \end{itemize} Let $\textsc{Sign} = (\algo{KeyGen}_{S}, \algo{Sign}_{S}, \algo{Verify}_{S})$ be a signature @@ -834,7 +834,7 @@ bit-string. Let $\V{PRF}$ be a pseudo-random function family. -Using these primitive, we now instantiate the syntax: +Using these primitives, we now instantiate the syntax: \begin{itemize} \item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \mathfrak{D})$: -- cgit v1.2.3 From 66a4b71a420562d43d49b4dcfa503d36bb49b77d Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:44:20 +0200 Subject: public commitment key --- taler-fc19/paper.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 2241039..8363133 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -827,9 +827,9 @@ 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_{pk})$ be a computationally hiding and binding +Let $(\algo{Setup}, H_{pck})$ be a computationally hiding and binding commitment scheme, where $\algo{Setup}$ generates the public commitment key -$pk$ and $H_{pk} : \{0,1\}^* \rightarrow \{0,1\}^\lambda$ deterministically commits to a +$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. @@ -840,7 +840,7 @@ Using these primitives, we now instantiate the syntax: \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{CK} \leftarrow \algo{Setup}(1^\lambda)$. + commitment key $\V{pck} \leftarrow \algo{Setup}(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)$. @@ -926,9 +926,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_{pk}(T_1, \dots, T_\kappa)\\ + h_T &:= H_{pck}(T_1, \dots, T_\kappa)\\ h_{\overline{m}} &:= H_{pk}(\overline{m}_1, \dots, \overline{m}_\kappa)\\ - h_C &:= H_{pk}(h_T \Vert h_{\overline{m}}) + h_C &:= H_{pck}(h_T \Vert h_{\overline{m}}) \end{align*} The exchange checks the signature $\V{sig}_1$, and aborts if invalid. Otherwise, @@ -961,7 +961,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_{pk}(T'_1, \dots, T_{\gamma-1}, T_\gamma, T_{\gamma+1}', \dots, T_\kappa') + h_T' &:= H_{pck}(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 @@ -971,8 +971,8 @@ Using these primitives, we now instantiate the syntax: \end{align*} and finally \begin{align*} - h_{\overline{m}}' &:= H_{pk}(\overline{m}_1', \dots, \overline{m}_\gamma, \dots, \overline{m}_\kappa')\\ - h_C &:= H_{pk}(h_T' \Vert h_{\overline{m}}'). + h_{\overline{m}}' &:= H_{pck}(\overline{m}_1', \dots, \overline{m}_\gamma, \dots, \overline{m}_\kappa')\\ + h_C &:= H_{pck}(h_T' \Vert h_{\overline{m}}'). \end{align*} For each $i \ne \gamma$, the exchange computes -- cgit v1.2.3 From a364e41bb0ff1c5567c461e682f728b6f11fe89b Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:49:56 +0200 Subject: fix gibberish in withdraw prepare --- taler-fc19/paper.tex | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 8363133..0d2899a 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -855,7 +855,8 @@ Using these primitives, we now instantiate the syntax: \begin{enumerate} \item \prt{C} generates coin key pair $(\V{skCoin}, \V{pkCoin}) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ - \item \prt{C} runs $(\overline{m}, r) \leftarrow \algo{Blind}_{CSK}(\mathcal{E}(\V{skCoin}), \mathcal{C}(m))$ with the exchange + \item \prt{C} runs $(\overline{m}, r) \leftarrow \algo{Blind}_{CSK}(\mathcal{E}(\V{sksE}), \mathcal{C}(\V{pksE}, \V{pkCoin}))$ + with the exchange \end{enumerate} The withdraw identifier is then @@ -866,7 +867,7 @@ Using these primitives, we now instantiate the syntax: \item $\algo{WithdrawPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{wid}))$: - The customer looks up $\V{skCoin}$, $\V{pkCoin}$, \V{pkD} $\overline{m}$ + The customer looks up $\V{skCoin}$, $\V{pkCoin}$, \V{pkD}, $\overline{m}$ and $r$ via the withdraw identifier $\V{wid}$. \begin{enumerate} -- cgit v1.2.3 From 28f5cb577ddf516b10ed8191e6997d67c8802b17 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:53:31 +0200 Subject: sksE -> skD --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 0d2899a..d17f8f2 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -855,7 +855,7 @@ Using these primitives, we now instantiate the syntax: \begin{enumerate} \item \prt{C} generates coin key pair $(\V{skCoin}, \V{pkCoin}) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ - \item \prt{C} runs $(\overline{m}, r) \leftarrow \algo{Blind}_{CSK}(\mathcal{E}(\V{sksE}), \mathcal{C}(\V{pksE}, \V{pkCoin}))$ + \item \prt{C} runs $(\overline{m}, r) \leftarrow \algo{Blind}_{CSK}(\mathcal{E}(\V{skD}), \mathcal{C}(\V{pkD}, \V{pkCoin}))$ with the exchange \end{enumerate} -- cgit v1.2.3 From b746fa22bb5c2b7b740179714005dd39ce1c1e21 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 10:56:34 +0200 Subject: colons --- taler-fc19/paper.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index d17f8f2..fe6f595 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -879,8 +879,8 @@ Using these primitives, we now instantiate the syntax: \item $\algo{Spend}(\V{transactionId}, f, \V{coin}, \V{pkMerchant})$: The deposit permission is computed as $\V{depositPermission} = (\V{pkCoin}, - \sigma_D, m)$ where $m = (\V{transactionId}, f, \V{pkMerchant})$ and $\sigma_D - = \algo{Sign}_{CSK}(skCoin, m)$. + \sigma_D, m)$ where $m := (\V{transactionId}, f, \V{pkMerchant})$ and $\sigma_D + := \algo{Sign}_{CSK}(skCoin, m)$. \item $\algo{Deposit}(\prt{E}(\V{sksE}, \V{pkMerchant}), \prt{M}(\V{skMerchant}, \V{pksE}, \V{depositPermission}))$: -- cgit v1.2.3 From 2936900de2e2efed303f3fa7c91885815f4a368f Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:02:17 +0200 Subject: skR --- taler-fc19/paper.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index fe6f595..3243e1f 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -892,12 +892,12 @@ Using these primitives, we now instantiate the syntax: Let $\V{skD}_u$ be the secret key corresponding to $\V{pkD}_u$. We write \[ \algo{Blind}^*_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(R, - \V{sk}_C, \V{pk}, m)) \mapsto (\overline{m}, r, \mathcal{T}_{B*}) \] for a + \V{skR}, \V{pk}, m)) \mapsto (\overline{m}, r, \mathcal{T}_{B*}) \] for a modified version of $\algo{Blind}_{BS}$ where the signature requester $\mathcal{R}$ takes all randomness from the sequence $\left(\V{PRF}(R,\texttt{"blind"}\Vert n)\right)_{n>0}$, the messages from the exchange are recorded in transcript $\mathcal{T}_{B*}$, and all messages sent by the - requester are signed with $\V{sk}_C$. + requester are signed with $\V{skR}$. Furthermore we write \[ \algo{KeyGen}^*_{CSK}(R, 1^\lambda) \mapsto (\V{sk}, \V{pk}) \] for a modified version of the key generation algorithm -- cgit v1.2.3 From ba1aa573d11a41d7c0824fba6dfc45656ff146e3 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:07:02 +0200 Subject: sk->pk for blind signing --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 3243e1f..117a950 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -914,7 +914,7 @@ Using these primitives, we now instantiate the syntax: \item and executes the modified blinding protocol \[ (\overline{m}_i, r_i, \mathcal{T}_{(B*,i)}) \leftarrow - \algo{Blind}^*_{BS}(\mathcal{E}(\V{skD_u}), \mathcal{C}(x_i, \V{skCoin}_0, \V{pkD}_u, \V{skCoin}_i)) + \algo{Blind}^*_{BS}(\mathcal{E}(\V{skD_u}), \mathcal{C}(x_i, \V{skCoin}_0, \V{pkD}_u, \V{pkCoin}_i)) \] with the exchange. \end{enumerate} -- cgit v1.2.3 From b4b5a9f2a667cfa90daa815479a7eedca06e4977 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:07:50 +0200 Subject: nonce is dead --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 117a950..e1cf467 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -921,7 +921,7 @@ Using these primitives, we now instantiate the syntax: The customer stores the refresh identifier \begin{equation} - \V{rid} := (\V{coin}_0, \V{pkD}_u, \V{nonce}, \{ s_i \}, \{ \overline{m}_i \}, \{r_i\}, \{\mathcal{T}_{(B*,i)}\} ). + \V{rid} := (\V{coin}_0, \V{pkD}_u, \{ s_i \}, \{ \overline{m}_i \}, \{r_i\}, \{\mathcal{T}_{(B*,i)}\} ). \end{equation} Now, the customer's wallet sends the commitment $\pi_1 = (\V{pkCoin}_0, \V{pkD}_u, h_C)$ together with signature $\V{sig}_1 -- cgit v1.2.3 From bf5365004f243e1fcad6e7feff1d8fdc0a51cee0 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:11:01 +0200 Subject: typos --- taler-fc19/paper.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index e1cf467..63695db 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -924,11 +924,11 @@ Using these primitives, we now instantiate the syntax: \V{rid} := (\V{coin}_0, \V{pkD}_u, \{ s_i \}, \{ \overline{m}_i \}, \{r_i\}, \{\mathcal{T}_{(B*,i)}\} ). \end{equation} - Now, the customer's wallet 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_{pck}(T_1, \dots, T_\kappa)\\ - h_{\overline{m}} &:= H_{pk}(\overline{m}_1, \dots, \overline{m}_\kappa)\\ + h_{\overline{m}} &:= H_{pck}(\overline{m}_1, \dots, \overline{m}_\kappa)\\ h_C &:= H_{pck}(h_T \Vert h_{\overline{m}}) \end{align*} -- cgit v1.2.3 From 41747eecd2594ebbdca9559149085622a30f7909 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:12:48 +0200 Subject: clarification --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 63695db..0022e26 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -936,7 +936,7 @@ Using these primitives, we now instantiate the syntax: depending on the commitment: \begin{enumerate} \item if the exchange did not see $\pi_1$ before, it marks $\V{pkCoin}_0$ - as spent for $D(\V{pkD}_u)$, chooses a uniform random $0 \le \gamma < \kappa$, stores it, + as spent for $D(\V{pkD}_u)$, chooses a uniform random $0 \le \gamma < \kappa$, stores it under $\pi_1$, and sends this choice in a signed message $(\gamma, \V{sig}_2)$ to the customer, where $\V{sig}_2 \leftarrow \algo{Sign}_{S}(\V{skESig}, \gamma)$. \item otherwise, the exchange sends back the same $\pi_2$ as it sent for the last -- cgit v1.2.3 From 4815e930dde9bb82fff9255d898c759c21e35c81 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:13:11 +0200 Subject: parns --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 0022e26..7b66903 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -943,7 +943,7 @@ Using these primitives, we now instantiate the syntax: equivalent $\pi_1$. \end{enumerate} - \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid}) \rightarrow \mathcal{T}$: + \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*} -- cgit v1.2.3 From 739b36cab367f66aeb6ff2d95974e7d1776bd4da Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:19:01 +0200 Subject: typos --- taler-fc19/paper.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 7b66903..2a1cc6e 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -947,22 +947,22 @@ Using these primitives, we now instantiate the syntax: 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, + \pi_3 := T_\gamma, \overline{m}_\gamma, (s_1, \dots, s_{\gamma-1}, s_{\gamma+1}, \dots, s_\kappa) \end{equation*} and signature \begin{equation*} - \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)) + \V{sig}_{3} \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, (\V{pkCoin}_0, + \V{pkD}_u, \mathcal{T}_{(B*,\gamma)}, \pi_3)) \end{equation*} to the exchange. - The exchange checks the signature $\V{sig}_{3'}$ and then computes for $i \ne \gamma$: + The exchange checks the signature $\V{sig}_{3}$ and then computes for $i \ne \gamma$: \begin{align*} (t_i', T_i') &\leftarrow \algo{KeyGen}^*_{CSK}(s_i, 1^\lambda)\\ 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_{pck}(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 @@ -1002,7 +1002,7 @@ Using these primitives, we now instantiate the syntax: For each completed refresh on $\V{pkCoin}_0$ recorded in the exchange's database, the exchange sends the following data back to the customer: the signed commit message $(\V{sig}_1, \pi_1)$, the transfer public key - $T_\gamma$, the signature $\V{sig}_{3'}$, the blinded signature $\overline{\sigma}_\gamma$, and the + $T_\gamma$, the signature $\V{sig}_{3}$, the blinded signature $\overline{\sigma}_\gamma$, and the transcript $\mathcal{T}_{(B*,\gamma)}$ of the customer's and exchange's messages during the \algo{Blind} protocol execution. @@ -1019,7 +1019,7 @@ Using these primitives, we now instantiate the syntax: \item Simulate the blinding protocol with the message transcript received from the exchange to obtain $(\overline{m}_\gamma, r_\gamma)$. \item Check that $\algo{Verify}_{CSK}(\V{pkCoin}_0, - \V{pkD}_u, \V{skCoin}_0,(\mathcal{T}_{(B*,\gamma)}, \overline{m}_\gamma), \V{sig}_{3'})$ + \V{pkD}_u, \V{skCoin}_0,(\mathcal{T}_{(B*,\gamma)}, \overline{m}_\gamma), \V{sig}_{3})$ indicates a valid signature, abort otherwise. \item Unblind the signature to obtain $\sigma_\gamma \leftarrow \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma)$ \item (Re-)add the coin $(\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$ to the customer's wallet. @@ -1088,7 +1088,7 @@ with the generic instantiation. verification. In that case, the game is aborted instead. Observe that in case this failure event happens, the adversary must have forged a - signature on $\V{sig}_{3'}$ on values not signed by the customer, yielding + signature on $\V{sig}_{3}$ on values not signed by the customer, yielding an existential forgery. Thus $\left| \Prb{\mathbb{G}_0 = 1} - \Prb{\mathbb{G}_1 = 1} \right|$ is negligible. -- cgit v1.2.3 From 32a88cf13de3b44ca577e0d67a2f7ffc73872537 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 11:43:26 +0200 Subject: typos --- taler-fc19/paper.tex | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 2a1cc6e..052ebd8 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -968,23 +968,15 @@ Using these primitives, we now instantiate the syntax: as indicated by the dot ($\cdot$) instead of a signing secret key), obtaining \begin{align*} (\overline{m}_i', r_i', \mathcal{T}_i) &\leftarrow - \algo{Blind}^*_{BS}(\mathcal{S}(\V{skD}_u), \mathcal{R}(x_i', \cdot, \V{pkD}_u, \V{skCoin}_i))\\ + \algo{Blind}^*_{BS}(\mathcal{S}(\V{skD}_u), \mathcal{R}(x_i', \cdot, \V{pkD}_u, \V{skCoin}'_i))\\ \end{align*} and finally \begin{align*} - h_{\overline{m}}' &:= H_{pck}(\overline{m}_1', \dots, \overline{m}_\gamma, \dots, \overline{m}_\kappa')\\ - h_C &:= H_{pck}(h_T' \Vert h_{\overline{m}}'). + 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}}'). \end{align*} - For each $i \ne \gamma$, the exchange computes - \begin{align*} - \overline{\sigma}_i' &\leftarrow \algo{Sign}(\mathcal{E}(\V{skD}_u), \mathcal{E}(\overline{m}_i'))\\ - \sigma_i' &\leftarrow \algo{UnblindSig}(r_i', \V{pkCoin}_i', \overline{\sigma}_i')\\ - b_i &\leftarrow \algo{Verify}_{BS}(\V{pkD}, \V{skCoin}_i', \sigma_i') - \end{align*} - - Now the exchange checks if $h_C = h_C'$ and if all $b_i = 1$ for $i \ne \gamma$. - If one of the checks fails, the exchange aborts the protocol. + Now the exchange checks if $h_C = h_C'$, and aborts the protocol if the check fails. Otherwise, the exchange sends a message back to $\prt{C}$ that the commitment verification succeeded. -- cgit v1.2.3 From c1dc251de5065984ad010801ef6b21c1e74e9f46 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 11:51:23 +0200 Subject: similify --- taler-fc19/paper.tex | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 052ebd8..43b72ac 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -753,11 +753,10 @@ is the signer and $\mathcal{R}$ is the signature requester: to blind a message $m$ that is to be signed later. The result is a blinded message $\overline{m}$ and a residual $r$ that allows to unblind a blinded signature on $m$ made by $\V{sk}$. \item $\algo{Sign}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\overline{m})) \mapsto - \overline{\sigma}$ is a protocol to sign a blinded message $\overline{m}$. + \overline{\sigma}$ is an algorithm to sign a blinded message $\overline{m}$. The result $\overline{\sigma}$ is a blinded signature that must be unblinded using the $r$ returned from the corresponding blinding operation before - verification. We restrict $\algo{Sign}_{BS}$ to be a two-move protocol, where the - requester sends the first message, and the signer responds. + verification. \item $\algo{UnblindSig}_{BS}(r, m, \overline{\sigma}) \mapsto \sigma$ is an algorithm to unblind a blinded signature. \item $\algo{Verify}_{BS}(\V{pk}, m, \sigma) \mapsto b$ is a algorithm to check the validity of a blind @@ -977,16 +976,18 @@ Using these primitives, we now instantiate the syntax: \end{align*} Now the exchange checks if $h_C = h_C'$, and aborts the protocol if the check fails. - - Otherwise, the exchange sends a message back to $\prt{C}$ that the commitment verification succeeded. + Otherwise, the exchange sends a message back to $\prt{C}$ that the commitment verification succeeded and includes + the signature + \begin{equation*} + \overline{\sigma}_\gamma := \algo{Sign}_{BS}(\mathcal{E}(\V{skD}_u), \mathcal{C}(\overline{m}_\gamma)). + \end{equation*} As a last step, the customer obtains the signature $\sigma_\gamma$ on the new coin's public key $\V{pkCoin}_u$ with - \begin{align*} - \overline{\sigma}_\gamma &\leftarrow \algo{Sign}(\mathcal{E}(\V{skD}_u), \mathcal{C}(\overline{m}_\gamma))\\ - \sigma_\gamma &\leftarrow \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma). - \end{align*} + \begin{equation*} + \sigma_\gamma := \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma). + \end{equation*} - Thus the new, unlinkable coin is $\V{coin}_u = (\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$. + Thus the new, unlinkable coin is $\V{coin}_u := (\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$. \item $\algo{Link}(\prt{E}(\V{sksE}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0))$: The customer sends the public key $\V{pkCoin}_0$ of $\V{coin}_0$ to the exchange. -- cgit v1.2.3 From 525fc09dc5d69441ae4ccfb7c0e56669b7ec2bdb Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 25 Sep 2018 11:56:19 +0200 Subject: alg not prot --- taler-fc19/paper.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 43b72ac..3fdc1ce 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -997,7 +997,7 @@ Using these primitives, we now instantiate the syntax: signed commit message $(\V{sig}_1, \pi_1)$, the transfer public key $T_\gamma$, the signature $\V{sig}_{3}$, the blinded signature $\overline{\sigma}_\gamma$, and the transcript $\mathcal{T}_{(B*,\gamma)}$ of the customer's and exchange's messages - during the \algo{Blind} protocol execution. + during the $\algo{Blind}^*_{BS}$ protocol execution. The following logic is repeated by the customer for each response: \begin{enumerate} @@ -1006,15 +1006,15 @@ Using these primitives, we now instantiate the syntax: \item Verify that $\V{sig}_1$ is a valid signature on $\pi_1$ by $\V{pkCoin}_0$, abort otherwise. \item Re-compute the transfer secret and the new coin's key pair as \begin{align*} - x_\gamma &\leftarrow \algo{Kx}_{CSK}(\V{skCoin}_0, T_\gamma)\\ - (\V{skCoin}_\gamma, \V{pkCoin}_\gamma) &\leftarrow \algo{KeyGen}_{CSK}^*(x_\gamma, 1^\lambda). + x_\gamma &:= \algo{Kx}_{CSK}(\V{skCoin}_0, T_\gamma)\\ + (\V{skCoin}_\gamma, \V{pkCoin}_\gamma) &:= \algo{KeyGen}_{CSK}^*(x_\gamma, 1^\lambda). \end{align*} \item Simulate the blinding protocol with the message transcript received from the exchange to obtain $(\overline{m}_\gamma, r_\gamma)$. \item Check that $\algo{Verify}_{CSK}(\V{pkCoin}_0, \V{pkD}_u, \V{skCoin}_0,(\mathcal{T}_{(B*,\gamma)}, \overline{m}_\gamma), \V{sig}_{3})$ indicates a valid signature, abort otherwise. - \item Unblind the signature to obtain $\sigma_\gamma \leftarrow \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma)$ + \item Unblind the signature to obtain $\sigma_\gamma := \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma)$. \item (Re-)add the coin $(\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$ to the customer's wallet. \end{enumerate} -- cgit v1.2.3 From 973b974fabd14a7a63110f5e06fb404c38ae4b59 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 13:00:39 +0200 Subject: blindness --- taler-fc19/paper.tex | 10 ++++------ taler-fc19/ref.bib | 9 +++++++++ 2 files changed, 13 insertions(+), 6 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 3fdc1ce..c82f33f 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -772,12 +772,10 @@ Such blind signature protocols have already been used to construct e-cash We require the following two security properties for $\textsc{BlindSign}$: \begin{itemize} - \item \emph{blindness}: Let $M$ be the set of all possible messages and $\overline{M}$ be the - set of all possible blinded messages. Then the distribution of - \[ \left\{ (m, \overline{m}) \,\middle| m\, \randsel M, \overline{m} \leftarrow \algo{Blind}_{BS}(\mathcal{S}(\V{sk}), m) \right\} \] - must be computationally - indistinguishable from - \[ \left\{ (m, x) \,\middle|\, m \randsel M, x \randsel \overline{M} \right\}. \] + \item \emph{blindness}: It should be computationally infeasible for a + malicious signer to decide which of two messages and has been signed first + in two executions with an honest user. The corresponding game can defined as + in Abe and Okamoto \cite{abe2000provably}. \item \emph{unforgeability}: An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$ is unable to produce $k+1$ valid signatures with non-negligible probability. \end{itemize} diff --git a/taler-fc19/ref.bib b/taler-fc19/ref.bib index 4fda028..007ee7d 100644 --- a/taler-fc19/ref.bib +++ b/taler-fc19/ref.bib @@ -2379,3 +2379,12 @@ url = {https://www.crockford.com/wrmg/base32.html} year = 2010, month = may, } + +@inproceedings{abe2000provably, + title={Provably secure partially blind signatures}, + author={Abe, Masayuki and Okamoto, Tatsuaki}, + booktitle={Annual International Cryptology Conference}, + pages={271--286}, + year={2000}, + organization={Springer} +} -- cgit v1.2.3 From 2393ab3a4d1c24d70c0f56f1514100e4abb17efd Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 13:01:22 +0200 Subject: remove zero-knowledge --- taler-fc19/paper.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index c82f33f..97fb55c 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -749,7 +749,7 @@ is the signer and $\mathcal{R}$ is the signature requester: \begin{itemize} \item $\algo{KeyGen}_{BS}(1^\lambda) \mapsto (\V{sk}, \V{pk})$ is the key generation algorithm for the signer of the blind signature protocol. - \item $\algo{Blind}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\V{pk}, m)) \mapsto (\overline{m}, r)$ is a possibly interactive zero-knowledge protocol + \item $\algo{Blind}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\V{pk}, m)) \mapsto (\overline{m}, r)$ is a possibly interactive protocol to blind a message $m$ that is to be signed later. The result is a blinded message $\overline{m}$ and a residual $r$ that allows to unblind a blinded signature on $m$ made by $\V{sk}$. \item $\algo{Sign}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\overline{m})) \mapsto -- cgit v1.2.3 From 6c335f33558b79293ed30bec6fd805ee17f1e206 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 13:08:08 +0200 Subject: ref schroeder for blindness game enhancement --- taler-fc19/paper.tex | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 97fb55c..f9f40a5 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -775,7 +775,8 @@ We require the following two security properties for $\textsc{BlindSign}$: \item \emph{blindness}: It should be computationally infeasible for a malicious signer to decide which of two messages and has been signed first in two executions with an honest user. The corresponding game can defined as - in Abe and Okamoto \cite{abe2000provably}. + in Abe and Okamoto \cite{abe2000provably}, with the additional enhancement + that the adversary generates the signing key \cite{schroder2017security}. \item \emph{unforgeability}: An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$ is unable to produce $k+1$ valid signatures with non-negligible probability. \end{itemize} -- cgit v1.2.3 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 From 0e5c388866db068a9dec4f80c81a10ca427c078e Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 16:05:41 +0200 Subject: typos --- taler-fc19/paper.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 1200ae7..7d34165 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -805,14 +805,14 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$: \item \emph{key exchange completeness}: 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 + a degenerate key pair $(\V{sk}_A, \V{pk}_A)$ 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), \end{equation*} - but the adversary can still produce a pair $(m, \sigma)$ such that $\algo{Verify}_{BS}(\V{pk}_A, m, \sigma) = 1$. + while 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 -- cgit v1.2.3 From 534bdbc8e54e678e799cdfb96cfb534fe52f8998 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 16:07:51 +0200 Subject: save space --- taler-fc19/paper.tex | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index 7d34165..947f3e1 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -809,9 +809,7 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$: 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), - \end{equation*} + $\algo{Kex}_{CSK}(\V{sk}_A, \V{pk}_B) \neq \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A)$, while 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 -- cgit v1.2.3