{"entities":{"Q1272333":{"pageid":1283083,"ns":120,"title":"Item:Q1272333","lastrevid":42993597,"modified":"2025-07-16T17:07:46Z","type":"item","id":"Q1272333","labels":{"en":{"language":"en","value":"Lattice reduction: a toolbox for the cryptoanalyst"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1233889"}},"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":"Q1272333$0488A93C-538C-4E61-AC29-ED99B496AEA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca1cc99cc9897693b712024dc864716e8740b742","datavalue":{"value":{"text":"Lattice reduction: a toolbox for the cryptoanalyst","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1272333$FC14A379-D05E-47B4-B848-E4CABDF27C13","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7edd8752534f2ac17ba9d8ed2569a696a4421072","datavalue":{"value":"0919.94011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$E8F7B7FF-577C-4BC0-BCC5-5D597B0E9AAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9dccdfd823b736341d3676b2ba8df66b8a35bb49","datavalue":{"value":{"entity-type":"item","numeric-id":775986,"id":"Q775986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272333$0A10CE1E-3585-4962-B0FB-6FF4EDBBACCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41058910419ac1a90dd34fc932d3917f689e31e9","datavalue":{"value":{"entity-type":"item","numeric-id":862418,"id":"Q862418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272333$333DFB7C-15BD-48CD-AEBB-2D1934A74FC6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d5eab3bbb3b6673353b9ed770934b15d004ef795","datavalue":{"value":{"entity-type":"item","numeric-id":166358,"id":"Q166358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272333$2ED14562-0A66-43B9-B00F-9CF150BC52C2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d92e17f445f5981fd8d8ab11b5f702b512eceb9","datavalue":{"value":{"time":"+1999-08-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1272333$2DB84B36-3449-4741-A520-43C1C9BAE775","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bfc398c01df37a8cd0d63139e5fa590ca1d30c13","datavalue":{"value":"A lattice \\(L\\) is a discrete subgroup of \\(\\mathbb R^n\\), the set of integral linear combinations  \\[  {\\lambda}_1 b_1 + \\cdots+{\\lambda}_p b_p  \\]  of a given set of independent \\(n\\)-dimensional vectors \\(b_1 , \\dots , b_p\\). The set \\((b_1 , \\ldots,b_p)\\) is said to be a basis of \\(L\\) and \\(p\\) its dimension. An aim of the paper is explain the application of lattice techniques to cryptanalysis by transforming the cryptographic problem into a lattice reduction problem. A brief description of the LLL algorithm is given to determine an approximation to the shortest vector in a lattice, in the sense of finding a vector whose length does not exceed the length of the shortest vector by more than a given multiplicative constant which depends on the lattice dimension and the actual algorithm used. Some generic problems that come under the scope of lattice reduction problems are considered, including searching for a linear dependence relation with small coefficients among a family of vectors. The case of modular relations is also discussed, as well as solving knapsacks and finding minimal polynomials. Two specific cryptanalyses are given, using these techniques: the cryptanalysis of Knuth's truncated linear congruential generator [\\textit{D. E. Knuth}, The Art of Computer Programming, Vol. 2, Addison-Wesley (1969; Zbl 0191.18001)] and the cryptanalysis of Damg\u00e5rd's hash function [\\textit{I. Damg\u00e5rd}, Crypto 1989, Lect. Notes Comput. Sci. 435, 416--427 (1989; Zbl 0724.68029)]. A sequence of appendices elaborates further on lattices and their application.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272333$2A8FED23-EA29-48C8-A34A-4CCB7F2F87C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$85141E4A-7272-48AE-B4B7-1880B134B808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$F48D3B4B-EB01-418D-9140-8A75C8381BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$47BC5AAA-C342-47B8-96B8-33CAD92B3EA1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a34c0bff80ca65d65dbebc83af25717d99d98358","datavalue":{"value":"1233889","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$4BB9F490-56AF-4250-80EC-7CE9B2502E5C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88a6469559583fc59bd625434aa5d9b0dc35201e","datavalue":{"value":"lattices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272333$A68486E2-4CFC-4E17-9A66-D8E6716F036D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ca18a341e8b649b565a1d8f1ff707d449835862","datavalue":{"value":"cryptanalysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272333$2F8E6A0E-4966-4231-BF55-39C99DF85660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e31db2384563df1e73cf1482781387213054f4b","datavalue":{"value":"knapsack cryptosystems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272333$1A18E00D-3B98-4C7E-B1A4-08F91AA3B2B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d088b961deeaebd3a27470e77a780d5f0e08f2ca","datavalue":{"value":"linear congruential generators","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272333$F19ACE05-9B1F-43D9-80D3-B6A96BAD8BA6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d55353e7bc3d0614b86e9af78e82c119a2d0a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":677137,"id":"Q677137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272333$814AFC23-CCCF-41C0-90E6-1436B4866289","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":"Q1272333$F61714AB-4BB6-4685-A809-8CAF2F719C91","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"513369848cd88e54d936d698352d309263e97469","datavalue":{"value":"https://doi.org/10.1007/s001459900042","type":"string"},"datatype":"url"},"type":"statement","id":"Q1272333$0904DE8A-F569-4477-B0E3-153D23D8A25A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"34f06617bea2a6c7e23faa047011e56212f4d98f","datavalue":{"value":"W1981326822","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$DB15DF9F-6DDE-4A13-8EA4-E1A032ED32B2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"caa335d4fb84e2e8b9e48c6bc17c7f0d799cb64e","datavalue":{"value":"10.1007/S001459900042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272333$D6399AFF-2821-4ED4-908F-F8B512050F5E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ff2e94e0ee78643935d8c49e8e88ac087ed8153","datavalue":{"value":{"entity-type":"item","numeric-id":2739436,"id":"Q2739436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dbd8714c853eedf7bf7554efd0a227b8e298b09","datavalue":{"value":{"amount":"+0.9108251","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$B27DD347-707B-496D-84F8-3BCB26131F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11e35323643e86f8403c763a263d8837f3f20854","datavalue":{"value":{"entity-type":"item","numeric-id":4787205,"id":"Q4787205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78529d67dceeef0264d5cd25e7179493d07b5f35","datavalue":{"value":{"amount":"+0.88369894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$95C87F86-0D55-4459-90A4-3C23528DE21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f1c2d97ba4e97331c25ac106581152b0187c314","datavalue":{"value":{"entity-type":"item","numeric-id":4736443,"id":"Q4736443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"110e25ac31e134fece6b32c20dbbe2fdbe09e445","datavalue":{"value":{"amount":"+0.8802368","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$A109C152-C298-49E0-AB92-253EF14687EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ef38c7877b4ba7d7843e5d27599321fd6322b56","datavalue":{"value":{"entity-type":"item","numeric-id":5188547,"id":"Q5188547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"533c9b265af3a3ea6107b2ae701a819ca4636479","datavalue":{"value":{"amount":"+0.8574759","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$FFA05B2B-0732-4A66-9F5C-AF559BFD1B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9659ed99802d9613c03dfbffaba0dd157dc7b54d","datavalue":{"value":{"entity-type":"item","numeric-id":4460823,"id":"Q4460823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10f29633b04e01b7763e48f764ccfd6707f0925b","datavalue":{"value":{"amount":"+0.8570802","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$CF2C8755-F8D1-4521-8EEA-3ACA5BF005D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21307655dbab78ac6fac2088710662222bcae92f","datavalue":{"value":{"entity-type":"item","numeric-id":4668909,"id":"Q4668909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a3f7d7397711b233ec932d9874596167cebab4a","datavalue":{"value":{"amount":"+0.8546858","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$7E2BBEDF-829E-480A-9588-E655C4D71140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a132c0189095cfba2773990a3c3da83bb6298873","datavalue":{"value":{"entity-type":"item","numeric-id":2868269,"id":"Q2868269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd3ca036f9d09d748e73b64dc86b4ea7a56e1a3e","datavalue":{"value":{"amount":"+0.85103637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$9E856722-F591-45D7-89DF-FA966DF2243B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebebd30dda1d84f92c03659f9bbae1643e38b370","datavalue":{"value":{"entity-type":"item","numeric-id":3800123,"id":"Q3800123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02f0772354e69591438d91a10d2d4d385f2d5ee3","datavalue":{"value":{"amount":"+0.84390414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$370567F8-9787-4E69-9A64-A6791573EDEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"684182c3bcf482ab92d4ca6bd5e40eca0feb3ac6","datavalue":{"value":{"entity-type":"item","numeric-id":5064138,"id":"Q5064138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cc9a02de97ad7830d3de6793aa93ee371ade314","datavalue":{"value":{"amount":"+0.8417939","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$9E44A7EA-7F8F-40AF-A0EC-0D5A204D011C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec5694a83c89ecd253f87934b5d6bd69e464e061","datavalue":{"value":{"entity-type":"item","numeric-id":3003370,"id":"Q3003370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2adf19c3a56be9cee6cce77cbcfa8a71c50dc738","datavalue":{"value":{"amount":"+0.8363909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1272333$2D42C785-EDB5-43EB-99F2-9ECCEA14DABE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1272333","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1272333"}}}}}