The hardness vs. randomness paradigm aims to construct pseudorandom generators (PRGs) based on complexity theoretic hardness assumptions. A seminal result in this area is a PRG construction by \cite{NW,IW97}.
A sequence of works \cite{KvM,SU01,Umans02,SU05} generalized the result of \cite{NW,IW97} to nondeterministic circuits. More specifically, they showed that if $\E=\DTIME(2^{O(n)})$ requires nondeterministic circuits of size $2^{\Omega(n)}$, then for every sufficiently large $s$, and every $\eps \ge \frac{1}{s}$, there is an $\eps$-PRG $G:\B^{r=O(\log s + \log \frac{1}{\eps})} \to \B^s$ that runs in time $\poly(s)$, and fools size $s$ nondeterministic circuits. In particular, for every size $s$ nondeterministic circuit $C$, \[\Pr[C(G(U_r))=1] \le \Pr[C(U_s)=1] + \eps.\]

Applebaum et al. \cite{AASY15} showed that ``black-box techniques'' cannot achieve such results for $\eps=s^{-\omega(1)}$. In order to circumvent this problem, Artemenko et al. \cite{AIKS16} suggested a ``multiplicative'' version of PRGs, which requires that:
\[\Pr[C(G(U_r))=1] \le 2 \cdot \Pr[C(U_s)=1] + \eps.\]
This still gives that $\Pr[C(G(U_r))=1]$ is very small, if $\Pr[C(U_s)=1]$ is very small, and is therefore suitable for applications that only require this consequence.
\cite{AIKS16} constructed such multiplicative PRGs for $\eps=s^{-\omega(1)}$ (based on very strong hardness assumptions).

In this paper, we give an optimal construction of multiplicative PRGs for nondeterministic circuits. More specifically, under the same hardness assumption used for (standard) PRGs for nondeterministic circuits, we show that for every $\eps \ge \frac{1}{2^{s}}$, there is a multiplicative PRG $G:\B^{r=O(\log s + \log \frac{1}{\eps})} \to \B^s$ that runs in time $\poly(s)$ and fools size $s$ nondeterministic circuits.

This gives the optimal seed length under a hardness assumption that is necessary, and provides improvements in several applications of multiplicative PRGs. Our result improves upon the previous multiplicative PRG construction of \cite{AIKS16}, which uses a stronger hardness assumption against $\Sigma_3$-circuits, and where the seed length is the suboptimal $r=O(\log s) + O(\log \frac{1}{\eps})^2$. Our result also improves upon the recent multiplicative PRG of Shaltiel \cite{ShaltielCCC25} that only achieves very small stretch (the output length in \cite{ShaltielCCC25} is less than twice the seed length).

\smallskip
We also show that black-box techniques cannot give a version of our result where ``nondeterministic'' is replaced by ``deterministic''. This justifies the current situation where hardness for nondeterministic circuits is used even if one only wants low error multiplicative PRGs that fool \emph{deterministic} circuits.

\smallskip
Our PRG construction borrows ideas from the recent ``low stretch'' PRG of Shaltiel \cite{ShaltielCCC25}, and the (standard) PRG construction of Shaltiel and Umans \cite{SU01}. Loosely speaking, we aim to get the ``multiplicativity'' of the former, and the ``large stretch'' of the latter. While both approaches generalize the list-decoding results of Sudan, Trevisan and Vadhan \cite{STV}, the two results are tailored to two very different parameter regimes, and we introduce several new ideas to make the two approaches co-exist.