key exchange completeness needs to be two properties

1 files changed, 22 insertions, 3 deletions

diff --git a/taler-fc19/paper.tex b/taler-fc19/paper.tex
index 8ea12ed..7f32db9 100644
--- a/taler-fc19/paper.tex
+++ b/taler-fc19/paper.tex
@@ -803,7 +803,8 @@ For more generalized notions of the security of blind signatures, see e.g.
 Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange:

 

 \begin{itemize}

-  \item $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$ is a key generation algorithm.

+  \item $\algo{KeyGenSec}_{CSK}(1^\lambda) \mapsto \V{sk}$ is a secret key generation algorithm.

+  \item $\algo{KeyGenPub}_{CSK}(\V{sk}) \mapsto \V{pk}$ produces the corresponding public key.

   \item $\algo{Sign}_{CSK}(\V{sk}, m) \mapsto \sigma$ produces a signature $\sigma$ over message $m$.

   \item $\algo{Verify}_{CSK}(\V{pk}, m, \sigma) \mapsto b$ is a signature verification algorithm.

     Returns $1$ if the signature $\sigma$ is a valid signature on $m$ by $\V{pk}$, and $0$ otherwise.

@@ -811,19 +812,37 @@ Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange:
     the shared secret $x$ from secret key $\V{sk}_1$ and public key $\V{pk}_2$.

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

+%TODO: Eliminate this by fixing evrything below

+

 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{key exchange completeness}:  We require that even for keys generated by the adversary,

+

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

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

+  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) = \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A).

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

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