Paper 2021/279
Information-Set Decoding with Hints
Anna-Lena Horlemann, Sven Puchinger, Julian Renner, Thomas Schamberger, and Antonia Wachter-Zeh
Abstract
This paper studies how to incorporate small information leakages (called “hints”) into information-set decoding (ISD) algorithms. In particular, the influence of these hints on solving the (n, k, t)-syndrome-decoding problem (SDP), i.e., generic syndrome decoding of a code of length n, dimension k, and an error of weight t, is analyzed. We motivate all hints by leakages obtainable through realistic side-channel attacks on code-based post-quantum cryptosystems. One class of studied hints consists of partial knowledge of the error or message, which allow to reduce the length, dimension, or error weight using a suitable transformation of the problem. As a second class of hints, we assume that the Hamming weights of subblocks of the error are known, which can be motivated by a template attack. We present adapted ISD algorithms for this type of leakage. For each third-round code-based NIST submission (Classic McEliece, BIKE, HQC), we show how many hints of each type are needed to reduce the work factor below the claimed security level. E.g., for Classic McEliece mceliece348864, the work factor is reduced below 2^128 for 175 known message entries, 9 known error locations, 650 known error-free positions, or known Hamming weights of 29 subblocks of roughly equal size.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Code-Based CryptographyInformation-Set DecodingPost-Quantum CryptographySide-Channel AttacksSyndrome-Decoding Problem
- Contact author(s)
- julian renner @ tum de
- History
- 2021-03-04: received
- Short URL
- https://ia.cr/2021/279
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/279,
author = {Anna-Lena Horlemann and Sven Puchinger and Julian Renner and Thomas Schamberger and Antonia Wachter-Zeh},
title = {Information-Set Decoding with Hints},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/279},
year = {2021},
url = {https://eprint.iacr.org/2021/279}
}