发布时间 : 星期三 文章合数剩余The Generic Composite Residuosity Problem更新完毕开始阅读
5.6AnalysisoftheGenericDCRProblemLemma5.1([CNS02])
LetN=PQbeaRSAmodulus.
53
?Ifthereexistsanalgorithmsolvingthe(N,??,e)-Hensel-RSAproblemfor??≥3,thenthereexistsanalgorithmsolvingthe(N,e)-RSAproblem.
?Ifthereexistsanalgorithmsolvingthe(N,2,N)-Hensel-RSAproblem,thenthereexistsanalgorithmsolvingthe(N,g)-compositeresiduosityclassproblem.
5.6AnalysisoftheGenericDCRProblem
WerelatethehardnessofsolvingthegenericDCRproblemtosolvingtheHensel-RSAproblem.IncombinationwiththeaboveresultsofCatalanoetal.,thisrelatesthegenericDCRproblemtotheRSAproblemif??≥3,andtothecompositeresiduosityclassproblemif??≥2.
Theorem5.1Ifsolvingthe(N,??,e)-Hensel-RSAproblemis(εHRSA,t)-hard,thensolvingthegeneric(N,??,e)-decisionalcompositeresiduosityproblemoverZN??is(ε??,t??)hardwithε≤??q2εHRSAq22N???1(P+Q+1)++PN??andt??+q≈t,wherePisthesmallestprimefactorofNandqisanupperboundonthenumberoforaclequeriesissuedbythegenericringalgorithmA.PROOF.Weproceedinasequenceofgames.Westartwithagamewherethe
$
isarandomalgorithminteractswithanoraclewithinitalstate(1,x)wherex←Z?N??
,andweendupwithagamewherethealgorithminteractswithelementofZ?N??
anoraclewherex≡yemodN??isane-thresidue.WewillobtaintheresultbyboundingtheprobabilitythatthealgorithmdistinguishesGameifromGamei?1foralli.InthefollowingletOidenotetheoraclethatAinteractswithinGamei.
Game0.ThisgamecorrespondstothegenericDCRexperimentdescribedabove,withb=0.Thatis,thealgorithminteractswithanoracleO0whoseinitiallistcon-$
isarandomelementofZ?.WehavetentsisL1=(1,x),wherex←Z?N??N??
Pr[AO0(N,??,e)=1]=Pr[AO(N,??,e)=1|b=0].
545TheGenericCompositeResiduosityProblem
Game1.Wechangethewaythechallengexissampled.Insteadofchoosing$$
,Osamplesx←ZN??.WeassumethatO1doessobychoosingtwox←Z?1??Nintegersx0←ZNandx1←ZN???1andsettingx=x1N+x0.Thisisequivalentto$
samplingx←ZN??.OtherwiseO1proceedsexactlylikeO0.
WehaveN???φ(N??)=N???N???1(P?1)(Q?1)=N???1(P+Q+1),andthus
????N???1(P+Q+1)????O1O0
.??Pr[A(N,??,e)=1]?Pr[A(N,??,e)=1]??≤
N??Game2.Inthisgamewemodifythewaytheintegerxissampled.OracleO2
$$
samplesx0←ZNandx1←ZN???1,butinsteadofperformingallcomputationsonintegers,oracleO2usespolynomialsfromZN??[X]fortheinternalrepresentationofringelements.Tothisend,itproceedsasfollows.
1.ThelistLisinitializedwithL1=1andL2=x=XN+x0.NotethatthevariableXisusedinsteadofx1(x1isnotusedthroughoutthegame,butitisusefultohaveitde?nedinordertocompareGame2toGame1intheanalysisbelow).2.Wheneverthealgorithmaskstoperformacomputation?∈{+,?,·}ontwolistelementsLi,Lj,theoraclecomputes
Lk=Li?Lj.
NotethateachlistelementLicanbewrittenasapolynomialLi(X)=(aiX+bi)N+ci,whereai,bi∈ZN???1andci∈ZN.
3.WheneverthealgorithmaskstoperformanequalitytestontwolistelementsLi,Lj,thenO2returns1if
(ai,bi,ci)=(aj,bj,cj),
and0otherwise.
ObservethatO2simulatesO1perfectly,unlessO2replieswith0onanequalitytestquerywhereO1wouldhavereturned1(theoppositecaseisimpossible).Notethatthishappensonlyif
(ai,bi,ci)=(aj,bj,cj)
but
Li(x1)≡Lj(x1)modN??.
$
$
5.6AnalysisoftheGenericDCRProblem55
Sinceci=cjimpliesLi(x1)≡Lj(x1)modN??,itsuf?cestoconsiderthecasewhereci=cjand(ai,bi)=(aj,bj).Inthiscasewehave
aix1+bi≡ajx1+bjmodN???1,
orequivalently
(ai?aj)x1+(bi?bj)≡0modN???1,
(5.2)
wherex1isuniformlyrandomandindependentofthealgorithm’sview.IfPde-notesthesmallestprimefactorofN,thenthepolynomial(5.2)ofdegreeonehasatmostonerootmoduloP.Thus,theprobabilitythatbyissuingqoraclequeriesthealgorithmcomputestwopairs(ai,bi)and(aj,bj))suchthatO2failstosimulateO1isatmostq2/P.Thisimplies
??q2??
????O2O1
??Pr[A(N,??,e)=1]?Pr[A(N,??,e)=1]??≤.
P
Game3.ThisgamecorrespondstothegenericDCRexperimentdescribedabove,withb=1.Thatis,wereplacethesimulatorfromthepreviousgamewithanoracleO3whoseinitiallistcontentsisL1=(1,x).HerexissampledbyO3bychoosing$
y←ZN??andcomputingx:=yNmodN??.Wewritexasx=x1N+x0.NotethatO2simulatesO3perfectly,unless
(ai,bi,ci)=(aj,bj,cj)
but
Li(x1)≡Lj(x1)modN??.
Notethatinthiscasethealgorithmmusthavecomputedtwopairs(ai,bi)and(aj,bj))suchthat
aix1+bi≡ajx1+bjmodN???1,orequivalently
x1≡(bj?bi)(ai?aj)?1modN???1.
(5.3)
SupposethereexistsanalgorithmAperformingasequenceofatmostqoper-ationssuchthattheprobabilitythatthereexisttwopairs(ai,bi)and(aj,bj))suchthat(5.3)holdsisatleastε.Thenwehave
????
????O3O3
??Pr[A(N,??,e)=1]?Pr[A(N,??,e)=1]??≤ε.WecanconstructanalgorithmBsolvingthe(N,??,e)-Hensel-RSAproblemas
$
follows.Breceivesasinputx0=xemodNforrandomx←ZN.Notethatx0isuniformlydistributedoverZN,sincethemapx→xemodNisapermutationover
565TheGenericCompositeResiduosityProblem
ZNifgcd(e,φ(N))=1.BrunsAasasubroutinebyimplementingthesimulatorfromGame2forA.WhenAterminates,orafteratmostqoraclequeries,B
$
guessestworandomindicesi,j←{1,...,q},andcomputesandreturns
τ≡(bj?bi)(ai?aj)?1modN???1.
Byassumption,withprobabilityatleastεthereexisttwopairs(ai,bi)and(aj,bj))suchthat(5.3)holds.Withprobability1/q2,Bguessestheindicesi,jcorrectly,suchthatitobtainsτ=x1.Thuswehaveε≤q2/εHRSA,andtherefore
????q2????O3O2
.??Pr[A(N,??,e)=1]?Pr[A(N,??,e)=1]??≤
εHRSAGame4.Wechangethewaythechallengeissampled.Insteadofchoosing$$
andthencomputesx:=yNmodN??.Thuswehavey←ZN??,O4choosesy←Z?N??
Pr[AO4(N,??,e)=1]=Pr[AO(N,??,e)=1|b=1].
and,likeinGame1,
????N???1(P+Q+1)????O4O3
.??Pr[A(N,??,e)=1]?Pr[A(N,??,e)=1]??≤
N??CollectingprobabilitiesfromGame0toGame4yields
????????OO
??Pr[A(N,??,e)=1|b=0]?Pr[A(N,??,e)=1|b=1]??
≤
q2εHRSA
q22N???1(P+Q+1)++PN????
Genericdisclaimer.Wenoteagainthatitseemsdangeroustoperceivehardness
resultsinthegenericmodelasevidencetowardsahardnessassumption,sincetheresultholdsonlyfora(quitegeneral,butstill)restrictedclassofalgorithms.ThisholdsespeciallygiventheresultsfromChapter4,showingthatthereexistpractical(i.e.notcontrived)computationalproblemswhichareprovablyhardtosolvegenerically,buteasytosolveingeneral.
However,wethinkthataproofinthegenericmodelisstillinterestingfromacryptanalyticpointofview,sinceitrulesoutalargeclassofalgorithms(namelyallalgorithmsthatdonotexploitspeci?cpropertiesoftherepresentationofringelements)solvingtheconsideredproblemef?ciently.