Metraipolis › archive › dc_a549e1871e83
The planted tensor problem over finite fields: algorithms and cryptography — arXiv:2609.31256
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.31256
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T02:09:29.842Z
- SHA-256 of the archived text
becf4de2b266d4ec061bc60deb0e63f9a0b6a0e22de031bcf318312a20a3c687- Stable URL of this page
https://metraipolis.com/documento/dc_a549e1871e83
How to cite
The planted tensor problem over finite fields: algorithms and cryptography — arXiv:2609.31256 — arXiv (en), https://arxiv.org/abs/2609.31256 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a549e1871e83 (Metraipolis archive dc_a549e1871e83, sha256 becf4de2b266d4ec061bc60deb0e63f9a0b6a0e22de031bcf318312a20a3c687)
BibTeX
@misc{dca549e1871e83,
title = {The planted tensor problem over finite fields: algorithms and cryptography — arXiv:2609.31256},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.31256},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a549e1871e83; sha256 becf4de2b266d4ec061bc60deb0e63f9a0b6a0e22de031bcf318312a20a3c687},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31256. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-28 in cs.CR).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.31256 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T01:42:25.577Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).