General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography

Zhengfeng Ji, Youming Qiao, Fang Song, Aaram Yun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

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, 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 × S, or where s is randomly chosen from S and t is the result of applying a random group action of gε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 instantiating this assumption by the general linear group action on tensors. Finally, we construct several cryptographic primitives such as digital signatures and pseudorandom functions. We give quantum security proofs based on the one-way group action assumption and the pseudorandom group action assumption.

Original languageEnglish
Title of host publicationTheory of Cryptography - 17th International Conference, TCC 2019, Proceedings
EditorsDennis Hofheinz, Alon Rosen
PublisherSpringer
Pages251-281
Number of pages31
ISBN (Print)9783030360290
DOIs
StatePublished - 2019
Event17th International Conference on Theory of Cryptography, TCC 2019 - Nuremberg, Germany
Duration: 1 Dec 20195 Dec 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11891 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Theory of Cryptography, TCC 2019
Country/TerritoryGermany
CityNuremberg
Period1/12/195/12/19

Fingerprint

Dive into the research topics of 'General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography'. Together they form a unique fingerprint.

Cite this