diff options
| -rw-r--r-- | taler-fc19/paper.tex | 94 |
1 files 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.
|