summaryrefslogtreecommitdiff
path: root/taler-fc19/paper.tex
diff options
context:
space:
mode:
authorJeff Burdges <burdges@gnunet.org>2018-09-25 10:31:15 -0400
committerJeff Burdges <burdges@gnunet.org>2018-09-25 10:31:15 -0400
commitd0716421b852348ddec12a20267fa25518189b5e (patch)
tree47153cef67d744d05c65d1db427ceee5a0f2336f /taler-fc19/paper.tex
parent2bc5b1e1df0286962548810dadb5848bd16fce39 (diff)
parent534bdbc8e54e678e799cdfb96cfb534fe52f8998 (diff)
downloadpapers-d0716421b852348ddec12a20267fa25518189b5e.tar.gz
papers-d0716421b852348ddec12a20267fa25518189b5e.tar.bz2
papers-d0716421b852348ddec12a20267fa25518189b5e.zip
Merge branch 'master' of ssh://taler.net/papers
Diffstat (limited to 'taler-fc19/paper.tex')
-rw-r--r--taler-fc19/paper.tex247
1 files changed, 117 insertions, 130 deletions
diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex
index 602afc3..ba4cd28 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.
@@ -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}$
@@ -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 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
@@ -773,33 +772,18 @@ 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, \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 non-negligible 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 (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 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 polynomial-time 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 SUF-CMA.
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 bit-string.
+=======
+scheme that satisfies selective unforgeability under chosen message attacks (SUF-CMA).
+>>>>>>> 534bdbc8e54e678e799cdfb96cfb534fe52f8998
-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 primitive, 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})$:
+<<<<<<< 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_{\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(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
\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}_{\gamma-1}', \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 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'})$
+ \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 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.
@@ -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
- 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}.
- Set $F := \{ R_i \mid i \leq l \}$. %TODO: Not ellegant, clean up below.
+ 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 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 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
- 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 \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]
@@ -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 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.
@@ -1411,7 +1398,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.
@@ -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 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.