Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Information Set Decoding with Soft Information and some cryptographic applications

Guo, Qian LU ; Johansson, Thomas LU orcid ; Mårtensson, Erik LU orcid and Stankovski, Paul LU (2017) 2017 IEEE International Symposium on Information Theory p.1793-1797
Abstract
The class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. Stern's algorithm is the origin of the most efficient algorithms in this class. In this paper we consider the same decoding problem but for a channel with soft information. We give a version of Stern's algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We then demonstrate how this new algorithm can be used in a few cryptographic applications, including a very efficient attack on a recently proposed McEliece-type cryptosystem.
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
IEEE International Symposium on Information Theory (ISIT)
pages
1793 - 1797
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
2017 IEEE International Symposium on Information Theory
conference location
Aachen, Germany
conference dates
2017-06-25 - 2017-06-30
external identifiers
  • scopus:85034051441
ISBN
978-1-5090-4096-4
DOI
10.1109/ISIT.2017.8006838
language
English
LU publication?
yes
id
b037b8ba-8282-4725-b2a5-10722080521d
date added to LUP
2017-07-03 22:20:13
date last changed
2024-01-14 00:06:34
@inproceedings{b037b8ba-8282-4725-b2a5-10722080521d,
  abstract     = {{The class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. Stern's algorithm is the origin of the most efficient algorithms in this class. In this paper we consider the same decoding problem but for a channel with soft information. We give a version of Stern's algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We then demonstrate how this new algorithm can be used in a few cryptographic applications, including a very efficient attack on a recently proposed McEliece-type cryptosystem.}},
  author       = {{Guo, Qian and Johansson, Thomas and Mårtensson, Erik and Stankovski, Paul}},
  booktitle    = {{IEEE International Symposium on Information Theory (ISIT)}},
  isbn         = {{978-1-5090-4096-4}},
  language     = {{eng}},
  pages        = {{1793--1797}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{Information Set Decoding with Soft Information and some cryptographic applications}},
  url          = {{http://dx.doi.org/10.1109/ISIT.2017.8006838}},
  doi          = {{10.1109/ISIT.2017.8006838}},
  year         = {{2017}},
}