The planted tensor problem over finite fields: algorithms and cryptography
A planted totally-isotropic tensor problem over finite fields yields crypto protocols with smaller public data.
The authors define a planted totally-isotropic space problem for random alternating bilinear maps over finite fields, analogous to planted clique. Setting the codomain dimension near n over log n, they give an average-case polynomial-time algorithm for planted dimension at least n/2 via non-commutative rank, plus a q to the O(n log n) algorithm. They conjecture exponential hardness when the planted dimension is about n/C for some constant C at least 3. Private simultaneous messages and secret-sharing protocols based on planted tensors have moderately smaller public data than planted-subgraph protocols, with polynomially related communication.
- Average-case polynomial algorithm exists when planted dimension is at least n/2.
- A slower q to the O of n log n algorithm also recovers the space.
- Authors conjecture exponential hardness for dimension about n over a constant.
- Planted-tensor PSM and secret sharing shrink public data versus subgraph protocols.
From the original article
1 min read at arxiv.orgInspired 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$.
By Yuxuan Liu · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.