A Finite Regime Analysis of Information Set Decoding Algorithms
Decoding of random linear block codes has been long exploited as a computationally hard problem on which it is possible to build secure asymmetric cryptosystems. In particular, both correcting an error-affected codeword, and deriving the error vector corresponding to a given syndrome were proven to...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/12/10/209 |
| _version_ | 1818037273708462080 |
|---|---|
| author | Marco Baldi Alessandro Barenghi Franco Chiaraluce Gerardo Pelosi Paolo Santini |
| author_facet | Marco Baldi Alessandro Barenghi Franco Chiaraluce Gerardo Pelosi Paolo Santini |
| author_sort | Marco Baldi |
| collection | DOAJ |
| description | Decoding of random linear block codes has been long exploited as a computationally hard problem on which it is possible to build secure asymmetric cryptosystems. In particular, both correcting an error-affected codeword, and deriving the error vector corresponding to a given syndrome were proven to be equally difficult tasks. Since the pioneering work of Eugene Prange in the early 1960s, a significant research effort has been put into finding more efficient methods to solve the random code decoding problem through a family of algorithms known as information set decoding. The obtained improvements effectively reduce the overall complexity, which was shown to decrease asymptotically at each optimization, while remaining substantially exponential in the number of errors to be either found or corrected. In this work, we provide a comprehensive survey of the information set decoding techniques, providing finite regime temporal and spatial complexities for them. We exploit these formulas to assess the effectiveness of the asymptotic speedups obtained by the improved information set decoding techniques when working with code parameters relevant for cryptographic purposes. We also delineate computational complexities taking into account the achievable speedup via quantum computers and similarly assess such speedups in the finite regime. To provide practical grounding to the choice of cryptographically relevant parameters, we employ as our validation suite the ones chosen by cryptosystems admitted to the second round of the ongoing standardization initiative promoted by the US National Institute of Standards and Technology. |
| first_indexed | 2024-12-10T07:24:14Z |
| format | Article |
| id | doaj.art-b3c21eb704324beca3f80ce1615f8ac9 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-10T07:24:14Z |
| publishDate | 2019-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-b3c21eb704324beca3f80ce1615f8ac92022-12-22T01:57:45ZengMDPI AGAlgorithms1999-48932019-10-01121020910.3390/a12100209a12100209A Finite Regime Analysis of Information Set Decoding AlgorithmsMarco Baldi0Alessandro Barenghi1Franco Chiaraluce2Gerardo Pelosi3Paolo Santini4Department of Information Engineering (DII), Università Politecnica delle Marche, 60131 Ancona, ItalyDepartment of Electronics, Information and Bioengineering (DEIB), Politecnico di Milano, 20133 Milano, ItalyDepartment of Information Engineering (DII), Università Politecnica delle Marche, 60131 Ancona, ItalyDepartment of Electronics, Information and Bioengineering (DEIB), Politecnico di Milano, 20133 Milano, ItalyDepartment of Information Engineering (DII), Università Politecnica delle Marche, 60131 Ancona, ItalyDecoding of random linear block codes has been long exploited as a computationally hard problem on which it is possible to build secure asymmetric cryptosystems. In particular, both correcting an error-affected codeword, and deriving the error vector corresponding to a given syndrome were proven to be equally difficult tasks. Since the pioneering work of Eugene Prange in the early 1960s, a significant research effort has been put into finding more efficient methods to solve the random code decoding problem through a family of algorithms known as information set decoding. The obtained improvements effectively reduce the overall complexity, which was shown to decrease asymptotically at each optimization, while remaining substantially exponential in the number of errors to be either found or corrected. In this work, we provide a comprehensive survey of the information set decoding techniques, providing finite regime temporal and spatial complexities for them. We exploit these formulas to assess the effectiveness of the asymptotic speedups obtained by the improved information set decoding techniques when working with code parameters relevant for cryptographic purposes. We also delineate computational complexities taking into account the achievable speedup via quantum computers and similarly assess such speedups in the finite regime. To provide practical grounding to the choice of cryptographically relevant parameters, we employ as our validation suite the ones chosen by cryptosystems admitted to the second round of the ongoing standardization initiative promoted by the US National Institute of Standards and Technology.https://www.mdpi.com/1999-4893/12/10/209asymmetric cryptosystemscode-based cryptosystemsinformation set decoding |
| spellingShingle | Marco Baldi Alessandro Barenghi Franco Chiaraluce Gerardo Pelosi Paolo Santini A Finite Regime Analysis of Information Set Decoding Algorithms Algorithms asymmetric cryptosystems code-based cryptosystems information set decoding |
| title | A Finite Regime Analysis of Information Set Decoding Algorithms |
| title_full | A Finite Regime Analysis of Information Set Decoding Algorithms |
| title_fullStr | A Finite Regime Analysis of Information Set Decoding Algorithms |
| title_full_unstemmed | A Finite Regime Analysis of Information Set Decoding Algorithms |
| title_short | A Finite Regime Analysis of Information Set Decoding Algorithms |
| title_sort | finite regime analysis of information set decoding algorithms |
| topic | asymmetric cryptosystems code-based cryptosystems information set decoding |
| url | https://www.mdpi.com/1999-4893/12/10/209 |
| work_keys_str_mv | AT marcobaldi afiniteregimeanalysisofinformationsetdecodingalgorithms AT alessandrobarenghi afiniteregimeanalysisofinformationsetdecodingalgorithms AT francochiaraluce afiniteregimeanalysisofinformationsetdecodingalgorithms AT gerardopelosi afiniteregimeanalysisofinformationsetdecodingalgorithms AT paolosantini afiniteregimeanalysisofinformationsetdecodingalgorithms AT marcobaldi finiteregimeanalysisofinformationsetdecodingalgorithms AT alessandrobarenghi finiteregimeanalysisofinformationsetdecodingalgorithms AT francochiaraluce finiteregimeanalysisofinformationsetdecodingalgorithms AT gerardopelosi finiteregimeanalysisofinformationsetdecodingalgorithms AT paolosantini finiteregimeanalysisofinformationsetdecodingalgorithms |