pairwiseubuntu12.10

ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithm:SolvingtheIdealLatticeChallengeof128dimensionsTsukasaIshiguro1ShinsakuKiyomoto1YutakaMiyake1TsuyoshiTakagi2KDDIR&DLaboratoriesInc.
1InstituteofMathematicsforIndustry,KyushuUniversity22014/3/281/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentBackgroundSomecontestsfromTUDarmstadt-SVPChallenge,IdealLatticeChallenge,LatticeChallenge2/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentBackgroundSomecontestsfromTUDarmstadt-SVPChallenge,IdealLatticeChallenge,LatticeChallengeOurcontributions·AparallelversionofanalgorithmforsolvingSVP·Improvementsusingidealstructures·Solvingthe128dimensionalSVPoverideallattice2/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentndimensionallatticeandSVPb1b2ShortestvectorsLatticebasisB=(b1,bn)∈Zn*n,bi∈ZnLatticeL(B)=1≤i≤nαibi,αi∈Z(Euclidean)normofv=(v1,.
.
,vn)||v||=1≤i≤nv2iDenition(ShortestVectorProblem(SVP))GivenalatticeL(B),ndashortestnon-zerovectorinL(B).
3/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentndimensionalideallatticevrot(v)rot2(v)Polynomialrepresentationv=(v1,vn)∈L(B)v(x)=1≤i≤nvixi1∈Z[x]Vectorrotationrot(v)=xv(x)modg(x)g(x):monic,deg(g(x))=nIfrot(v)∈L(B)forallv∈L(B),thentheL(B)iscalledideallattice4/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGauss-reducedDenition(Gauss-reduced)Iftwodifferentvectorsa,b∈L(B)satisfy||a±b||≥max(||a||,||b||),thena,barecalledGauss-reduced.
abb′=ababa+bbaab′a+b′Reducea,barenotGauss-reduced.
a,b′areGauss-reduced.
Wesaythatb(orb′)wasreducedbya.
5/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentPairwise-reducedDenition(Pairwise-reduced)LetAbeasetofdvectorsinL(B).
Ifeverypairoftwovectors(ai,aj)inAfori,j=1,d,ijisGauss-reduced,thentheAiscalledpairwise-reduced.
AnypairofvectorsareGauss-reducedSetofvectors6/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(1)chosenatrandomorpoppedfromstackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(2)checkandreducev(3)ifvwasreduced,movevintostackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(4)checkandreducei(5)ifiwasreduced,moveiintostackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(6)appendvtoL7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reducedGaussSievealgorithmconstructsabiglistLoflatticevectors,whichisalwayspairwise-reduced.
Finally,ashortestvectorappearedinthelistL.
7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithm8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithmOurgoalWeproposeafullyparallelizedGaussSievealgorithm.
8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithmOurgoalWeproposeafullyparallelizedGaussSievealgorithm.
OurstrategyOuralgorithmalwayskeepsthelistLpairwise-reducedwithoutreferencetothenumberofthreads.
8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(1)chooseatrandomorpoppedfromstackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(2)checkandreducevi(3)ifviwasreduced,moveviintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(4)checkandreducevi(5)ifviwasreduced,moveviintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(6)checkandreducei(7)ifiwasreduced,moveiintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(8)appendvitoLv4v3v2v19/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentIsanewLpairwise-reducedListL12345ListVv4v3v2v1·LandVarepairwise-reduced,respectivery·Allpairs(i,vj)areGauss-reduced→V∪Lispairwise-reducedanewL=ListV∪L12345v4v3v2v1+10/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingthe72dimensionalSVP02004006008001000120048121620242832Time(minutes)ThenumberofthreadsTotaltime·Thisinstancehas16cores·Therunningtimedereasesuntil16threads·ThesizesofthelistLaremostofthesame11/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentListoftheimprovementsofGaussSieveGenericimprovements-Samplingshortvectors·Reductionoflengthsofsamplingvectors→about5timesfaster-Improvementofimplementation·UsingSIMDoperations→n=80,96,128→about4timesfastersSpecicimprovements-IdealGaussSieveforn=2α(Anti-cycliclattice)[Schneider,'11]→n=128-Trinomiallatticeforn=2s3t·Inverserotationrot1(v)=x1v(x)modg(x)·Updatingtoshortvectors→n=96→morethan25timesfaster12/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentExperimentenvironmentAmazonEC2cc1.
8xlargeinstanceOS:Ubuntu12.
10IntelXeonE5-2670(2.
6Ghz),total16coresgsievelibrary[Voulgaris]compiler:g++4.
1.
2,OpenMP,OpenMPIImprovementofimplementationOurassumptions-Allabsolutevaluesofnormsofvectorsarelessthan216-CalculatingtimeofinnerproductismostexpensiveWeoptimizedinnerproductbyusingSIMDoperations-8-parallelizationof16-bitadditionandmultiplication(SSE4.
2)→about4timesfaster13/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingtheChallengesSVPChallengedimnCPUhours#instances#threadstype800.
9132Randomlattice962004128RandomlatticeIdealLatticeChallengedimnCPUhours#instances#threadstype800.
9132Ideallattice968132Trinomiallattice12829,994842,688Anti-cycliclatticeOriginalgsievelibraryrequiresabout1weekforsolvinga80dimensionalSVPTrinomiallattice:25timesfaster14/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentConclusionWeproposedaparallelversionoftheGaussSievealgorithmWefoundthenewconditionstospeeduptheGaussSievealgorithmWesolveda128dimensionalSVPoverideallattice,whichhadnotbeensolvedbeforeThefull-versionispublishedin[ePrint2013/388]Openproblems-HowisthetheoreticalcomplexityoftheGaussSieve,theParallelGaussSieve,andtheIdealGaussSieve-DoesthereexistotherconditionsortechniquestospeeduptheGaussSievealgorithm15/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperiment16/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingthe80dimensionalSVP01000200030004000500001000020000300004000050000Runningtime(seconds)Thenumberofsamples$r$17/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSamplingshortvectorOptimizationofsamplingalgorithm,namelySampleDalgorithminKlein'srandomizedroundingalgorithm.
Wetrytoadjusttheparameterwhichdeterminesthetradeoffbetweenthelengthofthenormofsamplevectorsandtherunningtimeofouralgorithm.
Average:6.
24GHMaximum:10.
58GH→Average:1.
66GHMaximum:2.
07GHGHistheGaussianheuristicbound:GH=(1/√π)Γ(n2+1)1n·det(L(B))1n18/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentApplyingIdealGaussSieve[Schneider,ePrint2011/458]Anti-cycliclattice-n=2α,α∈N-Cyclotomicpolynomial:g(x)=xn+1Vectorrotationrot(v)=(vn,v1,vn1)||roti(v)||=||v||,(1≤i≤n)Itiseasytogenerate(n1)independentvectorsroti(v)ofsamelengthfromonevectorvListL1234ListL1234rot(1)rot(2)rot(3)rot(4)rotn1(1)rotn1(2)rotn1(3)rotn1(4)19/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentTrinomialLattice(1/2)Cyclotomicpolynomial:g(x)=xn±xn/2+1-(case1)n=2·3m,m>0-(case2)n=2s3t,s>1,t>0Vectorrotationrot(v)=(vn,v1,vn22,vn21vn1,vn2vn1)Differentialofnorm||rot(v)||||v||=(vn1)22vn21vn1→If(vn1)22vn21vn1<0,normofalatticevectordecreases.
20/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentTrinomialLattice(2/2)Improvement3-1:Inverserotation-rot1(v)=x1v(x)modg(x)x1:inverseofxmodulog(x)Improvement3-2:Vectorupdate-choosingtheshortestvectorinfollowingvectorsrot(v),rot2(v)rotk(v)rot1(v),rot2(v)rotk(v)Solvingthe72dimensionalSVP4080120160200240048121620Runningtime(seconds)Onlyrotation[22]InverserotationInverserotation+Updatingvector21/15