Tightly-Secure Two-Tier Signatures on Code-Based Digital Signatures with Chameleon Hash Functions

Abstract

In the current landscape where quantum algorithms pose a significant threat to conventional digital signature algorithms, code-based digital signature algorithms have emerged as the primary focus of ongoing research in post-quantum cryptography. Digital signatures play a pivotal role in ensuring non-repudiation and authentication, making them an indispensable cryptographic technique. The vulnerability of most digital signature algorithms to quantum attacks have prompted a significant surge in research on code-based digital signature algorithms, which have emerged as a prominent field within post-quantum cryptography. There are generally three distinct approaches to constructing code-based digital signature algorithms: (1) Developing an algorithm that follows the inverse process of the code-based public-key encryption algorithm; (2) Utilizing zero-knowledge identification algorithms in conjunction with the Fiat–Shamir paradigm to formulate a signature algorithm; (3) Constructing a specialized subset of the syndrome space as the foundation for the digital signature algorithm. Chameleon Signature is a non-interactive signature that operates on the hash and signature paradigm, exhibiting comparable efficiency to conventional schemes. Its distinct advantage lies in the fact that the owner of the public key does not necessarily require access to the corresponding secret key within the Chameleon hash algorithm. Notably, Chameleon signatures possess an inherent characteristic of non-transferability, with their validity ascertainable solely by designated recipients. This paper introduces the first Chameleon hash function based on both KKS and HFE schemes, showcasing its superiority over traditional schemes through rank metrics and big fields for enhanced security. The deployment of Chameleon hash functions within hash-and-sign signature schemes introduces a nuanced layer of security and verification flexibility. This study elucidates the implications of integrating Chameleon hash functions into the recipient’s public key infrastructure, highlighting the dual capability it affords authorized parties for secure and adaptable verification processes, alongside mechanisms for the detection of unauthorized alterations.

Keywords

• digital signatures
• chameleon hash functions
• two-tier signatures
• KKS scheme
• public key signature
• HFE cryptosystem