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