Lower Bounds from Succinct Hitting Sets

We investigate the consequences of the existence of efficiently describable'' hitting sets for polynomial sized algebraic circuit ($\mathsf{VP}$), in particular, \emph{$\mathsf{VP}$-succinct hitting sets}. Existence of such hitting sets is known to be equivalent to a natural-proofs-barrier’’ towards algebraic circuit lower bounds, from the works that introduced this concept (Forbes \etal (2018), Grochow \etal (2017)). We show that the existence of $\mathsf{V}\mathsf{P}$-succinct hitting sets for $\mathsf{V}\mathsf{P}$ would either imply that $\mathsf{V}\mathsf{P}\mathrm{\ne }\mathsf{V}\mathsf{N}\mathsf{P}$, or yield a fairly strong lower bound against ${\mathsf{T}\mathsf{C}}^0$ circuits, assuming the Generalized Riemann Hypothesis (GRH). This result is a consequence of showing that designing efficiently describable ($\mathsf{V}\mathsf{P}$-explicit) hitting set generators for a class $\mathcal{C}$, is essentially the same as proving a separation between $\mathcal{C}$ and $\mathsf{V}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}$: the algebraic analogue of $\mathsf{\text{PSPACE}}$. More formally, we prove an upper bound on \emph{equations} for polynomial sized algebraic circuits ($\mathsf{V}\mathsf{P}$), in terms of $\mathsf{V}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}$. Using the same upper bound, we also show that even \emph{sub-polynomially explicit hitting sets} for $\mathsf{V}\mathsf{P}$ – much weaker than $\mathsf{V}\mathsf{P}$-succinct hitting sets that are almost polylog-explicit – would imply that either $\mathsf{V}\mathsf{P}\mathrm{\ne }\mathsf{V}\mathsf{N}\mathsf{P}$ or that $\mathsf{P}\mathrm{\ne }\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}$. This motivates us to define the concept of \emph{cryptographic hitting sets}, which we believe is interesting on its own.