Three is a shroud! Post-quantum signatures from trilinear forms

Three is a shroud! Post-quantum signatures from trilinear forms.

Given two square matrices $A$ and $B$, can we tell if there is an invertible square matrix $X$ such that $XAX^{-1}=B?$ Yes, quickly! Such an $X$ exists if and only if $A$ and $B$ are similar and there are efficiently computable invariants that precisely characterize similarity. Phrased differently, we can tell if there is a change of basis (given by the matrix $X$) for the vector space the matrices are acting on (as linear transformations by left multiplication), that takes $A$ to $B$. We may pose very many questions of this ilk with square matrices as inputs. The answer to most such questions is a resounding “Yes, quickly”, thanks to linear algebraic computation concerning matrices being easy. But one small step in dimension, jumping from two (square matrices) to three (3-tensors given by a cube of numbers), is a giant leap in computational complexity. Most linear algebraic problems concerning three or higher dimensional tensors are hard [1]. To us, a tensor will merely mean a cube of numbers, best thought of as either a linear mapping of two vectors to a third vector or as a linear mapping of three vectors to a scalar. In the latter point of view is known as a trilinear form and that will be our preferred perspective. The following seemingly-simple linear algebraic problem on tensors is believed to be hard: given two tensors, is there a basis change that takes one to the other? Again, basis change is synonymous with invertible matrices and we can ask for the same basis change in all three dimensions the tensor is acting on. Leveraging the hardness of such a tensor problem, a post-quantum signature scheme named ALTEQ (ALternating Tensor EQuivalence) was submitted to the most recent NIST signature competition [2,3]. This proposal injects precious diversity into hardness assumptions underlying post-quantum signatures. Most (widely accepted) such assumptions are of the difficulty of error correction problems set in lattices or codes. Lattice and code-based assumptions have withstood over two decades of cryptanalytic attacks and are anchored by worst case to average case complexity theoretic reductions. Tensor problems such as the one ALTEQ is based on are fairly new to cryptography and warrant further scrutiny. They are however supported by a web of complexity theoretic reductions connecting seemingly unrelated hard problems [4]. If the hardness assumption underlying ALTEQ falls, so does the whole web. Two other NIST signature submissions, LESS [5] and MEDS [6], are based on hard problems that are part of the web.

We sketch the main ideas behind the ALTEQ scheme in this blogpost, assuming not much more from the reader than knowledge of elementary linear algebra. We take liberties for ease of exposition: our sole objective is to offer a gentle invitation to the subject. This blog post is neither meant to be a cryptographic proposal nor advice. Please refer to the ALTEQ documentation [2] for an accurate/formal description. ALTEQ is based on the signature scheme in [3], which skirted with danger in parameter choices and fell to a cryptanalytic attack by Beullens [7]. The parameter choice in ALTEQ is more conservative than [3] and evades Beullens’ attack. For complexity-theoretic insight on why the underlying tensor problems are believed to be hard, refer to [4]. We start by rambling about signature schemes and zero-knowledge proofs, followed by the definition of the alternating tensor equivalence problem. We then invoke the Goldreich-Micali-Wigderson motif [8] to derive a signature scheme reliant on the hardness of the alternating tensor equivalence problem. Our description is helpful in understanding LESS and MEDS too, for they are built similarly.

Post-quantum signatures.

Say Alice wants to send a message to Bob. A signature is a string that Alice appends to the message such that Bob can verify that it was indeed Alice who sent it (authenticity) and that the message has not been tampered with (integrity). To set up such a signature scheme, Alice publishes some information for everyone to see, called the verification key. But she keeps some information secret to herself, called the signing key. No adversary with access to the verification key and message-signature pairs should be able to forge a signature for a new message. In particular, the adversary should not be able to infer the signing key.

A signature scheme is deemed post-quantum if it is run on classical computers yet remains secure even if the adversary can run algorithms in BQP (the complexity class which captures what is feasible on fault-tolerant quantum computers). This seems pessimistic, but with reason. If reliable quantum computers emerge in the near future, they are likely to first be accessible to a few entities, perhaps not all trust worthy. Further, we want cryptographic schemes practiced today to remain secure when quantum computers become viable.

The ALTEQ signature scheme is unforgeable under the assumption that a certain problem is difficult despite access to quantum computers. The problem (to be formally stated later) amounts to determining if two given alternating tensors are equivalent. A tensor to us merely refers to $n^3$ numbers, placed in the cells of an $n$-by-$n$-by-$n$ cube. An alternating tensor has some symmetry: roughly $n^3/3$ numbers (instead of $n^3$) suffice to determine the whole cube of numbers. Two tensors are equivalent if there is a change of basis (on all three dimensions the tensors are acting on) taking one tensor to the other. This basis change is in one-to-one correspondence with invertible $n$-by-$n$ matrices. Again, the same matrix/basis change is done in all three dimensions. The signature scheme is constructed via zero-knowledge protocols, which we next discuss.

Persuasion through conversation.

There is a convenient if not entirely precise analogy to understand zero-knowledge protocols. Think of Alice as having the solution to a puzzle whose solution is worth a huge prize. She walks into the bank that awards the prize and meets Bob at the counter. Can she claim the prize without revealing information about the solution that allows Bob to claim the prize for himself? A zero-knowledge protocol enables her to do so through conversation with Bob! Both Alice and Bob may flip coins during their conversation.

Alice does not want to reveal anything about the solution which would enable Bob to convince someone else that he has the solution. This property of an interactive protocol is called as zero-knowledge. While arguing that the protocol is zero-knowledge, we fear Bob has a quantum computer and can run BQP algorithms. Bob’s motive is to make certain that Alice indeed has the solution to the puzzle. This property where Bob is convinced only if Alice has a solution is called as soundness. In arguing for soundness, we fear Alice can run BQP algorithms. We fear worse, that Alice may not be faithful to the protocol. She may send whatever she pleases in place of the messages prescribed by the protocol.

Hashing the conversation.

Some zero knowledge protocols have the remarkable feature that all Bob sends Alice during the protocol are random numbers independent of the rest of the conversation. These random numbers are best thought of as random questions. The Fiat-Shamir transformation tells how Alice could generate these questions by herself while maintaining the integrity of the protocol. In essence, Alice unilaterally generates Bob’s random numbers as the cryptographic hash of the conversation thus far; transforming the conversation into an Alice monologue. The resulting protocol has no need for true interaction and gives a signature scheme. The soundness property that allows Bob to verify Alice’s claim translates to Alice’s signature being authentic. The zero-knowledge property, that is, the inability of Bob to learn enough to claim the prize for himself, translates to the signatures being unforgeable.

The stage is almost set to present the signature scheme, but we pause for a slightly more formal definition of the hard problem.

A cube of numbers.

Tensors are typically first taught over the real or complex numbers. But for our cryptographic application, finite fields are more appropriate. Let $p$ be an odd prime number. Take the set $\mathbb{F}_p:={0,1,2,\ldots,p-1}$ of numbers, viewed as the canonical set of remainders when one performs division by $p$. There is a natural way to perform arithmetic on this set, by which we mean add, subtract and multiply two elements. Simply perform arithmetic as integers; if the result falls beyond the set, take the remainder after division by $p$. For example, if the result of the integer arithmetic is $3p+1$, taking remainders gives us $1$. If the integer arithmetic gives $-2$, taking remainders gives $p-2$. Here on, view $\mathbb{F}_p$ not merely as a set, but a set along with the arithmetic we just endowed. Most properties we are familiar with and take for granted are inherited by $\mathbb{F}_p$ from integer arithmetic. Further, we can always divide in $\mathbb{F}_p$. That is, for $a$ and $b\neq 0$ in $\mathbb{F}_p$, there is a unique element $c$ in $\mathbb{F}_p$ such that $a=bc$. This property is a distinguishing feature of $p$ being a prime number. In contrast, dividing two integers typically does not result in an integer. In summary, $\mathbb{F}_p$ is a finite set endowed with addition, subtraction, multiplication and division: allowing us to speak of vector spaces over $\mathbb{F}_p$.

Let $n$ be a positive integer and let $\mathbb{F}_p^n$ denote the $n$ dimensional vector space over $\mathbb{F}_p$. A trilinear form (for our discussion) is a function $f:\mathbb{F}_p^n \times \mathbb{F}_p^n \times \mathbb{F}_p^n \longrightarrow \mathbb{F}_p$ that is linear in each coordinate. Linearity in the first coordinate merely means $f(x,y,z)+f(x^\prime,y,z)=f(x+x^\prime,y,z)$ and $f(cx,y,z)=cf(x,y,z)$ for all $x,x^\prime,y,z,c \in \mathbb{F}_p$. And so on, for the other two coordinates. Fix a basis for $\mathbb{F}^n_p$ in each dimension, say the standard basis. With this choice, a trilinear form $f$ is best thought of as a 3-tensor, a cube $A_f$ of elements from $\mathbb{F}_p$. This cube is of length $n$ in each of the three dimensions. Analogy with bilinear forms and matrices is helpful. A sqaure matrix gives a bilinear form as follows: send a pair of vectors to the field element obtained by multiplying the matrix with a vector on each of the two dimensions. A 3-tensor thought of as a cube on elements gives a trilinear form as follows: send a triple of vectors to the field element obtained by multiplying the tensor with a vector on each of the three dimensions.

Tensor equivalence.

For an invertible square matrix $X$ and a trilinear form $f$, let $X \circ f$ denote the trilinear form that maps $(x,y,z) \longmapsto f\left(X^tx,X^ty,X^tz\right).$ The $t$ in the exponent denotes transposition. That is, changing the basis (of each of the three the vector spaces acted upon) by $X^t$ takes $f$ to $X \circ f$. In terms of tensors, multiplication by $X$ in all dimensions takes $A_f$ to $A_{X \circ f}$. Two trilinear forms $f$ and $g$ are called equivalent if there is an invertible matrix $X$ such that $g=X \circ f$. This is a symmetric relation: $f$ is equivalent to $g$ if and only if $g$ is equivalent to $f$. The reason being, if $g=X \circ f$ for some invertible $X$, then $f=X^{-1} \circ g$.

It is believed to be hard to tell if two given trilinear forms $f$ and $g$ are equivalent, even for quantum algorithms. This hardness persists if the we restrict to alternating trilinear forms. A trilinear form $f$ is called as alternating if it maps to zero when atleast two of the three arguments are the same. That is, $f(x,x,z)=f(x,y,y)=f(z,y,z)=0$ for all $x,y,z \in \mathbb{F}_p^n$. The alternating property can be thought of as a symmetry: reducing the number of elements needed to write down the cube corresponding to an alternating tensor to roughly a third of $n^3$. This factor of three translates to smaller key and signature sizes.

The Goldreich-Micali-Wigderson protocol.

In a seminal paper, Goldreich, Micali and Wigderson proposed a zero-knowledge protocol for graph isomorphisms. The protocol applies more generally and is readily adapted into a zero-knowledge proof of alternating tensor equivalences, as follows. Consider $(p,n,f,g)$ where $f$ and $g$ are $n\times n \times n$ alternating trilinear forms over $\mathbb{F}_p$. The instance $(p,n,f,g)$ is public. Alice claims and wants to prove to Bob that $f$ and $g$ are equivalent.

1.) Alice sends Bob an alternating trilinear form $\widehat{f}$.

If she had a proof (an invertible matrix $X$ such that $g=X\circ f$) and were truthful, she would sample a uniformly random $n \times n$ invertible matrix $R$ and send $R \circ f$. By our hardness assumption, Bob can not tell if Alice’s message $\widehat{f}$ is equivalent to $f$ or not. Usually, a stronger hardness assumption holds: Bob cannot tell Alice’s message from a truly random alternating trilinear form.

2.) Bob sends Alice a random bit $b$.

Think of this bit as choosing one of two questions. If $b=0$, Bobs asks Alice for a proof that $f$ and $\widehat{f}$ are equivalent. If $b=1$, Bob asks Alice for a proof that $\widehat{f}$ and $g$ are equivalent. The surprise with which Bob poses one of the two questions is critical to enforcing soundness.

3.) Alice sends Bob an invertible matrix $Y$.

If her claim were true and she were truthful, she would build $Y$ depending on $b$ as follows. If $b=0$, she sets $Y:=R$ as proof that $f$ and $\widehat{f}$ are equivalent. If $b=1$, she sets $Y:= RX^{-1}$ as proof that $\widehat{f}$ and $g$ are equivalent. To someone without knowledge of $X$ (like poor Bob), the two possible answers look identically distributed.

Yet, Bob can verify that Alice’s final response is indeed a proof for the question he posed earlier. Bob just multiplies the first tensor in his question (in all dimensions) with the matrix Alice presents as the proof and verifies that the resulting tensor is what is sought.

If Alice’s claim were true, then by being truthful she passes Bob’s verification. If not, assuming it is hard to tell if two alternating trilinear forms are isomorphic, Alice can at best answer one of Bob’s possible questions, but not both. Therefore, she cannot pass the verification with a probability significantly greater than half.

Repetition for soundness.

There are two natural ways to boost the soundness probability from around a half to cryptographically acceptable levels. The first is to repeat this interaction a few times independently (for the same claim), and demand that Alice passes the verification only if she passes every repetition. The second is to expand the random question Bob poses to a few (say $c$) bits. Alice commits to $2^c$ random trilinear forms equivalent to $f$, one of whose equivalence Bob questions. The ALTEQ scheme uses an amalgamation of both these techniques to boost soundness, offering a tradeoff between signature sizes and signing/verification times. For simplicity, we are content with sketching a signature scheme arising from only the first way.

Hashing the commitment.

All that remains is to invoke the Fiat-Shamir transformation [7] to rid the zero-knowledge protocol of interaction. Choose $p$ and $n$ big enough to ensure that the alternating tensor equivalence problem on $\mathbb{F}_p^n$ is intractable.

Key generation: Independently draw a uniformly random alternating trilinear form $f$ on $\mathbb{F}_p^n$ and a uniformly random invertible $n \times n$ matrix $X$. Let $g:=X \circ f$. The pair $(f,g)$ is made the public verification key. Only Alice gets the secret signing key $X$.

Signature: Say $M$ is the message Alice wants to sign. Let $m$ be the number of rounds of repetition of the zero knowledge protocol. Greater $m$ is, harder the signature is to forge. Alice draws $m$ mutually independent invertible $n \times n$ matrices $R_1,R_2,\ldots,R_m$. She then computes her commitments $(\widehat{f}_1:=R_1 \circ f, \widehat{f}_2:=R_2 \circ f, \ldots, \widehat{f}_m:=R_m \circ f),$ indexed by the rounds. Alice unilaterally generates Bob’s questions herself as $(b_1,b_2,\ldots,b_m):=H(M,\widehat{f}_1,\widehat{f}_2,\ldots,\widehat{f}_m),$ where $H$ is a public cryptographic hash function mapping to $m$-bits. There are several ways to choose these questions, we presented a naive (but easy to understand) method that gives long signatures. The method in ALTEQ is much more intricate, yielding much shorter signatures. Finally, she answers the i-th round question $b_i$ as follows. If $b_i=0$, she sets $Y_i:=R_i$ as proof that $f$ and $\widehat{f}_i$ are equivalent. If $b_i=1$, she sets $Y_i:= R_iX^{-1}$ as proof that $\widehat{f}_i$ and $g_i$ are equivalent. She signs the message $M$ by appending the message with her commitments and answers, as $\left(M,\widehat{f}_1,\widehat{f}_2,\ldots,\widehat{f}_m,Y_1,Y_2,\ldots,Y_m\right).$

Verification: Bob hashes the message concatenated with Alice’s commitments to know the $m$ questions that Alice answered. Bob verifies that every answer in Alice’s signature is indeed a proof of the corresponding question; exactly as he would do in the zero-knowledge protocol. The soundness and zero-knowledge of the interactive protocol translate to the signatures being authentic and unforgeable.

[1]: C.J. Hillar and L-H Lim, Most tensor problems are NP-Hard. Journal of the ACM, Volume 60, Issue 6, Article No. 45, pp 1–39. [2]: M. Bläser, D. H. Duong, A. K. Narayanan, T. Plantard, Y. Qiao, A. Sipasseuth, G. Tang, ALTEQ: a cryptographic signature algorithm based on the hardness of the alternating trilinear form equivalence problem. https://pqcalteq.github.io/ [3]: G. Tang, D. H. Duong, A. Joux, T. Plantard, Y. Qiao, and W. Susilo, Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms, EUROCRYPT 2022: Advances in Cryptology – EUROCRYPT 2022 pp 582–612. [4]: J. Grochow, and Y. Qiao, On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, SIAM Journal on Computing, Vol. 52, Iss. 2 (2023). [5]: J-F. Biasse, G. Micheli, E. Persichetti, and P. Santini, LESS is More: Code-Based Signatures without Syndromes. AFRICACRYPT 2020. [6]: T. Chou, R. Niederhagen, E. Persichetti, T. H. Randrianarisoa, K. Reijnders, S. Samardjiska, and M. Trimoska, Take your MEDS: Digital Signatures from Matrix Code Equivalence. https://eprint.iacr.org/2022/1559.pdf [7]: W. Beullens, Graph-theoretic algorithms for the alternating trilinear form equivalence problem, https://eprint.iacr.org/2022/1528 [8]: O. Goldreich, S. Micali and A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM, Volume 38, Issue 3, pp 690–728. [9]: A. Fiat, A. Shamir, How to Prove Yourself: Practical Solutions to Identification and Signature Problems, Advances in Cryptology — CRYPTO’ 86. Lecture Notes in Computer Science. Vol. 263. Springer Berlin Heidelberg. pp. 186–194.