remove ROM, add commitment scheme, clarify *-algos

1 files changed, 32 insertions, 31 deletions

diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex
index 7ba662c..18a9b08 100644
--- a/taler-fc19/paper.tex
+++ b/taler-fc19/paper.tex
@@ -741,12 +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 protocol.  Our instantiation is in the random oracle model (ROM), i.e. usage

-of the hash function $H : \{0,1\}^* \mapsto \{1,\dots,2^\lambda\}$ is modeled

-by an oracle $\ora{H}$ that returns a value randomly chosen from

-$\{1,\dots,2^\lambda\}$ with uniform probability.  Subsequent oracle queries on

-the same bit string return the same value.

-

+exchange, a commitment scheme 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}$

@@ -818,7 +813,6 @@ Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange:
 

 We occasionally need these key generation algorithms separately, but

 we usually combine them into $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$. 

-%TODO: Eliminate this by fixing evrything below.  Search for KeyGen.*CSK

 

 We require the following security properties to hold for $\textsc{CoinSignKx}$:

 \begin{itemize}

@@ -827,11 +821,11 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$:
 

   \item \emph{honest key generation}:  

    Any probabilistic polynomial-time adversary has only negligible chance

-   to produce a public key $\V{pk}$ and a signature $\sigma$ that verifies,

+   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 robustness}:  

+  \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,

@@ -842,21 +836,25 @@ We require the following security properties to hold for $\textsc{CoinSignKx}$:
   \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}$.

-	%TODO: Isn't this just a PRF assumption???

 \end{itemize}

 

-We combine honest key generation and key exchange robustness in \emph{key exchange completeness} below.

-%TODO: Eliminate this by fixing evrything below

-

 Let $\textsc{Sign} = (\algo{KeyGen}_{S}, \algo{Sign}_{S}, \algo{Verify}_{S})$ be a signature

 scheme that satisfies SUF-CMA.

 

-Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instantiate the syntax:

+Let $(\algo{Setup}_C, 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.

+

+Let $\V{PRF}$ be a pseudo-random function family.

+

+Using these primitive, we now instantiate the syntax:

 

 \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)$.

+    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)$.

@@ -906,15 +904,18 @@ Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instanti
 

     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 modified version of $\algo{Blind}_{BS}$ where the signature requester $\mathcal{R}$

-    takes all randomness from seed $R$, 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$.

+    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

+    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$.

 

-    Furthermore we write

-    \[ \algo{KeyGen}^*_{CSK}(R, 1^\lambda) \mapsto (\V{sk}, \V{pk}) \]

-    for a modified version of the key generation algorithm that takes randomness from seed $R$.

+    Furthermore we write \[ \algo{KeyGen}^*_{CSK}(R, 1^\lambda) \mapsto

+    (\V{sk}, \V{pk}) \] for a modified version of the key generation algorithm

+    that takes randomness from the sequence $\left(\V{PRF}(R,\texttt{"key"}\Vert

+    n)\right)_{n>0}$.

 

     For each $i\in \{1,\dots,\kappa \}$, the customer

     \begin{enumerate}

@@ -926,7 +927,7 @@ Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instanti
       \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}(H(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{skCoin}_i))

       \]

         with the exchange.

     \end{enumerate}

@@ -939,9 +940,9 @@ Using \textsc{Blind}, \textsc{CoinSignKx}, \textsc{Sign} and $H$ we now instanti
     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(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}})

+      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}})

     \end{align*}

 

     The exchange checks the signature $\V{sig}_1$, and aborts if invalid.  Otherwise,

@@ -1081,7 +1082,7 @@ with the generic instantiation.
 \subsection{Anonymity}

 

 \begin{theorem}

-  In the random oracle model, our instantiation satisfies anonymity.

+  Our instantiation satisfies anonymity.

 \end{theorem}

 % TODO: PRF suffices

 

@@ -1161,9 +1162,9 @@ with the generic instantiation.
   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 randeom oracle to using the non-determinized algorithms

+  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)

+  to using the non-determinized algorithms

   $\algo{KeyGen}_{CSK}$ and $\algo{Blind}_{BS}$.

   % TODO: PRF suffices