Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Efficient Authentication Protocols from the Restricted Syndrome Decoding Problem

Nguyen, Vu LU orcid ; Johansson, Thomas LU orcid and Khairallah, Mustafa LU (2025)
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 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... (More)
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 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. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
in press
subject
host publication
10th IEEE European Symposium on Security and Privacy
pages
16 pages
language
English
LU publication?
yes
id
895dcb52-cc3e-46ef-bdef-115d69838d1d
date added to LUP
2025-04-22 12:08:36
date last changed
2025-04-23 14:27:53
@inproceedings{895dcb52-cc3e-46ef-bdef-115d69838d1d,
  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.<br/>An appropriate choice of multiplicative subgroup and ring structure gives rise to a very efficient hardware implementation compared to other 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.}},
  author       = {{Nguyen, Vu and Johansson, Thomas and Khairallah, Mustafa}},
  booktitle    = {{10th IEEE European Symposium on Security and Privacy}},
  language     = {{eng}},
  title        = {{Efficient Authentication Protocols from the Restricted Syndrome Decoding Problem}},
  year         = {{2025}},
}