{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:37:04Z","timestamp":1780090624367,"version":"3.54.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:00:00Z","timestamp":1607817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:00:00Z","timestamp":1607817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["187711"],"award-info":[{"award-number":["187711"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["801434"],"award-info":[{"award-number":["801434"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["713683"],"award-info":[{"award-number":["713683"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Low-rank parity-check (LRPC) codes are rank-metric codes over finite fields, which have been proposed by Gaborit et al.\u00a0(Proceedings of the workshop on coding and cryptography WCC, vol 2013, 2013) for cryptographic applications. Inspired by a recent adaption of Gabidulin codes to certain finite rings by Kamche et al.\u00a0(IEEE Trans Inf Theory 65(12):7718\u20137735, 2019), we define and study LRPC codes over Galois rings\u2014a wide class of finite commutative rings. We give a decoding algorithm similar to Gaborit et al.\u2019s decoder, based on simple linear-algebraic operations. We derive an upper bound on the failure probability of the decoder, which is significantly more involved than in the case of finite fields. The bound depends only on the rank of an error, i.e., is independent of its free rank. Further, we analyze the complexity of the decoder. We obtain that there is a class of LRPC codes over a Galois ring that can decode roughly the same number of errors as a Gabidulin code with the same code parameters, but faster than the currently best decoder for Gabidulin codes. However, the price that one needs to pay is a small failure probability, which we can bound from above.<\/jats:p>","DOI":"10.1007\/s10623-020-00825-9","type":"journal-article","created":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T18:02:21Z","timestamp":1607882541000},"page":"351-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Low-rank parity-check codes over Galois rings"],"prefix":"10.1007","volume":"89","author":[{"given":"Julian","family":"Renner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2020-1040","authenticated-orcid":false,"given":"Alessandro","family":"Neri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Puchinger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,12,13]]},"reference":[{"key":"825_CR1","doi-asserted-by":"crossref","unstructured":"Aragon N., Gaborit P., Hauteville A., Ruatta O., Z\u00e9mor G.: Low rank parity check codes: New decoding algorithms and applications to cryptography. arXiv:1904.00357 (2019).","DOI":"10.1109\/TIT.2019.2933535"},{"key":"825_CR2","volume-title":"Finite commutative rings and their applications","author":"G Bini","year":"2012","unstructured":"Bini G., Flamini F.: Finite commutative rings and their applications, vol. 680. Springer Science & Business Media, New York (2012)."},{"issue":"4","key":"825_CR3","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1016\/S0019-9958(72)90223-9","volume":"20","author":"IF Blake","year":"1972","unstructured":"Blake I.F.: Codes over certain rings. Inf. Control 20(4), 396\u2013404 (1972).","journal-title":"Inf. Control"},{"issue":"4","key":"825_CR4","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0019-9958(75)80001-5","volume":"29","author":"IF Blake","year":"1975","unstructured":"Blake I.F.: Codes over integer residue rings. Inf. Control 29(4), 295\u2013300 (1975).","journal-title":"Inf. Control"},{"issue":"3","key":"825_CR5","first-page":"22","volume":"33","author":"I Constantinescu","year":"1997","unstructured":"Constantinescu I., Heise W.: A metric for codes over residue class rings. Problemy Peredachi Inf. 33(3), 22\u201328 (1997).","journal-title":"Problemy Peredachi Inf."},{"issue":"3","key":"825_CR6","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/0097-3165(78)90015-8","volume":"25","author":"P Delsarte","year":"1978","unstructured":"Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226\u2013241 (1978).","journal-title":"J. Comb. Theory Ser. A"},{"issue":"10","key":"825_CR7","doi-asserted-by":"publisher","first-page":"5899","DOI":"10.1109\/TIT.2014.2346079","volume":"60","author":"C Feng","year":"2014","unstructured":"Feng C., N\u00f3brega R.W., Kschischang F.R., Silva D.: Communication over finite-chain-ring matrix channels. IEEE Trans. Inf. Theory 60(10), 5899\u20135917 (2014).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"11","key":"825_CR8","doi-asserted-by":"publisher","first-page":"7576","DOI":"10.1109\/TIT.2013.2274264","volume":"59","author":"C Feng","year":"2013","unstructured":"Feng C., Silva D., Kschischang F.R.: An algebraic approach to physical-layer network coding. IEEE Trans. Inf. Theory 59(11), 7576\u20137596 (2013).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"825_CR9","first-page":"3","volume":"21","author":"EM Gabidulin","year":"1985","unstructured":"Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Inf. 21(1), 3\u201316 (1985).","journal-title":"Problemy Peredachi Inf."},{"key":"825_CR10","unstructured":"Gaborit P., Murat G., Ruatta O., Z\u00e9mor G.: Low rank parity check codes and their application to cryptography. In: Proceedings of the Workshop on Coding and Cryptography WCC. vol.\u00a02013 (2013)."},{"issue":"6","key":"825_CR11","doi-asserted-by":"publisher","first-page":"4480","DOI":"10.1109\/TIT.2017.2778726","volume":"64","author":"E Gorla","year":"2017","unstructured":"Gorla E., Ravagnani A.: An algebraic framework for end-to-end physical-layer network coding. IEEE Trans. Inf. Theory 64(6), 4480\u20134495 (2017).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"825_CR12","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/18.312154","volume":"40","author":"AR Hammons","year":"1994","unstructured":"Hammons A.R., Kumar P.V., Calderbank A.R., Sloane N.J., Sol\u00e9 P.: The Z4-linearity of Kerdock, Preparata, Goethals, and related codes. IEEE Trans. Inf. Theory 40(2), 301\u2013319 (1994).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"825_CR13","doi-asserted-by":"publisher","first-page":"R11","DOI":"10.37236\/1489","volume":"7","author":"T Honold","year":"2000","unstructured":"Honold T., Landjev I.: Linear codes over finite chain rings. Electr. J. Comb. 7, R11\u2013R11 (2000).","journal-title":"Electr. J. Comb."},{"issue":"12","key":"825_CR14","doi-asserted-by":"publisher","first-page":"7718","DOI":"10.1109\/TIT.2019.2933520","volume":"65","author":"HT Kamche","year":"2019","unstructured":"Kamche H.T., Mouaha C.: Rank-metric codes over finite principal ideal rings and applications. IEEE Trans. Inf. Theory 65(12), 7718\u20137735 (2019).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"825_CR15","unstructured":"Kiran T., Rajan B.S.: Optimal STBCs from codes over Galois rings. In: IEEE International Conference on Personal Wireless Communications (ICPWC), pp. 120\u2013124 (2005)."},{"key":"825_CR16","volume-title":"Finite rings with identity","author":"BR McDonald","year":"1974","unstructured":"McDonald B.R.: Finite rings with identity, vol. 28. Marcel Dekker Incorporated, New York (1974)."},{"key":"825_CR17","unstructured":"Melchor C.A., et al.: Nist post-quantum cryptography standardization proposal: rank-Ouroboros, LAKE and LOCKER (ROLLO) (2020)."},{"issue":"10","key":"825_CR18","doi-asserted-by":"publisher","first-page":"6463","DOI":"10.1109\/TIT.2011.2165816","volume":"57","author":"B Nazer","year":"2011","unstructured":"Nazer B., Gastpar M.: Compute-and-forward: harnessing interference through structured codes. IEEE Trans. Inf. Theory 57(10), 6463\u20136486 (2011).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"825_CR19","doi-asserted-by":"crossref","unstructured":"Qachchach I.E., Habachi O., Cances J., Meghdadi V.: Efficient multi-source network coding using low rank parity check code. In: IEEE Wireless Communications and Networking Conference (WCNC) (2018).","DOI":"10.1109\/WCNC.2018.8377229"},{"key":"825_CR20","doi-asserted-by":"crossref","unstructured":"Renner J., Jerkovits T., Bartz H.: Efficient decoding of interleaved low-rank parity-check codes. In: International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY) (2019).","DOI":"10.1109\/REDUNDANCY48165.2019.9003356"},{"key":"825_CR21","doi-asserted-by":"crossref","unstructured":"Renner J., Puchinger S., Wachter-Zeh A., Hollanti C., Freij-Hollanti R.: Low-rank parity-check codes over the ring of integers modulo a prime power. In: IEEE International Symposium on Information Theory (ISIT), conference version of this paper. arXiv:2001.04800 (2020).","DOI":"10.1109\/ISIT44484.2020.9174384"},{"issue":"2","key":"825_CR22","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1109\/18.75248","volume":"37","author":"RM Roth","year":"1991","unstructured":"Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37(2), 328\u2013336 (1991).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"825_CR23","doi-asserted-by":"publisher","first-page":"3951","DOI":"10.1109\/TIT.2008.928291","volume":"54","author":"D Silva","year":"2008","unstructured":"Silva D., Kschischang F.R., Koetter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory 54(9), 3951\u20133967 (2008).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"825_CR24","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(78)90461-8","volume":"37","author":"E Spiegel","year":"1978","unstructured":"Spiegel E.: Codes over Zm, revisited. Inf. Control 37(1), 100\u2013104 (1978).","journal-title":"Inf. Control"},{"key":"825_CR25","unstructured":"Storjohann A.: Algorithms for matrix canonical forms. Ph.D. thesis, ETH Zurich (2000)."},{"issue":"10","key":"825_CR26","doi-asserted-by":"publisher","first-page":"5306","DOI":"10.1109\/TIT.2015.2451623","volume":"61","author":"NE Tunali","year":"2015","unstructured":"Tunali N.E., Huang Y.C., Boutros J.J., Narayanan K.R.: Lattices over Eisenstein integers for compute-and-forward. IEEE Trans. Inf. Theory 61(10), 5306\u20135321 (2015).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"825_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern Computer Algebra","author":"J Von Zur Gathen","year":"2013","unstructured":"Von Zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)."},{"issue":"11","key":"825_CR28","doi-asserted-by":"publisher","first-page":"5641","DOI":"10.1109\/TIT.2010.2068750","volume":"56","author":"MP Wilson","year":"2010","unstructured":"Wilson M.P., Narayanan K., Pfister H.D., Sprintson A.: Joint physical layer coding and network coding for bidirectional relaying. IEEE Trans. Inf. Theory 56(11), 5641\u20135654 (2010).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"825_CR29","doi-asserted-by":"publisher","first-page":"e3256","DOI":"10.1002\/dac.3256","volume":"30","author":"AK Yazbek","year":"2017","unstructured":"Yazbek A.K., EL Qachchach I., Cances J.P., Meghdadi V.: Low rank parity check codes and their application in power line communications smart grid networks. Int. J. Commun. Syst. 30(12), e3256 (2017).","journal-title":"Int. J. Commun. Syst."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-020-00825-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-020-00825-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-020-00825-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T21:27:33Z","timestamp":1612906053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-020-00825-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,13]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["825"],"URL":"https:\/\/doi.org\/10.1007\/s10623-020-00825-9","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,13]]},"assertion":[{"value":"20 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}