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.