Using Coding Techniques for Attacking PostQuantum Cryptographic Assumptions and Systems
(2016) Abstract
 Postquantum cryptography for resisting possible attacks from malicious quantum adversaries has become one of the key topics in recent cryptographic research. Its ultimate goal is to search for efficient and secure primitives replacing the factoring and discrete logbased schemes in service that will be broken in polynomial time by Shor’s algorithm. It is now an urgent task to complete this replacement due to the rapid development in building quantum computers.
Among all known postquantum candidates, latticebased and codebased cryptography are two very attractive branches for their solid mathematical foundations as well as their versatile cryptographic applications. There exist several important hardness assumptions in these... (More)  Postquantum cryptography for resisting possible attacks from malicious quantum adversaries has become one of the key topics in recent cryptographic research. Its ultimate goal is to search for efficient and secure primitives replacing the factoring and discrete logbased schemes in service that will be broken in polynomial time by Shor’s algorithm. It is now an urgent task to complete this replacement due to the rapid development in building quantum computers.
Among all known postquantum candidates, latticebased and codebased cryptography are two very attractive branches for their solid mathematical foundations as well as their versatile cryptographic applications. There exist several important hardness assumptions in these two areas, especially that the famous hard learning problems, i.e., the learning parity with noise (LPN) problem, the learning with errors (LWE) problem and their variants, are difficult to solve. It plays a crucial role to determine the concrete complexity of the discussed instances of these problems when characterising the security level of cryptosystems employing these instances.
The LPN assumption and its variants also have significance in Lightweight cryptography, a field for building lowcost cryptographic schemes for highly constraint devices. A better solving algorithm will definitely lead to a security reduction of the schemes making use of the suggested parameters.
In this thesis, we introduce new algorithmic ideas for improving the solving algorithms of these hard problems and analyse their concrete complexity. Our tools are existing techniques from various aspects of the welldeveloped coding theory, and many targeted cryptosystems should increase the size of the suggested parameters for a certain security level. We also present the first keyrecovery reaction attack against QCMDPC, a codebased publickey encryption scheme. This attack can be applied to the CCA2 converted version of QCMDPC to break the claimed CCA2 security. The results can be summarised in the following.
• We use covering codes for solving LPN – the instances suggested for 80bit security in HB variants and LPNC can be solved in less than 2^80 operations.
• We use CRT codes for solving RingLPN with a reducible polynomial –we break the Lapin authentication protocol using the proposed instance for 80bit security in about 2^71 operations.
• We use lattice codes for solving LWE and its variants – we reduce the time complexity for solving some suggested parameter settings drastically; for example, for an instance suggested by Regev with dimension n = 512, the improvement factor is about 2^70 . Several other cryptosystems should employ LWE instances with a larger dimension.
• Using the Hamming leakage model, we reduce the problem of using a sidechannel attack on the fresh rekeying countermeasure to a slightly generalised RingLPN problem with a reducible polynomial, and solve it via birthdaytype attacks and FWHT – compared with the previous research, the improvement factor is about 2^10 in the 128bit leakage model with the same amount of SNR and leaking traces.
• We make use of the fact that the decoding error probability of the iterative decoding algorithm employed in QCMDPC is highly correlated with the error patterns, and leaks some information of the secret key – we implement the attack, which works well targeting both the CPA and CCA2secure versions of QCMDPC.
Besides these attacks, we propose a new McEliecetype publickey cryptosystem generalising MDPC from the binary case to a larger alphabet and suggest parameters based on knowledge of the concrete complexity of the above hard problems. This scheme is very attractive as a topic related to both latticebased and codebased cryptography, which takes advantage of iterative decoding, the McEliece structure, the Euclidean metric, as well as a more compact way of representing information. This scheme is still far from mature and needs to be refined further. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/5a6f70bc8ed6422b815b68c7e2e25be9
 author
 Guo, Qian ^{LU}
 supervisor

 Thomas Johansson ^{LU}
 Paul Stankovski ^{LU}
 opponent

 Associate Professor Albrecht, Martin R., University of London, UK
 organization
 publishing date
 2016
 type
 Thesis
 publication status
 published
 subject
 pages
 243 pages
 publisher
 Department of Electrical and Information Technology, Lund University
 defense location
 Lecture hall E:1406, building E, Ole Römers väg 3, Lund University, Faculty of Engineering LTH, Lund
 defense date
 20161213 10:15
 ISBN
 9789176239834
 9789176239827
 language
 English
 LU publication?
 yes
 id
 5a6f70bc8ed6422b815b68c7e2e25be9
 date added to LUP
 20161116 07:26:01
 date last changed
 20161117 07:50:22
@phdthesis{5a6f70bc8ed6422b815b68c7e2e25be9, abstract = {Postquantum cryptography for resisting possible attacks from malicious quantum adversaries has become one of the key topics in recent cryptographic research. Its ultimate goal is to search for efficient and secure primitives replacing the factoring and discrete logbased schemes in service that will be broken in polynomial time by Shor’s algorithm. It is now an urgent task to complete this replacement due to the rapid development in building quantum computers.<br/><br/>Among all known postquantum candidates, latticebased and codebased cryptography are two very attractive branches for their solid mathematical foundations as well as their versatile cryptographic applications. There exist several important hardness assumptions in these two areas, especially that the famous hard learning problems, i.e., the learning parity with noise (LPN) problem, the learning with errors (LWE) problem and their variants, are difficult to solve. It plays a crucial role to determine the concrete complexity of the discussed instances of these problems when characterising the security level of cryptosystems employing these instances.<br/><br/>The LPN assumption and its variants also have significance in Lightweight cryptography, a field for building lowcost cryptographic schemes for highly constraint devices. A better solving algorithm will definitely lead to a security reduction of the schemes making use of the suggested parameters.<br/><br/>In this thesis, we introduce new algorithmic ideas for improving the solving algorithms of these hard problems and analyse their concrete complexity. Our tools are existing techniques from various aspects of the welldeveloped coding theory, and many targeted cryptosystems should increase the size of the suggested parameters for a certain security level. We also present the first keyrecovery reaction attack against QCMDPC, a codebased publickey encryption scheme. This attack can be applied to the CCA2 converted version of QCMDPC to break the claimed CCA2 security. The results can be summarised in the following.<br/><br/>• We use covering codes for solving LPN – the instances suggested for 80bit security in HB variants and LPNC can be solved in less than 2^80 operations.<br/>• We use CRT codes for solving RingLPN with a reducible polynomial –we break the Lapin authentication protocol using the proposed instance for 80bit security in about 2^71 operations.<br/>• We use lattice codes for solving LWE and its variants – we reduce the time complexity for solving some suggested parameter settings drastically; for example, for an instance suggested by Regev with dimension n = 512, the improvement factor is about 2^70 . Several other cryptosystems should employ LWE instances with a larger dimension.<br/>• Using the Hamming leakage model, we reduce the problem of using a sidechannel attack on the fresh rekeying countermeasure to a slightly generalised RingLPN problem with a reducible polynomial, and solve it via birthdaytype attacks and FWHT – compared with the previous research, the improvement factor is about 2^10 in the 128bit leakage model with the same amount of SNR and leaking traces.<br/>• We make use of the fact that the decoding error probability of the iterative decoding algorithm employed in QCMDPC is highly correlated with the error patterns, and leaks some information of the secret key – we implement the attack, which works well targeting both the CPA and CCA2secure versions of QCMDPC.<br/><br/>Besides these attacks, we propose a new McEliecetype publickey cryptosystem generalising MDPC from the binary case to a larger alphabet and suggest parameters based on knowledge of the concrete complexity of the above hard problems. This scheme is very attractive as a topic related to both latticebased and codebased cryptography, which takes advantage of iterative decoding, the McEliece structure, the Euclidean metric, as well as a more compact way of representing information. This scheme is still far from mature and needs to be refined further.}, author = {Guo, Qian}, isbn = {9789176239834}, language = {eng}, pages = {243}, publisher = {Department of Electrical and Information Technology, Lund University}, school = {Lund University}, title = {Using Coding Techniques for Attacking PostQuantum Cryptographic Assumptions and Systems}, year = {2016}, }