From 74f745bb854ad16f10b1f9dc9b3bef55236e32e8 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Tue, 25 Sep 2018 16:47:18 +0200 Subject: proof stuff --- taler-fc19/paper.tex | 59 ++++++++++++++++++---------------------------------- 1 file changed, 20 insertions(+), 39 deletions(-) diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex index ba4cd28..3778c63 100644 --- a/taler-fc19/paper.tex +++ b/taler-fc19/paper.tex @@ -818,16 +818,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 -<<<<<<< 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 and $H : \{0,1\}^* \rightarrow \{0,1\}^\lambda$ a collision-resistant hash function. @@ -837,15 +828,8 @@ Using these primitives, we now instantiate the syntax of our income-transparent \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)$: @@ -1250,27 +1234,25 @@ Our instantiation satisfies {weak income transparency}. \begin{enumerate} \item the execution of the refresh protocol is incomplete, \item the commitment for the $\gamma$-th blinded coin and transfer - public key does not match the revealed value, + public key is dishonest, \item a commitment for a blinded coin and transfer public key other - than the $\gamma$-th does not match the revealed value, + than the $\gamma$-th is dishonest, \end{enumerate} - We show these to be exhaustive by assuming their converses all hold: - 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 $\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. - 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, - so customer now re-compute the new coin correctly, violating $R_i \in F$. + We show these to be exhaustive by assuming their converses all hold: As the + commitment is signed by $\V{skCoin}_0$, our key exchange completeness + 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 revealed $\gamma$-th transfer public key is honest. Hence 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, thus 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, so customer now re-compute the new coin correctly, violating + $R_i \in F$. We shall prove \begin{equation}\label{eq:income-transparency-proof} @@ -1279,11 +1261,10 @@ Our instantiation satisfies {weak income transparency}. where the expectation runs over any probability space used by the adversary and challenger. - We shall optimize our adversary in ways that maximize $p \over b + p$ by - proving the optimised adversary exists. We may then restrict our analysis - to these optimised adversaries, which suffices for our game result, but - note that reductions would not permit this trick. - %TODO: Improve?? + We shall now consider executions of the income transparency game with an + optimal adversary with respect to maximizing $p \over b + p$. Note that this + is permissible since we are not carring out a reduction, but are interested + in the expectation of the game's return value. As a reminder, if a refresh operation is initiated using a false commitment that is detected by the exchange, then the new coin cannot be obtained, and -- cgit v1.2.3