The planted tensor problem over finite fields: algorithms and cryptography

Yuxuan Liu; Youming Qiao; Gang Tang; Chuanqi Zhang

Source-linked AI summary

The planted tensor problem over finite fields: algorithms and cryptography

Yuxuan Liu, Youming Qiao, Gang Tang, Chuanqi Zhang

arXiv:2609.31256v1Sep 25, 2026cs.DScs.CR

TL;DR

The paper asks whether a planted-substructure problem can be both potentially exponentially hard and useful for cryptography, given the quasipolynomial-time algorithm for planted clique. It introduces planted totally-isotropic spaces in random tensors and studies their algorithms and cryptographic applications; for d≥n/2, recovery is possible in average-case polynomial time.

Problem
The paper asks whether a planted-substructure problem can be potentially exponentially hard and useful for cryptographic applications, addressing the inconvenience that planted clique is solvable in quasipolynomial time.
Source: §1 · p. 3
Method
The paper introduces a tensor version of planted clique, investigates its algorithms, and explores cryptographic applications using planted tensor assumptions.
Source: §1 · p. 3, §1.3 · p. 8
Results
For d≥n/2, the planted totally-isotropic space can be recovered in average-case polynomial time.
Source: §3.2 · p. 17, §3.5 · p. 24
Takeaways & Limitations
The authors’ current evidence suggests exponential-time hardness in the proposed smaller-dimension regime, and they adapt planted-clique cryptographic protocols to planted totally-isotropic spaces.
Source: §1.3 · p. 8, §1.5 · p. 13
For d=⌈n/C⌉ with C≥3, the best known general-case algorithm takes q^O(n log n) time, and search-versus-decision relations remain poorly understood.
Source: §1.5 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

The introduction presents planted totally-isotropic spaces as a linear-algebraic analogue of planted cliques and a candidate source of hardness for cryptography. It previews evidence for their hardness and cryptographic protocols based on planted tensors, including comparisons with graph-based constructions.

1 Introduction

The motivation is that standard planted clique can be solved in quasipolynomial time, whereas practical cryptographic protocols typically rely on subexponential-time hardness against polynomial-time algorithms.The paper asks whether a planted-substructure problem can be potentially exponentially hard and useful for cryptography.Source: §1 · p. 3

1.1 From planted cliques to planted totally-isotropic spaces

For random alternating bilinear maps with m ≥ 2, the maximum TI-space dimension is ⌊(m + 2n)/(m + 2)⌋ with high probability.At m = ⌈n/log n⌉, the paper notes this is (2 + o(1)) log n, motivating focus on larger planted spaces.Source: §1.1 · p. 5
The planted TI problem asks for recovery or detection of a random d-dimensional subspace on which a random alternating bilinear map vanishes, and is a linear-algebraic analogue—not a direct encoding—of planted clique.The map is sampled conditioned on the subspace being totally isotropic.Source: §1.1 · pp. 5–6

1.2 Algorithms for the planted totally-isotropic space problem

For m = ⌈n/log n⌉, planted TI spaces are recoverable in polynomial time for d ≥ n/2; a q^O(n log n)-time recovery algorithm also applies.The polynomial-time recovery uses solutions to the non-commutative rank problem.Source: §1.2 · p. 6
The authors conjecture exponential-time hardness for recovering planted spaces of dimension ⌈n/C⌉ and for distinguishing planted from unplanted maps, for some C ≥ 3.They also report experiments using polynomial-equation solving in Magma.Source: §1.2 · pp. 6–7

1.3 Cryptographic applications of the planted tensor problem

The paper presents private simultaneous messages and forbidden-graph secret-sharing constructions based on planted tensors, following graph-based protocols.These applications are motivated by the conjectured exponential-time hardness of planted TI spaces.Source: §1.3 · pp. 7–8
For cryptographic applications, the paper generalizes zero-valued TI planting to embedding and hiding a specified tuple of alternating matrices, defining recovery and decision versions of the B-planted random tensor problem.The hiding step applies a random invertible change of basis.Source: §1.3 · p. 8
Under fixed and random planted-alternating-tensor 2-hint conjectures, the PSM and secret-sharing protocols claim security against q^o(n)-time adversaries.The fixed-subtensor and randomly sampled-subtensor assumptions both allow two vectors from the row space of the inverse hidden transformation as hints.Source: §1.3 · pp. 8–9

1.4.1 Review of PSM and FGSS with public information from planted graphs

The reviewed graph-based PSM encodes Boolean functions as planted bipartite graphs, while graph-based FGSS removes edges forbidden by the access structure and publishes the graph or its complement.For PSM, parties send their embedded vertex locations and the referee checks adjacency; in FGSS, authorized pairs use retained edges to recover the secret.Source: §1.4.1 · p. 10

1.4.2 Our construction of PSM and FGSS from planted tensors

Tensor-based FGSS ties party shares to the hiding transformation, so authorized pairs recover secrets while unauthorized pairs receive only limited hints; the construction also supports multi-bit secrets.The final protocol naturally transmits m log q bits, and its hints are two vectors in the inverse transformation's row space.Source: §1.4.2 · pp. 11, 13
Tensor-based PSM publishes a planted alternating tensor and gives parties compact private values that let the referee evaluate a bilinear function on their inputs.The protocol extends the planted-graph paradigm to bilinear functions over finite fields, and its security assumption accounts for the two transmitted vectors revealed to an adversary.Source: §1.4.2 · p. 12
At matched security, graph-based protocols require public information moderately exponential in the tensor-based size, while tensor communication costs n log q = Θ((log N)^2).The tensor protocols also natively support multi-coordinate outputs and claim exponential security under their conjecture, unlike the reviewed graph protocols' quasipolynomial-time security guarantee.Source: §1.3 · p. 9, §1.4.2 · p. 13

1.5 Discussions and open problems

Initial evidence suggests planted totally-isotropic space recovery could be exponential-time hard, and planted-clique cryptographic protocols can be adapted to this problem.The paper presents this as an initial investigation and evidence, rather than a hardness proof.Source: §1.5 · p. 13
For d = ⌈n/C⌉ with C ≥ 3, the best algorithm takes q^O(n log n) time; improving it, even to q^O(n), remains open.The setting is AT(n, m = ⌈n/log n⌉, q, d = ⌈n/C⌉).Source: §1.5 · p. 14
Open questions include public-key encryption from planted TI spaces, as in, and the poorly understood relation between search and decision, unlike planted clique.The paper also calls for better understanding of AT(n, m = ⌈n/log n⌉, q, d = ⌈n/C⌉) for C ≥ 3.Source: §1.5 · p. 14
The work relates to UOV key recovery: prior work plants TI spaces in m = d = n/C symmetric matrices, whereas this paper uses alternating matrices and m = ⌈n/log n⌉.The UOV setting uses constant C > 2; the authors note that closer comparison would be interesting.Source: §1.5 · p. 14

2 Preliminaries

The preliminaries establish notation for graphs, matrices, vectors, tensors, and bilinear maps, then define alternating structures, degree, and the random distributions used later.

Basic notation

The preliminaries use Fq for length-n vectors and define the Grassmannian Gr(d, V) for d-dimensional subspaces of V.Source: §2 · p. 14

Tensor and bilinear-map notation

A tensor can be represented by its frontal matrix slices, and bilinear maps and tensors are treated as interchangeable through their corresponding forms and coordinates.The paper also defines transformations of tensors and bilinear maps using invertible matrices.Source: §2 · p. 15

Degree

For a vector v, its degree in a bilinear map is the rank of the map obtained by fixing v as one input, representing its neighborhood information.Source: §2 · p. 15

Alternating structures

An alternating matrix represents a bilinear form that vanishes on every pair of equal vectors; a frontal-alternating tensor has alternating matrices as all its frontal slices.The paper denotes the space of n × n alternating matrices by Λ(n, Fq) and the space of frontal-alternating tensors by AT(n, m, Fq).Source: §2 · p. 15

Distributions and adversaries

The notation distinguishes random alternating bilinear maps, maps with a planted totally-isotropic space, and maps with a given planted tensor.A cryptographic adversary is defined as a probabilistic polynomial-time algorithm.Source: §2 · p. 15

3 On the hardness of the planted totally-isotropic space problem

This section studies the algorithmic hardness of the planted totally-isotropic-space problem, presenting distinguishing and recovery algorithms across dimension regimes and evaluating polynomial-system attacks alongside an exponential-hardness conjecture in an intermediate regime.

3.1 Review of some algorithms for the planted clique problem

For planted cliques of size d = ω(log n), enumerating vertex sets of size 3 log n yields a quasipolynomial-time recovery algorithm.A found subset of the planted clique is connected to every clique vertex, enabling recovery of the clique with high probability.Source: §3.1 · p. 16
For planted clique size d = C · √n, give a spectral recovery algorithm, while use the Lovász θ-function for recovery in more general random graph models.Kučera [Kuč95] gives a degree-based polynomial-time algorithm for d ≥ C · √n log n.Source: §3.1 · p. 16
For d = C · √n planted cliques, use degree-based combinatorial methods that outperform spectral methods for smaller constants C; runs in O(n2) time with constant success probability.[DGGP14]’s iterative filtering method works for C ≈ 1.65 with high success probability.Source: §3.1 · p. 16

3.2 Algorithmic landscape of the planted TI space problem

For 2 log n ≪ d ≪ n/2, subspace enumeration recovers in q^O(n log n) time, but the authors conjecture q^Ω(n) time is required when d = ⌈n/C⌉ for some C ≥ 3.For d ≤ 2 log n, the planted structure is comparable to the largest totally-isotropic space in a random instance, so distinguishing or recovery is impossible; the authors describe a potential statistical-computational gap stronger than planted clique’s conjectured quasipolynomial hardness.Source: §3.2 · p. 17
Near d = n/2, the rank-profile method distinguishes planted from random tensors but does not directly recover the planted space; for d ≥ n/2, polynomial-time recovery is available.The rank-profile distinguisher works at d = n/2 − c for c = O(n / log n), with time polynomial in n and exponential in c; recovery at d ≥ n/2 uses techniques from the non-commutative rank problem.Source: §3.2 · p. 17

3.3 A qO(n log n)-time recovery algorithm

For random ϕ sampled from A_T(n, m = ⌈n/log n⌉, q, d) with d ≫ (2 + o(1)) log n, an algorithm recovers the planted TI space with probability 1 − q^−Ω(n) in q^O(n log n) time.With high probability, V is the unique d-dimensional TI space, so the first space accepted by the algorithm must be V.Source: §3.3 · pp. 17–18

3.4 A distinguisher through rank profiles

For d > n/2, a deterministic O(n^3)-time rank test distinguishes planted from random maps with success probability at least 1 − O(1/q).The test uses rank deficiency of an arbitrary frontal slice in the planted distribution.Source: §3.4 · p. 19
For even n ≥ 30, with m = ceil(n/log n) and d = n/2, Algorithm 1 distinguishes planted from random alternating bilinear maps with advantage at least 1 − O(q^-0.5) in O(q^5.5 · n^3) time.It outputs Planted if some k ∈ [N] has rank(Mk) = n−4, and Random otherwise.Source: §3.4 · p. 20
For d=n/2−c, the first asymptotic separation occurs at corank(M)=2c+4; an algorithm distinguishes planted AT(n,m=⌈n/log n⌉,q,d) from random AT(n,m,q) with advantage at least 1−O(q−0.5).Source: §3.4 · p. 23

3.5 A polynomial-time recovery algorithm for d ≥n/2

For d ≥ n/2 and m=⌈n/log n⌉, a polynomial-time algorithm recovers the planted totally-isotropic space with high probability.The algorithm searches for a pair (U,W) with ϕ(U,W)=0; for d>n/2, the planted space is the canonical shrunk subspace recovered by deterministic polynomial-time methods. At d=n/2, such pairs are invariant-subspace pairs.Source: §3.5 · p. 24

3.6 Algorithms based on solving polynomial equations

The recovery search becomes a quadratic polynomial system in a basis matrix X, with an auxiliary inverse constraint enforcing invertibility of a chosen d×d block, solved via a Gröbner basis.The planted equations impose XAkXt=0 for each tensor slice; the chosen block constraint can exclude solutions whose corresponding block is singular.Source: §3.6 · pp. 24–25
The hybrid solver took 23 seconds at (d,n)=(20,60) and 428 seconds at (30,90) after fixing correct entries, but exhaustive guessing leaves it no better than q^O(n log n).These timings measure only Gröbner-basis computation after fixing n(log n)^2 entries; without guesses, the d=3, n=6 instance over F131 took about 41 seconds. Exhaustive guessing adds a factor q^(n(log n)^2).Source: §3.6 · pp. 26–27

4 From planting totally-isotropic spaces to planting subtensors

The section formulates indistinguishability assumptions for planting alternating tensors, including variants with hints and with a random planted tensor. It uses these assumptions to state conjectured hardness and derive a simulator guarantee.

4 From planting totally-isotropic spaces to planting subtensors

PAT assumes a random alternating tensor containing a planted alternating subtensor remains computationally indistinguishable from a random tensor of the same size.The planted subtensor may be arbitrary; the text expects totally-isotropic-space planting to be easier than planting other tensors.Source: §4 · p. 27
PATw2H strengthens PAT by giving the adversary two vectors related to the hiding action in the planting.The assumption requires indistinguishability for every pair of linearly independent vectors.Source: §4 · pp. 27–28
The section conjectures PATw2H hardness for d = ceil(n/C), C >= 3, with constant epsilon c against non-uniform q^o(n)-time adversaries.It also states a corresponding conjecture for the random-planted-tensor-with-2-hints variant.Source: §4 · pp. 27–28
Under PATw2H, a non-uniform PPT simulator can reproduce the adversary's view from the fixed planted tensor and the target bilinear-output vector, up to advantage epsilon.Lemma 13 gives the bound as an at-most-epsilon difference in acceptance probabilities.Source: §4 · p. 28
PlRanAltTensorW2Hints replaces the fixed planted tensor in PATw2H with a random one, making the assumption weaker than PATw2H.The corresponding conjecture posits hardness for d = ceil(n/C), C >= 3, against non-uniform q^o(n)-time adversaries.Source: §4 · p. 28

5 Private Simultaneous Messages from Planted Tensors

The section builds private simultaneous messages protocols for bilinear functions from planted alternating tensors. Alternating lifts connect general bilinear maps to the alternating setting, and the protocol's security is based on the planted-tensor assumptions.

5.1 PSM protocol with public information

The protocol gives two parties public information and private shared values for independently encoding inputs, with the output required to reveal no more than the function value under computational security.The section adapts the public-information PSM model of from Boolean functions to bilinear maps.Source: §5.1 · p. 29

5.2 Alternating lifts of bilinear maps

An alternating lift represents a bilinear map as the restriction of an alternating bilinear map on a larger space through two fixed linear embeddings.The protocol is then specified using such a lift and the planted alternating tensor framework.Source: §5.2 · p. 30

5.3 PSM protocols with public information from planted tensors

The construction publishes a planted, obfuscated alternating tensor and gives the parties partial transformation information for encoding their inputs.The protocol applies to alternating bilinear functions and extends to arbitrary bilinear functions through an alternating lift.Source: §5 · p. 28, §5.3 · pp. 30–31
The referee evaluates the bilinear forms on the two messages, and the protocol is perfectly correct and computationally secure under the stated planted-tensor assumptions.The security proof makes the real transcript indistinguishable from a simulator's transcript depending on the function output, not the private inputs.Source: §5.3 · pp. 31–32

6 Secret Sharing Schemes from Planted (Random) Tensors

The section constructs secret-sharing schemes with public information for forbidden-graph access structures using planted random tensors. Authorized pairs can recover the secret, while security against forbidden pairs is based on the PlRanAltTensorW2Hints assumption.

6.1 Forbidden graph secret-sharing schemes with public information

In the public-information model, graph edges specify authorized pairs and non-edges specify forbidden pairs; public information supports reconstruction but should not help adversaries learn the secret.The construction extends the binary secret of to a length-m q-ary secret.Source: §6 · pp. 32–33, §6.1 · pp. 33–34
The scheme defines public information and individual shares so authorized pairs recover the secret, while forbidden pairs and single parties are not allowed access.The access structure encodes authorized pairs as edges of the graph.Source: §6.1 · pp. 33–34

6.2 Forbidden graph secret-sharing schemes with public information from planted random tensors

Tensor puncturing zeroes the bilinear-map values for forbidden pairs while retaining values for authorized pairs.The scheme uses this operation to construct forbidden-graph secret sharing from planted random tensors.Source: §6.2 · p. 34
Under Conjecture 6, a polynomial-overhead reduction rules out an adversary that recovers the secret from a forbidden pair, since such an adversary would break the planted-tensor assumption.The proof compares recovery success when the tensor is planted versus when it is random.Source: §6.2 · p. 36