149 lines
8.7 KiB
TeX
149 lines
8.7 KiB
TeX
\subsection{Digital Signature Scheme}
|
|
|
|
A digital signature scheme is a method to ensure the authenticity of data. The signer, which is in the possession of a private key, generates a signature for a specific message. The verifier is then able to verify the authenticity of this data using the public key and the generated signature.
|
|
|
|
\begin{definition}
|
|
A digital signature scheme SIG = (\keygen,\sign,\verify) is a tuple of algorithms.
|
|
|
|
\begin{itemize}[label={}]
|
|
\item \textbf{\keygen}: The key generation algorithm, which upon receiving the security parameter as input outputs a matching tuple of public and private key.
|
|
\item \textbf{\sign}: The signature algorithm, which upon receiving a secret key and a message, outputs a signature for that message.
|
|
\item \textbf{\verify}: The verification algorithm, which upon receiving a public key, a message and a signature, outputs $1$ if the signature gets accepted and $0$ otherwise.
|
|
\end{itemize}
|
|
|
|
For the digital signature scheme to be correct, it is required that $\forall (\pubkey, \privkey) \in \keygen(par), \m \in \messagespace, \signature \in \sign(\privkey, \m): \verify(\pubkey, \m, \signature) = 1$
|
|
\end{definition}
|
|
|
|
A common security notion for digital signature schemes is the existential unforgeability under chosen message attack (EUF-CMA) security. It requires that no adversary is able to forge a signature for a message to which they have not observed a valid signature, given a public key. A stronger notion, that is often used, is strong unforgeability under chosen message attack (SUF-CMA), which only requires the adversary to provide a message signature pair that has not been provided to the adversary. With this security notion, the adversary also wins if it is able to forge a new valid signature from an already valid one. Both of these notions are in the single-user setting. In the multi-user setting of these security notions, the adversary is supplied with $N$ public keys and has to forge a signature for one of those public keys. In the following, the multi-user definitions of the EUF-CMA and SUF-CMA security notions are defined, respectively $N$-MU-EUF-CMA and $N$-MU-SUF-CMA. The single-user variant of these security notions can be seen as a special case of the multi-user definitions in which the adversary is only provided with one public key.
|
|
|
|
\begin{definition}[$N$-MU-EUF-CMA]
|
|
Let $SIG = (\keygen, \sign, \verify)$ be a digital signature scheme and $N$ be an integer. Let the $N$-MU-EUF-CMA game be defined in figure \ref{game:mu-euf-cma}. $SIG$ is $N$-MU-EUF-CMA secure if for all ppt adversaries $\adversary{A}$, we have
|
|
|
|
\[ \advantage{SIG,\adversary{A}}{\textsf{$N$-MU-EUF-CMA}}(\secparamter) \assign \prone{\textsf{$N$-MU-EUF-CMA}^{\adversary{A}}} \leq negl(\secparamter). \]
|
|
\end{definition}
|
|
|
|
\begin{figure}[h]
|
|
\hrule
|
|
\normalsize
|
|
\vspace{1mm}
|
|
\begin{algorithmic}
|
|
\Statex \underline{\game $\text{$N$-MU-EUF-CMA}$}
|
|
\State \textbf{for} $i \in \{1,2,...,N\}$
|
|
\State \quad $(\pubkey_i, \privkey_i) \randomassign \keygen(1^\secparamter)$
|
|
\State $(\m^*, \signature^*) \randomassign \adversary{A}^{\sign(\inp, \inp)}(\pubkey_1, \pubkey_2, ..., \pubkey_n)$
|
|
\State \Return $\exists i \in \{1,2,...,N\}: \verify(\pubkey_i, \m^*, \signature^*) \test 1 \wedge (\pubkey_i, \m^*) \notin M$
|
|
\end{algorithmic}
|
|
\vspace{2mm}
|
|
\begin{algorithmic}
|
|
\Statex \underline{\oracle \Osign($i \in \{1,2,...,N\}$, $\m \in \messagespace$)}
|
|
\State $\signature \randomassign \sign(\privkey_i, \m)$
|
|
\State $M \assign M \cup \{(\pubkey_i, \m)\}$
|
|
\State \Return $\signature$
|
|
\end{algorithmic}
|
|
\hrule
|
|
\caption{$N$-MU-EUF-CMA Security Game}
|
|
\label{game:mu-euf-cma}
|
|
\end{figure}
|
|
|
|
\begin{definition}[$N$-MU-SUF-CMA]
|
|
Let $SIG = (\keygen, \sign, \verify)$ be a digital signature scheme and $N$ be an integer. Let the $N$-MU-SUF-CMA game be defined in figure \ref{game:mu-suf-cma}. $SIG$ is $N$-MU-SUF-CMA secure if for all ppt adversaries $\adversary{A}$, we have
|
|
|
|
\[ \advantage{SIG,\adversary{A}}{\textsf{$N$-MU-SUF-CMA}}(\secparamter) \assign \prone{\textsf{$N$-MU-SUF-CMA}^{\adversary{A}}} \leq negl(\secparamter). \]
|
|
\end{definition}
|
|
|
|
\begin{figure}[h]
|
|
\hrule
|
|
\normalsize
|
|
\vspace{1mm}
|
|
\begin{algorithmic}
|
|
\Statex \underline{\game $\text{$N$-MU-SUF-CMA}$}
|
|
\State \textbf{for} $i \in \{1,2,...,N\}$
|
|
\State \quad $(\pubkey_i, \privkey_i) \randomassign \keygen(1^\secparamter)$
|
|
\State $(\m^*, \signature^*) \randomassign \adversary{A}^{\sign(\inp, \inp)}(\pubkey_1, \pubkey_2, ..., \pubkey_n)$
|
|
\State \Return $\exists i \in \{1,2,...,N\}: \verify(\pubkey_i, \m^*, \signature^*) \test 1 \wedge (\pubkey_i, \m^*, \signature^*) \notin M$
|
|
\end{algorithmic}
|
|
\vspace{2mm}
|
|
\begin{algorithmic}
|
|
\Statex \underline{\oracle \Osign($i \in \{1,2,...,N\}$, $\m \in \messagespace$)}
|
|
\State $\signature \randomassign \sign(\privkey_i, \m)$
|
|
\State $M \assign M \cup \{(\pubkey_i, \m, \signature)\}$
|
|
\State \Return $\signature$
|
|
\end{algorithmic}
|
|
\hrule
|
|
\caption{$N$-MU-SUF-CMA Security Game}
|
|
\label{game:mu-suf-cma}
|
|
\end{figure}
|
|
|
|
The $N$-MU-EUF-NMA security game is similar to the $N$-MU-EUF-CMA game. The only difference is that the adversary does not has access to an oracle to obtain valid signatures for arbitrary messages. Again the EUF-NMA security notation is a special case of the $N$-MU-EUF-NMA security notation with $N=1$.
|
|
|
|
\begin{definition}[$N$-MU-EUF-NMA]
|
|
Let $SIG = (\keygen, \sign, \verify)$ be a digital signature scheme and $N$ be an integer. Let the $N$-MU-EUF-NMA game be defined in figure \ref{game:mu-uf-nma}. $SIG$ is $N$-MU-EUF-NMA secure if for all ppt adversaries $\adversary{A}$, we have
|
|
|
|
\[ \advantage{SIG,\adversary{A}}{\textsf{$N$-MU-EUF-NMA}}(\secparamter) \assign \prone{\textsf{$N$-MU-EUF-NMA}^{\adversary{A}}} \leq negl(\secparamter). \]
|
|
\end{definition}
|
|
|
|
\begin{figure}[h]
|
|
\hrule
|
|
\vspace{1mm}
|
|
\begin{algorithmic}
|
|
\State \underline{\game $\text{$N$-MU-EUF-NMA}$}
|
|
\State \textbf{for} $i \in \{1,2,...,N\}$
|
|
\State \quad $(\pubkey_i, \privkey_i) \randomassign \keygen(1^\secparamter)$
|
|
\State $(\m^*, \signature^*) \randomassign \adversary{A}(\pubkey_1, \pubkey_2, \pubkey_n)$
|
|
\State \Return $\exists i \in \{1,2,...,N\}: \verify(\pubkey_i, \m^*, \signature^*) \test 1$
|
|
\end{algorithmic}
|
|
\hrule
|
|
\caption{$N$-MU-EUF-NMA Security Game}
|
|
\label{game:mu-uf-nma}
|
|
\end{figure}
|
|
|
|
\subsection{Security Assumptions}
|
|
|
|
This thesis proves the security of the EdDSA signature scheme using two assumptions. The single-user security of EdDSA can be proven using the discrete logarithm assumption, while the multi-user security of EdDSA requires the stronger one-more discrete logarithm assumption. Both security assumptions are presented in this section.
|
|
|
|
\subsubsection{Discrete Logarithm Problem}
|
|
|
|
\begin{definition}[Discrete Logarithm Problem]
|
|
Let $\group{G}$ be a cyclic group of order $L$ with a generator $\groupelement{B}$. The advantage of an adversary $\adversary{A}$ is defined as following:
|
|
|
|
\[ \advantage{\group{G}, \adversary{A}}{\textsf{DLog}} \assign \Pr[a \test a' | a \randomsample \field{L}; a' \randomassign \adversary{A}(a\groupelement{B})]. \]
|
|
\end{definition}
|
|
|
|
\subsubsection{One-More Discrete Logarithm}
|
|
|
|
The one-more discrete logarithm assumption is stronger than the discrete logarithm assumption. In this assumption the adversary is supplied with $N$ group elements and an oracle to obtain the discrete logarithm of up to $N-1$ group elements. The task of the adversary is to output the discrete logarithm for all supplied group elements.
|
|
|
|
\begin{definition}[One-More Discrete Logarithm Problem \cite{JC:BNPS03}]
|
|
Let $\group{G}$ be a cyclic group of order $L$ with a generator $\groupelement{B}$. Let the one-more discrete logarithm game be defined in figure \ref{game:om-dlog}. The advantage of an adversary $\adversary{A}$ is defined as following:
|
|
|
|
\[ \advantage{\group{G}, \adversary{A}}{\textsf{OM-DLog}} \assign \prone{\textsf{OM-DLog}^{\adversary{A}}}. \]
|
|
\end{definition}
|
|
|
|
\begin{figure}[h]
|
|
\hrule
|
|
\vspace{1mm}
|
|
\begin{multicols}{2}
|
|
\begin{algorithmic}
|
|
\Statex \underline{\game OM-DLog}
|
|
\State $\pset{L} \assign \{\}$
|
|
\State $N \assign 0$
|
|
\State $(a'_1, ..., a'_N) \randomassign \adversary{A}^{DL(\inp), CH()}()$
|
|
\State \Return $\forall i \in \{1,2,...,N\}: a_i \test a'_i$
|
|
\end{algorithmic}
|
|
\columnbreak
|
|
\begin{algorithmic}
|
|
\Statex \underline{\oracle CH()}
|
|
\State $N \assign N + 1$
|
|
\State $a_i \randomsample \field{L}$
|
|
\State $\groupelement{A_i} \assign a_i \groupelement{B}$
|
|
\State $\pset{L} \assign \pset{L} \cup \{a_i\}$
|
|
\State \Return $\groupelement{A_i}$
|
|
\end{algorithmic}
|
|
\end{multicols}
|
|
\vspace{1mm}
|
|
\hrule
|
|
\caption{One-More Discrete Logarithm}
|
|
\label{game:om-dlog}
|
|
\end{figure}
|
|
|
|
The DL oracle outputs the discrete logarithm of the input element in respect to the generator $\groupelement{B}$ and is allowed to be called $N - 1$ times. |