Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms

Gang Tang, Dung Hoang Duong, Antoine Joux, Thomas Plantard, Youming Qiao, and Willy Susilo

Abstract

In this paper, we propose a practical signature scheme based on the alternating trilinear form equivalence problem. Our scheme is inspired by the Goldreich-Micali-Wigderson's zero-knowledge protocol for graph isomorphism, and can be served as an alternative candidate for the NIST's post-quantum digital signatures. First, we present theoretical evidences to support its security, especially in the post-quantum cryptography context. The evidences are drawn from several research lines, including hidden subgroup problems, multivariate cryptography, cryptography based on group actions, the quantum random oracle model, and recent advances on isomorphism problems for algebraic structures in algorithms and complexity. Second, we demonstrate its potential for practical uses. Based on algorithm studies, we propose concrete parameter choices, and then implement a prototype. One concrete scheme achieves 128 bit security with public key size ~ 4100 bytes, signature size ~ 6800 bytes, and running times (key generation, sign, verify) ~ 0.8ms on a common laptop computer.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
digital signaturesisomorphism problemstrilinear forms
Contact author(s)
hduong @ uow edu au
History
2022-04-12: revised
See all versions
Short URL
https://ia.cr/2022/267

CC BY

BibTeX

@misc{cryptoeprint:2022/267,
author = {Gang Tang and Dung Hoang Duong and Antoine Joux and Thomas Plantard and Youming Qiao and Willy Susilo},
title = {Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms},
howpublished = {Cryptology ePrint Archive, Paper 2022/267},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/267}},
url = {https://eprint.iacr.org/2022/267}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.