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) 10th IEEE European Symposium on Security and Privacy, Euro S and P
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
published
subject
host publication
Proceedings - IEEE 10th European Symposium on Security and Privacy, Euro S and P 2025
pages
16 pages
conference name
10th IEEE European Symposium on Security and Privacy, Euro S and P
conference location
Venice, Italy
conference dates
2025-06-30 - 2025-07-04
external identifiers
  • scopus:105016204512
ISBN
979-833159493-0
DOI
10.1109/EuroSP63326.2025.00053
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-11-11 13:43:58
@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    = {{Proceedings - IEEE 10th European Symposium on Security and Privacy, Euro S and P 2025}},
  isbn         = {{979-833159493-0}},
  language     = {{eng}},
  title        = {{Efficient Authentication Protocols from the Restricted Syndrome Decoding Problem}},
  url          = {{http://dx.doi.org/10.1109/EuroSP63326.2025.00053}},
  doi          = {{10.1109/EuroSP63326.2025.00053}},
  year         = {{2025}},
}