Abstract

Inspired by the planted clique problem for random graphs, we introduce the planted totallyisotropic space problem for random tensors as follows. Let _U_ = _[]_ F _[n] q_[and] _[W][]_[=][F] _[m] q_ be finitedimensional vector spaces over a finite field F _q_ . Given _d _ N, choose a random _d_ -dimensional subspace _V U_ , and construct a random alternating bilinear map __ : _U U 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 (PhamQiaoWigderson Wigderson, _in progress_ ), we initiate the study of the algorithmic hardness of this problem. Setting _m_ = _n/_ log _n_ , we show that this problem admits an average-case polynomial-time algorithm for _d 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_ = _n/C_ with some constant _C _ 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 (AbramBeimelIshaiKushilevitz Narayanan, _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.