Paper 2024/2074

EQSIGN: Practical Digital Signatures from the Non-Abelian Hidden Subgroup Problem and Information Theoretic Equivocation

Abstract

We present a novel digital signature scheme grounded in non-commutative cryptography and implemented over a bilinear matrix group platform. At the core of our design is a unique equivocation function that obfuscates intermediate elements, effectively concealing outputs and minimizing observable information leakage. To the best of our knowledge, this is the first digital signature scheme to combine information-theoretic security with computational hardness, relying on a challenging instance of the Non-Abelian Hidden Subgroup Problem (NAHSP) and strengthened by practical guarantees. This dual-layered security approach ensures robustness against both classical and quantum adversaries while maintaining communication overheads competitive with RSA. Our work represents a significant advancement toward efficient, quantum-resilient digital signatures for real-world applications. This paper is an early pre-release intended to invite collaboration and feedback. The work is presented for research purposes only and is not intended for use in production systems.

Note: This preprint is an early release of EQSIGN, a novel digital signature scheme based on the Non-Abelian Hidden Subgroup Problem (NAHSP). We invite peer review and constructive feedback from the cryptographic community to refine the theoretical framework, validate practical applications, and explore optimization opportunities. Future revisions will address input from reviewers and collaborators. -- Added additional explanation around non-intuitive aliasing that occurs as the end of our equivocation function.