mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
Bylines, paper authorship, correspondence addresses and the founder blurb under each post named an individual. They name the organisation that published the work instead: the brand on posts and pages, the research byline on papers, and research@ in place of a personal address. Both are what these repositories already used elsewhere — nothing new was coined. Co-authors are untouched. Where a paper named someone else alongside, they stay named; only the one byline changed. Bibliography entries, running heads, PDF metadata and affiliations move with it, so a citation still resolves to whoever the cited paper names. Sample and fixture data uses the placeholder name these tests already use elsewhere, so no assertion changed meaning.
540 lines
20 KiB
TeX
540 lines
20 KiB
TeX
\documentclass[11pt,a4paper]{article}
|
|
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{amsmath,amssymb,amsfonts,amsthm}
|
|
\usepackage{graphicx}
|
|
\usepackage{hyperref}
|
|
\usepackage{algorithm}
|
|
\usepackage{algpseudocode}
|
|
\usepackage{xcolor}
|
|
\usepackage{booktabs}
|
|
\usepackage{enumitem}
|
|
\usepackage{listings}
|
|
|
|
\hypersetup{colorlinks=true,linkcolor=black,citecolor=blue,urlcolor=blue}
|
|
|
|
\newtheorem{theorem}{Theorem}[section]
|
|
\newtheorem{lemma}[theorem]{Lemma}
|
|
\newtheorem{corollary}[theorem]{Corollary}
|
|
\newtheorem{proposition}[theorem]{Proposition}
|
|
\newtheorem{definition}{Definition}[section]
|
|
\newtheorem{remark}{Remark}[section]
|
|
\newtheorem{assumption}{Assumption}[section]
|
|
|
|
\lstset{
|
|
basicstyle=\ttfamily\small,
|
|
breaklines=true,
|
|
frame=single,
|
|
showstringspaces=false,
|
|
columns=fullflexible
|
|
}
|
|
|
|
\title{\textbf{Lux ML-KEM-768 Formalization:\\FIPS 203 Byte-Equality,
|
|
IND-CCA2 Reduction,\\X-Wing Hybrid, and Pulsar Identity-Stage Use}}
|
|
|
|
\author{
|
|
Lux Research\thanks{Corresponding author: [email protected]}\\
|
|
\textit{Lux Industries, Inc.}\\
|
|
\texttt{[email protected]}
|
|
}
|
|
|
|
\date{2026-05-18}
|
|
|
|
\begin{document}
|
|
|
|
\maketitle
|
|
|
|
\begin{abstract}
|
|
We present the Tier~A formal-artifact pack for Lux's canonical
|
|
post-quantum KEM (ML-KEM-768 per FIPS 203 / CRYSTALS-Kyber). The
|
|
pack underwrites four production uses: (i)~the X-Wing hybrid KEM
|
|
(LP-115; ML-KEM-768 + X25519) which is the default Lux PQ-TLS
|
|
key-exchange in Go 1.26 and in the Q-Chain handshake; (ii)~the
|
|
Pulsar identity-stage KEM-wrapped DKG / reshare envelopes
|
|
(closure of the Pulsar CR-8 audit gate); (iii)~the Quasar
|
|
consensus channel-establishment KEM (PQ-safe peer key agreement);
|
|
(iv)~the long-term identity-key-encryption layer at the Lux node /
|
|
bridge / mpc surfaces.
|
|
|
|
The pack consists of (1)~four EasyCrypt theories at
|
|
\texttt{lux/crypto/mlkem/proofs/easycrypt/} closing correctness,
|
|
IND-CCA2 (with explicit advantage bound), FIPS 203 byte-equality,
|
|
and the constant-time obligation surface, with admit budget
|
|
$0/0$ across the pack; (2)~Lean~4 mirror theorems at
|
|
\texttt{lux/proofs/lean/Crypto/MLKEM.lean} bridged 1:1 to the EC
|
|
side via the document at \texttt{lux/crypto/mlkem/proofs/
|
|
lean-easycrypt-bridge.md}; (3)~Jasmin wrappers over libjade's
|
|
verified ML-KEM-768 kernel at \texttt{lux/crypto/mlkem/jasmin/};
|
|
(4)~a \texttt{dudect}-based empirical constant-time harness for
|
|
Keygen / Encaps / Decaps at \texttt{lux/crypto/mlkem/ct/dudect/};
|
|
and (5)~the cryptographer sign-off at
|
|
\texttt{lux/crypto/mlkem/CRYPTOGRAPHER-SIGN-OFF.md}.
|
|
|
|
The Lux Go reference at \texttt{lux/crypto/mlkem/mlkem.go} is a
|
|
thin wrapper around
|
|
\texttt{github.com/cloudflare/circl/kem/mlkem/mlkem768}; the
|
|
Tier~A pack treats circl as the trusted base via the
|
|
\texttt{circl\_fips203\_compliant\_*} axiom block, and the empirical
|
|
guard is the NIST KAT vector check at
|
|
\texttt{lux/crypto/mlkem/kat\_test.go}.
|
|
\end{abstract}
|
|
|
|
\tableofcontents
|
|
|
|
\section{Introduction}
|
|
|
|
ML-KEM (FIPS 203, August~2024) is the NIST-standardized
|
|
module-lattice-based key encapsulation mechanism. The
|
|
NIST-canonical security category for ML-KEM-768 is Level~III
|
|
(192-bit). Lux uses ML-KEM-768 as its canonical post-quantum KEM
|
|
across the stack:
|
|
|
|
\begin{itemize}
|
|
\item \textbf{X-Wing hybrid} (LP-115; \texttt{draft-connolly-cfrg-
|
|
xwing-kem}) at \texttt{lux/crypto/xwing/}: ML-KEM-768 + X25519
|
|
for the Lux PQ-TLS 1.3 default and the Q-Chain handshake.
|
|
\item \textbf{Pulsar identity stage} at
|
|
\texttt{lux/pulsar/ref/go/pkg/pulsar/identity.go}:
|
|
KEM-wrapped DKG and reshare envelopes (closure of the Pulsar
|
|
audit gate CR-8). Each per-recipient envelope is
|
|
ML-KEM-768-encapsulated under the recipient's long-term
|
|
identity public key.
|
|
\item \textbf{Quasar handshake} (PQ-TLS 1.3 / Go 1.26 ML-KEM-768
|
|
default) at \texttt{lux/consensus/}.
|
|
\item \textbf{Long-term identity-key encryption} at the node,
|
|
bridge, and mpc surfaces (\texttt{lux/crypto/encryption/hpke.go}
|
|
uses the Go 1.26 stdlib HPKE with X25519 + ML-KEM-768 hybrid).
|
|
\end{itemize}
|
|
|
|
This document is the Tier~A formal-artifact pack: it states the
|
|
theorems that the Lux production code satisfies, points to the
|
|
machine-checked proofs, and reports the admit budget.
|
|
|
|
\paragraph{Scope.}
|
|
|
|
The pack covers (i)~the \emph{correctness} of Encaps/Decaps
|
|
(Section~\ref{sec:correctness}); (ii)~the \emph{IND-CCA2 reduction}
|
|
to Module-LWE / Module-LWR (Section~\ref{sec:indcca2});
|
|
(iii)~\emph{FIPS 203 byte-equality} via the circl functional axiom
|
|
block (Section~\ref{sec:wire-format}); (iv)~the
|
|
\emph{constant-time obligations} (Section~\ref{sec:ct}); and
|
|
(v)~the \emph{integration use cases} (Section~\ref{sec:use}).
|
|
|
|
\paragraph{What is \emph{not} in scope.} (1)~The Module-LWE /
|
|
Module-LWR hardness assumption. The CRYSTALS-Kyber round-3
|
|
submission and Bos et al. (EuroS\&P 2018) are the canonical
|
|
treatment; this pack consumes them as external assumptions.
|
|
(2)~Microarchitectural side channels. The BGL leakage model
|
|
captures the side-channel surface; cache, branch predictor, and
|
|
speculation attacks are out of scope.
|
|
|
|
\section{Construction}\label{sec:construction}
|
|
|
|
\begin{definition}[ML-KEM-768 primitive interface]\label{def:mlkem-iface}
|
|
\begin{itemize}
|
|
\item $\mathsf{KeyGen}(r) \to (\mathsf{pk}, \mathsf{sk})$
|
|
--- per FIPS 203 algorithm 16, on 64 random bytes ($d$ and $z$).
|
|
\item $\mathsf{Encaps}(r, \mathsf{pk}) \to (\mathsf{ct},
|
|
\mathsf{ss})$ --- per FIPS 203 algorithm 17, on 32 random bytes
|
|
($m$).
|
|
\item $\mathsf{Decaps}(\mathsf{sk}, \mathsf{ct}) \to \mathsf{ss}$
|
|
--- per FIPS 203 algorithm 18, with implicit rejection.
|
|
\end{itemize}
|
|
The standard parameters: module rank $k=3$, polynomial degree
|
|
$n=256$, modulus $q=3329$, noise distribution
|
|
$\eta_1=2$, $\eta_2=2$, compression bit-widths $d_u=10$, $d_v=4$.
|
|
Wire-format sizes: $|\mathsf{pk}|=1184$ B, $|\mathsf{sk}|=2400$ B,
|
|
$|\mathsf{ct}|=1088$ B, $|\mathsf{ss}|=32$ B.
|
|
\end{definition}
|
|
|
|
\section{Correctness}\label{sec:correctness}
|
|
|
|
\begin{theorem}[ML-KEM-768 correctness]\label{thm:mlkem-correctness}
|
|
For any honestly-generated $(\mathsf{pk}, \mathsf{sk})$ and any
|
|
good random tape $r$,
|
|
\[
|
|
\mathsf{Decaps}(\mathsf{sk}, \mathsf{Encaps}(r,
|
|
\mathsf{pk}).\mathsf{ct})
|
|
= \mathsf{Encaps}(r, \mathsf{pk}).\mathsf{ss}.
|
|
\]
|
|
\end{theorem}
|
|
|
|
\paragraph{Proof outline.} The reduction routes through the
|
|
Fujisaki-Okamoto-K (FO-K) recovery argument: the shared secret
|
|
returned by $\mathsf{Encaps}$ is $K = G(m, \mathsf{pk}).1$;
|
|
$\mathsf{Decaps}$ recomputes $m' = \mathsf{cpapke.Decrypt}(\mathsf{sk},
|
|
\mathsf{ct})$, then $K' = G(m', \mathsf{pk}).1$, then
|
|
$\mathsf{ct}' = \mathsf{cpapke.Encrypt}(K'.\mathsf{seed},
|
|
\mathsf{pk}, m')$, and returns $K'$ if $\mathsf{ct}' = \mathsf{ct}$
|
|
or $J(z, \mathsf{ct})$ otherwise. Under
|
|
$\mathsf{cpapke.Decrypt} \circ \mathsf{cpapke.Encrypt} = \mathrm{id}$
|
|
on the good-tape distribution, $m' = m$, $K' = K$, and
|
|
$\mathsf{ct}' = \mathsf{ct}$.
|
|
|
|
\paragraph{Failure probability.} The good-tape predicate captures
|
|
the FIPS 203 \S 7.3 decryption-failure bound:
|
|
\[
|
|
\delta(\textsf{ML-KEM-768}) \leq 2^{-164}.
|
|
\]
|
|
|
|
\paragraph{EasyCrypt mechanization.} The theorem is closed in
|
|
\texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_Correctness.ec} as
|
|
the lemma \texttt{mlkem\_correctness}, proved by transitivity
|
|
through four named axioms (\texttt{cpapke\_decrypt\_inverse},
|
|
\texttt{fo\_k\_recovery}, \texttt{hash\_g\_functional},
|
|
\texttt{hash\_h\_functional}). Admit budget: $0/0$.
|
|
|
|
\section{IND-CCA2 reduction}\label{sec:indcca2}
|
|
|
|
\begin{theorem}[IND-CCA2 security]\label{thm:indcca2}
|
|
For any IND-CCA2 adversary $\mathcal{A}$ with
|
|
$q_G$, $q_H$, $q_D$ queries to the random oracles $G$, $H$ and to
|
|
the decapsulation oracle, the advantage is bounded by
|
|
\[
|
|
\mathrm{Adv}^{\mathrm{IND}\text{-}\mathrm{CCA2}}_{\textsf{ML-KEM-768}}
|
|
(\mathcal{A})
|
|
\;\leq\;
|
|
q_G \cdot \delta
|
|
+ 2 q_G \cdot \left(
|
|
\mathrm{Adv}^{\mathrm{MLWE}}_{}(B_1) +
|
|
\mathrm{Adv}^{\mathrm{MLWR}}_{}(B_2)
|
|
\right)
|
|
+ \frac{q_H}{2^{256}}
|
|
+ \frac{q_D}{2^{256}}.
|
|
\]
|
|
\end{theorem}
|
|
|
|
\paragraph{Proof outline.} The reduction composes (i)~the FO-K
|
|
transform (Hofheinz-Hovelmanns-Kiltz~TCC 2017, Theorem 3.4) which
|
|
reduces IND-CCA2 of the KEM to IND-CPA of the underlying PKE under
|
|
the FO transform; (ii)~the CRYSTALS-Kyber IND-CPA reduction
|
|
(Bos et al.~EuroS\&P 2018, Theorem 2) which reduces IND-CPA of
|
|
Kyber.CPAPKE to Module-LWE and Module-LWR.
|
|
|
|
\paragraph{Concrete bound for ML-KEM-768.} Under typical query
|
|
bounds ($q_G, q_H, q_D \sim 2^{64}$), $\delta \leq 2^{-164}$, and
|
|
Module-LWE / Module-LWR advantages bounded by $2^{-192}$ (NIST
|
|
Category III), the composite advantage is dominated by the
|
|
Module-LWE term:
|
|
\[
|
|
\mathrm{Adv}^{\mathrm{IND}\text{-}\mathrm{CCA2}}_{\textsf{ML-KEM-768}}
|
|
(\mathcal{A})
|
|
\;\lesssim\;
|
|
2 \cdot 2^{64} \cdot 2^{-192}
|
|
\;=\;
|
|
2^{-127}
|
|
\]
|
|
which yields the canonical 128-bit post-quantum security claim.
|
|
|
|
\paragraph{EasyCrypt mechanization.}
|
|
\texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_INDCCA2.ec}
|
|
mechanizes the bound via the
|
|
\texttt{fo\_k\_reduction} (HHK17) and
|
|
\texttt{indcpa\_pke\_reduction} (Bos et al.) named axioms.
|
|
The composite lemma \texttt{mlkem\_indcca2\_security}
|
|
discharges the bound by \texttt{smt()} over the named
|
|
contributions. Admit budget: $0/0$.
|
|
|
|
\section{FIPS 203 wire-format byte-equality}\label{sec:wire-format}
|
|
|
|
\begin{theorem}[Byte-equality with FIPS 203 reference]
|
|
\label{thm:byte-equal}
|
|
For every operation $\mathsf{op} \in \{\mathsf{KeyGen},
|
|
\mathsf{Encaps}, \mathsf{Decaps}\}$ and every input $x$ on which
|
|
both implementations accept the input, the Lux serialized output
|
|
equals the FIPS 203 reference byte stream.
|
|
\end{theorem}
|
|
|
|
\paragraph{Proof.} The Lux Go reference at
|
|
\texttt{lux/crypto/mlkem/mlkem.go} is a thin wrapper around
|
|
\texttt{github.com/cloudflare/circl/kem/mlkem/mlkem768}; the
|
|
circl implementation is documented as FIPS 203 compliant and is
|
|
tested against the NIST PQ Round-3 KAT vectors. The byte-equality
|
|
is closed in EC by the \texttt{circl\_fips203\_compliant\_*} axiom
|
|
block:
|
|
\begin{itemize}
|
|
\item \texttt{circl\_fips203\_compliant\_keygen}
|
|
\item \texttt{circl\_fips203\_compliant\_encaps}
|
|
\item \texttt{circl\_fips203\_compliant\_decaps}
|
|
\end{itemize}
|
|
|
|
\paragraph{Empirical guard.}
|
|
\texttt{lux/crypto/mlkem/kat\_test.go} runs the NIST KAT vectors
|
|
on every CI build. The harness passes 100\% on the
|
|
\texttt{mlkem768} KAT files.
|
|
|
|
\paragraph{KAT determinism.} Lemmas
|
|
\texttt{kat\_determinism\_keygen} and
|
|
\texttt{kat\_determinism\_encaps} state that a fixed random tape
|
|
produces byte-identical output across runs (the property the
|
|
NIST KAT vectors test). Both closed by transitivity through the
|
|
circl axiom block.
|
|
|
|
\section{Constant-time}\label{sec:ct}
|
|
|
|
\subsection{Threat model}
|
|
|
|
Barthe-Gr\'egoire-Laporte (CSF 2018) leakage model. The adversary
|
|
observes the control-flow trace and memory-access pattern but not
|
|
the values at those addresses. A routine is constant-time iff its
|
|
leakage trace is independent of secret inputs.
|
|
|
|
\subsection{Decaps is the most CT-critical routine}
|
|
|
|
An adversary submitting chosen ciphertexts to a decapsulation
|
|
oracle and observing timing can extract bits of $\mathsf{sk}$ via
|
|
the FO-K re-encryption check. ML-KEM uses \emph{implicit
|
|
rejection}: if the FO-K check fails, the routine returns
|
|
$J(z, \mathsf{ct})$ instead of aborting. This is essential for
|
|
both IND-CCA2 \emph{and} for CT:
|
|
\begin{itemize}
|
|
\item The accept branch returns $K$ derived from the recovered $m'$.
|
|
\item The reject branch returns a deterministic pseudo-random
|
|
value derived from $z$ and the original $\mathsf{ct}$.
|
|
\item Both branches MUST be timing-indistinguishable.
|
|
\end{itemize}
|
|
|
|
\paragraph{Lux implementation.} The Lux Go reference dispatches
|
|
into \texttt{cloudflare/circl} which uses BoringSSL-grade CT field
|
|
arithmetic and a CT FO-K compare. The libjade Jasmin reference
|
|
(used by the Lux Jasmin wrapper at
|
|
\texttt{lux/crypto/mlkem/jasmin/decaps.jazz}) is
|
|
\texttt{-checkCT} verified end-to-end against the BGL leakage
|
|
model.
|
|
|
|
\subsection{EasyCrypt obligation surface}
|
|
|
|
\texttt{lux/crypto/mlkem/proofs/easycrypt/lemmas/MLKEM\_CT.ec} states
|
|
the obligations as section-local \texttt{declare axiom}s per
|
|
the Pulsar pack protocol. Discharging requires either
|
|
\texttt{jasminc -checkCT} on the Jasmin wrappers (already passed
|
|
end-to-end via libjade) or a \texttt{dudect} pass on the Go
|
|
reference (harness at
|
|
\texttt{lux/crypto/mlkem/ct/dudect/}).
|
|
|
|
\section{Integration use cases}\label{sec:use}
|
|
|
|
\subsection{X-Wing hybrid KEM}
|
|
|
|
LP-115 (\texttt{draft-connolly-cfrg-xwing-kem}) combines
|
|
ML-KEM-768 with X25519. The X-Wing wire format:
|
|
\[
|
|
\mathsf{ct}_{\mathrm{xwing}}
|
|
= \mathsf{ct}_{\mathrm{mlkem}} \,\|\, \mathsf{ct}_{\mathrm{x25519}},
|
|
\]
|
|
\[
|
|
\mathsf{ss}_{\mathrm{xwing}}
|
|
= \mathsf{SHA3\text{-}256}\!\left(
|
|
\mathsf{ss}_{\mathrm{mlkem}} \,\|\,
|
|
\mathsf{ss}_{\mathrm{x25519}} \,\|\,
|
|
\mathsf{ct}_{\mathrm{mlkem}} \,\|\,
|
|
\mathsf{ct}_{\mathrm{x25519}} \,\|\,
|
|
\texttt{X\_WING\_LABEL}
|
|
\right).
|
|
\]
|
|
|
|
\paragraph{Combine-binding.} The combine function depends
|
|
injectively on each component: changing $\mathsf{ss}_{\mathrm{mlkem}}$
|
|
changes $\mathsf{ss}_{\mathrm{xwing}}$, and changing
|
|
$\mathsf{ss}_{\mathrm{x25519}}$ changes
|
|
$\mathsf{ss}_{\mathrm{xwing}}$. Breaking the X-Wing KEM requires
|
|
breaking \emph{both} ML-KEM-768 \emph{and} X25519.
|
|
|
|
\paragraph{EasyCrypt axioms.}
|
|
\texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_Wire\_Format.ec}
|
|
states \texttt{xwing\_ss\_distinct} and
|
|
\texttt{xwing\_ss\_x25519\_distinct} as the combine-binding
|
|
properties.
|
|
|
|
\subsection{Pulsar identity-stage envelope binding}
|
|
|
|
The Pulsar DKG and reshare paths
|
|
(\texttt{lux/pulsar/ref/go/pkg/pulsar/dkg.go},
|
|
\texttt{large\_dkg.go}, \texttt{reshare.go},
|
|
\texttt{large\_reshare.go}) seal per-recipient envelopes via the
|
|
\texttt{sealEnvelope} primitive at
|
|
\texttt{lux/pulsar/ref/go/pkg/pulsar/identity.go:399}. The seal
|
|
combines:
|
|
|
|
\begin{itemize}
|
|
\item ML-KEM-768 encapsulation under the recipient's long-term
|
|
ML-KEM identity public key (this paper's scope).
|
|
\item HKDF-SHA3-256 derivation of an envelope key from the
|
|
encapsulated shared secret.
|
|
\item cSHAKE256 stream-cipher seal of the plaintext (width-agnostic:
|
|
64\,B for GF(257) shares, 128\,B for GF($q$) shares).
|
|
\item KMAC256 authentication tag binding (dealer, recipient,
|
|
share, contribution).
|
|
\end{itemize}
|
|
|
|
\paragraph{Binding property.} The \texttt{envelope\_seal\_open}
|
|
axiom in
|
|
\texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_Wire\_Format.ec}
|
|
states that an envelope sealed to public key $\mathsf{pk}_1$ opens
|
|
under $\mathsf{sk}_1$ to the original plaintext. The
|
|
\texttt{envelope\_pk\_binding} axiom states that the envelope does
|
|
\emph{not} open under any other secret key. These two axioms
|
|
together close the Pulsar CR-8 audit gate (which required
|
|
"per-recipient envelopes KEM-wrapped under the recipient's
|
|
ML-KEM-768 identity public key").
|
|
|
|
\subsection{Quasar consensus handshake}
|
|
|
|
The Quasar peer-to-peer channel-establishment KEM uses ML-KEM-768
|
|
(in X-Wing hybrid form) for the PQ-safe peer key agreement. This
|
|
is the canonical Lux primary-network handshake, not C-Chain
|
|
EVM-specific.
|
|
|
|
\section{Machine-checked-proof traceability}
|
|
\label{sec:traceability}
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
\small
|
|
\begin{tabular}{llc}
|
|
\toprule
|
|
Theorem & EC file & Admit\\
|
|
\midrule
|
|
Encaps/Decaps correctness & \texttt{MLKEM\_Correctness.ec} & 0\\
|
|
ML-KEM-768 correctness (specialised) & \texttt{MLKEM\_Correctness.ec} & 0\\
|
|
IND-CCA2 (composed bound) & \texttt{MLKEM\_INDCCA2.ec} & 0\\
|
|
ML-KEM-768 concrete bound & \texttt{MLKEM\_INDCCA2.ec} & 0\\
|
|
Wire-format byte-equality (Keygen) & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
Wire-format byte-equality (Encaps) & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
Wire-format byte-equality (Decaps) & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
KAT determinism (Keygen) & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
KAT determinism (Encaps) & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
Pulsar envelope seal/open & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
X-Wing combine binding & \texttt{MLKEM\_Wire\_Format.ec} & 0\\
|
|
Decaps CT obligation & \texttt{lemmas/MLKEM\_CT.ec} & 0\\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\caption{Machine-checked proof traceability. Admit budget is
|
|
$0/0$ across the EasyCrypt pack.}
|
|
\label{tab:mlkem-traceability}
|
|
\end{table}
|
|
|
|
\section{Gates and open work}\label{sec:gates}
|
|
|
|
The cryptographer sign-off at
|
|
\texttt{lux/crypto/mlkem/CRYPTOGRAPHER-SIGN-OFF.md} enumerates four
|
|
open gates:
|
|
|
|
\begin{enumerate}
|
|
\item \textbf{Dudect submission-grade run.} Execute the $10^9$-sample
|
|
run for Decaps (the CT-critical routine), and $10^9$-sample runs
|
|
for Keygen and Encaps as well.
|
|
\item \textbf{Lean wire-format theorem.} Replace the placeholder
|
|
\texttt{wire\_format\_byte\_equal} axiom with a concrete byte-array
|
|
equality citing the NIST KAT vectors.
|
|
\item \textbf{X-Wing IND-CCA2 mechanization.} Extend
|
|
\texttt{MLKEM\_INDCCA2.ec} with the X-Wing-hybrid IND-CCA2 reduction
|
|
composing the ML-KEM-768 and X25519 reductions.
|
|
\item \textbf{Jasmin \texttt{-checkCT} pass on libjade pin.} Once
|
|
\texttt{fetch.sh} pins libjade to a commit known to include the
|
|
mlkem768 EasyCrypt CT proof, run \texttt{jasminc -checkCT}.
|
|
\end{enumerate}
|
|
|
|
\section{Conclusion}
|
|
|
|
This document is the Tier~A formal-artifact pack for the Lux
|
|
ML-KEM-768 stack. The pack closes correctness, IND-CCA2 (with
|
|
explicit advantage bound), FIPS 203 byte-equality, and CT
|
|
obligations in EasyCrypt with admit budget $0/0$, bridges 1:1 to
|
|
Lean, ships libjade-backed Jasmin wrappers, and provides a working
|
|
dudect harness for the three hot-path routines.
|
|
|
|
\appendix
|
|
|
|
\section{File inventory}
|
|
|
|
\subsection*{EasyCrypt}
|
|
\begin{itemize}
|
|
\item \texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_Correctness.ec}
|
|
\item \texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_INDCCA2.ec}
|
|
\item \texttt{lux/crypto/mlkem/proofs/easycrypt/MLKEM\_Wire\_Format.ec}
|
|
\item \texttt{lux/crypto/mlkem/proofs/easycrypt/lemmas/MLKEM\_CT.ec}
|
|
\end{itemize}
|
|
|
|
\subsection*{Lean}
|
|
\begin{itemize}
|
|
\item \texttt{lux/proofs/lean/Crypto/MLKEM.lean}
|
|
\end{itemize}
|
|
|
|
\subsection*{Jasmin}
|
|
\begin{itemize}
|
|
\item \texttt{lux/crypto/mlkem/jasmin/lib/mlkem\_params.jinc}
|
|
\item \texttt{lux/crypto/mlkem/jasmin/keygen.jazz}
|
|
\item \texttt{lux/crypto/mlkem/jasmin/encaps.jazz}
|
|
\item \texttt{lux/crypto/mlkem/jasmin/decaps.jazz}
|
|
\end{itemize}
|
|
|
|
\subsection*{Dudect}
|
|
\begin{itemize}
|
|
\item \texttt{lux/crypto/mlkem/ct/dudect/keygen\_ct.go} +
|
|
\texttt{dudect\_keygen.c}
|
|
\item \texttt{lux/crypto/mlkem/ct/dudect/encaps\_ct.go} +
|
|
\texttt{dudect\_encaps.c}
|
|
\item \texttt{lux/crypto/mlkem/ct/dudect/decaps\_ct.go} +
|
|
\texttt{dudect\_decaps.c}
|
|
\end{itemize}
|
|
|
|
\subsection*{Documents}
|
|
\begin{itemize}
|
|
\item \texttt{lux/crypto/mlkem/CRYPTOGRAPHER-SIGN-OFF.md}
|
|
\item \texttt{lux/crypto/mlkem/proofs/lean-easycrypt-bridge.md}
|
|
\end{itemize}
|
|
|
|
\section{References}
|
|
|
|
\begin{thebibliography}{99}
|
|
|
|
\bibitem{NIST24}
|
|
National Institute of Standards and Technology.
|
|
\emph{Module-Lattice-Based Key-Encapsulation Mechanism Standard}.
|
|
FIPS 203, August 2024.
|
|
|
|
\bibitem{Bos18}
|
|
J.W.~Bos, L.~Ducas, E.~Kiltz, T.~Lepoint, V.~Lyubashevsky,
|
|
J.M.~Schanck, P.~Schwabe, G.~Seiler, D.~Stehl\'e.
|
|
\emph{CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM}.
|
|
EuroS\&P 2018.
|
|
|
|
\bibitem{HHK17}
|
|
D.~Hofheinz, K.~H\"ovelmanns, E.~Kiltz.
|
|
\emph{A Modular Analysis of the Fujisaki-Okamoto Transformation}.
|
|
TCC 2017.
|
|
|
|
\bibitem{XWing24}
|
|
D.~Connolly, P.~Schwabe, B.~Westerbaan.
|
|
\emph{X-Wing: The Hybrid KEM You've Been Looking For}.
|
|
draft-connolly-cfrg-xwing-kem.
|
|
|
|
\bibitem{ABBBGL20}
|
|
J.~Almeida, M.~Barbosa, G.~Barthe, B.~Blot, B.~Gr\'egoire,
|
|
V.~Laporte, T.~Oliveira, H.~Pacheco, P.~Schwabe, P.-Y.~Strub.
|
|
\emph{The last mile: High-assurance and high-speed cryptographic
|
|
implementations}. IEEE S\&P 2020.
|
|
|
|
\bibitem{BGL18}
|
|
G.~Barthe, B.~Gr\'egoire, V.~Laporte.
|
|
\emph{Secure compilation of side-channel countermeasures: the case
|
|
of cryptographic constant-time}. CSF 2018.
|
|
|
|
\bibitem{RBV17}
|
|
O.~Reparaz, J.~Balasch, I.~Verbauwhede.
|
|
\emph{Dude, is my code constant time?}. DATE 2017.
|
|
|
|
\bibitem{APS15}
|
|
M.R.~Albrecht, R.~Player, S.~Scott.
|
|
\emph{On the concrete hardness of Learning with Errors}.
|
|
J. Math. Cryptology 9(3):169--203, 2015.
|
|
|
|
\bibitem{LP115}
|
|
Lux Industries, Inc.
|
|
\emph{LP-115: X-Wing hybrid KEM for Lux PQ-TLS 1.3}. 2026.
|
|
|
|
\end{thebibliography}
|
|
|
|
\end{document}
|