Some Notes on CodeBased Cryptography
(2015) Abstract
 This thesis presents new cryptanalytic results in several areas of codingbased cryptography. In addition, we also investigate the possibility of using convolutional codes in codebased publickey cryptography.
The first algorithm that we present is an informationset decoding algorithm, aiming towards the problem of decoding random linear codes. We apply the generalized birthday technique to informationset decoding, improving the computational complexity over previous approaches.
Next, we present a new version of the McEliece publickey cryptosystem based on convolutional codes. The original construction uses Goppa codes, which is an algebraic code family admitting a welldefined code structure. In... (More)  This thesis presents new cryptanalytic results in several areas of codingbased cryptography. In addition, we also investigate the possibility of using convolutional codes in codebased publickey cryptography.
The first algorithm that we present is an informationset decoding algorithm, aiming towards the problem of decoding random linear codes. We apply the generalized birthday technique to informationset decoding, improving the computational complexity over previous approaches.
Next, we present a new version of the McEliece publickey cryptosystem based on convolutional codes. The original construction uses Goppa codes, which is an algebraic code family admitting a welldefined code structure. In the two constructions proposed, large parts of randomly generated parity checks are used. By increasing the entropy of the generator matrix, this presumably makes structured attacks more difficult.
Following this, we analyze a McEliece variant based on quasicylic MDPC codes. We show that when the underlying code construction has an even dimension, the system is susceptible to, what we call, a squaring attack. Our results show that the new squaring attack allows for great complexity improvements over previous attacks on this particular McEliece construction.
Then, we introduce two new techniques for finding lowweight polynomial multiples. Firstly, we propose a general technique based on a reduction to the minimumdistance problem in coding, which increases the multiplicity of the lowweight codeword by extending the code. We use this algorithm to break some of the instances used by the TCHo cryptosystem. Secondly, we propose an algorithm for finding weight4 polynomials. By using the generalized birthday technique in conjunction with increasing the multiplicity of the lowweight polynomial multiple, we obtain a much better complexity than previously known algorithms.
Lastly, two new algorithms for the learning parities with noise (LPN) problem are proposed. The first one is a general algorithm, applicable to any instance of LPN. The algorithm performs favorably compared to previously known algorithms, breaking the 80bit security of the widely used (512,1/8) instance. The second one focuses on LPN instances over a polynomial ring, when the generator polynomial is reducible. Using the algorithm, we break an 80bit security instance of the Lapin cryptosystem. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/4934002
 author
 Löndahl, Carl ^{LU}
 supervisor
 opponent

 Dr. Sendrier, Nicolas, INRIA Rocquencourt; France
 organization
 publishing date
 2015
 type
 Thesis
 publication status
 published
 subject
 pages
 178 pages
 defense location
 Lecture hall E:1406, Ebuilding, Ole Römers väg 3, Lund University Faculty of Engineering
 defense date
 20150206 10:15
 ISBN
 9789176231197
 language
 English
 LU publication?
 yes
 id
 6a9d5d9d4e4a45ae93d57071bc57180d (old id 4934002)
 date added to LUP
 20150119 10:03:05
 date last changed
 20160919 08:45:18
@phdthesis{6a9d5d9d4e4a45ae93d57071bc57180d, abstract = {This thesis presents new cryptanalytic results in several areas of codingbased cryptography. In addition, we also investigate the possibility of using convolutional codes in codebased publickey cryptography.<br/><br> <br/><br> The first algorithm that we present is an informationset decoding algorithm, aiming towards the problem of decoding random linear codes. We apply the generalized birthday technique to informationset decoding, improving the computational complexity over previous approaches.<br/><br> <br/><br> Next, we present a new version of the McEliece publickey cryptosystem based on convolutional codes. The original construction uses Goppa codes, which is an algebraic code family admitting a welldefined code structure. In the two constructions proposed, large parts of randomly generated parity checks are used. By increasing the entropy of the generator matrix, this presumably makes structured attacks more difficult.<br/><br> <br/><br> Following this, we analyze a McEliece variant based on quasicylic MDPC codes. We show that when the underlying code construction has an even dimension, the system is susceptible to, what we call, a squaring attack. Our results show that the new squaring attack allows for great complexity improvements over previous attacks on this particular McEliece construction.<br/><br> <br/><br> Then, we introduce two new techniques for finding lowweight polynomial multiples. Firstly, we propose a general technique based on a reduction to the minimumdistance problem in coding, which increases the multiplicity of the lowweight codeword by extending the code. We use this algorithm to break some of the instances used by the TCHo cryptosystem. Secondly, we propose an algorithm for finding weight4 polynomials. By using the generalized birthday technique in conjunction with increasing the multiplicity of the lowweight polynomial multiple, we obtain a much better complexity than previously known algorithms.<br/><br> <br/><br> Lastly, two new algorithms for the learning parities with noise (LPN) problem are proposed. The first one is a general algorithm, applicable to any instance of LPN. The algorithm performs favorably compared to previously known algorithms, breaking the 80bit security of the widely used (512,1/8) instance. The second one focuses on LPN instances over a polynomial ring, when the generator polynomial is reducible. Using the algorithm, we break an 80bit security instance of the Lapin cryptosystem.}, author = {Löndahl, Carl}, isbn = {9789176231197}, language = {eng}, pages = {178}, school = {Lund University}, title = {Some Notes on CodeBased Cryptography}, year = {2015}, }