Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Complexity TheoryHomomorphic ComputationLattice-based Cryptography
- Contact author(s)
-
abram damiano @ protonmail com
giulio malavolta @ unibocconi it
ldr709 @ gmail com - History
- 2026-09-22: approved
- 2026-09-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2093
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2093,
author = {Damiano Abram and Giulio Malavolta and Lawrence Roy},
title = {Tree Encodings {III}: Time/Space Hardness from Lattice Problems},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2093},
year = {2026},
url = {https://eprint.iacr.org/2026/2093}
}
