Abstrakt. Det mest kända latticeproblemet är det kortaste vektorproblemet (SVP), som har många tillämpningar inom kryptologi. De bästa approximationsalgoritmer kända för SVP i hög dimension förlitar sig på en subrutin för exakt SVP i låg dimension. I detta dokument bedömer vi hur praktisk den bästa (teoretiska) algoritmen är känd för exakt SVP i låg dimension: den siktalgoritm som föreslogs av Ajtai, Kumar och Sivakumar (AKS) 2001. ACS är en randomiserad algoritm av tid och utrymme komplexitet 2 O(n), som teoretiskt är mycket lägre än den super-exponentiella komplexiteten hos alla alternativa SVP algoritmer. Förvånansvärt nog har inget genomförande och ingen praktisk analys av AKS någonsin rapporterats. Det ansågs i själva verket allmänt att AKS var opraktiskt: till exempel hävdade Schnorr 2003 att den konstant dolda i 2 O(n) komplexitet var minst 30. I detta dokument visar vi att AKS faktiskt kan göras praktiskt: vi presenterar en heuristisk variant av AKS vars körtid är (4/3+ε) n polynom-tid operationer, och vars utrymmeskrav är (4/3+ε) n/2 polynomialt många bitar. Vår implementering kan experimentellt hitta kortaste lattice vektorer upp till dimension 50, men är långsammare än klassiska alternativa SVP algoritmer i dessa dimensioner.
Nguyen och Vidick REF visade att tidskomplexet för AKS är O(2 5.9n+O(n) ) med rymdkomplexet O(2 2.95n+O(n) ).
Sieve algorithms for the shortest vector problem are practical
{'venue': 'J. Mathematical Cryptology', 'journal': 'J. Mathematical Cryptology', 'mag_field_of_study': ['Computer Science', 'Mathematics']}