Some recent progress on the complexity of lattice problems
- 格式:pdf
- 大小:408.27 KB
- 文档页数:21
SomeRecentProgressontheComplexityofLatticeProblems
Jin-YiCai
DepartmentofComputerScienceandEngineering
StateUniversityofNewYork
Buffalo,NY14260.USA.
cai@cse.buffalo.edu
Abstract
Wesurveysomerecentdevelopmentsinthestudyofthecom-
plexityoflatticeproblems.Afteradiscussionofsomeprob-
lemsonlatticeswhichcanbealgorithmicallysolvedeffi-
ciently,ourmainfocusistherecentprogressoncomplex-
ityresultsofintractability.WewilldiscussAjtai’sworst-
case/average-caseconnections,NP-hardnessandnon-NP-
hardness,transferencetheoremsbetweenprimalanddual
lattices,andtheAjtai-Dworkcryptosystem.
1Introduction
Therehavebeensomeexcitingdevelopmentsrecentlycon-
cerningthecomplexityoflatticeproblems.Researchinthe
algorithmicaspectsoflatticeproblemshasbeenactivein
thepast,especiallyfollowingLov´asz’sbasisreductional-
gorithmin1982.Therecentwaveofactivityandinterest
canbetracedinlargeparttotwoseminalpaperswrittenby
Mikl´osAjtaiin1996andin1997respectively.
Inhis1996paper[1],Ajtaifoundaremarkableworst-
casetoaverage-casereductionforsomeversionsofthe
shortestlatticevectorproblem(SVP),therebyestablishinga
worst-casetoaverage-caseconnectionfortheselatticeprob-
lems.Suchaconnectionisnotknowntoholdforanyother
probleminNPbelievedtobeoutsideP.Inhis1997paper
[2],buildingonpreviousworkbyAdleman,Ajtaifurther
provedtheNP-hardnessofSVP,underrandomizedreduc-
tion.TheNP-hardnessofSVPhasbeenalongstanding
openproblem.Stimulatedbythesebreakthroughs,manyre-
searchershaveobtainednewandinterestingresultsforthese
andotherlatticeproblems[3,11,13,14,15,16,17,18,19,
23,30,31,32,33,34,52,55,57].Ourpurposeinthisarticle
istosurveysomeofthisdevelopment.
Ithinktheselatticeproblemsareintrinsicallyinteresting.
Moreover,theworst-casetoaverage-caseconnectiondis-Idonotwanttosay“theconverseisfalse”,sinceitisprobablytrueforthereasonthatbothPNPandthereexistsecurepublic-keycryptosys-tems.ButitisbelievedthatitisinsufficienttoassumeonlyPNPinordertoprovepseudorandomnumbergenerators
exist.firstdiscusswhatisalgorithmicallycomputableefficiently
forsomelatticeproblems(Section3),thenIwilldiscuss
Ajtai’sworst-case/average-caseconnection(Section4),NP-
hardnessresults(Section5),evidenceofnon-NP-hardness
(Section6),transferencetheoremsrelatingprimalanddual
lattices(Section7),andtheAjati-Dworkcryptosystem(Sec-
tion8).
Theselectionofthetopicsishighlysubjectiveanditre-
flectsmylimitedknowledgeandpersonaltaste.Theyare
alsorestrainedbythespacelimitation.Iamsuremanyim-
portantworkshavebeenneglectedornotgivenitsproper
due.Iapologizeforanysuchomissionsormistakes.
2Preliminaries
Alatticeisadiscreteadditivesubgroupinsome.Dis-
cretenessmeansthateverylatticepointisanisolatedpoint
inthetopologyof.Analternativedefinitionisthatalat-
ticeconsistsofalltheintegrallinearcombinationsofaset
oflinearlyindependentvectors,
forall
wherethevectors’sarelinearlyindependentover.Such
asetofgeneratingvectorsarecalledabasis.Thedimension
ofthelinearspan,orequivalentlythenumberof’sinaba-
sisistherank(ordimension)ofthelattice,andisdenoted
by.Wemaywithoutlossofgeneralityassumethat,forotherwisewecanreplacebyitslinear
span.Wedenoteas.
Thebasisofalatticeisnotunique.Anytwobasesarere-
latedtoeachotherbyanintegralmatrixofdeterminant.
Suchamatrixiscalledaunimodularmatrix.Clearlyanin-
tegralmatrixhasanintegralinverseiffitisunimodular,fol-
lowingCramer’srule.
Theparallelepiped
iscalledthefundamentaldomainofthelattice.
Sincebasistransformationisunimodular,thedetermi-
nantwhichisthevolumeofthefunda-
mentaldomainisindependentofthebasis,
andisdenotedby.
Weusetodenotelinearspanover.Givenabasisof,letbethelinear
spanof,andbethesub-
latticegeneratedby.Wedenotebytheor-
thogonalcomplementof.TheprocessofGram-Schmidt
orthogonalizationobtainsfromabasisasetoforthogonalvectors,whereistheor-
thogonalcomponentofperpendicularto:
.
3FromGausstoLov´asz
Beforewediscussintractabilityresultsonlatticeproblems,
letusfirsttakealookatwhatisalgorithmicallyfeasible.In
thissectionwegiveabriefaccountofthemotivationsforthe
2studyoflatticeproblems,someramifications,andthemain
ideasofthebasisreductionalgorithmofLov´asz.
WeshouldstartwithGauss.Theoriginalmotivationfor
thestudyof2-dimensionallatticescamefromthetheoryof
quadraticformsinnumbertheory,whichculminatedinthe
TheoryofGenusandCompositionbyGauss(seee.g.,[28,
22,21]).
Gaussgaveanalgorithmwhichcompletelysolvedthe
classificationproblemof2-dimensionallattices.Thealgo-
rithmcanbeviewedasa2-dimensionalgeneralizationof
aversionoftheEuclideanalgorithm,theCentralizedEu-
clideanAlgorithm(CEA).InthisCEA,giventwointegersand,suppose,wedividebywith
aquotientandaremainder,suchthat
.Thisisquiteobviousgeometrically.Numerically,
willdo.Inapossibletiewhen
,and,we
canbreakthetiearbitrarily.Gauss’algorithmterminatesif.Otherwise,weswitchtheroleofandwith