General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography. (arXiv:1906.04330v1 [cs.CR])

Starting from the one-way group action framework of Brassard and Yung (Crypto
'90), we revisit building cryptography based on group actions. Several previous
candidates for one-way group actions no longer stand, due to progress both on
classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g.,
discrete logarithm).

We propose the general linear group action on tensors as a new candidate to
build cryptography based on group actions. Recent works
(Futorny--Grochow--Sergeichuk, Lin. Alg. Appl., 2019) suggest that the
underlying algorithmic problem, the tensor isomorphism problem, is the hardest
one among several isomorphism testing problems arising from areas including
coding theory, computational group theory, and multivariate cryptography. We
present evidence to justify the viability of this proposal from comprehensive
study of the state-of-art heuristic algorithms, theoretical algorithms, and
hardness results, as well as quantum algorithms.

We then introduce a new notion called pseudorandom group actions to further
develop group-action based cryptography. Briefly speaking, given a group $G$
acting on a set $S$, we assume that it is hard to distinguish two distributions
of $(s, t)$ either uniformly chosen from $S\times S$, or where $s$ is randomly
chosen from $S$ and $t$ is the result of applying a random group action of
$g\in G$ on $s$. This subsumes the classical decisional Diffie-Hellman
assumption when specialized to a particular group action. We carefully analyze
various attack strategies that support the general linear group action on
tensors as a candidate for this assumption.

Finally, we establish the quantum security of several cryptographic
primitives based on the one-way group action assumption and the pseudorandom
group action assumption.

Article web page: