Paper 2026/2093 Original: eprint.iacr.org/2026/2093 ↗

Tree Encodings III: Time/Space Hardness from Lattice Problems

Abstract

Assuming the polynomial-time hardness of a variant of the short integer solution (SIS) problem, we show the existence of sequential and memory-hard functions. Such an assumption postulates the hardness of a problem against polynomial-time algorithms, regardless of their memory and depth. Yet, we show that this assumption implies that $\mathsf{P} \neq \mathsf{NC}$, that $\mathsf{P} \neq \mathsf{L}$, and that the $\mathsf{NC}$ hierarchy is proper, i.e., that $\mathsf{NC}^1 \subsetneq \mathsf{NC}^2\subsetneq \mathsf{NC}^3 \dots$ Our main technical tool is a new variant of homomorphic computation over lattice encodings, which does not impose a bound on the circuit depth and is not based on bootstrapping.