TY - GEN
T1 - Information-Set Decoding with Hints
AU - Horlemann, Anna Lena
AU - Puchinger, Sven
AU - Renner, Julian
AU - Schamberger, Thomas
AU - Wachter-Zeh, Antonia
N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - 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 sub-blocks 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 9 known error locations, 650 known error-free positions or known Hamming weights of 29 sub-blocks of roughly equal size.
AB - 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 sub-blocks 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 9 known error locations, 650 known error-free positions or known Hamming weights of 29 sub-blocks of roughly equal size.
KW - Code-based cryptography
KW - Information set decoding
KW - Post-quantum cryptography
KW - Side-channel attacks
UR - http://www.scopus.com/inward/record.url?scp=85127035722&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-98365-9_4
DO - 10.1007/978-3-030-98365-9_4
M3 - Conference contribution
AN - SCOPUS:85127035722
SN - 9783030983642
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 60
EP - 83
BT - Code-Based Cryptography - 9th International Workshop, CBCrypto 2021, Revised Selected Papers
A2 - Wachter-Zeh, Antonia
A2 - Bartz, Hannes
A2 - Liva, Gianluigi
PB - Springer Science and Business Media Deutschland GmbH
T2 - 9th International Workshop on Code-Based Cryptography, CBCrypto 2021
Y2 - 21 June 2021 through 22 June 2021
ER -