chap03-sec04.tex

% !TEX root = ../zeth-protocol-specification.tex

\section{Instantiate $\sigscheme_{\otsig}$}\label{instantiation:otsig}

\zeth~uses the one-time Schnorr-based signature scheme introduced by Bellare and Shoup~\cite{bellare2007two} for its long proven security, simplicity, speed and size. Its security relies on the one-more discrete log problem (see~\cref{preliminaries:def:om-dlog}) and the collision resistance of the underlying hash function $\crh$ (see~\cref{preliminaries:def:collision-resistance}) that we instantiate with \sha{256}.

Note that no signature operations or data are used in the arithmetic circuit describing the \zeth~statement. Hence the curve used for the signature scheme can be chosen independently of \Curve (the scalar field of which is used for the arithmetic circuit, and consequently for commitments and bit string encodings described in \cref{instantiation:prf-comm-crh} and \cref{instantiation:mkhash}). $\BNCurve$ is used since it is supported by the \evm, in the form of precompiled contracts. This allows a gas-efficient implementation in the \mixer~contract.

This one-time signature scheme (see~\cref{preliminaries:def:ot-sig}) is defined by the two-tier signature scheme over a cyclic group $(p, \gset, \langle \ggen \rangle, \otimes)$.
In the two-tier signature scheme, the hash function $\crh$ only needs to be collision resistant (the random oracle model is not used). Similarly, the variable $\hk$ represents the key of the hash function (a particular instance).

To turn this two-tier signature scheme into a one-time signature scheme, one simply has to define the one-time signature key generation \kgen~as the combination of both primary and secondary key generations of the two-tier (see~\cite[Section 6]{bellare2007two}). The one-time signing key (respectively verification key) of the one time signature scheme is defined as both the primary and secondary signing key (respectively verification key) of the two-tier scheme,~\cref{instantiation:fig:ots-from-two-tier-sig}

% Local macros to align with Bellare and Shoup notations in
% https://eprint.iacr.org/2007/273.pdf
\newcommand{\ppk}{\ensuremath{\varstyle{ppk}}\xspace}
\newcommand{\psk}{\ensuremath{\varstyle{psk}}\xspace}
\newcommand{\spk}{\ensuremath{\varstyle{spk}}\xspace}
\newcommand{\ssk}{\ensuremath{\varstyle{ssk}}\xspace}

\begin{figure*}[ht]
    \begin{minipage}[t]{0.33\textwidth}
        \begin{align*}
            & \underline{\kgen(\secparam):} \\
            & \hk \sample \BB^{\kl} \\
            & \ggen \sample \gset^* \\
            & x \sample \FFx{p} \\
            & \ppk = (\hk, \ggen, \groupenc{x}) \\
            & \psk = (\hk, \ggen, x) \\
            & y \sample \FFx{p} \\
            & \spk =  \groupenc{y} \\
            & \ssk = (y, \groupenc{y}) \\
            & \pk = (\ppk, \spk) \\
            & \sk = (\psk, \ssk) \\
        \end{align*}
    \end{minipage}%
    \begin{minipage}[t]{0.33\textwidth}
        \begin{align*}
            & \underline{\sig(\sk, \msg):}\\
            & \hk, \ggen, x = \sk.\psk \\
            & y, \groupenc{y} = \sk.\ssk \\
            & c = \crh(\hk, \groupenc{y} \concat \msg) \\
            & \sigma = y \bmod p \\
            & \sigma\ \text{+=}\ c \cdot x \bmod p \\
            & \pcreturn \sigma
        \end{align*}
    \end{minipage}%
    \begin{minipage}[t]{0.33\textwidth}
        \begin{align*}
        & \underline{\verify(\pk, \msg, \sigma):}\\
        &  \hk, \ggen, \groupenc{x} = \pk.\ppk \\
        &  \groupenc{y} = \pk.\spk \\
        &  c = \crh(\hk, \groupenc{y} \concat \msg)\\
        &  \pcif \sigma = \groupenc{y} \otimes c \cdot \groupenc{x} \pcthen \\
        &  \pcind \pcreturn 1\\
        &  \pcelse\\
        &  \pcind \pcreturn 0\\
        &  \pcendif
        \end{align*}
    \end{minipage}
\caption{One-time signature scheme from two tier Schnorr based signature scheme by Bellare and Shoup~\cite{bellare2007two}}\label{instantiation:fig:ots-from-two-tier-sig}
\end{figure*}

\subsection{Security requirements satisfaction}

We now prove that this signature scheme satisfies all the security requirements listed in~\cref{zeth-protocol:sec-req}.

\begin{theorem}
    The One-Time Schnorr signature is strongly unforgeable under chosen-message attacks $(\sufcma)$ assuming that the \omdlog~problem is hard in \gset~and that the hash function $\crh$ is collision resistant.

\begin{proof}
    See~\cite[Theorems 5.1, 5.2 and 6.1]{bellare2007two}.
\end{proof}

\end{theorem}

\subsection{Data types}\label{instantiation:otsig:data-types}

We now describe the data types and operations associated with this signature scheme.

\begin{description}
    \item[\vkOtsDType] Denotes the verification key associated with the one-time signature scheme.
        \begin{table}[H]
        \centering
        \begin{tabular}{cp{20em}c}
            Field & Description & Data type\\ \toprule
            $\ppk$ & Encoding of the scalar $x$ in the group & $\gsetBN$ \\ \midrule
            $\spk$ & Encoding of the scalar $y$ in the group & $\gsetBN$ \\ \bottomrule
        \end{tabular}
        \caption{\vkOtsDType~data type}\label{instantiation:tab:vk-ots-dtype}
        \end{table}
    \item[\skOtsDType] Denotes the signing key associated with the one-time signature scheme.
        \begin{table}[H]
        \centering
        \begin{tabular}{cp{20em}c}
            Field & Description & Data type\\ \toprule
            $\psk$ & Scalar element $x$ & $\FFx{\rBN}$ \\ \midrule
            $\ssk$ & Scalar element $y$ and its encoding in the group & $\FFx{\rBN} \times \gsetBN$ \\ \midrule
        \end{tabular}
        \caption{\skOtsDType~data type}\label{instantiation:tab:sk-ots-dtype}
        \end{table}
    \item[\sigOtsDType] Denotes the signature data type associated with the one-time signature scheme. $\sigOtsDType$ is an alias for $\FFx{\rBN}$.
\end{description}