A Quantum Resistant Chameleon Hashing and Signature Scheme

Abstract

Chameleon signatures introduced by Krawczyk and Rabin are based on well-established hash-and-sign paradigm. It is a non-interactive signature scheme that simultaneously provides the properties of non-transferability and non-repudiation. The chameleon hash function is a trapdoor one-way function which prevents everyone except the holder of the trapdoor information from computing collision on a message digest. The chameleon signature scheme achieves non-transferability as the recipient of the signature is the holder of the trapdoor information. He could be able to compute collision on the hash value and hence no third party could be able to identify the real signer. In the initial constructions of chameleon signature schemes, the occurrences of collisions expose the secret key of the recipient. This strongly prevents the recipient to compute hash collisions, partially undermining the concept of non-transferability. Hence it is important to overcome this key exposure problem, and its aligned problems of key revocation and key redistribution. Also the existing chameleon signature schemes are based on the hard problems in number theory such as integer factorization or the discrete log problem over various groups. The construction of a large-scale quantum computer would render insecurity to these schemes. Hence as recommended by NISTIR 8105, we propose a quantum resistant chameleon hashing and signature scheme based on hard problems in coding theory. The scheme also satisfies the security properties of chameleon signature, such as collision resistance, semantic security, key exposure freeness, non-transferability and unforgeability. As code-based cryptosystem is an important candidate of postquantum cryptosystem, the proposed code-based chameleon signature scheme would be a promising alternative to the number theoretic based schemes. In addition, we also propose a method to transform the code-based chameleon hashing scheme into an ordinary signature scheme and prove its unforgeability in the random oracle model.

Keywords:

• CFS signature
• Chameleon hashing
• Chameleon signatures
• Code-based cryptography
• Collision-resistance
• Digital signatures

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Notes on contributors

P. Thanalakshmi

P Thanalakshmi is an assistant professor in the Department of Applied Mathematics and Computational Sciences, PSG College of Technology, Coimbatore, India. She is pursuing her PhD degree in mathematics with Anna University, Chennai. She is a life member of CRSI. Her research interests include hash-based cryptography and code-based cryptography. Email: [email protected]

R. Anitha

R Anitha is a visiting professor in the Department of Applied Mathematics and Computational Sciences, PSG College of Technology, Coimbatore, India. She received her PhD degree from Bharathiyar University, Coimbatore, in 1997. She is life member of CRSI, ISTE and member of ACM. Her research interests include cryptography, security protocols, information security and system security. Corresponding author. Email: [email protected]