A post-quantum hybrid encryption based on QC-LDPC codes in the multi-user setting. (English) Zbl 1458.94285

Summary: The encryption schemes based on coding theory are one of the most accredited choices in post-quantum scenario, where QC-LDPC codes are usually employed to construct concrete schemes due to the well security and good efficiency. In this work, we introduce a new IND-CCA secure multi-instance framework for code-based hybrid encryption primitive in the random oracle model, which is derived from our new multi-instance KEM and DEM building modules.
We note that previous multi-instance KEM and DEM are usually derived from single-instance KEM and DEM, and hence suffers from large parameter sizes and security loss. Nevertheless, our multi-instance KEM is a direct construction based on a key generation function and a one-way trapdoor function, and our multi-instance DEM is constructed from a standard DEM and MAC with a tag in the input to achieve a tighter security loss. Finally, we present a IND-CCA secure multi-instance hybrid encryption scheme based on QC-LDPC codes in the random oracle model, where the scheme achieves small private key size and only consumes addition and multiplication operations over \(\mathbb{F}_2 [x]\).


94A60 Cryptography
94B60 Other types of codes


LEDAkem; McEliece
Full Text: DOI


[1] Aref, Mohammad Reza; Shooshtari, Masoumeh Koochak; Johansson, Thomas; Ahmadian-Attari, Mahmoud, Cryptanalysis of mceliece cryptosystem variants based on quasi-cyclic low-density parity check codes, IET Inf. Secur., 10, 4, 194-202 (2016) · Zbl 1402.94064
[2] Baldi, Marco; Barenghi, Alessandro; Chiaraluce, Franco; Pelosi, Gerardo; Santini, Paolo, Ledakem: a post-quantum key encapsulation mechanism based on qc-ldpc codes, (International Conference on Post-Quantum Cryptography (2018), Springer), 3-24 · Zbl 1425.94046
[3] Baldi, Marco; Bianchi, Marco; Chiaraluce, Franco, Optimization of the parity-check matrix density in qc-ldpc code-based mceliece cryptosystems, (2013 IEEE International Conference on Communications Workshops (ICC) (2013), IEEE), 707-711
[4] Baldi, Marco; Chiaraluce, Franco, Cryptanalysis of a new instance of mceliece cryptosystem based on qc-ldpc codes, (2007 IEEE International Symposium on Information Theory (2007), IEEE), 2591-2595
[5] Bellare, Mihir; Boldyreva, Alexandra; Micali, Silvio, Public-key encryption in a multi-user setting: security proofs and improvements, (International Conference on the Theory and Applications of Cryptographic Techniques (2000), Springer), 259-274 · Zbl 1082.94504
[6] Bellare, Mihir; Tackmann, Björn, The multi-user security of authenticated encryption: Aes-gcm in tls 1.3, (Annual International Cryptology Conference (2016), Springer), 247-276 · Zbl 1378.94023
[7] Berger, Thierry P.; Cayrel, Pierre-Louis; Gaborit, Philippe; Otmani, Ayoub, Reducing key length of the mceliece cryptosystem, (International Conference on Cryptology in Africa (2009), Springer), 77-97 · Zbl 1246.94022
[8] Berlekamp, Elwyn R.; Mceliece, Robert J.; Van Tilborg, Henk C. A., On the inherent intractability of certain coding problems, IEEE Trans. Inf. Theory, 24, 3, 384-386 (1978) · Zbl 0377.94018
[9] Cramer, Ronald; Shoup, Victor, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM J. Comput., 33, 1, 167-226 (2004) · Zbl 1045.94013
[10] Fabšič, Tomáš; Hromada, Viliam; Stankovski, Paul; Zajac, Pavol; Guo, Qian; Johansson, Thomas, A reaction attack on the qc-ldpc mceliece cryptosystem, (International Workshop on Post-Quantum Cryptography (2017), Springer), 51-68 · Zbl 1437.94061
[11] Gallager, Robert, Low-density parity-check codes, IRE Trans. Inf. Theory, 8, 1, 21-28 (1962) · Zbl 0107.11802
[12] Giacon, Federico; Kiltz, Eike; Poettering, Bertram, Hybrid encryption in a multi-user setting, revisited, (IACR International Workshop on Public Key Cryptography (2018), Springer), 159-189 · Zbl 1385.94038
[13] Ghazal, Kachigar; Tillich, Jean-Pierre, Quantum information set decoding algorithms, (International Workshop on Post-Quantum Cryptography (2017), Springer), 69-89 · Zbl 1429.94060
[14] Mceliece, R. J., A public-key cryptosystem based on algebraic coding theory, 114-116 (1978), Deep Space Network Progress Report, 44
[15] Misoczki, Rafael; Tillich, Jean-Pierre; Sendrier, Nicolas; Barreto, Paulo S. L.M., Mdpc-mceliece: new mceliece variants from moderate density parity-check codes, (2013 IEEE International Symposium on Information Theory (2013), IEEE), 2069-2073
[16] Monico, Chris; Rosenthal, Joachim; Shokrollahi, Amin, Using low density parity check codes in the mceliece cryptosystem, (2000 IEEE International Symposium on Information Theory (Cat. No. 00CH37060) (2000), IEEE), 215
[17] Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Probl. Control Inf. Theory, 15, 2, 159-166 (1986) · Zbl 0611.94007
[18] Persichetti, Edoardo, Secure and anonymous hybrid encryption from coding theory, (International Workshop on Post-Quantum Cryptography (2013), Springer), 174-187 · Zbl 1306.94085
[19] Prange, Eugene, The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, 8, 5, 5-9 (1962)
[20] Shoup, Victor, A proposal for an iso standard for public key encryption (version 2.1), IACR ePrint Arch., 112 (2001)
[21] von Maurich, Ingo; Güneysu, Tim, Lightweight code-based cryptography: Qc-mdpc mceliece encryption on reconfigurable devices, (2014 Design, Automation/Test in Europe Conference/Exhibition (DATE) (2014), IEEE), 1-6 · Zbl 1306.94099
[22] von Maurich, Ingo; Heberle, Lukas; Güneysu, Tim, Ind-cca secure hybrid encryption from qc-mdpc niederreiter, (International Workshop on Post-Quantum Cryptography (2016), Springer), 1-17 · Zbl 1334.94097
[23] Zaverucha, Gregory M., Hybrid encryption in the multi-user setting, IACR Crypt. ePrint Arch., 2012, 159 (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.