diff options
author  Jeff Burdges <burdges@gnunet.org>  20180925 10:31:15 0400 

committer  Jeff Burdges <burdges@gnunet.org>  20180925 10:31:15 0400 
commit  d0716421b852348ddec12a20267fa25518189b5e (patch)  
tree  47153cef67d744d05c65d1db427ceee5a0f2336f  
parent  2bc5b1e1df0286962548810dadb5848bd16fce39 (diff)  
parent  534bdbc8e54e678e799cdfb96cfb534fe52f8998 (diff)  
download  papersd0716421b852348ddec12a20267fa25518189b5e.tar.gz papersd0716421b852348ddec12a20267fa25518189b5e.tar.bz2 papersd0716421b852348ddec12a20267fa25518189b5e.zip 
Merge branch 'master' of ssh://taler.net/papers
rwrr  talerfc19/paper.tex  247  
rwrr  talerfc19/ref.bib  9 
2 files changed, 126 insertions, 130 deletions
diff git a/talerfc19/paper.tex b/talerfc19/paper.tex index 602afc3..ba4cd28 100644  a/talerfc19/paper.tex +++ b/talerfc19/paper.tex @@ 78,7 +78,7 @@ We consider a Chaumstyle~\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:incometransparencyexpectation}
E\left[\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)\right] \le {1\over\kappa} \mathperiod
\end{equation}
 In (\ref{eq:incometransparencyexpectation}), the expectation runs over
+ In (\ref{eq:incometransparencyexpectation}), 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 ecash
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.
@@ 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}$
@@ 756,8 +756,7 @@ is the signer and $\mathcal{R}$ is the signature requester: \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} to be a twomove 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
@@ 773,33 +772,18 @@ Such blind signature protocols have already been used to construct ecash 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\} \]
 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\}. \]
+ \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}, 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 nonnegligible probability.
\end{itemize}
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,51 +796,56 @@ 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 (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 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*}
 \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 completeness}:
+ Any probabilistic polynomialtime adversary has only negligible chance to find
+ 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
+ $\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
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
+<<<<<<< HEAD
scheme that satisfies SUFCMA.
Let $(\algo{Setup}_C, H_{pk})$ be a computationally 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 bitstring.
+=======
+scheme that satisfies selective unforgeability under chosen message attacks (SUFCMA).
+>>>>>>> 534bdbc8e54e678e799cdfb96cfb534fe52f8998
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 primitive, 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})$:
+<<<<<<< HEAD
Generate the exchange's signing key pair
$\V{skESign} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$ and
public commitment key $\V{CK} \leftarrow \algo{Setup}_C(1^\lambda)$.
+=======
+ Generate the exchange's signing key pair $\V{skESign} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$.
+
+>>>>>>> 534bdbc8e54e678e799cdfb96cfb534fe52f8998
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)$:
@@ 870,7 +859,8 @@ Using these primitive, 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{skD}), \mathcal{C}(\V{pkD}, \V{pkCoin}))$
+ with the exchange
\end{enumerate}
The withdraw identifier is then
@@ 881,7 +871,7 @@ Using these primitive, 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}
@@ 891,10 +881,10 @@ 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)$.
+ \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}))$:
@@ 906,12 +896,12 @@ Using these primitive, 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
@@ 928,87 +918,81 @@ Using these primitive, 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}
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
+ 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_{\overline{m}} &:= G_{pk}(\overline{m}_1, \dots, \overline{m}_\kappa)\\
 h_C &:= H_{pk}((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,
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
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*}
 \pi_3 = T_\gamma, \overline{m}_\gamma,
+ \pi_3 := T_\gamma, \overline{m}_\gamma,
(s_1, \dots, s_{\gamma1}, 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(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
\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(\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*}
 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.

 Otherwise, the exchange sends a message back to $\prt{C}$ that the commitment verification succeeded.
+ 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 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.
@@ 1016,9 +1000,9 @@ Using these primitive, 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.
+ during the $\algo{Blind}^*_{BS}$ protocol execution.
The following logic is repeated by the customer for each response:
\begin{enumerate}
@@ 1027,15 +1011,15 @@ Using these primitive, 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 Recompute 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'})$
+ \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}
@@ 1053,7 +1037,7 @@ Using these primitive, we now instantiate the syntax: %private key being a multiple of the cofactor.
%
%In this vein, almost all postquantum key exchanges suffer from key exchange
%failures that permit invalid key attacks against nonephemeral keys.
+%failures that permit invalid key attacks against nonephemeral keys.
%All these schemes support only one ephemeral party by revealing the
%ephemeral party's private key to the nonephemeral party,
% ala the FujisakiOkamoto transform~\cite{fujisakiokamoto} or similar.
@@ 1102,7 +1086,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.
@@ 1150,7 +1134,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}
@@ 1160,7 +1144,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 +1229,44 @@ Our instantiation satisfies {weak income transparency}. \end{theorem}
\begin{proof}
 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
 noncorrupted users, for some $l \leq \ell$. % So $\ell \leq w + X$.
+ noncorrupted 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 noncorrupted user could obtain the coin $C'$ consumed in the refresh
 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.
+ 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 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
 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 nonexclusive cases
\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,
+ \item the commitment for the $\gamma$th blinded coin and transfer
+ 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
 of $\textsc{CoinSignKx}$ applies to the coin public key.
 We assumed the $\gamma$th transfer public key is honest too, so
+ As the commitment is signed by $\V{skCoin}_0$, our honest key generation
+ assumption of $\textsc{CoinSignKx}$ applies to the coin public key.
+ Any commitments that match were computed honestly, thanks to our
+ commitment scheme $(\algo{Setup}_C, H_{pk})$ being computationally
+ binding.
+ We assumed the $\gamma$th transfer public key is honest, so
our key exchange completeness assumption of $\textsc{CoinSignKx}$
 yields $t C' \neq c' T$ where $T = t G$ is the transfer key.
+ yields $\algo{Kex}_{CSK}(t,C') = \algo{Kex}_{CSK}(c',T)$ where
+ $T = \algo{KeyGenPub}_{CSK}(t)$ is the transfer key.
It follows our customer obtains the correct transfer secret and
 derives the correct coins because our commitment scheme
 $(\algo{Setup}_C, H_{pk})$ is computationally binding.
+ derives the correct coins.
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,
@@ 1359,18 +1346,18 @@ As for $F = \emptyset$, the return value of the game must be $0$, we conclude % $E(p/b) = {1 \over \kappa1}$
%As it turns out, there is a simple hashbased solutions that provides
%postquantum anonymity without additional assumptions though:
%% because the coin holder is encrypting to themselves:
+%postquantum 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}[Onemore forgery]
@@ 1378,7 +1365,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 nonnegligible
% probability. The ``onemore 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.
@@ 1411,7 +1398,7 @@ with blinding factors produced by FDPRF 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 RSAKTI assumption as discussed in \cite{bellare2003onemore}.
+we require the RSAKTI assumption as discussed in \cite{bellare2003onemore}.
%TODO: Jeff always cited multoiiple papers for RSAKTI, but forgets why.
As the blinding step in RSA blind signatures is noninteractive, storage
and verification of the transcript is omitted in refresh and link.
@@ 1421,10 +1408,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 DiffieHellman 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 ellipticcurve signatures, concretely Ed25519.
diff git a/talerfc19/ref.bib b/talerfc19/ref.bib index 4fda028..007ee7d 100644  a/talerfc19/ref.bib +++ b/talerfc19/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={271286}, + year={2000}, + organization={Springer} +} 