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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2022/1698}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.