Strong Keys for Tensor Isomorphism Cryptography

A three dimensional tensor can be transformed into another by a triple of invertible square matrices, by multiplying in each dimension. The action is symmetric: if a triple of matrices takes a tensor $A$ to $B$, then the triple of inverses of those matrices takes $B$ to $A$. Two tensors that can be transformed into each other are called isomorphic. The decision version of the tensor isomorphism problem (TI) is given two tensors over a finite field to tell if they are isomorphic. The promise search version asks for an isomorphism (a triple of invertible matrices) between two given isomorphic tensors over a finite field. The tensor isomorphism problem is complete for the complexity class TI which contains other cryptographically important problems such as cubic polynomial equivalence, matrix code equivalence, alternating trilinear form equivalence (ATFE) etc. and longstanding group theoretic problems such as p-group isomorphism [10]. Many of these problems are connected by tight nearly linear or quadratic time complexity reductions. Matrix code equivalence is in fact the same as TI, merely phrased differently. ATFE is TI restricted to alternating tensors with the same invertible matrix acting in all three dimensions, and remains TI-complete. Cubic polynomial equivalence is TI restricted to symmetric tensors. These problems may be phrased in arbitrary dimensions, but they remain hard even when restricted to three dimensions. With a difficult to find isomorphism problem at hand, it is not hard to design a zero knowledge identification scheme using the Goldreich-Micali-Wigderson construction, which yields signature schemes through the Fiat-Shamir transform. Following this motif, Patarin in his pioneering work on multivariate cryptography proposed a signature scheme based on the hardness of cubic polynomial equivalences [19]. Recently, NIST first round on-ramp signature schemes MEDS [3] and ALTEQ [1] are built on TI and ATFE respectively, with competitive efficiency and signature sizes. Beyond efficiency, part of the appeal of tensor isomorphism problems is that there is strong evidence of average case hardness. Further, attempts to solve it using extensions of Shor’s algorithm on a quantum computer must confront the hidden subgroup problem over (products of) general linear groups, believed to be among the hardest [9]. But recently the following weak key vulnerability was identified, warranting caution in the key generation algorithms of tensor isomorphism based cryptosystems.

The public verification key in MEDS was a random $(k+1)\times (k+1)\times (k+1)$ tensor. But very recently, in reaction to a cryptanalytic attack by Narayanan, Qiao and Tang [17], MEDS adopted a $(k_1+1)\times (k_2+1)\times (k_3+1)$ format where $k_1,k_2,k_3$ are not all equal, but still fairly balanced. We will informally call it a nearly cubic format. For levels I,III and V, the respective choices are $26\times 25\times 25$, $35\times 34\times 34$ and $45\times 44\times 44$ [20, Table 7]. The private signing key is a triple of matrices. In ALTEQ, the public key is a random $(k+1)\times (k+1)\times (k+1)$ alternating tensor and the private key is an invertible matrix. Recently, Ran and Samardjiska identified tensors that have certain geometric structures called “triangles” for MEDS and 3-dimensional 2-singularity for ALTEQ as weak public keys [20]. Heuristically, a public key has a triangle (or a 3-dimensional 2-singularity) with probability roughly $1/q$, where $q$ is the field size. They further devised Gröbner basis algorithms (augmented with equations encoding the triangle/ 3-dimensional 2-singular structure) to compute such a triangle (or a 3-dimensional 2-singularity), which upon finding reveals a secret key. Conditioned on a weakness being present, their algorithm can detect and find the weakness faster than previously known (but still in exponential time, so there is no contradiction to the belief that testing singularity is hard). For MEDS, since the underlying prime 4093 is small, taking the conservative assumption that weak keys are likely, the triangle finding algorithm takes away 6 bits of security [20, Table 6]. For ALTEQ, the algorithm to find 3-dimensional 2-singular structures is much faster, exploiting the anti-symmetry of the alternating tensors and the fact that the same matrix acts in all three dimensions. In fact, for ALTEQ level I parameters, the weakness (if it exists) can be found fast in practice. Luckily for ALTEQ, the field size is a large prime close to $2^{32}$. Therefore, the probability of drawing a weak key is heuristically at most $2^{-32}$. In the future, ALTEQ has the choice of doubling the bit length of the current prime, and safely ignoring the weak key issue as a rare occurrence that only happens with probability within the NIST accepted bound of $2^{-64}$. Beyond signature schemes, certain commitment schemes were also under attack, exploiting the chance that the public key is tensor rank deficient [8]. We will focus on evading the attacks on MEDS as the testing ground. Since non degeneracy is a stronger guarantee than tensor rank, the attacks on the commitment scheme in [8] is also evaded by our sampling algorithm for MEDS. Sampling for ALTEQ is complicated by the antisymmetry. Symmetric tensors (polynomials) and antisymmetric tensors have hyperdeterminants that split into irreducible factors indexed by the symmetries [18]. A modified version of our construction taking this splitting into account might work for ALTEQ, but we defer that to future work.

Increasing the field size to dodge the weak key attacks on MEDS seems natural. Yet to be certain it works, the heuristic weak key probability estimate of $1/q$ needs to be proven. In validating the need for their weak key attack, [20] proved a lower bound on the weakness probability. But to be certain that increasing the field sizes is a provable remedy to the weak key attacks, we need an upper bound. Such a rigorous upper bound using hyperdeterminants and counting points on projective varieties over finite fields was proven in [12]. Consequently, increasing the field size to be exponentially large is a provably sound strategy against the weak key attacks. But increasing the field size $q$ comes at the cost of efficiency and signature sizes, both of which grow roughly as $\log q$. For instance, if ALTEQ were to double the bit length of their field size, then the signature sizes would double too. We present a sampling algorithm for boundary formats that applied in the MEDS context samples exclusively from strong public keys, evading the weak key attacks. The sampling algorithm works for boundary formats in arbitrary dimensions, accommodating any future applications in cryptography and beyond. In the MEDS context, the existence of “triangles” coincides precisely with degeneracy and we merely need to specialize our algorithm to the three dimensional and move the nearly cubic MEDS format $(k_1+1)\times (k_2+1)\times (k_3+1)$ to a boundary format of the form $(k_2+k_3+1)\times (k_2+1)\times (k_3+1)$. The public keys sampled are indistinguishable from uniformly drawn strong public keys assuming hardness of the tensor isomorphism problem. Therefore, the sampling sidesteps the weak key issue without the need of any new assumptions, reopening up the possibility of instantiating MEDS and similar schemes over small field sizes. Curiously, there is a recent trapdoor construction from tensors that works exclusively in boundary formats [16]. We anticipate future cryptographic constructions set in boundary formats, for which our sampling algorithms apply in full generality in arbitrary dimensions. After posting an earlier version of this paper online, we became aware of a very recent TI algorithm (Hull attack) of Couvreir and Levrat [4] applicable to boundary formats (The aforementioned [17] only applies to cubical formats). For $(2k+1)\times (k+1)\times (k+1)$ boundary formats, their run time is roughly $q^{k/2}$. More generally, their complexity estimate is roughly $q^k$, with $k$ being the length of the shortest dimension. Therefore, it is imperative to make sure the lengths of the dimensions are reasonably balanced and none of the lengths are too short. In particular, $(k+1)\times (k+1)\times (k+1)$ and $(2k+1)\times (k+1)\times (k+1)$ formats seem comparable in security, except our algorithm can provably sample safe keys in the boundary format. The downside of this boundary format is that tensors (and hence the signatures) are twice as long to write down as the cubical format. A careful comparison of both the complexity of TI and the possibility of evading weak key attacks is thus warranted, before deciding on the format for cryptography. A high level description of the non degenerate tensor sampling problem and our sampling algorithms follows, aided by illustrative small examples in three dimensions.

An $r$ dimensional tensor to us is an element $A$ in the tensor product of (dual) vector spaces of dimensions $k_1+1,k_2+1,\mathrm{\dots },k_r+1$ over a finite field ${𝔽}_q$. We also think of such a tensor as a multilinear form given by a $(k_1+1)\times (k_2+1)\times \mathrm{\dots }\times (k_r+1)$ format $r$-dimensional matrix. We will call $k_j+1$ as the length in the $j$-th dimension. The lengths $k_j+1$ have a plus one for convenience, as working in $k_j$ dimensional projective space will make $k_j$ appear often in formulae. Square matrices correspond to the $r=2$, $k_1=k_2$ with the same length in both dimensions. A square matrix being degenerate corresponds to its determinant vanishing. Since the determinant is polynomial time computable, it is easy to test for degeneracy. Further, the determinant is a monic irreducible polynomial in the entries of the square matrix. Therefore, the set of degenerate matrices forms a closed sub variety, in fact a hypersurface. A generic matrix lies outside this hypersurface. Therefore, drawing a generic matrix and rejecting if the determinant is zero samples from non degenerate square matrices. Consider the following algebraic definition of degeneracy of square matrices: A matrix $A$ is degenerate if there is a pair of non zero vectors $(w^{\text{left}},w^{\text{right}})$ such that $w^{\text{left}}A$ and $A{w}^{\text{right}}$ are both zero vectors. The definition may seem atypical, but is clarified by thinking of $(w^{\text{left}},w^{\text{right}})$ as a pair of left and right kernel vectors. It is this motif that easily generalises in the following definition for three dimensional tensors. A three dimensional tensor $A$ (trilinear form) is degenerate, if there exists a triple $(w^{(1)},w^{(2)},w^{(3)})$ of non zero kernel vectors such that evaluating the trilinear form at all but one (so, two) of the vectors results in the all zero dual vector. That is,

are zero (dual) vectors in the first, second and third dimension respectively. Likewise, an $r$ dimensional tensor is degenerate if there is an $r$-tuple of non zero vectors such that evaluating the $r$-linear form at all but one of the vectors gives the zero (dual) vector. See [6, Chap. 4](also § 2) for a formal algebraic definition and also an equivalent analytic definition in terms of singularity. Singular and degenerate are equivalent in our contexts.

Cayley discovered an analogue of the determinant for the $2\times 2\times 2$ format, depicted below with the vertices of the cube indexing the tensor entries [2].

Nearly two centuries later, Gelfand, Kapranov and Zelevinsky generalised Cauchy’s construction to arbitrary $r$ dimensional formats satisfying the convexity condition $k_j\le {\sum }_{\mathrm{\ell }\ne j}{k}_{\mathrm{\ell }},\forall 1\le j\le r$ under the name of hyperdeterminants. Analogous to the determinant, the hyperdeterminant is an integer polynomial in the entries of the tensor that vanishes precisely when the tensor is singular. However, the hyperdeterminant is conjectured to be hard (VNP hard to compute, NP hard to zero test) in three or more dimensions [11]. Therefore, it is unlikely for the strategy of generating a random tensor and testing for its hyperdeterminant to be non zero to work efficiently. Formats satisfying the convexity condition as a strict inequality for every dimension $j$ are called interior formats. Formats satisfying the convexity condition with equality for at least one dimensions $j$ are called boundary formats. We will call formats not satisfying the convexity condition as exterior formats. Interior and boundary formats have an associated hyperdeterminant, to help reason about degeneracy. Degenerate tensors of an exterior format form a variety of co-dimension more than one, meaning there is no single polynomial such as a hyperdeterminant to characterise degeneracy. Across all formats, non degenerate tensors form a Zariski closed set of co-dimension at least one. Therefore, most tensors are non degenerate.

The Problem: Given an $r$-dimensional format $(k_1+1)\times (k_2+1)\times \mathrm{\dots }\times (k_r+1)$ and a finite field ${𝔽}_q$, sample a non degenerate tensor of that format over ${𝔽}_q$.

The problem is interesting over other fields too. We can construct non degenerate tensors over real/complex numbers by merely populating the tensor with algebraically independent entries. This works for all interior or boundary formats, since the hyperdeterminant exists and being a primitive polynomial with integer entries, cannot vanish specialised to algebraically independent entries. But these constructions seem contrived, involving either transcendental numbers or algebraic numbers of large degree/height. We will instead focus on finite fields, the cryptographically most relevant setting. Our constructions involve a more refined look at the hyperdeterminant and can be lifted to the rationals or reals or complex numbers in a straightforward manner.

We next sketch the main ideas of the first step, with the aid of illustrative small examples of diagonal and Vandermonde-Weyman-Zelevinsky tensors. For every interior or boundary format, Weyman and Zelevinsky defined a notion of diagonal tensors. The diagonal entries are easiest to describe for three dimensional boundary formats $(k_1+1)\times (k_2+1)\times (k_3+1)$, say with $k_1=k_2+k_3$. In this case, the diagonal entries are those whose first coordinate index is the sum of the rest of the coordinate indices. A $3\times 2\times 2$ boundary format diagonal tensor is pictured below, with only the diagonal entries labeled and visible.

The description of diagonal entries for interior formats needs a little more notation and we defer it to later sections. Either way, for all interior and boundary formats, there is a simple rule to identify which tensor coordinates are diagonal. Weyman and Zelevinsky proved that hyperdeterminants of interior or boundary format have a monomial lying as a vertex of the Newton polytope, consisting purely of positive powers of all the diagonal entries [23][Theorem 7.1]! Further, a boundary format tensor whose diagonal entries are precisely the non-zero entries is non degenerate. This leads to a simple sampling algorithm. Pick a diagonal boundary format tensor with random non zero diagonal entries. The remedy for the weak key attacks on MEDS is thus simple, to merely sample the public key tensors this way and scramble. For the MEDS relevant $(2k+1)\times (k+1)\times (k+1)$ boundary formats, the degrees of freedom is $\mathrm{\Theta }(k^2)$. For interior format diagonal tensors, we can write down a monomial in the hyperdeterminant involving all the diagonal entries. But there could be other monomials making it difficult to find an assignment of diagonal entries such that the hyperdeterminant provably does not vanish. The obvious question we leave open is if there is a polynomial time algorithm to sample non degenerate interior format tensors, even when restricted to cubic three dimensional formats. We work out some small examples and hint at the possibility of using diagonal tensors towards this goal.

Boundary formats accomodate a curious alternative to diagonal tensors, albeit with much fewer degrees of freedom. Weyman and Zelevinsky constructed boundary format analogues of Vandermonde matrices, which we propose to use to generate non-singular tensors [23]. Classical Vandermonde matrices are structured square matrices completely described by a vector of entries, whose singularity is characterised by the distinctness of the entries of the vector. Weyman and Zelevinsky constructed structured boundary format tensors completely characterised by $r-1$ vectors, packaged as the columns of a defining matrix. Its degeneracy is characterised by the distinctness of the column entries of the description matrix. We will call such tensors Vandermonde-Weyman-Zelevinsky (VWZ) tensors. By simply drawing a description matrix whose columns each have distinct elements, we construct a non-singular boundary format tensor. This construction works in arbitrary dimension. As an example, a $2\times 3$ matrix defines a $3\times 2\times 2$ boundary format VWZ tensor, as in figure 1.

As the second family of samplers, we propose a recursive algorithm for constructing high dimensional non degenerate boundary format tensors from fewer dimensional ones by exploiting the multiplicativity of hyperdeterminants. Dionisi and Ottaviani’s [5] high dimensional analogue of the the Binet-Cauchy theorem is key to preserving non degeneracy during the recursion. This may be seen as a reduction of the non-singular tensor sampling problem (for boundary formats) from arbitrary to three dimensions. The smaller dimensional problems may be solved by sampling diagonal tensors, Vandermonde-Weyman-Zelevnisky tensors or by other methods devised in the future. Further, if the smaller dimensional instance is of small enough format, it can be solved exhaustively or using the algorithms in [12]. Curiously, the scrambling we do in the recursive framework at the interior vertices of the recursion tree can scramble the tensors across the orbits of the tensor isomorphism action. Therefore, this is a robust framework promising pseudorandom boundary format non degenerate tensors. Tensor isomorphism based cryptography is based on the action of random tuples of invertible matrices multiplying in each dimension. In our recursive sampling, we identify a more general scrambling action by convolution of non degenerate tensors. It is a fascinating open problem to construct cryptographic primitives using convolution of non degenerate tensors. A challenge or an opportunity in using convolution of non degenerate tensors is that the tensor dimension increases.

For exterior formats, we start with a non degenerate boundary format tensor in one higher dimension. This boundary format is chosen to envelope the target exterior format, such that the slices of the boundary format in the longest dimension are of the target exterior format. Non degeneracy of the enveloping boundary format ensures non degeneracy of every slice in the longest dimension.

Evidently, the theory of hyperdeterminants developed by Gelfand, Kapranov and Zelevinsky [7][6, Chap. 14] play a central role in our constructions, alongside further developments by Weyman and Zelevinsky [23]. But these foundational works built the theory over the complex numbers. We need the theory to hold in positive characteristic. We could look to generic model theoretic tools such as Lefschetz principle to lift the theory from complex numbers to positive characteristic, say to an algebraic closure of our finite field. But such a generic method would exclude a finite set of primes from being the characteristic, without explicit knowledge of which primes are exclude. This is unsatisfactory for cryptography, where we need to know if the theorems work for our chosen characteristic. Further, the very definition of hyperdeterminants uses geometric tools (such as tangency and projective duality) that need great care while translating to positive characteristic [14, 15]. Thankfully, Kaji proved that the hyperdeterminant theory does indeed translate to every prime characteristic [13]. We take this for granted and invoke theorems from hyperdeterminant theory originally stated in characteristic zero without further clarification. One exception is the degeneracy characterisation of Vandermonde-Weyman-Zelevinsky tensors [23, Prop. 7.3]. We observe that only one direction of this characterisation is needed by us. For this direction, we present a self contained elementary exposition of Weyman and Zelevinsky’s proof in theorem 2, making it apparent that is works in all characteristics.