Paper 2025/021
Efficient Authentication Protocols from the Restricted Syndrome Decoding Problem
Abstract
In this paper, we introduce an oracle version of the Restricted Syndrome Decoding Problem (RSDP) and propose novel authentication protocols based on the hardness of this problem. They follow the basic structure of the HB-family of authentication protocols and later improvements but demonstrate several advantages. An appropriate choice of multiplicative subgroup and ring structure gives rise to a very efficient hardware implementation compared to other \emph{Learning Parity with Noise} based approaches. In addition, the new protocols also have lower key size, lower communication costs, and potentially better completeness/soundness compared to learning-based alternatives. This is appealing in the context of low-cost, low-powered authenticating devices such as radio frequency identification (RFID) systems. Lastly, we show that with additional assumptions, RSDP can be used to instantiate a Man-in-the-Middle secured authentication protocol.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Contact author(s)
-
thomas johansson @ eit lth se
mustafa khairallah 1608 @ eit lth se
vu nguyen @ eit lth se - History
- 2025-01-07: approved
- 2025-01-06: received
- See all versions
- Short URL
- https://ia.cr/2025/021
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2025/021,
author = {Thomas Johansson and Mustafa Khairallah and Vu Nguyen},
title = {Efficient Authentication Protocols from the Restricted Syndrome Decoding Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/021},
year = {2025},
url = {https://eprint.iacr.org/2025/021}
}
