The planted tensor problem over finite fields: algorithms and cryptography

Abstract

Inspired by the planted clique problem for random graphs, we introduce the planted totally-isotropic space problem for random tensors as follows. Let $U\cong \mathbb{F}_q^n$ and $W\cong \mathbb{F}_q^m$ be finite-dimensional vector spaces over a finite field $\mathbb{F}_q$. Given $d\in \mathbb{N}$, choose a random \(d\)-dimensional subspace \(V\leq U\), and construct a random alternating bilinear map $\phi:U\times U\to W$ subject to the constraint \(\phi(V,V)=0\). Such a $V$ is known as a totally-isotropic space of $\phi$, and the goal is to recover $V$. Building on the recent probabilistic analysis of random tensors (Pham--Qiao--Wigderson--Wigderson, \emph{in progress}), we initiate the study of the algorithmic hardness of this problem. Setting $m=\lceil n/\log n\rceil$, we show that this problem admits an average-case polynomial-time algorithm for $d\geq n/2$, by leveraging recent advances on the non-commutative rank problem. We also show that this problem admits a $q^{O(n\log n)}$-time algorithm. We carry out algorithmic experiments using polynomial-system solving. From these results, we conjecture that the planted totally-isotropic space problem for $d=\lceil n/C\rceil$ with some constant $C\geq 3$ is exponentially hard. Based on this evidence of computational hardness, we explore cryptographic applications of the planted totally-isotropic space problem and related planted tensor problems. We present private simultaneous messages and secret sharing protocols based on planted tensor problems, following the protocols based on planted subgraphs in (Abram--Beimel--Ishai--Kushilevitz--Narayanan, \emph{TCC}'23). At the same security level, the public information size of protocols based on planted subgraphs is (moderately) exponential in that of protocols based on planted tensors, while the communication costs of these protocols are polynomially related.