Digital Signature from Syndrome Decoding Problem

Abdelhaliem  Babiker

Paper 2022/1698

Digital Signature from Syndrome Decoding Problem

Abdelhaliem Babiker, Imam Abdulrahman Bin Faisal University

Abstract

This paper introduces new digital signature scheme whose security against existential forgery under adaptive chosen message attack is based on hardness of the Syndrome Decoding Problem. The hardness assumption is quite simple and hence easy to analyze and investigate. The scheme as whole is neat with intuitive security definition and proof in addition to elegant and efficient signing and verifying algorithms. We propose parameter sets for three security levels (128-bits, 192-bits, and 256 bits) and estimate the corresponding sizes of the keys and the signature for each level. Additionally, the scheme has an interesting feature of signature verification using an arbitrary part of the public key, which allows the verifying party to store a small random secret part of the public key rather than the full-size public key. Using small part of the public key for verification gives us more time and memory efficient verification mode which we call Light Verification Key Mode (LVK) mode. Also, we suggest Light Signing Key Mode (LSK) which enables a smaller size of the private (signing) key while maintaining the same security level.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Code-Based Cryptography Syndrome Decoding Digital Signature
Contact author(s): haliem abbas @ gmail com
History: 2022-12-10: approved; 2022-12-07: received; See all versions
Short URL: https://ia.cr/2022/1698
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1698,
      author = {Abdelhaliem  Babiker},
      title = {Digital Signature from Syndrome Decoding Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1698},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1698}},
      url = {https://eprint.iacr.org/2022/1698}
}