Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A new birthday-type algorithm for attacking the fresh re-keying countermeasure

Guo, Qian LU and Johansson, Thomas LU orcid (2019) In Information Processing Letters 146. p.30-34
Abstract

The fresh re-keying scheme is a countermeasure designed to protect low-cost devices against side-channel attacks. In this paper, we present a new birthday-type attack based on a refined reduction to RING-LPN with a reducible polynomial. Compared with the previous research, our algorithm significantly reduces the time complexity in the 128-bit leakage model—with an SNR equal to 8.21 and at most 2 20 traces, for instance, the key can be recovered using 2 41.96 bit-operations.

Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Birthday attacks, Cryptography, Fresh re-keying, LPN, RING-LPN
in
Information Processing Letters
volume
146
pages
5 pages
publisher
Elsevier
external identifiers
  • scopus:85062016188
ISSN
0020-0190
DOI
10.1016/j.ipl.2019.02.005
language
English
LU publication?
yes
id
7d31820c-2c32-440e-83c4-007b7137a49a
date added to LUP
2019-03-05 13:57:25
date last changed
2025-10-14 09:53:09
@article{7d31820c-2c32-440e-83c4-007b7137a49a,
  abstract     = {{<p>                             The fresh re-keying scheme is a countermeasure designed to protect low-cost devices against side-channel attacks. In this paper, we present a new birthday-type attack based on a refined reduction to RING-LPN with a reducible polynomial. Compared with the previous research, our algorithm significantly reduces the time complexity in the 128-bit leakage model—with an SNR equal to 8.21 and at most 2                             <sup>20</sup>                              traces, for instance, the key can be recovered using 2                             <sup>41.96</sup>                              bit-operations.                         </p>}},
  author       = {{Guo, Qian and Johansson, Thomas}},
  issn         = {{0020-0190}},
  keywords     = {{Birthday attacks; Cryptography; Fresh re-keying; LPN; RING-LPN}},
  language     = {{eng}},
  pages        = {{30--34}},
  publisher    = {{Elsevier}},
  series       = {{Information Processing Letters}},
  title        = {{A new birthday-type algorithm for attacking the fresh re-keying countermeasure}},
  url          = {{http://dx.doi.org/10.1016/j.ipl.2019.02.005}},
  doi          = {{10.1016/j.ipl.2019.02.005}},
  volume       = {{146}},
  year         = {{2019}},
}