{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T18:10:41Z","timestamp":1771611041874,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:00:00Z","timestamp":1618704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:00:00Z","timestamp":1618704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["713683"],"award-info":[{"award-number":["713683"]}],"id":[{"id":"10.13039\/100010663","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,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose the new rank-metric code-based cryptosystem  which is based on the hardness of <jats:underline>l<\/jats:underline>ist decoding and <jats:underline>i<\/jats:underline>nterleaved decoding of <jats:underline>Ga<\/jats:underline>bidulin codes.  is an improved variant of the <jats:italic>Faure\u2013Loidreau<\/jats:italic> (FL) system, which was broken in a structural attack by <jats:italic>Gaborit, Otmani, and Tal\u00e9 Kalachi<\/jats:italic> (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail\u2014hence  resists the GOT attack. We also prove that the public-key encryption version of  is IND-CPA secure in the standard model and the key encapsulation mechanisms version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of  are short ciphertext sizes and (relatively) small key sizes. Further,  guarantees correct decryption and has no decryption failure rate. It is <jats:italic>not<\/jats:italic> based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented.<\/jats:p>","DOI":"10.1007\/s10623-021-00861-z","type":"journal-article","created":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T14:02:37Z","timestamp":1618754557000},"page":"1279-1319","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding"],"prefix":"10.1007","volume":"89","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0584-2226","authenticated-orcid":false,"given":"Julian","family":"Renner","sequence":"first","affiliation":[]},{"given":"Sven","family":"Puchinger","sequence":"additional","affiliation":[]},{"given":"Antonia","family":"Wachter-Zeh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,18]]},"reference":[{"key":"861_CR1","unstructured":"Aguilar\u00a0Melchor, C., Aragon, N., Bardet, M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J., Gaborit, P., Hauteville, A., Otmani, A., Ruatta, O., Tillich, J., Zemor, G.: ROLLO - Rank-Ouroboros, LAKE & LOCKER. Second round submission to the NIST post-quantum cryptography call (2019). https:\/\/pqc-rollo.org"},{"key":"861_CR2","unstructured":"Aguilar\u00a0Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J., Gaborit, P., Zemor, G., Couvreur, A., Hauteville: Rank quasi cyclic (RQC). Second round submission to the NIST post-quantum cryptography call (2019). https:\/\/pqc-rqc.org"},{"key":"861_CR3","unstructured":"Aragon, N., Barreto, P., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J., Gaborit, P., Gueron, S., G\u00fcneysu, T., Aguilar\u00a0Melchor, C., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J., Vasseur, V., Zemor, G.: BIKE - bit flipping key encapsulation. Second round submission to the NIST post-quantum cryptography call (2019). https:\/\/pqc-rollo.org"},{"key":"861_CR4","doi-asserted-by":"crossref","unstructured":"Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.P.: A new algorithm for solving the rank syndrome decoding problem. In: IEEE Int. Symp. Inf. Theory (ISIT) (2018)","DOI":"10.1109\/ISIT.2018.8437464"},{"key":"861_CR5","doi-asserted-by":"crossref","unstructured":"Augot, D., Finiasz, M.: A public key encryption scheme based on the polynomial reconstruction problem. LNCS: Revised selected papers of EUROCRYPT 2003 2656, 229\u2013249 (2003)","DOI":"10.1007\/3-540-39200-9_14"},{"key":"861_CR6","doi-asserted-by":"crossref","unstructured":"Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.P.: An algebraic attack on rank metric code-based cryptosystems. Tech. rep. (2019). arXiv:1910.00810v1","DOI":"10.1007\/978-3-030-45727-3_3"},{"key":"861_CR7","doi-asserted-by":"crossref","unstructured":"Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.P., Verbel, J.: Algebraic attacks for solving the rank decoding and minrank problems without Gr\u00f6bner basis (2020)","DOI":"10.1007\/978-3-030-64837-4_17"},{"key":"861_CR8","unstructured":"Bernstein, D., Chou, T., Lange, T., Maurich, I., Misoczki, R., Niederhagen, R., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Wang, W.: Classic McEliece. Second round submission to the NIST post-quantum cryptography call (2019). https:\/\/classic.mceliece.org"},{"key":"861_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-12929-2_6","volume-title":"Post-Quantum Cryptography","author":"DJ Bernstein","year":"2010","unstructured":"Bernstein D.J.: Grover vs. mceliece. In: Sendrier N. (ed.) Post-Quantum Cryptography, pp. 73\u201380. Springer, Berlin Heidelberg (2010)."},{"key":"861_CR10","doi-asserted-by":"crossref","unstructured":"Bettaieb, S., Bidoux, L., Gaborit, P., Marcatel, E.: Preventing timing attacks against RQC using constant time decoding of Gabidulin codes. In: Int. Conf. on Post-Quantum Cryptography (PQCrypto) (2019)","DOI":"10.1007\/978-3-030-25510-7_20"},{"key":"861_CR11","doi-asserted-by":"crossref","unstructured":"Boyer M., Brassard G., H\u00f8yer P., Tapp A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4\u20135), 493\u2013505 (1998)","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"861_CR12","doi-asserted-by":"publisher","first-page":"105169","DOI":"10.1016\/j.jcta.2019.105169","volume":"171","author":"E Byrne","year":"2020","unstructured":"Byrne E., Ravagnani A.: Partition-balanced families of codes and asymptotic enumeration in coding theory. J. Comb. Theory A 171, 105169 (2020).","journal-title":"J. Comb. Theory A"},{"key":"861_CR13","doi-asserted-by":"crossref","unstructured":"Caruso, X., Le Borgne, J.: Fast multiplication for skew polynomials. In: ISSAC (2017)","DOI":"10.1145\/3087604.3087617"},{"issue":"3","key":"861_CR14","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":"2","key":"861_CR15","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TIT.2010.2095232","volume":"57","author":"T Etzion","year":"2011","unstructured":"Etzion T., Vardy A.: Error-correcting codes in projective space. IEEE Trans. Inform. Theory 57(2), 1165\u20131173 (2011).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"861_CR16","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/11779360_24","volume-title":"Coding and Cryptography","author":"C Faure","year":"2006","unstructured":"Faure C., Loidreau P.: A new public-key cryptosystem based on the problem of reconstructing p-polynomials. Coding and Cryptography, pp. 304\u2013315. Springer, Berlin (2006)."},{"key":"861_CR17","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/s00145-011-9114-1","volume":"26","author":"E Fujisaki","year":"2013","unstructured":"Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol 26, 80\u2013101 (2013).","journal-title":"J. Cryptol"},{"issue":"1","key":"861_CR18","first-page":"3","volume":"21","author":"EM Gabidulin","year":"1985","unstructured":"Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21(1), 3\u201316 (1985).","journal-title":"Probl. Inf. Transm."},{"issue":"12","key":"861_CR19","doi-asserted-by":"publisher","first-page":"3289","DOI":"10.1109\/TIT.2003.820038","volume":"49","author":"EM Gabidulin","year":"2003","unstructured":"Gabidulin E.M., Ourivski A.V., Honary B., Ammar B.: Reducible rank codes and their applications to cryptography. IEEE Trans. Inform. Theory 49(12), 3289\u20133293 (2003).","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1\u20133","key":"861_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10623-008-9185-7","volume":"49","author":"EM Gabidulin","year":"2008","unstructured":"Gabidulin E.M., Pilipchuk N.I.: Error and erasure correcting algorithms for rank codes. Des. Codes Cryptogr. 49(1\u20133), 105\u2013122 (2008).","journal-title":"Des. Codes Cryptogr."},{"issue":"7","key":"861_CR21","doi-asserted-by":"publisher","first-page":"1391","DOI":"10.1007\/s10623-017-0402-0","volume":"86","author":"P Gaborit","year":"2018","unstructured":"Gaborit P., Otmani A., Tal\u00e9 Kalachi H.: Polynomial-time key recovery attack on the Faure-Loidreau scheme based on gabidulin codes. Des. Codes Cryptogr. 86(7), 1391\u20131403 (2018).","journal-title":"Des. Codes Cryptogr."},{"key":"861_CR22","doi-asserted-by":"crossref","unstructured":"Gadouleau, M., Yan, Z.: Complexity of decoding Gabidulin codes. In: IEEE Annual Conf. Inform. Science and Syst, pp. 1081\u20131085 (2008)","DOI":"10.1109\/CISS.2008.4558679"},{"key":"861_CR23","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-70500-2_12","volume-title":"Theory of Cryptography","author":"D Hofheinz","year":"2017","unstructured":"Hofheinz D., H\u00f6velmanns K., Kiltz E.: A modular analysis of the Fujisaki-Okamoto transformation. In: Kalai Y., Reyzin L. (eds.) Theory of Cryptography, pp. 341\u2013371. Springer International Publishing, Cham (2017)."},{"issue":"8","key":"861_CR24","doi-asserted-by":"publisher","first-page":"3579","DOI":"10.1109\/TIT.2008.926449","volume":"54","author":"R Koetter","year":"2008","unstructured":"Koetter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inform. Theory 54(8), 3579\u20133591 (2008).","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"5","key":"861_CR25","doi-asserted-by":"publisher","first-page":"2740","DOI":"10.1109\/20.617715","volume":"33","author":"VY Krachkovsky","year":"1997","unstructured":"Krachkovsky V.Y., Lee Y.X.: Decoding for iterative Reed-Solomon coding schemes. IEEE Trans. Magn. 33(5), 2740\u20132742 (1997).","journal-title":"IEEE Trans. Magn."},{"key":"861_CR26","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511525926","volume-title":"Finite Fields","author":"R Lidl","year":"1996","unstructured":"Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and its ApplicationsCambridge University Press, Cambridge (1996)."},{"key":"861_CR27","unstructured":"Loidreau, P., Overbeck, R.: Decoding rank errors beyond the error correcting capability. In: Int. Workshop Alg. Combin. Coding Theory (ACCT) (2006)"},{"key":"861_CR28","unstructured":"Loidreau, P.: M\u00e9trique rang et cryptographie (in French). M\u00e9oire d\u2019habilitation \u00e1 diriger des recherches, Universit\u00e9Pierre et Marie Curie, Paris 6 (2007)"},{"key":"861_CR29","doi-asserted-by":"crossref","unstructured":"Loidreau, P.: A new rank metric codes based encryption scheme. In: Int. Conf. on Post-Quantum Cryptography (PQCrypto) (2017)","DOI":"10.1007\/978-3-319-59879-6_1"},{"key":"861_CR30","unstructured":"Marsaglia, G.: Bounds on the rank of the sum of matrices (1967)"},{"key":"861_CR31","unstructured":"National Institute of Standards and Technology (NIST), U.S. Department of Commerce: Post-quantum cryptography standardization (2017), https:\/\/csrc.nist.gov\/Projects\/post-quantum-cryptography\/Post-Quantum-Cryptography-Standardization"},{"issue":"2","key":"861_CR32","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10623-017-0354-4","volume":"86","author":"A Neri","year":"2018","unstructured":"Neri A., Horlemann-Trautmann A.L., Randrianarisoa T., Rosenthal J.: On the genericity of maximum rank distance and gabidulin codes. Des. Codes Cryptogr. 86(2), 341\u2013363 (2018).","journal-title":"Des. Codes Cryptogr."},{"key":"861_CR33","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10623-008-9175-9","volume":"49","author":"R Nojima","year":"2008","unstructured":"Nojima R., Imai H., Kobara K., Morozov K.: Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptogr. 49, 289\u2013305 (2008).","journal-title":"Des. Codes Cryptogr."},{"key":"861_CR34","unstructured":"Overbeck, R.: Public Key Cryptography based on Coding Theory. Ph.D. thesis, TU Darmstadt, Darmstadt, Germany (2007)"},{"key":"861_CR35","first-page":"50","volume":"3715","author":"R Overbeck","year":"2005","unstructured":"Overbeck R.: A new structural attack for GPT and variants. LNCS MYCRYPT 3715, 50\u201363 (2005).","journal-title":"LNCS MYCRYPT"},{"key":"861_CR36","doi-asserted-by":"crossref","unstructured":"Puchinger, S., Wachter-Zeh, A.: Sub-quadratic decoding of Gabidulin codes. In: IEEE Int. Symp. Inf. Theory (ISIT), pp. 2554\u20132558 (2016)","DOI":"10.1109\/ISIT.2016.7541760"},{"key":"861_CR37","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.jsc.2017.11.012","volume":"89","author":"S Puchinger","year":"2018","unstructured":"Puchinger S., Wachter-Zeh A.: Fast operations on linearized polynomials and their applications in coding theory. J. Symb. Comp 89, 194\u2013215 (2018).","journal-title":"J. Symb. Comp"},{"issue":"4","key":"861_CR38","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1109\/TIT.2016.2532343","volume":"62","author":"N Raviv","year":"2016","unstructured":"Raviv N., Wachter-Zeh A.: Some Gabidulin codes cannot be list decoded efficiently at any radius. IEEE Trans. Inform. Theory 62(4), 1605\u20131615 (2016).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"861_CR39","doi-asserted-by":"crossref","unstructured":"Renner, J., Jerkovits, T., Bartz, H., Puchinger, S., Loidreau, P., Wachter-Zeh, A.: Randomized decoding of Gabidulin codes beyond the unique decoding radius. In: Int. Conf. on Post-Quantum Cryptography (PQCrypto) (2020)","DOI":"10.1007\/978-3-030-44223-1_1"},{"key":"861_CR40","unstructured":"Richter, G., Plass, S.: Error and erasure decoding of rank-codes with a modified Berlekamp-Massey algorithm. In: International ITG Conference on Systems, Communications and Coding 2004 (SCC) (2004)"},{"key":"861_CR41","unstructured":"Rosenkilde, J.S.H.: Personal Communication (2018)"},{"key":"861_CR42","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-030-23696-0_5","volume-title":"Progress in Cryptology: AFRICACRYPT 2019","author":"HA Shehhi","year":"2019","unstructured":"Shehhi H.A., Bellini E., Borba F., Caullery F., Manzano M., Mateu V.: An ind-cca-secure code-based encryption scheme using rank metric. In: Buchmann J., Nitaj A., Rachidi T. (eds.) Progress in Cryptology: AFRICACRYPT 2019, pp. 79\u201396. Springer International Publishing, Cham (2019)."},{"issue":"2","key":"861_CR43","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1109\/TIT.2010.2096032","volume":"57","author":"VR Sidorenko","year":"2011","unstructured":"Sidorenko V.R., Jiang L., Bossert M.: Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes. IEEE Trans. Inform. Theory 57(2), 621\u2013632 (2011).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"861_CR44","doi-asserted-by":"crossref","unstructured":"Silva, D., Kschischang, F.R.: Fast encoding and decoding of gabidulin codes. In: IEEE Int. Symp. Inf. Theory (ISIT), pp. 2858\u20132862 (2009)","DOI":"10.1109\/ISIT.2009.5205272"},{"issue":"9","key":"861_CR45","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., K\u00f6tter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inform. Theory 54(9), 3951\u20133967 (2008).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"861_CR46","unstructured":"Trombetti, R., Zullo, F.: On the list decodability of rank metric codes. preprint (2019), https:\/\/arxiv.org\/abs\/1907.01289"},{"key":"861_CR47","unstructured":"W.\u00a0A. Stein and et\u00a0al.: SageMath Software (http:\/\/wwwsagemathorg)"},{"issue":"11","key":"861_CR48","doi-asserted-by":"publisher","first-page":"7268","DOI":"10.1109\/TIT.2013.2274653","volume":"59","author":"A Wachter-Zeh","year":"2013","unstructured":"Wachter-Zeh A.: Bounds on list decoding of rank-metric codes. IEEE Trans. Inform. Theory 59(11), 7268\u20137277 (2013).","journal-title":"IEEE Trans. Inform. Theory"},{"key":"861_CR49","unstructured":"Wachter-Zeh, A.: Decoding of Block and Convolutional Codes in Rank Metric. Ph.D. thesis, Ulm University and University of Rennes 1, Ulm, Germany and Rennes, France (2013)"},{"key":"861_CR50","doi-asserted-by":"crossref","unstructured":"Wachter-Zeh, A., Puchinger, S., Renner, J.: Repairing the Faure-Loidreau public-key cryptosystem. In: IEEE Int. Symp. Inf. Theory (ISIT), pp. 2426\u20132430 (2018)","DOI":"10.1109\/ISIT.2018.8437561"},{"issue":"2","key":"861_CR51","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/s10623-014-9953-5","volume":"73","author":"A Wachter-Zeh","year":"2014","unstructured":"Wachter-Zeh A., Zeh A.: List and unique error-erasure decoding of interleaved gabidulin codes with interpolation techniques. Des. Codes Cryptogr. 73(2), 547\u2013570 (2014).","journal-title":"Des. Codes Cryptogr."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-021-00861-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-021-00861-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-021-00861-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T15:25:28Z","timestamp":1622042728000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-021-00861-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,18]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["861"],"URL":"https:\/\/doi.org\/10.1007\/s10623-021-00861-z","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,18]]},"assertion":[{"value":"15 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}