Abstract
A new protograph-based framework for message passing (MP) decoding of low density parity-check (LDPC) codes with Hamming weight amplifiers (HWAs), which are used e.g. in the NIST post-quantum crypto candidate LEDAcrypt, is proposed. The scheme exploits the correlations in the error patterns introduced by the HWA using a turbo-like decoding approach where messages between the decoders for the outer code given by the HWA and the inner LDPC code are exchanged. Decoding thresholds for the proposed scheme are computed using density evolution (DE) analysis for belief propagation (BP) and ternary message passing (TMP) decoding and compared to existing decoding approaches. The proposed scheme improves upon the basic approach of decoding LDPC code from the amplified error and has a similar performance as decoding the corresponding moderate-density parity-check (MDPC) code but with a significantly lower computational complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
As in most of the literature, we loosely define a code to be QC if there exists a permutation of its coordinates such that the resulting (equivalent) code has the following property: if \(\textit{\textbf{x}}\) is a codeword, then any cyclic shift of \(\textit{\textbf{x}}\) by \(\ell \) positions is a codeword. For example, a code admitting a parity-check matrix as an array of \(R_0\times N_0\) circulants does not fulfill this property. However the code is QC in the loose sense, since it is possible to permute its coordinates to obtain a code for which every cyclic shift of a codeword by \(\ell =N_0\) positions yields another codeword.
- 3.
We assume that \(G'(x)\) can be brought into systematic form which is possible with high probability (see [8]).
- 4.
We assume that the CCA-2 security conversions from [12] are applied to the McEliece cryptosystem to allow for systematic encoding without security reduction.
References
McEliece, R.J.: A public-key cryptosystem based on algebraic codes. Deep Space Netw. Progr. Rep. 44, 114–116 (1978)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Monico, C., Rosenthal, J., Shokrollahi, A.: Using low density parity check codes in the McEliece cryptosystem. In: Proceedings IEEE International Symposium Information Theory (ISIT), Sorrento, Italy, p. 215 (2000)
Baldi, M., Chiaraluce, F.: Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC Codes. In: IEEE International Symposium on Information Theory, pp. 2591–2595 (2007)
Otmani, A., Tillich, J.-P., Dallot, L.: Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes. Math. Comput. Sci. 3(2), 129–140 (2010)
Baldi, M., Bodrato, M., Chiaraluce, F.: A new analysis of the mceliece cryptosystem based on QC-LDPC codes. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 246–262. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85855-3_17
Baldi, M., Bianchi, M., Chiaraluce, F.:Optimization of the parity-check matrix density in QC-LDPC code-based McEliece cryptosystems. In: 2013 IEEE International Conference on Communications Workshops (ICC), pp. 707–711. IEEE(2013)
Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., Santini, P.: LEDAcrypt: low-dEnsity parity-checkcoDe-bAsed cryptographic systems. NIST PQC submission (2019). https://www.ledacrypt.org/
Gallager, R.G.: Low-Density Parity-Check Codes. M.I.T. Press, Cambridge (1963)
Rudolph, L.: A class of majority logic decodable codes (corresp.). IEEE Trans. Inf. Theory 13(2), 305–307 (1967)
Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. In: IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, pp. 2069–2073 (2013)
Kobara, K., Imai, H.: Semantically secure McEliece public-key cryptosystems -conversions for McEliece PKC. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 19–35. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_2
Thorpe, J.: Low-density parity-check (LDPC) codes constructed from protographs. JPL IPN, Technical report, pp. 42–154, August 2003
Abbasfar, A., Yao, K., Disvalar, D.: Accumulate repeat accumulate codes. In: Proceedings of IEEE Globecomm, Dallas, Texas (2004)
Divsalar, D., Dolinar, S., Jones, C., Andrews, K.: Capacity-approaching protograph codes. IEEE JSAC 27(6), 876–888 (2009)
Liva, G., Chiani, M.: Protograph LDPC code design based on EXIT analysis. In: Proceedings of IEEE Globecomm, Washington, US, pp. 3250–3254, December 2007
Bartz, H., Liva, G.: On decoding schemes for the MDPC-McEliece cryptosystem. In: 12th International ITG Conference on Systems, Communications and Coding (SCC), pp. 1–6. VDE (2019)
Lechner, G., Pedersen, T., Kramer, G.: Analysis and design of binary message passing decoders. IEEE Trans. Commun. 60(3), 601–607 (2011)
Yacoub, E.B., Steiner, F., Matuz, B., Liva, G.: Protograph-based LDPC code design for ternary message passing decoding. In: 12th International ITG Conference on Systems, Communications and Coding, SCC 2019, pp. 1–6. VDE, February 2019
Chung, S.-Y., Forney, G.D., Richardson, T.J., Urbanke, R.: On the design of low-density parity-check codes within \(0.0045\) dB of the Shannon limit. IEEE Commun. Lett. 5(2), 58–60 (2001)
Jin, H., Richardson, T.: A new fast density evolution. In: 2006 IEEE Information Theory Workshop-ITW Punta del Este, pp. 183–187. IEEE (2006)
Pulini, P., Liva, G., Chiani, M.: Unequal diversity LDPC codes for relay channels. IEEE Trans. Wirel. Commun. 12(11), 5646–5655 (2013)
Chung, S.-Y., Richardson, T.J., Urbanke, R.L.: Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation. IEEE Trans. Inf. Theory 47(2), 657–670 (2001)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bartz, H., Yacoub, E.B., Bertarelli, L., Liva, G. (2020). Protograph-Based Decoding of Low-Density Parity-Check Codes with Hamming Weight Amplifiers. In: Baldi, M., Persichetti, E., Santini, P. (eds) Code-Based Cryptography. CBCrypto 2020. Lecture Notes in Computer Science(), vol 12087. Springer, Cham. https://doi.org/10.1007/978-3-030-54074-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-54074-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54073-9
Online ISBN: 978-3-030-54074-6
eBook Packages: Computer ScienceComputer Science (R0)