papers/lux-hybrid-pq-architecture/sections/03-dual-signature-construction.tex

\section{Dual-Signature Construction}

\label{sec:dual-sig}

\subsection{Construction}

Let $\textsf{BLS} = (\textsf{BLS.KeyGen}, \textsf{BLS.Sign}, \textsf{BLS.Verify})$ be
BLS12-381 signatures~\cite{boneh2001bls} and $\textsf{PQ} = (\textsf{PQ.KeyGen},
\textsf{PQ.Sign}, \textsf{PQ.Verify})$ be ML-DSA-65~\cite{fips204}.

\begin{definition}[Hybrid signature scheme]
\label{def:hybrid-sig}
The hybrid signature scheme $\textsf{Hyb} = (\textsf{Hyb.KeyGen}, \textsf{Hyb.Sign},
\textsf{Hyb.Verify})$ is defined as:
\begin{itemize}[leftmargin=2em]
  \item $\textsf{Hyb.KeyGen}(1^\lambda)$: Run $(pk_B, sk_B) \leftarrow \textsf{BLS.KeyGen}(1^\lambda)$
        and $(pk_P, sk_P) \leftarrow \textsf{PQ.KeyGen}(1^\lambda)$.
        Output $pk = (pk_B, pk_P)$ and $sk = (sk_B, sk_P)$.
  \item $\textsf{Hyb.Sign}(sk, m)$: Compute $\sigma_B \leftarrow \textsf{BLS.Sign}(sk_B, m)$
        and $\sigma_P \leftarrow \textsf{PQ.Sign}(sk_P, m)$.
        Output $\sigma = (\sigma_B, \sigma_P)$.
  \item $\textsf{Hyb.Verify}(pk, m, \sigma)$: Parse $\sigma = (\sigma_B, \sigma_P)$
        and $pk = (pk_B, pk_P)$. Accept iff
        $\textsf{BLS.Verify}(pk_B, m, \sigma_B) = 1$ \textbf{and}
        $\textsf{PQ.Verify}(pk_P, m, \sigma_P) = 1$.
\end{itemize}
\end{definition}

The AND-composition in verification is critical: the verifier rejects unless
\emph{both} signatures are valid.

\subsection{Security Proof Sketch}

\begin{theorem}[Hybrid EUF-CMA security]
\label{thm:hybrid-euf}
If $\textsf{BLS}$ is EUF-CMA secure under the co-CDH assumption in the random oracle
model, and $\textsf{PQ}$ is EUF-CMA secure under the Module-LWE assumption (NIST
security level 3), then $\textsf{Hyb}$ is EUF-CMA secure as long as at least one
of the two assumptions holds.
\end{theorem}

\begin{proof}[Proof sketch]
Suppose adversary $\mathcal{A}$ forges a hybrid signature $\sigma^* = (\sigma_B^*,
\sigma_P^*)$ on message $m^*$. By the AND-verification rule, both $\sigma_B^*$ and
$\sigma_P^*$ must be valid. Therefore $\mathcal{A}$ has simultaneously:
\begin{enumerate}
  \item Forged a BLS signature (breaking co-CDH), \emph{and}
  \item Forged an ML-DSA signature (breaking Module-LWE).
\end{enumerate}

By contrapositive: if co-CDH holds, then $\sigma_B^*$ cannot be forged, so the
hybrid scheme is secure regardless of ML-DSA's status. If Module-LWE holds, then
$\sigma_P^*$ cannot be forged, so the hybrid scheme is secure regardless of BLS's
status. The hybrid is therefore at least as secure as the stronger of the two
components.

More formally, let $\varepsilon_{\text{Hyb}}$ be the advantage of any PPT adversary
against $\textsf{Hyb}$. Then:
\[
  \varepsilon_{\text{Hyb}} \leq \min(\varepsilon_{\text{BLS}}, \varepsilon_{\text{PQ}})
\]
where $\varepsilon_{\text{BLS}}$ and $\varepsilon_{\text{PQ}}$ are the advantages
against the individual schemes. This follows directly from the fact that a successful
hybrid forgery implies successful forgery against \emph{both} components.
\end{proof}

\begin{remark}
The inequality $\varepsilon_{\text{Hyb}} \leq \min(\varepsilon_{\text{BLS}},
\varepsilon_{\text{PQ}})$ shows the hybrid is \emph{strictly stronger} than either
component in the transition period where we are uncertain which assumption is
stronger. It can never be weaker.
\end{remark}

\subsection{Aggregation Compatibility}

BLS signatures support aggregation: $n$ individual signatures on the same message
compress to a single 48-byte aggregate signature. ML-DSA does not support aggregation
natively. We address this asymmetry in the consensus layer:

\begin{enumerate}[leftmargin=2em]
  \item \textbf{Per-block}: BLS aggregate signature (48 bytes) for fast verification.
  \item \textbf{Per-epoch}: STARK proof compressing $n$ ML-DSA signatures into
        $\sim$200 bytes, verified once per epoch.
\end{enumerate}

This two-tier approach preserves BLS aggregation benefits while adding post-quantum
security at the epoch boundary.

%% ========================================================================
%%  4. HYBRID KEY EXCHANGE
%% ========================================================================