Planted isotropic space problem in finite fields aids cryptography research
The planted tensor problem over finite fields: algorithms and cryptography
Data Structures and AlgorithmsCryptography and Security
Summary
Finding hidden patterns in certain mathematical objects called tensors can be very hard. The authors study a problem where a special subspace is hidden in a random tensor, and they want to find this subspace. They show that some cases can be solved quickly, but believe others remain very hard to solve. Using this presumed difficulty, they suggest new ways to build cryptographic protocols that keep information secure and efficient.
What this means in practice
- •For cryptographic protocol designers: Design private communication protocols using planted tensor problems to reduce public information size while maintaining security.
- •For distributed system engineers: Implement secret sharing schemes based on planted tensor structures to achieve efficient and secure data distribution.
Authors
Yuxuan Liu, Youming Qiao, Gang Tang, Chuanqi Zhang
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 $φ:U\times U\to W$ subject to the constraint \(φ(V,V)=0\). Such a $V$ is known as a totally-isotropic space of $φ$, 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.