{"entities":{"Q6112240":{"pageid":13246547,"ns":120,"title":"Item:Q6112240","lastrevid":47872357,"modified":"2026-01-02T22:59:16Z","type":"item","id":"Q6112240","labels":{"en":{"language":"en","value":"Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7709009"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$12608051-A907-4B45-A164-2DEF415AE272","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34605173e066a3784818db5ec51318c0838e9c93","datavalue":{"value":{"text":"Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6112240$569B73E5-6298-4D0C-A31E-05B80546BDD1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"518da6371166b1c7b6359a74eb54a64392c5c81f","datavalue":{"value":"1520.14054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$434AD367-83F2-4F76-892A-742AAE39D3F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fe483abc3a8a4d9f6c25ffddaaffffe27487510","datavalue":{"value":{"entity-type":"item","numeric-id":821001,"id":"Q821001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$3FAEE618-D6C4-4C18-A507-69E5FF4D3850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8690f723412481432db838eec3eb43a6aead711b","datavalue":{"value":{"entity-type":"item","numeric-id":285461,"id":"Q285461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$02CE5C14-60F2-4DAE-B7AF-18D3D49C1019","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6930ab8e1ff702d6af91a0a660c081a26e7eb4f9","datavalue":{"value":{"entity-type":"item","numeric-id":259257,"id":"Q259257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$6D7DA93F-CF09-4578-80D7-2B555F0FB85E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffdb0464ea79457016bb9a741b774f33799ce913","datavalue":{"value":{"time":"+2023-07-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6112240$A36BD458-A207-4973-BD67-2343D255CE3A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7455b5922c97152e81f2091c5556e32c015d14d9","datavalue":{"value":"The paper presents two cryptanalytic attacks, with polynomial time complexity, to the IKKR public-key cryptosystem, a code-based scheme due to \\textit{F. Ivanov} et al. [Lect. Notes Comput. Sci. 12087, 41--49 (2020; Zbl 1459.94117)].  The first proposed code-based cryptosystem was the celebrated scheme of \\textit{R. J. McEliece} [DSN Progress Report. Technical report. Pasadena: Jet Propulsion Laboratory (1978)]. In it a message \\(m\\) of length \\(k\\)\\, is ciphered as \\(c=mG_{\\mathrm{pub}}+e\\) where \\(G_{\\mathrm{pub}}\\)\\, is a \\(k\\times n\\)\\, matrix, in fact a generating matrix of a Goppa code, disguised to look as the generating matrix of a general lineal code, and \\(e\\)\\, a error vector with Hamming weigh less or equal that the correcting capability of the Goppa code.  The IKKR cryptosystem (in fact two versions: the modified and the ungraded one) takes a different approach, introducing a new matrix \\(E_{\\mathrm{pub}}\\)\\, and allowing \\(e\\)\\, to be of arbitrary weigh. The ciphering is now \\(c=mG_{\\mathrm{pub}}+eE_{\\mathrm{pub}}\\).  An attack to the IKKR-PKE, the LCKN attack, was proposed by \\textit{Y. Lee} et al. [IEEE Commun. Lett. 24, No. 12, 2678--2681 (2020; \\url{doi:10.1109/LCOMM.2020.3019054})]. The first attack of the present paper is similar to it ``whilst our second attack is more efficient than the LCKN attack''.  Section 2 provides the necessary details about error-correcting codes defined over a finite field \\(\\mathbb{F}_q\\)\\, and Section 3 summarizes the modified and the ungraded IKKR crytosystem.  Section 4 reveals a weakness in the design of the IKKR scheme which is crucial in the two proposed plaintext recovery attacks.(Algorithms 2 and 3). The first algorithm has complexity \\(n^4 + 2n^3+n^2\\)\\, operations in the underlying field \\(\\mathbb{F}_q\\)\\, while Algorithm 3 has complexity \\(2n^3+k^4+k^3+k^2\\)\\, operations.  Section 5 shows results of an implementation using Magma V2.20-5, see Table 3. These results show that ``we can recover the plaintext from a given ciphertext in less than 176 miliseconds''. Finally Section 6 proves the impossibility of repairing both versions of the IKKR scheme.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$8D7F557A-13DB-46E6-B255-4E49B787BC8A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$A6B6804C-FEB8-4DFB-AD27-24C88152D792","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"332a7ca0fc2503044cbe5299ecaa975484163791","datavalue":{"value":"14G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$4E1E34AD-E1B9-4D4A-AC71-F5DCCF3E1960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$79174B3E-4530-4415-BAD0-D36EAA7B646E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4430c94528f7856126af01b3ac6ccc7f8c77602b","datavalue":{"value":"94B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$66AFAABF-1AFF-4F88-A89B-F7F83830C031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5120626c87fbc492ba1414fde6695c15d7ff0d86","datavalue":{"value":"94B27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$DA777986-18FF-4260-A3D6-545DCBDAB69A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5149af4e949ec5212c2548b58c1c7a23c914c47e","datavalue":{"value":"7709009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$1C8E455F-CF16-496F-80AF-313C76333CDC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"686b718c4df90342b5b9b085cf67da9bc2a8c6cd","datavalue":{"value":"code-based cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$9B86D005-AF08-44C1-83FD-D63772015456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c3c8ae83355a448101bccce9b68ab3546425fd6","datavalue":{"value":"McEliece cryptosystem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$41038730-1CD3-47D4-A6C6-A4D145D8890D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8858b8cb63065bc66c53dc02bc7cd9b9ec114fd8","datavalue":{"value":"post-quantum cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$84C5BD8A-DC75-4DF7-A96E-C0DBBD185ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ca18a341e8b649b565a1d8f1ff707d449835862","datavalue":{"value":"cryptanalysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$B1AF6C06-CC23-438E-A5FC-ACA9A80D6990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb2b96144a0e13484bf7b8318814495f97f49a80","datavalue":{"value":"plaintext recovery attack","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$8384B89F-AF84-44B6-9883-C4B72BB4BF69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03d27045659eb5e49a87c4028dc943f70a40ab6d","datavalue":{"value":"public-key encryption","type":"string"},"datatype":"string"},"type":"statement","id":"Q6112240$95AF6A70-010F-4340-BA5C-EDCD1F628C07","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$25457728-C62F-4C21-9ED5-1E02BE948C7D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"796bfe535ae22f74e6ff09ac0d053d5f645ea90a","datavalue":{"value":"https://doi.org/10.3934/amc.2020132","type":"string"},"datatype":"url"},"type":"statement","id":"Q6112240$54A3BB1B-849E-47AE-8B47-02D0D76FA481","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a5291cdb21b4063672a2050877cb1d897fc325f","datavalue":{"value":"W3127124253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$1F85FB78-96C3-46F0-9B92-D33904C24E59","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc70935ab1a0f615694347cc2219f160fdff4b44","datavalue":{"value":{"entity-type":"item","numeric-id":1280761,"id":"Q1280761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$301990A8-1041-4A8A-81E5-FBF90168EFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f731ba36bd6756a622d5db45e9da4aa0f541809c","datavalue":{"value":{"entity-type":"item","numeric-id":2894429,"id":"Q2894429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$8D17B416-1B41-4385-B629-941FD773B79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca29d7d10d8f4dc9ce98d5874bd788d477fa9729","datavalue":{"value":{"entity-type":"item","numeric-id":4156300,"id":"Q4156300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$293D5FA1-1386-4DF7-B3EF-D3C20F0D9F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d0ba7dadfaabcd4a1d0797c918ad363dbb85005","datavalue":{"value":{"entity-type":"item","numeric-id":5199223,"id":"Q5199223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$3BFA30B1-207C-4B90-B3B3-AF51F42A1678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1063c9d231f8e900b205cbaf0e81afb59b750e4c","datavalue":{"value":{"entity-type":"item","numeric-id":5739026,"id":"Q5739026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$9FEE2CEF-B016-4521-9202-5BF03223E003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"848f6fd42fc053107e53083ca8d9f9e6d8c422d2","datavalue":{"value":{"entity-type":"item","numeric-id":5855596,"id":"Q5855596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$462E6A85-A81E-44D4-812F-D2D6DBE40F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9db8d6f2e72bed230ad01ef9b2913c3962654cf9","datavalue":{"value":{"entity-type":"item","numeric-id":2221106,"id":"Q2221106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$B29DE1B3-C4CA-4B52-8458-0D57F08AD819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c716dd8a9b96fa56e00dca59c061bcb36d1be2f3","datavalue":{"value":{"entity-type":"item","numeric-id":3803024,"id":"Q3803024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$7D7F9CF5-D4F2-4A69-AE5F-08DD6CBC85E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"307bcd4e236932a2d2ab6b0d3b00629532366b40","datavalue":{"value":{"entity-type":"item","numeric-id":3818991,"id":"Q3818991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$6F854168-3C12-4067-B7B0-D2AC8D194427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03d646813d6dd939fd62a4efd861ec710faf2279","datavalue":{"value":{"entity-type":"item","numeric-id":2948329,"id":"Q2948329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$E7EF41B7-D5D2-41E1-8CF5-4476A41FFF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a481c8a3e38142416a35f15cf39e5f23a77a036","datavalue":{"value":{"entity-type":"item","numeric-id":2363734,"id":"Q2363734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$7D60AED3-1390-4E57-897A-295A6BAEA1C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c89717bb1e3493fce6ea9aedbef713ede081e7c","datavalue":{"value":{"entity-type":"item","numeric-id":3569139,"id":"Q3569139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$A5384EC4-F322-403B-9968-0EC71BFCA90E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f80b7bf7ee3761e8ce051e2d2e8650b43a647047","datavalue":{"value":{"entity-type":"item","numeric-id":3835408,"id":"Q3835408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6112240$223F626C-8346-4854-AAD8-FCBF40786001","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"89941a335ccf7124de425e9cfb39771abb12f3ee","datavalue":{"value":"10.3934/AMC.2020132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6112240$DD8EEA43-220C-4235-A742-7AE21926266D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40dd8a8806d2a5abd6b732cb13126c48c66c5434","datavalue":{"value":{"entity-type":"item","numeric-id":6174648,"id":"Q6174648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1cb088f288bfd78710d566245589e986b2279bc","datavalue":{"value":{"amount":"+0.8055935502052307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6112240$C02D9EC2-16ED-4C82-A8AD-47CE9EC04596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c9352656fbb921bce2dac9ad1087e82ac737521","datavalue":{"value":{"entity-type":"item","numeric-id":2802612,"id":"Q2802612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"623d3fe8b9ed1637cd5f3eefc779b632d0cabb2a","datavalue":{"value":{"amount":"+0.7661821246147156","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6112240$750CE3E4-04B2-4838-B58F-D29619807EAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bae51f0884aa91467b8d5f28cacee75eaef5820","datavalue":{"value":{"entity-type":"item","numeric-id":4303931,"id":"Q4303931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d1da32712713fcaaf7a62c197a817b48fa4a443","datavalue":{"value":{"amount":"+0.7653934955596924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6112240$6E62073B-5C00-4088-80F0-C6C5723586A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9539028215f89c3db015c7a977a69cc5bf4d28dc","datavalue":{"value":{"entity-type":"item","numeric-id":3803024,"id":"Q3803024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b91771b289a707d02e7bdc29455a6ccb8ed8f142","datavalue":{"value":{"amount":"+0.7650551199913025","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6112240$46459C8F-5054-4DFB-9FA9-92E953FC470A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06ab999083a331792e7a6e73b1e75036cd53168f","datavalue":{"value":{"entity-type":"item","numeric-id":3569137,"id":"Q3569137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ea55d1d2531a50c98ed7a32f5570a4c09f0411c","datavalue":{"value":{"amount":"+0.7649595737457275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6112240$142AACF1-E365-4B35-B972-70FA9B706D6C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6112240","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6112240"}}}}}