Complexity of statistical attacks on QC‐LDPC code‐based cryptosystems. (1st May 2020)

• Record Type: Journal Article
• Authors: Santini, Paolo; Baldi, Marco; Chiaraluce, Franco
• Is Part Of: IET information security. Volume 14:Number 3(2020)
• Page Start: 304
• Page End: 312
• Publication Date: 2020-05-01
• Subjects: parity check codes -- quantum cryptography -- public key cryptography -- decoding -- cryptography -- cyclic codes; statistical attacks -- QC‐LDPC code‐based cryptosystems -- public‐key cryptosystems -- moderate‐density parity‐check codes -- post‐quantum cryptography -- compact keys -- high algorithmic efficiency -- decoding procedure -- secret key -- cryptanalysis procedures -- QC structure -- information set decoding algorithm; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2019.0420
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : Public‐key cryptosystems built on quasi‐cyclic (QC) low‐density parity‐check and moderate‐density parity‐check codes are promising candidates for post‐quantum cryptography, since they are characterised by compact keys and high algorithmic efficiency. The main issue with this kind of system is represented by the fact that, since the decoding procedure is probabilistic, it may leak information about the secret key. In this work, the authors study cryptanalysis procedures that aim at recovering the secret key by exploiting this fact. They identify the phenomenon that is at the basis of these procedures and show that the QC structure plays an important role in the success of these attacks. They use a graph analogy to study the complexity of these attacks, and show that their feasibility strongly depends on the QC structure. They also devise an approach to perform full cryptanalysis by combining an information set decoding algorithm with some partial knowledge about the structure of the secret key.