Breaking the hardness assumption and IND‐CPA security of HQC submitted to NIST PQC project. (1st May 2020)

• Record Type: Journal Article
• Authors: Liu, Zhen; Pan, Yanbin; Xie, Tianyuan
• Is Part Of: IET information security. Volume 14:Number 3(2020)
• Page Start: 313
• Page End: 320
• Publication Date: 2020-05-01
• Subjects: decoding -- public key cryptography -- quantum cryptography -- computational complexity -- optimisation -- cyclic codes; IND‐CPA security -- NIST PQC project -- hamming quasicyclic cryptosystem -- code‐based key encapsulation mechanism -- NIST standardisation process -- public‐key encryption scheme -- IND‐CCA2 secure KEM -- revised scheme HQC‐ β -- HQC cryptosystem -- s‐DQCSD problem -- s‐decision quasi‐cyclic syndrome decoding -- plaintext attack; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2019.0214
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : Hamming quasi‐cyclic (HQC) cryptosystem, proposed by Aguilar Melchor et al ., is a code‐based key encapsulation mechanism (KEM) submitted for the NIST standardisation process of post‐quantum cryptography (PQC). Under the assumption that the s ‐decision quasi‐cyclic syndrome decoding ( s ‐DQCSD) problem is hard for s = 2 and 3, HQC, viewed as a public‐key encryption scheme, is proven to be indistinguishability under chosen plaintext attack (IND‐CPA) secure, and can be transformed into an IND‐Adaptive chosen ciphertext attack secure KEM. However, the authors will show that the s ‐DQCSD problem is actually not intractable and HQC cannot attain IND‐CPA security with all the proposed parameter sets. As HQC was selected as one of the second‐round candidates by NIST, it was also updated to resist attack. The underlying s ‐DQCSD problem was replaced by the s ‐DQCSD with a parity problem and they claimed that the updated HQC could attain IND‐CPA security under the hardness of the new problem. However, they find that there is some flaw in their security proof and the updated HQC is still vulnerable to attack. To fix it, they define a new problem called s ‐DQCSD with variable weight and present revised scheme HQC‐ β, which finally attains the IND‐CPA security under the hardness assumption of the new problem.