{"entities":{"Q7361269":{"pageid":31519346,"ns":120,"title":"Item:Q7361269","lastrevid":105364412,"modified":"2026-10-07T13:35:20Z","type":"item","id":"Q7361269","labels":{"en":{"language":"en","value":"Hardness of Lattice Problems"}},"descriptions":{"en":{"language":"en","value":"AFP entry CVP_Hardness"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6e96acc5f2073da5f1445491184b516809f8cff4","datavalue":{"value":"https://isa-afp.org/entries/CVP_Hardness.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361269$64C0309F-F88F-484A-AC27-CDA241604756","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1e4ab32b89a08d15e9f667f335823ed489c69f8a","datavalue":{"value":{"time":"+2023-02-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361269$E103272B-0E07-4025-879E-7486F215E0D1","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"5c7a061d577dcccfffdf73a25e38b5684211d46b","datavalue":{"value":"Katharina Kreuzer","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361269$E6A133E5-E827-4C86-B361-9E68E3C7B16C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a60ca8dc0ffeec5c118290f33c394e5a19b87646","datavalue":{"value":{"text":"Hardness of Lattice Problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361269$B4AC7684-1174-4A28-983F-D0E75CA868D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"60091f029c8d1f88a0874039fad29d06df03f5ff","datavalue":{"value":"This article formalizes the NP-hardness proofs of the Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) in maximum norm as well as the CVP in any p-norm for p>=1. CVP and SVP are two fundamental problems in lattice theory. Lattices are a discrete, additive subgroup of R^n and are used for lattice-based cryptography. The CVP asks to find the nearest lattice vector to a target. The SVP asks to find the shortest non-zero lattice vector. This entry formalizes the basic properties of lattices, the reduction from CVP to Subset Sum in both maximum and p-norm for a finite p with 1<= p and the reduction of SVP to Partition using the Bounded Homogeneous Linear Equations problem (BHLE) as an intermediate step. The formalization uncovered a number of problems with the existing proofs in the literature.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361269$7A984F12-A0B2-41E2-AC21-E4DEEA924D01","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$618454CA-69B9-4CE4-B4DC-A108C9BB9ED3","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"85b898be4838452e6583c1aefc063dcd622112e3","datavalue":{"value":{"entity-type":"item","numeric-id":7361604,"id":"Q7361604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$2899E46C-61ED-4505-AF80-2237AAD243FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"58b378310c3c01d83cef379d83129d9bd06f9769","datavalue":{"value":{"entity-type":"item","numeric-id":7361750,"id":"Q7361750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$AB1ECB25-08A3-43A5-85C5-374026FF2C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"67e8a5ea879a7dc06c8ce830c1b61b9bb35cc48f","datavalue":{"value":{"entity-type":"item","numeric-id":7361432,"id":"Q7361432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$C44A8283-CC43-4F9D-99C7-139991073832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"6b0c8751e5c0af23677c31da7dad8b06ad87cc15","datavalue":{"value":{"entity-type":"item","numeric-id":7361415,"id":"Q7361415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$0A680D96-B819-489C-B3F9-AE3273D1898E","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"67cfe7e765f8f36de5d26ce854526f3fec39cd26","datavalue":{"value":{"entity-type":"item","numeric-id":7360802,"id":"Q7360802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$9FF1C0F5-7D8C-4FD5-9785-36FF45AEACC4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361269$4EAB6C42-A77F-4A2A-BED4-F46D38061372","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hardness of Lattice Problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hardness_of_Lattice_Problems"}}}}}