mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
47 lines
1.4 KiB
TeX
47 lines
1.4 KiB
TeX
\section{Correctness Verification}
|
|
|
|
|
|
\subsection{Round-Trip Property}
|
|
|
|
The most important correctness test: $\text{INTT}(\text{NTT}(a)) = a$ for all polynomials $a$.
|
|
|
|
\begin{lstlisting}[language=Go,caption={NTT round-trip fuzz test}]
|
|
func FuzzNTTRoundTrip(f *testing.F) {
|
|
f.Add(make([]byte, 512))
|
|
f.Fuzz(func(t *testing.T, data []byte) {
|
|
if len(data) < 512 {
|
|
t.Skip()
|
|
}
|
|
var a, original [256]int32
|
|
for i := range a {
|
|
a[i] = int32(binary.LittleEndian.Uint16(
|
|
data[2*i:])) % Q
|
|
original[i] = a[i]
|
|
}
|
|
NTT(&a)
|
|
INTT(&a)
|
|
for i := range a {
|
|
got := reduce(a[i])
|
|
want := reduce(original[i])
|
|
if got != want {
|
|
t.Fatalf("index %d: got %d, want %d", i, got, want)
|
|
}
|
|
}
|
|
})
|
|
}
|
|
\end{lstlisting}
|
|
|
|
\subsection{Homomorphism Property}
|
|
|
|
$\text{NTT}(a \cdot b) = \text{NTT}(a) \otimes \text{NTT}(b)$ where $\otimes$ is
|
|
pointwise multiplication. This verifies that the NTT correctly enables fast polynomial
|
|
multiplication.
|
|
|
|
\subsection{Cross-Implementation Testing}
|
|
|
|
We test our Go+AVX2 implementation against the reference C implementation (pqcrystals)
|
|
and a pure Python implementation. All three must produce identical outputs for the
|
|
NIST known-answer test vectors.
|
|
|
|
%% ============================================================
|