A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors
Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community, including several larger projects and a standardization effort from NIST. One of the most promising algorithms is the code-based
- PDF / 580,664 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 172 Views
Abstract. Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community, including several larger projects and a standardization effort from NIST. One of the most promising algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this work we present a very efficient key recovery attack on the QCMDPC scheme using the fact that decryption uses an iterative decoding step and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80 bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility. Keywords: CCA-security · Key-recovery attack tography · QC-MDPC · Reaction attack
1
· Post-quantum cryp-
Introduction
Given the existence of a large quantum computer, cryptosystems based on factoring or discrete logarithm will no longer be secure, as a quantum computer is able to solve both problems in polynomial time [33]. However, it is not yet known to what extent a future quantum computer can be used to successfully solve other types of problems. New algorithms for secure encryption in a postquantum world (when large quantum computers exist) are currently receiving Supported by the Swedish Research Council (Grants No. 2015-04528). c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 789–815, 2016. DOI: 10.1007/978-3-662-53887-6_29
790
Q. Guo et al.
a lot of attention in the research community, including several larger projects and a standardization effort from NIST [9]. It is often mentioned that the new schemes could be from one of the areas: lattice-based, code-based, hash-based and multi-variate [5]. For code-based schemes, the basic construction is the McEliece public-key cryptosystem (PKC) [28], based on the hardness of decoding a random linear code. The general idea is to transform polynomially solvable instance of the problem into something that looks like a random instance. In this case we transform the generator matrix of a code with simple and efficient decoding to a generator matrix for a randomly looking code. Not knowing the inverse of this transformation, the attacker is facing a presumably hard problem, namely, decoding the random code. The McEliece
Data Loading...
