Public key cryptography [Elektronische Ressource] : theory and practice / von Bodo Möller
117 pages
Deutsch
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Public key cryptography [Elektronische Ressource] : theory and practice / von Bodo Möller

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
117 pages
Deutsch

Description

Public-Key CryptographyTheory and PracticeVom Fachbereich Informatikder Technischen Universit at DarmstadtgenehmigteDissertationzur Erreichung des akademischen GradesDoctor rerum naturalium (Dr. rer. nat.)vonDipl.-Inform. Bodo M olleraus HamburgReferenten: Prof. Dr. Johannes Buchmann (TU Darmstadt)Prof. Dr. Christof Paar (Ruhr-Universit at Bochum)Tag der Einreichung: 1. Juli 2003Tag der mundlic hen Prufung: 16. September 2003Darmstadt, 2003Hochschulkennzi er: D 17Viele haben auf die eine oder andere Weise dazu beigetragen, dass diese Dissertation so entstehenkonnte, wie sie nun vorliegt. Der Versuch einer vollst andigen Aufz ahlung musste scheitern; hier seienzun achst die erw ahnt, die nicht mit Namen genannt werden k onnen, weil sie als anonyme Gutachterfur Konferenzen atigt waren und dabei Anregungen zur Darstellung einiger der hier pr asentiertenErgebnisse beigetragen haben. Au erdem zu nennen ist David Hopwood, der in einer fruheren Fassungder Ausfuhrungen zur beweisbaren Sicherheit des Mix-Verfahrens (hier in Abschnitt 4.2) eine Luc keaufgespurt hat. Prof. Johannes Buchmann hat es auf bemerkenswerte Weise verstanden, die Arbeits-bedingungen zu scha en, in denen diese Dissertation gedeihen konnte, und hat wertvolle Anregungengeliefert. Auch alle anderen am Fachgebiet Theoretische Informatik hatten teil daran, eine angenehmeund fruchtbare Arbeitsatmosph are zu scha en. Danke!Darmstadt, im September 2003 B. M.

Sujets

Informations

Publié par
Publié le 01 janvier 2003
Nombre de lectures 29
Langue Deutsch

Exrait

Public-KeyTheoryandCryptographPracticey

ten:Referen

VomFachbereichInformatik
derTechnischenUniversit¨atDarmstadt
genehmigte

Dissertation

zurDoctorErreichrerumungdesnaturaliumakademisc(Dr.henrer.Gradesnat.)

von

ollerM¨doBoDipl.-Inform.

burgHamaus

Prof.Dr.JohannesBuchmann(TUDarmstadt)
Prof.Dr.ChristofPaar(Ruhr-Universit¨atBochum)

TagderEinreichung:1.Juli2003
Tagderm¨undlichenPr¨ufung:16.September2003

2003Darmstadt,Hochschulkennziffer:D17

VielehabenaufdieeineoderandereWeisedazubeigetragen,dassdieseDissertationsoentstehen
konnte,wiesienunvorliegt.DerVersucheinervollst¨andigenAufz¨ahlungm¨usstescheitern;hierseien
zun¨achstdieerw¨ahnt,dienichtmitNamengenanntwerdenk¨onnen,weilsiealsanonymeGutachter
f¨urKonferenzent¨atigwarenunddabeiAnregungenzurDarstellungeinigerderhierpr¨asentierten
Ergebnissebeigetragenhaben.AußerdemzunennenistDavidHopwood,derineinerfr¨uherenFassung
derAusf¨uhrungenzurbeweisbarenSicherheitdesMix-Verfahrens(hierinAbschnitt4.2)eineL¨ucke
aufgesp¨urthat.Prof.JohannesBuchmannhatesaufbemerkenswerteWeiseverstanden,dieArbeits-
bedingungenzuschaffen,indenendieseDissertationgedeihenkonnte,undhatwertvolleAnregungen
geliefert.AuchalleanderenamFachgebietTheoretischeInformatikhattenteildaran,eineangenehme
undfruchtbareArbeitsatmosph¨arezuschaffen.Danke!

Darmstadt,imSeptember2003

M.B.

Abstract

3

TheoryI:artPProvablesecurityisanimportantgoalinthedesignofpublic-keycryptosystems.Formost
securityproperties,itiscomputationalsecuritythathastobeconsidered:anattackscenario
describeshowadversariesinteractwiththecryptosystem,tryingtoattackit;thesystemcan
becalledsecureifadversarieswithreasonablyboundedcomputationalmeanshavenegligible
prospappropriateectsofsensesuccess.meansThethatlackofthereislittlecomputationalhopeforproblemsabsolutethatproareofsofguaranteedcomputationaltobehardsecuritinyan.
complexInstead,cryptographicreduction-basedschemesecuritisyprorelatedofstohavethetobsecuriteyused:ofthesimplercomputationalunderlyingsecuritcryptographicyofa
primitives(underappropriatenotionsofsecurity).Theideaistoshowthatifthecomplex
scdescribhemeedisnotquansecure,titativelythenasthisis“concretebecausesecuritoney”,ofthemeasuredprimitivdepesisendingnotonsecure.thepowSecuriterygivcanenbtoe
ersaries.advTheDHAESconstruction(duetoAbdalla,Bellare,andRogaway)allowsbuildingapublic-
keyencryptionschemefromakeyencapsulationmechanism(KEM),aone-timemessage
authenticationcode(one-timeMAC),andapseudo-randombitstringgenerator.Areduction-
basedsecurityproofshowsthatDHAESachievessecurityagainst(adaptive)chosen-ciphertext
attacgeneralksifattacthesekscenariounderlyingforprimitivpublic-keseyaresecure.encryption.)(Suchchosen-ciphertextattacksarethemost
Aspecificapplicationforpublic-keycryptographyisconsidered,namelyChaum’smix
chainwithoutconceptrequiringforuntrusttraceableinasingleelectronicauthoritmaily,viamessagescryptographicarerecursivremailers:elytopublic-kobtaineyanonencryptedymity
latoyermofultipleinencryption.termediatesToconceal(mixes),asmeacuchhofwhicinformationhforwaspardsossiblethewhenmessageusingaftervariableremoving(sourceone
routed)chains,allmessagespassedtomixesshouldbeofthesamelength;thus,message
lengthshouldnotdecreasewhenamixtransformsaninputmessageintothecorresponding
outputmessagedirectedatthenextmixinthechain.Chaumdescribedanimplementationfor
suchlength-preservingmixes,butitisnotsecureagainstactiveattacks.Thisthesispresents
anewconstructionforpracticallength-preservingmixes,whichusesthecryptographicprim-
itivesdescribedforDHAES.Theconventionaldefinitionofsecurityagainstchosenciphertext
attacpropriateksforsecuritpublic-kyeydefinitionsencryptionarescintrohemesduced;isnotitisshoapplicablewnthattothemixlength-preservingconstructionmixes,acsohievap-es
provablesecurity.

PracticeI:IartPMostinstantiationsofpublic-keycryptographyinvolvecomputingpowers(exponentiation)
orcomputingpowerproducts(“multi-exponentiation”)insomecommutativesemigroupwith
neutralelement.Thisthesisdescribestheslidingwindowtechniqueforarbitrarycommuta-
tivesemigroupswithneutralelementanditssigned-digitvariant(“windowNAF”)forgroups
whereinversionisfast(e.g.pointgroupsofellipticcurvesandclassgroupsofimaginary
quadraticnumberfields),andthenpresentsnewtechniques.Fractionalwindows,agen-
eralizationofthepreviouslyknownwindowmethods,canbeusefulfordeviceswithlimited
storage.Interleavedexponentiationisasimplestrategyformulti-exponentiation;thecompar-
isonwithprevioussimultaneousexponentiationmethodsshowsthatitoftenprovidesbetter

4

.efficiency

WindowNAFsplittingisamethodforfastexponentiationwithprecomputation

forafixedbaseingroupswhereinversionisfast.

Forthecaseofellipticcurves,side-channelattacksarediscussed,i.e.attackswhereadver-

sariesusepowerconsumptionmeasurementsorsimilarobservationstoderiveinformationon

secretvalues.Twomethodsareshownthataredesignedtolimitpotentialinformationleak-
ageavailabletoadversaries:a2w-aryleft-to-rightmethodemployingspecialrepresentations
ofscalars,anda2w-aryright-to-leftmethodwithaspecialrandomizedinitializationstage.

of

scalars,

and

a

2

-ary

right-to-left

method

with

methodemployingspecialrepresentations

a

special

randomized

initialization

stage.

Zusammenfassung

5

TheorieI:eilTBeweisbareSicherheitisteinwichtigesZielbeimEntwurfvonPublic-Key-Kryptosystemen.
F¨urdiemeistenSicherheitseigenschaftenmusshierbeipraktischeSicherheitgegenAngreifer
mitbeschr¨anktenMittelnbetrachtetwerden:EinAngriffsszenariobeschreibt,wieGegner
mitdemKryptosysteminteragierend¨urfen,umesanzugreifen;dasSystemkanndannals
sicherbezeichnetwerden,wennGegnermiteinempraktikablenRechenaufwandnurver-
nachl¨assigbareErfolgsaussichtenerzielenk¨onnen.DaeskeineBerechnungsproblemegibt,die
bewiesenermaßenineinemgeeignetenSinneschwersind,gibtesnurwenigHoffnungf¨ur
absoluteSicherheitsbeweiseimSinnesolcherpraktischerSicherheit.Stattdessenmussauf
reduktionsbasierteSicherheitsbeweisezur¨uckgegriffenwerden:DiepraktischeSicherheiteines
komplexenkryptographischenSystemswirdzuderSicherheiteinfachererzugrundeliegender
kryptographischerPrimitive(mitjeweilspassendenSicherheitsbegriffen)inBeziehunggestellt.
DerGrundgedankeist,zuzeigen,dassdaskomplexeSystemnurdannunsicherseinkann,
wenneinederPrimitivenunsicherist.DieSicherheitkannals,,konkreteSicherheit“quantita-
tivbeschriebenwerdeninAbh¨angigkeitvondenMitteln,dieGegnernzurVerf¨ugungstehen.
MitdemDHAES-SchemavonAbdalla,BellareundRogawaykannmanauseinem
Schl¨usselaustauschverfahren(keyencapsulationmechanism,KEM),einemEinmal-MAC
(messageauthenticationcode)undeinemPseudozufallsbitstringgeneratoreinPublic-Key-
Verschl¨usselungsverfahrenkonstruieren.EinreduktionsbasierterSicherheitsbeweiszeigt,dass
DHAESSicherheitgegen(adaptive),,Chosen-ciphertext“-Angriffeerzielt,fallsdiezugrun-
deliegendenPrimitivesichersind.(SolcheChosen-ciphertext-Angriffesinddasallgemeinste
Angriffsszenariof¨urPublic-Key-Verschl¨usselung.)
EinespezifischeAnwendungf¨urPublic-Key-Kryptographiewirdbetrachtet,ChaumsMix-
Ketten-Konzeptf¨urnichtverfolgbareE-Mail¨uberkryptographischeRemailer:DamitAb-
senderAnonymit¨aterreichenk¨onnen,ohneeinereinzelnenStellevertrauenzum¨ussen,werden
Nachrichtenrekursivf¨urmehrereZwischenstellenverschl¨usselt(die,,Mixe“),diejeweilsdie
Nachrichtweitersenden,nachdemsieeineEbenederVerschl¨usselungentfernthaben.Umbei
derBenutzungvonvariablenMix-KettensowenigInformationwiem¨oglichzuverraten,sollten
alleanMixegesandteNachrichtendiegleicheL¨angehaben;alsosolltedieNachrichtenl¨ange
sichnichtverringern,wenneinMixeineankommendeNachrichtumwandeltindieNachricht,
dieerandenn¨achstenMixinderKetteweiterzuleitenhat.DievonChaumbeschriebene
Konstruktionf¨ursolchel¨angenerhalteneMixeistnichtsichergegenaktiveAngreifer.Diese
DissertationstellteineneueKonstruktionf¨urpraktischel¨angenerhalteneMixevor,welcheauf
denf¨urDHAESangegebenenkryptographischenPrimitivenaufbaut.Die¨ublicheDefinition
f¨urSicherheitgegen,,Chosen-ciphertext“-AngriffebeiPublic-Key-Verschl¨usselungkannf¨ur
l¨angenerhaltendeMixenichtangewendetwerden;deshalbwerdenangemesseneSicherheits-
definitionenvorgestellt.Eswirdgezeigt,dassdieMix-KonstruktionbeweisbareSicherheit
bietet.

PraxisI:IeilTBeiderDurchf¨uhrungvonPublic-Key-Kryptographiesind¨ublicherweisePotenzenzuberech-
nen(Exponentiation)oderProduktevonPotenzen(,,Multi-Exponentiation“).DieseDisser-
tationbeschreibtdie,,Sliding-window“-Technikf¨urbeliebigekommutativeHalbgruppenmit
neutralemElementundihreVariantemitvorzeichenbehafteterCodierung(,,windowNAF“),

6

dief¨urGruppenmitschnellerInvertierungverwendetwerdenkann(z.B.Punktegruppen
elliptischerKurvenoderKlassengruppenimagin¨arquadratischerZahlk¨orper).Anschließend
wzu,erden,fractionalneueTecwindohnikwsen“kpr¨annasenf¨urtiert:RecDiehnerVmitbescerallgemeinerunghr¨anktemderSpbeicekannherplatztenFvonVenstermethoorteilsein.den
,,Ingleichterleamitveddenexpbekonenanntentiation“Multi-Expisteineoneneinfachetiations-MethoStrategiefden¨ur(,,simMulti-Expultaneousonenexptiation;onendertiationVer-“)
odezeigt,zurdassscderhnellenneueExpAnsatzonenofttiationbesseremitVorbEffizienzerechnliefert.ung,f¨ur,WindoeinewNAFfeststehendesplittingBasis“istineineGruppMeth-en
mitschnellerInvertierung.
d.h.F¨urAngriffe,denFballeivondenenelliptiscAngreiferhenKurvMessungenenwerdendesscStromhließlicvherbraucSeitenkhsoder¨analangriffeahnlicheBeobacdiskutiert,h-
dentungenvborgestellt,enutzen,dieumgezieltdemInformationBek¨annubterwerdengeheimevonWertegeheimerzuerhalten.InformationZwei¨ubVererfahrenSeitenkwan¨er-ale
wenderSktgegenalarewirkben:eruht,eine2und-¨areeine2w-¨Links-nacareRech-rechhts-nacts-Methoh-links-Methode,dieaufdemiteinerspeinemeziellenbesonderenDarstellungran-
hritt.Initialisierungsscdomisierten

1arungErkl¨

7

Hiermiterkl¨areich,dassichdievorliegendeArbeit–abgesehenvondeninihrausdr¨ucklich
genanntenHilfen–selbst¨andigverfassthabe.

WissenschaftlicherWerdegangdesVerfassersinKurzfassung2

1999Okt.–1993Okt.10.20.1999

Nov.1999–Sept.2003

StudiumderInformatikmitErg¨anzungsfachMathematik
anderUniversit¨atHamburg
(Dipl.-Inform.)ufung¨Diplompr

wissenschaftlicherMitarbeiteramFachgebietTheoretische
Informatik(Prof.J.Buchmann),FachbereichInformatik,
TechnischeUniversit¨atDarmstadt

12gem¨gem¨aßaߧ§920Abs.Abs.13derderPromotionsordnPromotionsordnungungderderTUTUDarmstadtDarmstadt

8

tstenCon

1ductiontroIn

TheoryI

2Public-KeyCryptographyandProvableSecurity
2.1Information-TheoreticSecurity..........................
2.2Public-KeyCryptography.............................
2.3ComputationalSecurity..............................
2.3.1Example:IND-CPASecurity.......................
2.3.2Reduction-BasedSecurityProofs.....................
2.3.3AsymptoticSecurityProofs........................
2.3.4TheRandomOracleModel........................
2.3.5Conclusions.................................

3HybridPublic-KeyEncryption:TheDHAESConstruction
3.1AdaptiveChosen-CiphertextAttacks.......................
3.2PrimitivesfortheDHAESConstruction.....................
3.3TheDHAESPublic-KeyEncryptionScheme..................
3.4TheSecurityoftheDHAESConstruction....................
3.4.1SecurityoftheKeyEncapsulationMechanism.............
3.4.2SecurityoftheOne-TimeMessageAuthenticationCode........
3.4.3SecurityofthePseudo-RandomBitStringGenerator.........
3.4.4SecurityResultfortheDHAESConstruction..............

4APublic-KeyCryptosystemforLength-PreservingChaumianMixes
4.1TheMixEncryptionScheme...........................
4.1.1Encryption.................................
4.1.2Decryption.................................
4.2ProvableSecurity..................................
4.2.1UnlinkabilityoftheMixEncryptionScheme...............
4.2.2CCASecurityoftheMixEncryptionScheme..............
4.2.3SecurityResults..............................

9

13

15

171718202122232425

272830323333343535

3941424345464749

10

tstenCon

53PracticeII5ExponentiationandMulti-ExponentiationinPublic-KeyCryptography55
6EfficientExponentiation59
6.1AFrameworkforExponentiation.........................59
6.1.1Left-to-RightMethods...........................60
6.1.2Right-to-LeftMethods...........................61
6.2SlidingWindowExponentiationandWindowNAFExponentiation......62
6.2.1ModifiedWindowNAFs..........................63
6.3FractionalWindows................................64
6.3.1SignedFractionalWindows........................64
6.3.2UnsignedFractionalWindows.......................67
6.4CompactEncodings................................69
7EfficientMulti-Exponentiation71
7.1SimultaneousExponentiation...........................72
w7.1.1Simultaneous2-AryExponentiationMethod..............73
7.1.2SimultaneousSlidingWindowExponentiationMethod.........74
7.2InterleavedExponentiation............................75
7.2.1BasicInterleavedExponentiationMethod................76
7.2.2Window-NAFBasedInterleavedExponentiationMethod.......77
7.3ComparisonofSimultaneousandInterleavedExponentiationMethods....78
w7.3.1ComparisonbetweentheSimultaneous2-AryMethodandtheBasic
InterleavedMethod.............................79
7.3.2ComparisonbetweentheSimultaneousSlidingWindowMethodand
theWindow-NAFBasedInterleavedMethod..............79
7.3.3ComparisonbetweentheDimitrov-Jullien-MillerMulti-Exponentiation
MethodandInterleavedExponentiation.................80
7.3.4Multi-ExponentiationwithFractionalWindows.............81
7.3.5Examples..................................81
7.3.6Conclusions.................................82
7.4ExponentiationandMulti-ExponentiationwithPrecomputationforFixedBases82
7.4.1ExponentSplitting.............................84
7.4.2Lim-LeePrecomputation.........................84
7.4.3WindowNAFSplitting..........................85
8EllipticCurvePointMultiplicationwithResistanceagainstSide-Channel
87ksttacA8.1PreviousSide-ChannelAttackCountermeasures.................88
8.2SecurityagainstSide-ChannelAttacks......................90
8.2.1EllipticCurvePointOperations......................90
8.2.2FieldOperations..............................91
w8.32-AryLeft-to-RightMethod...........................92
8.3.1RecodingAlgorithms............................92
8.3.2PointMultiplicationAlgorithm......................94
8.3.3UniformityofthePointMultiplicationAlgorithm............95

tstenCon

w8.42-AryRight-to-LeftMethod
..StageInitialization8.4.18.4.2Right-to-LeftStage..
8.4.3ResultStage.....
8.4.4Variants........
8.5EfficiencyComparison....
8.6ScalarRandomization....

yBibliograph

Index

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

11

979899100100102104

107

115

12

tstenCon

1Chapter

ductiontroIn

Thisdissertationexaminesmultipleaspectsofpublic-keycryptography.
PartIlooksatthetheoryofprovablysecurepublic-keycryptography,focusingonencryp-
tion.First,chapter2givesanintroductiontothistopicareaanddiscussesthelimitations
ofprovablesecurity.Then,chapter3describestheDHAESconstructionforpublic-keyen-
cryptionandgivesareduction-basedsecurityproofforit.Chapter4concludesthepartby
presentingaconstructionforaspecificvariantofencryption,namelypublic-keyencryption
withlength-expandingdecryptionforusewithChaum’smixconceptforuntraceableelectronic
mail.Again,securityisprovedinareduction-basedway.
PartIIconcernsitselfwithanimportanttopicforthepracticeofpublic-keycryptography,
namelytheimplementationofexponentiationandmulti-exponentiation.Chapter5shows
sometypicalapplicationscenarios.Chapter6presentstechniquesforefficientexponentiation.
Chapter7presentstechniquesforefficientmulti-exponentiationandforefficientexponentia-
tionwithprecomputationforfixedbases.Finally,chapter8includestheissueofside-channel
attacksintotheconsiderationanddescribestechniquesforellipticcurvepointmultiplication
(aspecificcaseofexponentiation)thataredesignedtoresistsuchattacks.
Ofcourse,noattemptismadetogiveacompletesurveyonthetheoryorthepracticeof
public-keycryptography.Thiswouldamounttocompilingavastcollectionofmaterial,and
suchacollectionwouldbeoutdatedquicklyasmuchresearchisdoneinbothareas.Instead,
thegoalhereistoprovideanintroductiontoprovablesecurity(chapters2and3)andto
givesufficientcontextfortheareasofmyownresearchresultsconcerningprovablysecure
public-keycryptography(chapter4;cf.myconferencepublication[63]),efficientimplemen-
tationofexponentiationandmulti-exponentiation(chapters6and7;cf.[58,62]),andpoint
multiplicationwithresistanceagainstside-channelattacks(chapter8;cf.[59,60,61]).

13

14

troIn

duction

Part

I

Theory

15

16

2Chapter

ProvPublic-KeyableSecurityCryptographyand

Thetermcryptographyoriginallyreferstohiddenwriting.Todayithasamuchbroader
meaningandcoversvariousrelatedconceptsbesidesencryption,suchasauthentication.In
thefollowingchaptersonthetheoryofprovablysecurepublic-keycryptography,wewill
lookatcertainconstructionsspecificallyforencryption.Thepresentchapterprovidessome
backgroundforthis,focusingontheaspectofprovability;muchofitscontentappliestoother
typesofpublic-keycryptographyaswell.

tionsenvConNotationalx∈SmeansthatxisuniformlyrandomlychosenfromsetS(wherethedistributionisun-
derstoRodtobeindependentofanyothergivenprobabilitydistributionsthatdonotexplicitly
).xonenddepForabitstrings(anelementof{0,1}∗),|s|denotesitslength.Theconcatenationof
wstringsbitsofss.andThtisus,prefixdenoted(ss||||t.t)F=ors|s∈|{≥0,w1,}|s|.prefixw(s)isthestringconsistingoftheleftmost
Algorithmsareusually|s|probabilistic(randomized).

ySecuritInformation-Theoretic2.1Herewelookatsymmetriccryptographybeforeproceedingtopublic-keycryptography,which
isalsoknownasasymmetriccryptography,inthenextsection.Assumeasimplescenario
wherejusttwopartiesareinvolved,AandB.Then,insymmetriccryptography,AandB
mustbothhaveknowledgeofapieceofdatathatshouldbekeptsecretfromothers,thekey.
Asimplesymmetriccryptosystemisthefollowing([88],[79]).
ProtoPartiescolAand2.1.BLetagreGebeonaakfiniteeyKgr∈oup.GV(aernamuniformlyencryptionrandomingrelementoupGofGworks).Tasofolencryptlows.
Rsomemessagerepresentedbyanelementm∈G(theplaintext),Acomputesthegroupelement
c=m+K(theciphertext).B,whenhavingreceivedc,canrecovertheplaintextmasc−K.
TheVernamencryptionschemeisalsoknownastheone-timepad(OTP)becausekeach
keysomekshould∈NbewithusedXORonlyasforgroupopencryptingeration,asinglebutthescmessage.hemewOftenorkstheinangroupyfiniteisG=group.{0,1}for

17

18

Public-KeyCryptographyandProvableSecurity

Theonlyassumptionwemakeonthedistributionofmisthatitbestochasticallyinde-
pendentofthedistributionofK.Thenforanyelementsm,c∈G,wehave
Pr[m=m|c=c]=Pr[m=m|K=c−m]=Pr[m=m]
becauseKhasindependentuniformdistribution.Thismeansthat,ifKiskeptsecret,an
advfromit:ersarythewhoVernamobservesencryptionsomescciphertexthemeisccannotinformation-thelearnoranyeticallyinformationsecure.whatsoeveronm
AcaveatisthatthisresultonlyholdsifkeysKareperfectlyrandom.Inimplementations,
willthererevwillealatusuallyleastbaetinsomeyamounbias.tHoofweverinformationminisculeonitthemaycorrespbe,thisondingmeansplainthattexts.Tciphertextsypically
thebiaswillbesmallenoughsothatitdoesnotreallymatteratall,andno-onewillknow
thedetailsaboutthebiasthatwouldbenecessarytoexploitit;weshouldjustkeepinmind
thatperfectinformation-theoreticsecurityremainsamathematicalutopiaanepsilonaway.

yCryptographPublic-Key2.2

Inthepartiesasymmetricthatorareinpublic-keyvolved.cryptoInstead,graphythek([32],ey[33]),generationthereisnoalgorithmlongerproasingleduceskmeyultiplesharedkbeysy
thatareassociatedwithanother:usually,thereisasecretkeythatshouldbeknownonlyto
asingleentity,andapublickeythatmaybemadeknowntoeveryone.
Oneformofpublic-keycryptographyispublic-keyencryption,wheresomeone’spublic
keyusingcanthebecorrespusedtoondingencryptsecretkplaintextsey.sucAnotherhthatimptheortantresultingformofciphertextspublic-kcaneybecryptographdecryptedy
aredigitalsignatureschemes:theentityholdingthesecretkeycanuseitto“sign”digital
documentsbycomputingavalue,a“signature”,suchthatanyonewhoknowsthepublickey
canvcryptographicerifywhetherprotothecolsaresignatureknownisvthatalidbforelongagivinentothemessage.areaofAlsovpublic-kariouseyothercryptographscenariosy.Wfore
willfocusonpublic-keyencryptionandspecificcloselyrelatednotionsandnotgointothe
detailsofdigitalsignaturesorotherprotocols.
nismA(KEM;conceptseerelated[80]).toAsinpublic-kpublic-keyeyencryptionencryption,isthesomeone’snotionofapublickeykeyencisusedapsulationtomecreatecha-a
ciphertextfromwhichaplaintextcanberecoveredusingtheassociatedsecretkey.Unlikefor
public-keyencryption,thesenderdoesnotgettospecifyanarbitraryplaintextwhencreating
theciphertext;instead,therandomized“encryption”algorithmoutputsboththeplaintext
toandcolsawherecorresptheondingplaintextciphertext.isintendedThisasaapproackeyhforissymmetricappropriateforcryptographuseiny–hencecryptographicthetermpro-
kencapsulation.eyNotethatbothsymmetricandpublic-keyencryptionschemescanberandomized:encrypt-
ingagivenplaintextforaconstantkeydoesnotnecessarilyyieldauniqueresult.However,
encryptionfollowedbydecryptionhasadeterministicresult,namelytheoriginalplaintext;
thisisincontrastwithKEMs.(Thevariantofpublic-keyencryptionthatwewillconsiderin
chapter4isanunusualexceptionwheredecryptionyieldstheoriginalplaintextpaddedwith
someadditionaldata,whichisdeterminedwhileencrypting.Inthatpublic-keycryptosystem
withlength-expandingdecryption,theresultofencryptionfollowedbydecryptionispartially
pseudo-random.)partiallyanddeterministic

19yCryptographPublic-Key2.2whereAwewillformalizationalsoloofoktheatnotiondifferenoftaattacpublic-kkeyscenariosencryptionandseeschohemewthewillappsecuritearyinofsectionpublic-k3.1,ey
canbencryptioneinexpressedastrongquansensetitativ(i.e.ely.whenAexpformalizationosedtoanofadvtheersarynotioninaofafar-goingKEMattacwillkappearscenario)in
sectionpreview3.2some(seeofsectionthesesub3.4.1jects,forbutsecuritywithoutnotionsgoingforaalltheKEM).wayInyetthe(wepresentreattcthesehapter,weconceptswill
Assomewhatbasicinformallyexamples,,wandeloweokatconfinethreetovarianrathertsoflimitedtheattacDiffie-Helkscenarioslman(DH)forkeaseeyofexpencapsulationosition).
mechanism([33],[1],[2],[80]).
Protocol2.2.LetGbeafinitegroup(whoseorder#(G)isknown)andg∈G.Akeypair
consistingofasecretkeySKandapublickeyPKisgeneratedasfollows:pick
SK∈R0,1,...,#(G)−1
andletPK=gSK.
AsenderwhoknowsthepublickeyPKgeneratesaciphertextK∈Gandthecorresponding
plaintextK∈Gasfollows:pick
x∈R0,1,...,#(G)−1
andletK=gx
andx.PK=KNowifthesendertransmitsKtotheownerofthesecretkey,thelattercanrecoverthe
plaintextKbycomputingKSK.
(ObservethatKSK=gx∙SK=PKx=K).
Protocol2.3.Again,letGbeafinitegroup(ofknownorder)andg∈G.
Letkbeapositiveinteger,andleth:G→{0,1}kbesomehashfunction.(Bythis,we
semecanond:thatwehwantshouldtobeintuitivelyablebassumeehavethatlikeforaranyandomlyy∈G,chosenthekmap-bitfromstringtheh(y)firstissetrtoandom.the
However,notethatthisisjustawaytothinkaboutwhathappensandiscertainlynothowh
canbedefinedinpractice.)
col2.2NowwiththetheDiffie-Helhelpoflmanthehashkeyencfunction.apsulationKeymegenerchanismationcisanasbeabpove:erformedsimilartoproto-
SK∈R0,1,...,#(G)−1,PK=gSK.
ThesendernowproceedsasfollowstogenerateaciphertextK∈Gandacorresponding
plaintextK∈{0,1}k:pick
x∈R0,1,...,#(G)−1,
letthenxPK=K

20

Public-KeyCryptographyandProvableSecurity

andK=h(gx).
TheownerofthesecretkeycanrecoverKfromKbycomputing
h(KSK).
Protocol2.4.AfurthervariantoftheDiffie-Hellmanschemeworksmostlyastheprevious
one,butappliesahashfunctiondifferently.Wedescribejustthedifferencestoprotocol2.3.
Thistime,wehaveahashfunctionh:G×G→{0,1}k.ThesendercomputesK∈{0,1}k
asK=h(K,gx),
andtheownerofthesecretkeycomputesitas
K=h(K,KSK).
Inthesethreeprotocols,wehaveassumedthatinadditiontothespecificpublickeys,
sendersalsohavecertainadditionalinformation:theyknowwhichgroupGtocompute
in,theyknowwhichelementg∈Gtouse,andtheyknowtheorder#(G)ofthegroup.
Suchinformationiscollectivelyreferredtoasdomainparameters.Itispossibletoconsider
generatingdomainparameterspartofkeygeneration,butitisalsopossibletousefixed
domainparametersformanykeypairs.
Observethatkeyencapsulationmechanismscaneasilybecombinedwithsymmetricen-
cryptionschemestocreatepublic-keyencryptionschemes.Forexample,anyoftheDiffie-
HellmanvariantsdescribedabovecanbefollowedbyVernamencryption(protocol2.1)inan
appropriategroupusingtheDHresultKasakey.InthecaseoftheDHvariantwithouta
hashfunction(protocol2.2),thiscombinationiscalledElGamalencryption[35].
Notethatitisimpossibletoachievefullinformation-theoreticsecurityinameaningful
senseforpublic-keycryptography:thepublickeynecessarilymustcontainatleastpartial
informationonthesecretkey,orthetwokeys(secretandpublic)wouldnotbeassociated
witheachother.Forexample,intheDiffie-Hellmanschemesthatwepresentedabove,key
PKdeterminesSKmodulotheorderofginG(secretkeysthatarecongruentmoduloord(g)
areequivalentiftheprotocolisfollowedbybothparties).Insteadofinformation-theoretic
security,insection2.3wewillconsidercomputationalsecurity,i.e.securityagainstadversaries
means.computationaloundedbwith(Somepublic-keyprotocolsexistthataredesignedtoachieveatleastacertainnotionof
securityinmorethanacomputationalsense.Fail-stopsignatureschemes[72]aresignature
schemeswhereasecurityfailureofthesystemcanbedetectedwithveryhighprobability:
manydifferentpossiblesecretkeysmatcheachgivenpublickey,andifanadversarybreaks
thesystemcomputationallyandproducesaseeminglyvalidsignature,thenthissignature
willlikelybebasedonasecretkeydifferingfromthelegitimateone,anddifferfromthe
signatureonthesamemessagethatwouldhavebeenproducedbythelegitimatesignerwith
hisoriginalsecretkey.Insuchcases,thekeyownercandemonstratethattherehasbeena
securityfailureandthatthusthefakesignatureshouldnotbeconsideredvalid.)

ySecuritComputational2.3toAsexaminecinformation-theoreticomputationalsesecuritcurity.yisoutAdvofersariesthearequestionmofordelledaspublic-keyprobabilisticcryptographalgorithmsy,wehathatve

ySecuritComputational2.3

21

somehowinteractwiththecryptographicschemethattheyareattacking(detailsofthis
interactiondependonthespecificnotionofsecurity).Thenwecantrytoanalyzetheprob-
abilitieswithwhichanadversarycanachievecertainattackgoalsundergivencomplexity
bounds.Theseboundsmightbeexplicit(e.g.amaximumnumberofalgorithmsteps)or
implicit.Basedonsuchprobabilities,wewilldefinetheadvantageoftheadversaryinthe
respectiveattackscenarioasarealnumberintheinterval[0,1]wherevalue0(noadvantage)
meansthatthecryptographicschemeissecureunderthenotionofsecurityunderconsidera-
tionagainsttherespectiveadversary,andwherevalue1meansthatthecryptographicscheme
istotallyinsecureunderthenotionofsecurityconsideredagainsttherespectiveadversary
(withitscomplexitybounds).
(Bewarethatotherdefinitionsfortheadvantagecanbefoundintheliterature:sometimes,
theadvantagerangesfrom−1/2to1/2,wherevalue0meansnoadvantageasaboveandwhere
both−1/2and1/2indicatetotalinsecurity.SuchameasureAdvcanbetransformedintoa
measureAdvfollowingourconventionbytakingAdv=2∙|Adv|.)
Whatwearereallyinterestedinistheinherentsecurityofthecryptographicschemeunder
acertainnotionofsecurity,notjustthesecurityagainstsomespecificadversary.Something
thatwillusuallyhavetobespecifiedisanuppertimeboundfortheadversariesthataretobe
considered.Wecanalsoincludeadditionalparametersbesidesthetimebound:forexample,
attackmodelsoftenprovidetheadversarywith“encryptionoracles”and“decryptionoracles”
orthelike,whichwillprocessrequestssentbytheadversary;insuchmodels,wecanhave
parametersforthemaximumnumberofqueriestospecificoracles,andthemaximumsizeof
allqueriestothem.Thentheadvantageofarbitraryadversariescanbedefinedasafunction
ofallsuchparameters:itistheinfimumofadvantagesofalladversariesthatobserveall
thespecifiedbounds.Thisisknownastheconcretesecurityapproach([7],[8]):securityis
describedquantitatively,measureddependingonthepowergiventoadversaries.

2.3.1Example:IND-CPASecurity
Asafirstexample,weshowabasicnotionofsecurityforpublic-keyencryption,namely
indistinguishabilityunderchosen-plaintextattack(IND-CPA),whichgoesbackto[37].(For
strongersecuritynotions,seethenextchapter.)Assumethatsomepublic-keyencryption
schemePKEisgiven.IntheIND-CPAscenario,adversariesengageinthefollowingattack
game:1.Theadversaryqueriesakeygenerationoracle,whichcomputesakeypair(PK,SK)using
thekeygenerationalgorithmspecifiedforPKE.ThepublickeyPKismadeavailableto
theadversary,andSKiskeptsecret.
2.Nowtheadversarychoosestwobinarystringsm0andm1ofthesamelengthand
sendsthemtoaso-calledencryptionoracle,whichsecretlypicksb∈R{0,1},appliesthe
encryptionalgorithmofPKEtombusingthekeyPK,andrespondswiththeresulting
string,whichwecallthechallengeciphertext.
3.Theadversaryoutputsabitb∈{0,1},whichissupposedtobeaguessforthevalueof
.bbitNowforaspecificadversaryA(aninteractiveprobabilisticalgorithmwithboundedrunning
time),wedefineitsCPAadvantageagainstthepublic-keyencryptionschemeas
AdvCPAPKE,A=Pr[b=1|b=1]−Pr[b=1|b=0].

22

Public-KeyCryptographyandProvableSecurity

ecausebthatNotePr[b=1|b=1]−Pr[b=1|b=0]=Pr[b=1|b=1]+Pr[b=0|b=0]−1
=2Pr[b=b]−1,
wecanalsowritethisas
2AdvCPAPKE,A=2∙Pr[b=b]−1.
(Observethatifthereisanadversarythattendstoguesswrong,thisisjustasbadasif
ittendstoguessright:byalwaysinvertingtheadversary’soutputbitb,onecasecanbe
other.)thetointransformedTheterm“chosen-plaintextattack”referstothefactthattheadversarycanencrypt
arbitraryplaintextsofitsownchoicebecauseitknowsthepublickeyPK.Observethata
public-keyencryptionschemecannotbesecureunderthisdefinitionunlessitisrandomized
(presumingthatitissoundinthesensethatdecryptingtheencryptionofagivenplaintext
willactuallyrecovertheoriginalplaintext):foradeterministicscheme,theadversarycould
simplyencryptm0orm1;oneoftheciphertextswillequalthechallengeciphertext,andif
m0=m1,thisimmediatelyrevealsb.

2.3.2Reduction-BasedSecurityProofs
Provingthecomputationalsecurityofacryptographicschemewouldamounttoshowingthat
somethingthatiseasytodowithknowledgeofallcryptographickeysinvolvedisahardcom-
putationalproblemforanadversarywhodoesnotknowtherelevantsecretkeys.However,
exceptintheverynarrowrangewhereweactuallyhaveinformation-theoreticsecurity,this
touchesthelimitsofcomplexitytheory,andthereislittlehopeforactuallyprovablecom-
putationalsecurity.Instead,onecanresorttoreduction-basedsecurityproofs,inwhichitis
shownthatacryptographicschemecompliestothesecuritynotioninquestionprovidedthat
isacertainsecureunderunderlyinganappropriatecomputationalsecurityproblemisdefinitionhard,proorvidedthatathatcomplexthesimplercryptographiccryptographicscheme
schemes(orprimitives)fromwhichitisbuiltaresecureundertheirrespectivesecurityno-
tions.Thepointofsuchproofsbyreductionisthatexpressionsofsecurityforcryptographic
schemescanberelatedtocomputationalproblemsthataresimpletodescribeandmoredi-
byrectlyexperience,accessiblei.e.forbythecomplexitfailureytoanalyses,findefficienandttheinalgorithmstractabilitafteryofinwhictensivhemayresearcbeh.supported
Observethatsayingthatacomputationalproblem“ishard”isquiteambiguous:itmight
merelymeanthattheproblemhassomedifficultinstances(cf.theexpression“NP-hard”in
complexitytheory);oritmightmeanthateasyinstancesareindeedrare.Inthecontextof
cryptography,weneedproblemsthatarehardinthestrictersense.Toavoidtheambiguity,
wewillusuallyspeakof“securecryptographicprimitives”ratherthan“hardcomputational
problems”(any“hardproblem”intheappropriatesensecanbeconsideredacryptographic
e).primitivSayingthatsomecryptographicscheme“issecure”isclearlysimplicistic.Theconcrete
securityapproachcanbeusedtomakequantitativestatementsaboutsecurity.Reduction-
basedsecurityproofsworkasfollows:iftheadvantagethatanadversarymaybeableto
obtainagainstacryptographicschemecanbeboundedbyafunctionoftheadvantagesof

ySecuritComputational2.3

23

relatedadversariesagainsttheunderlyingprimitives(wheretheseadversariesarederived
fromtheadversaryagainstthefullscheme),thenonecanobtainsecuritystatementsthat
essentiallystatethatthefullschememustbesecureunlessoneoftheunderlyingprimitives
isvulnerable.(Somecaremustbetakenasthisintuitiveinterpretationmaysometimesbe
toosimplicistic,e.g.ifaderivedadversaryincursasignificantslowdowncomparedwiththe
originaladversarythatitisbasedon.)
Securityassumptionsmadeforprimitivesoftenhavebasicallythefollowingform:“No
adversaryrunninginatmostnstepscanachieveanadvantagebetterthan.”Observe
thatwhilesuchstatementsmayappeartodescribeaninherentpropertyoftheprimitivein
question,infacttheyimplicitlymakeassumptionsontheadversariesaswell.Thereason
isthatthemachinemodelthatadversariesaresupposedtoruninisleftunspecified.(For
example,one“stepofcomputation”insomemachineformalizationmightrequirealarge
numberofstepsinanotherone.)Theformalassumptiondescribesrestrictionsonwhat
adversariescanachieve,butnothingspecificabouttheprimitivetakenforitself.
Inprinciplewecouldfillthisvoidanddefineaprecisemachinemodelforadversaries.
Then,withrespecttothisparticularmodel,thesecurityassumptionwouldbeeithertrueor
false.Forsomepossiblemodels,itwillbetrue,forothersitwillbefalse.(Wecouldconsider
amachinemodelinwhichtheproblemathandcanbesolvedimmediatelybecausethere
issomespecificbuilt-inoperationthatachievesthis.)Ofcourseweusuallyhopethatthe
modelsinwhichthesecurityassumptionisfalsearecontrived,andthatforrealisticonesit
true.is

2.3.3AsymptoticSecurityProofs
Oftencryptographicschemesarethoughttobeparameterizedbyasecurityparameter,a
non-negativeintegerk,whichispossiblyboundedfrombelow,i.e.k≥k0forsomek0.Key
generation,encryptionandanyotherlegitimateuseofthecryptographicschemeisexpected
tobepossibleintimepolynomialink(assumingappropriatelengthboundsforinputssuch
asplaintexts).Insuchparameterizedsettings,wewillusuallybeconcernedwithsetsofkeys
andofmessagesthathaveunboundedcardinality.Itisunderstoodthattomakeitpossible
todescribecryptographicschemesthroughalgorithms,elementsofsuchsetswillhavetobe
representedaswordsoversomefinitealphabet.
Forexample,forDiffie-Hellman(protocols2.2,2.3and2.4)usingthemultiplicativegroup
ofsomeprimefield,i.e.G=(Z/pZ)∗,kcouldbethelengthofprimepinbits(herewehave
toinsistthatk≥2).ElementsofGcanberepresentedasbitstringsoflengthkthatcontain
theminimumpositiveintegerintherespectiveresidueclassmodulop,expressedinbinary.
Theuseofsecurityparametersprovidesanapproachtoprovablecomputationalsecurity
forcryptographicschemes.Afunctionf:N→Riscallednegligibleiff(n)=O1/P(n)for
anypolynomialP,i.e.ifforanym∈Nthereisannmsuchthatf(n)<1/nmforn≥nm.
Wewanttocallacryptographicschemesecureaccordingtosomespecifiedsecuritynotionif
breakingitishardinthesensethatanyadversarywithrun-timeboundedpolynomiallyin
securityparameterkhasadvantagenegligibleink.Observethatsecuritystatementsofthis
asymptotic.areformAshasalreadybeennotedinsection2.3.2,wecannotreallyhopeforactualprovable
computationalsecurityforpublic-keycryptography:rememberthatthefamousquestion
whethertheclassoflanguagesacceptedbydeterministicpolynomial-timemachinescoincides
withtheclassoflanguagesacceptedbynon-deterministicpolynomial-timemachines(P=

24

Public-KeyCryptographyandProvableSecurity

NP)remainsunsettled,andobservethatbecauseNPalgorithmscaninternallyguesssecret
keys,efficientadversariescouldbeconstructedifP=NP.Sowestillhavetoconfineto
reduction-basedsecurityproofsthatrelyonassumptionsaboutthesecurityofunderlying
primitives(which,inturn,arecapturedinthepresumednegligibilityoftheadvantageofany
polynomiallyboundedadversarytargetingtherespectiveprimitive).
Onesuperficialadvantageofasymptoticsecurityresultsshowinganegligibleadvantage
comparedwithsecurityresultsdescribingconcretesecurityasdiscussedintheprevioussec-
tionisthatherewecanappealtowell-knownequivalencesbetweendifferentmachinemodels:
asymptoticsecuritystatementsdonotdependonspecificmachinemodels.However,acanon-
icalclassofequivalentmodelsexistsonlyinasymptotics,andthisinitselfisabasicdrawback.
Securitystatementsthatareasymptoticinthesecurityparameterimplythat,givenanyad-
versary,itsadvantagecanbekeptarbitrarilyclosetozeroifonlythesecurityparameteris
chosensufficientlylarge(providedthattheunderlyingprimitivesareindeedsecure).However,
whenacryptographicschemeisactuallyemployed,onehastofixsomespecificvalueofthe
securityparameter,sothisparameterclearlycannotchangedependingonwhichadversary
oneconsiders.Withthesecurityparameterfixed,theproblemdegeneratestoonewithafinite
numberofcases(sincegeneratinganinstanceoftheproblemisassumedtohavepolynomial
complexity).Thismeansthattheproblemcannowbesolvedinconstanttime.Anadversary
againstapublic-keycryptosystemcouldevenuseafixedtablethatmapseachpublickeyto
acorrespondingsecretkeytosolveeachinstanceoftheprobleminstantly.
Whilethusanasymptoticstatementobtainedthroughareduction-basedsecurityproof
doesnotreallysayanythingaboutpracticalinstantiationsofthecryptographicscheme,it
canstillbeconsideredavaluableheuristicresult:essentially,onecanhopethattheconcrete
choiceofthesecurityparameterwillbelargeenoughsuchthattheasymptoticresulthasa
closecorrespondencetoreality.

2.3.4TheRandomOracleModel
Oneapproachtoheuristicsecurityistherandomoraclemodel[9].Remembertheremark(for
protocol2.3above)thatitisconvenienttoassumethathashfunctionsbehavelikerandomly
chosenfunctions.Therandomoraclemodelformalizesthisidealizationbyreplacingconcrete
hashfunctionsbyrandomlychosenfunctions.Theadversary’sadvantageintheattackgame
ismeasuredunderthisrandomdistribution.Theadversarydoesnotobtainacomplete
descriptionofthehashfunction.Instead,valuesofthehashfunctioncanonlybeobtained
individuallybywayoforaclequeries:arandomoracleissubstitutedforthehashfunction.
Theintuitionbehindtherandomoraclemodelisthatsecurityproofsinthisidealization
indicatethatacryptographicschemeissecureagainstgenericattacksthatdonotexploit
specificpropertiesofsomeparticularhashfunction.However,clearlynospecificchoiceofa
hashfunctioncanbehavelikearandomoracle–therandomoraclemodeldoesnotcorrespond
toanyexplicitassumptiononsecuritypropertiesofhashfunctions.
Itiseasytoseethatitisalreadyproblematictoconsiderahashfunctionasasinglefixed
function.Acollisionofahashfunction
h:dom(h)→{0,1}k
wheredom(h)⊆{0,1}∗isapair(m0,m1)ofstringssuchthatm0=m1but
h(m0)=h(m1).

2.3ySecuritComputational

25

Unless#dom(h)≤2k,itisclearthathwillhaveacollision.Ifhbehavessomehow“ran-
domly”,onemightexpectthatfindingacollisionwouldbedifficult(ifkischosensufficiently
large).However,ifhisfixed,thereareconceivablysimplealgorithmsfor“finding”acollision:
suchalgorithmsdonothavetodoanyactualwork,theycansimplyoutputacollisionofh
thatisbuiltintothealgorithm.Hence,hashfunctionsusedinpracticeshouldbemodeled
askeyedfunctionfamilies(hK)K∈KwhereaspecifichashfunctionhK,K∈RK,isdeter-
minedatsystemset-uptime.Thentheadvantageofadversariescanbeconsideredunder
thisrandomdistribution.Thisapproachmakesitpossibletoformalizethesecurityofhash
functionsincludingtheintractabilityoffindingcollisions,butdoesnotprovidejustification
fortherandomoraclemodel.
Particulardoubthasbeencastonthemethodologyofemployingtherandomoraclemodel
forsecurityproofsbyshowingthatanessentialdiscrepancyremainingbetweenthekeyed
functionfamilymodelforpracticalhashfunctionsandtherandomoraclemodelallowscon-
structingcryptographicschemesthatcanbeprovensecureintherandomoraclemodel,but
areinsecureforanyinstantiationofthehashfunction[20,21].Descriptionsofactualhash
functionswillbe“small”(ofpolynomialsize,consideredasymptotically),whilethecomplete
specificationofarandomlychosenfunctionasintherandomoraclemodelwouldbe“large”
(requireexponentialsize).Theexampleconstructionsfrom[20,21]useadiagonalization
techniquetoexploitthisdiscrepancy.
Thesenegativeresultshavebeenpresentedinasymptoticformin[20,21].Aswehave
seeninsection2.3.3,asymptoticsecuritystatementscannotsayanythingonpracticalinstan-
tiationsofcryptographicschemesanyway,sothepublishedresultisnotdirectlymeaningful.
However,theasymptoticformisnotessential,andsimilarresultscouldbeobtainedforpar-
ticularmachinemodelsinnon-asymptoticsettings[19].

Conclusions2.3.5Inmodel.sectionsNosp2.3.3ecificandc2.3.4,hoicewofeahavesecurityconsideredparameterasymptoticcanbesecurity“asymptotic”,andtheandrandomnosporacleecific
choiceofahashfunctioncanbea“randomoracle”;sosecurityresultsshouldavoidthese
conceptsifwewantthemtohaveadirectpracticalinterpretation.Inthefollowingchapters,
provablesecuritywillbehandledaccordingtoareduction-basedconcrete-securityapproach:
cryptographicschemesarebuiltfromsimplercryptographicprimitives;thesecurityofthe
compoundschemecanberelatedquantitativelytothesecurityoftheunderlyingprimitives,
wheresecurityisexpressedthroughtheadvantagethatcanbeachievedbyanadversary.
Thesecurityproofswillnotreferexplicitlytosecurityparametersortoasymptoticsecurity,
andmighttheybewillaappropriatevoidtorandomexamineoracles.inHomorewever,detailitistheunderstosecuritoydthatassumptionstheuseofthatsucwhemakconceptseon
cryptographicprimitives.Wewillsimplyassumethatappropriateprimitivesareavailable,
sothisassumptionsissueonwillprimitivremaines,outinofanysighcaset.weSinceendwupedorelyingnothaonveheuristicaljustificationforconsiderations,thesecuritandy
wecannotgetfarifwearenotwillingtodoso.

26

Public-Key

yCryptograph

and

ablevPro

ySecurit

3Chapter

TheHybridDHAESPublic-KeyConstructionEncryption:

ToimproveoverthesecurityoftheElGamalpublic-keyencryptionscheme,whichaswe
willseedoesnotresistextendednotionsofanattack,theschemeDHAES[1]wasdevised.
Thisschemecombinesmultiplecryptographicprimitives:akeyencapsulationmechanism
(KEM),aone-timemessageauthenticationcode(one-timeMAC),andasymmetriccipher.
Constructionsforpublic-keyencryptionthatinvolvesymmetricencryptionareoftencalled
hybrid.

DHAESstandsforDiffie-HellmanAuthenticatedEncryptionSchemeorDiffie-Hellman
AugmentedEncryptionScheme.TheschemeasoriginallypublishedusestheDiffie-Hellman
kwhiceyhexcstandshangeformechanismDiffie-HelasinlmanprotoIntecolgrate2.4.dAlaterEncryptionvariantSchemeofthe[2],schemeusesprotopublishedcol2.3asDHIES,instead
of(thereviewis[80]).someOtherindicationKEMsthatcanbthisecusedhangeofwithoutthecKEMhangingwastheill-advisedessenceoffromtheasecuritDHAES/DHIESypoint
scheme.Thegeneralizationforarbitrarykeyencapsulationmechanismswasfirstlaidout
inusing[30].anyIntheKEM.following,theterm“theDHAESconstruction”referstothegeneralscheme

Inthischapter,wewilllookattheDHAESconstructionforarbitrarykeyencapsula-
tionmechanisms,butonlyforspecificsymmetricciphers,namelyXOR-basedstreamciphers
(wheretheciphertextisgeneratedfromtheplaintextandviceversabyXORingapseudo-
randombitstring)–acasethatwasaccidentilynotcoveredbytheoriginalsecurityresultin
[1]and[2].ThesecurityresultfortheDHAESconstructionthatwewillarriveatleanson
[30].

Section3.1describeschosen-ciphertextattacksagainstpublic-keyencryptionschemesand
showsthattheElGamalpublic-keyencryptionschemeisnotsecureunderthisstrongnotion.
Thensection3.2describesthecryptographicprimitivesneededbytheDHAESconstruction,
andsection3.3describeshowtheyareusedtoencryptanddecryptwithDHAES.Finally,
section3.4showshowthesecurityofDHAESfollowsfromthesecurityoftheunderlying
es.primitiv

27

28

HybridPublic-KeyEncryption:TheDHAESConstruction

3.1AdaptiveChosen-CiphertextAttacks
Insection2.3.1,wehavelookedatabasicsecuritynotionforpublic-keyencryption,indis-
tinguishabilityunderchosen-plaintextattack(IND-CPA).Inpractice,adversariesareoften
inabetterpositiontolaunchanattackthanprovidedinthatattackmodel:theymaybe
abletomakeupciphertextsandsubmitthesechosenciphertextsfordecryption.Depending
onthespecificattackscenario,thedecryptionresultsmayormaynotbemadecompletely
availabletotheadversary.Weareinterestedinaverystrongcharacterizationofsecurityfor
public-keyencryption,soweassumetheworstanduseattackmodelswheretheadversary
hasaccesstoadecryptionoracle.
RememberthatintheattackscenarioforIND-CPA,theadversarychoosestwomessages
m0andm1,obtainstheencryptionofarandomonembofthese,andthenhastoguess
whetherb=0orb=1.Theadversarycanbeconsideredasrunningitsattackintwostages:
firstthefindstage,whichendswhentheadversaryoutputsm0andm1,andthentheguess
stage,whichstartswhentheadversaryisgiventhechallengeciphertext.Ifweextendthis
attackscenariotoallowachosen-ciphertextattack,wealwaysprovidetheadversarywitha
decryptionoracleforthefindstage.Thestrongestnotionofachosen-ciphertextattackisan
adaptivechosen-ciphertextattack[74],wheretheadversaryalsohasaccesstoadecryption
oracleintheguessstage;fortheguess-stageoracle,wehavetoimposetherestrictionthat
theadversarymaynotusetheliteralchallengeciphertextasaquery(otherwise,theoracle’s
answerwouldmakeittrivialtodeterminebforanysoundpublic-keyencryptionschemeif
m0=m1).
Sometimesbothnon-adaptivechosen-ciphertextattacks(CCA1)andadaptivechosen-
ciphertextattacks(CCA2)areconsideredintheliterature,butusuallyonlythestrongest
notionofattackisrelevant.Inthefollowing,thetermchosen-ciphertextattack(CCA)without
furtherqualificationisunderstoodtorefertotheadaptivekind.
BeforeweproceedtoformalizeCCAsecurityforpublic-keyencryption,firstwedefinethe
notionofapublic-keyencryptionschememorecompletely.Hereweassumethatallmessages
areencodedasbitstrings(ifwestartwithaschemedefinedforgroupelements,suchasthe
ElGamalencryptionschemeassketchedinsection2.2,wehavetoaddappropriateencoding
anddecodingfunctionalitytothesystem’sspecification).Forthisdefinition,rememberthat
algorithmsareusuallyprobabilistic(refertothenotationalconventionsatthebeginningof
thepresentchapter).Notethatourformalizationusesnoexplicitsecurityparameter;this
correspondstohavingsomefixedsecurityparameterbuiltintothekeygenerationalgorithm.
Definition3.1.Apublic-keyencryptionscheme
PKE

specifiesakeygenerationalgorithm

KeyGen.PKEthatproduceskeypairs(PK,SK)consistingofapublickeyPKandasecretkeySK,an
algorithmEncrypt.PKEusingthepublickey,andanalgorithm

Decrypt.PKE

3.1AdaptiveChosen-CiphertextAttacks

29

usingthesecretkey.Foraplaintextm(anarbitrarybitstring,possiblysubjecttolength
limitationsforthespecificpublic-keyencryptionscheme),
PKE.Encrypt(PK,m)
returnsabitstringc,aciphertext.Onarbitraryinputc,
PKE.Decrypt(SK,c)
mayeitherreturnsomestringmorfailandreturnthespecialvalueinvalid.Ifthekeypair
(PK,SK)hasbeenproducedbyPKE.KeyGenandchasbeenproducedbyPKE.Encrypt(PK,m),
thenevaluationofPKE.Decrypt(SK,c)willreturnstringm.
Securityinthesenseofindistinguishabilityunderchosen-ciphertextattack(IND-CCA)is
describedthroughthefollowingattackgame:
1.Theadversaryqueriesakeygenerationoracle,whichusesPKE.KeyGentodeterminea
paireyk)SK,PK(andrespondswithPK(whilesecretlystoringSK).
2.[Findstage.]Theadversarymakesasequenceofqueriestoadecryptionoracle.Each
queryisanarbitrarystrings,andtheoraclerespondswithPKE.Decrypt(SK,s).
3.Theadversarychoosesmessagesm0andm1subjectonlytotheconditionthat|m0|=
|m1|andsendsthemtoanencryptionoracle.Theencryptionoraclechoosesauniformly
randombitb∈{0,1}anddetermines
c=PKE.Encrypt(PK,mb),
whichisreturnedtotheadversaryasthechallengeciphertext.
4.[Guessstage.]Theadversaryagainmakesasequenceofqueriestoadecryptionoracle
asinthefindstage,wherethistimethedecryptionoraclerefusesbeingaskedforthe
challengeciphertextc(itreturnsinvalidforthiscase).
5.Theadversaryoutputsabitb∈{0,1}.
Thebitboutputbytheadversaryissupposedtobeitsguessforthevalueofb.
NowletAbeanyadversaryintheaboveattackgame,i.e.aninteractiveprobabilistic
algorithmwithboundedrunningtime.ItsCCAadvantageagainstthepublickeyencryption
ishemescAdvCCAPKE,A=Prb=1|b=1−Prb=1|b=0.
Similarlytowhatwehaveseeninsection2.3.1,thiscanalsobewrittenas
22∙Pr[b=b]−1.
LetusconsiderthesecurityoftheElGamalpublic-keyencryptionscheme(seesection2.2).
Ifmessagesareencodedasgroupelements,thenIND-CPAsecurity(section2.3.1)canbe

30

HybridPublic-KeyEncryption:TheDHAESConstruction

provenprovidedthattheschemeisusedingroupsforwhichtheso-calledDecisionDiffie-
Hellman(DDH)assumptionholds;see[85]fordetailsonthereduction.(TheDDHassumption
statesessentiallythatadversariestryingtotellaparttherandomdistributions(ga,gb,gab)and
(ga,gb,y)witha,b∈R0,...,#(G)−1,y∈RGcannotdosignificantlybetterthanguess.)Now
letusconsiderElGamalencryptionunderthestrongerIND-CCAsecuritynotion.ElGamal
ciphertextsforplaintextmhavethegeneralstructure(K,m+K),andforanygroupelement
x,computing(K,x+m+K)yieldsaciphertextcorrespondingtoplaintextx+m.Thus,
bgiveenusedtheascahallengequerytotheciphertext,decryptiontheadvoracleersarysocanthateasilythederivplainetextacanrelatedberecociphertextveredthatfrommathey
oracle’sreplysimplybysubtractingagroupelement.Thismakesiteasytosuccessfullyattack
theencryptionschemeintheIND-CCAscenario;clearly,ElGamalencryptionisnotsecure
sense.thisinkeyThus,encryptioniftheschemeIND-CCAisnotnotionofsufficient.Incryptographicthischapter,securitywmeustwillbemet,examinethetheElGamalDHAESpublic-con-
struction,whichachievesthisgoal.

3.2PrimitivesfortheDHAESConstruction
TheDHAESconstructionaspresentedinthefollowingrequiresthreeunderlyingcrypto-
graphicprimitives:akeyencapsulationmechanism(KEM),aone-timemessageauthentica-
tioncode(one-timeMAC),andapseudo-randombitstringgeneratorforuseinanXOR-based
streamcipher.(NotethatDHAES/DHIESasdescribedin[1]and[2]canuseothersymmetric
ell.)wasciphersDefinition3.2.Akeyencapsulationmechanism
KEM

specifiesakeygenerationalgorithm

KeyGen.KEMthatproduceskeypairs(PK,SK)consistingofapublickeyPKandasecretkeySK,an
algorithmEncrypt.KEMusingthepublickey,andanalgorithm

Decrypt.KEMencusingtheapsulationsecretmekey.chanismIncontrtakesastnowithinputappublic-keyartfromtheencryption,publicthekey:Encryptalgorithmofakey
KEM.Encrypt(PK)
generatesaciphertextKofafixedlength
CipherLen.KEM

3.2PrimitivesfortheDHAESConstruction

31

correspondingtoa(pseudo-)randomstringKofafixedlength
OutLen.KEMandoutputsthepair(K,K).Evaluationof
KEM.Decrypt(SK,K)
willreturnsaidstringKifthekeypair(PK,SK)hasbeenproducedbyKEM.KeyGen.On
arbitraryinputK,thecomputationKEM.Decrypt(SK,K)mayeitherreturnsomestringK
orfail(returnthespecialvalueinvalid).
TherandommessageKwillbeknownbothtothepartyrunningKEM.Encrypt(PK)andto
thesecretkeyownerwhorunsKEM.Decrypt(SK,K).Inthissense,ciphertextKencapsulates
therandommessageK.Itcanbeusedasakeyforsymmetric-keycryptography;hencethe
encapsulation”.ey“ktermOnechoiceforakeyencapsulationmechanismistheDiffie-Hellmanvariantfromproto-
col2.4.KEM.CipherLencanbekeptparticularlysmallbyusingthegroupofrationalpoints
onanappropriateellipticcurve[12]andusing(exceptininternalcomputations)justxcoor-
dinatesofpoints(see[55]).Specificationsforvariouskeyencapsulationmechanismscanbe
[80].infoundDefinition3.3.Aone-timemessageauthenticationcode(one-timeMAC)
CMAspecifiesakeylength
,KeyLen.CMAlengthoutputan,OutLen.CMAandadeterministicalgorithmthattakesasinputakeyKoflengthMAC.KeyLenandabit
strings(oftheoreticallyarbitrarylength,althoughpracticalrealizationswilltypicallyhave
somelargefixedlimit)andreturnsastring
MAC(K,s)
oflengthMAC.OutLen.
Candidateone-timemessageauthenticationcodesareUHASH[50]andHMAC[5].(The
UHASHschemeisthecombinationofakeyderivationfunctionwithanalmoststrongly
universalhashfunction[89]andisthecoreofUMACasspecifiedin[50].Notethatthereis
anearlierversionofUMACdescribedin[11],forwhichsecurityargumentsareprovidedthat
arebasedonadifferentapproach.)
Definition3.4.Apseudo-randombitstringgenerator
STREAMspecifiesakeylength
,KeyLen.STREAM

32

HybridPublic-KeyEncryption:TheDHAESConstruction

lengthoutputan,OutLen.STREAMandadeterministicalgorithmtakingasinputakeyKoflengthSTREAM.KeyLenandgener-
atinganoutputstringSTREAM(K)
oflengthSTREAM.OutLen.Alternatively,
OutLen.STREAMmaybeinfinite;inthiscase,foranyintegern,
STREAM(K,n)
generatesanoutputstreamoflengthn.
Aconvenientexampleimplementationistheso-calledcountermodeofasymmetricblock
cipherwhereE(theKdenotesoutputblocsequencekcipheristheencryptionprefixofusingappropriatekeyK;seelength[6]ofandEK(0)[52]).||EK(1)||EK(2)||...

3.3TheDHAESPublic-KeyEncryptionScheme
WespecifyDHAESasapublic-keyencryptionschemePKEfollowingdefinition3.1,assuming
thatprimitivesKEM,MAC,andSTREAMasdescribedinsection3.2areavailable.Werequire
thatKEM.OutLen=MAC.KeyLen+STREAM.KeyLen
thatandSTREAM.OutLen=∞.
DHAESpermitsencryptingmessagesofarbitrarylength.
ThekeygenerationalgorithmPKE.KeyGenforDHAESissimplyKEM.KeyGen.
TheencryptionalgorithmdeterminesPKE.Encrypt(PK,m)asfollows:
1.UseKEM.Encrypt(PK)togenerateapair(K,K).
2.SplitKintheform
K=KMAC||KSTREAM
suchthat|KMAC|=MAC.KeyLen(andthus|KSTREAM|=STREAM.KeyLen).
3.ComputeC=m⊕STREAM(KSTREAM,|m|).
4.ComputeM=MAC(KMAC,C).
5.ReturntheciphertextK||M||C.
ThedecryptionalgorithmcomputesPKE.Decrypt(PK,K||M||C)asfollows(notethat
theciphertextcanbeuniquelysplitintoitsthreecomponentsbecauseKEM.CipherLenand
MAC.OutLenarefixed):

3.4TheSecurityoftheDHAESConstruction

Compute1.K=KEM.Decrypt(SK,K).
Ifthiscomputationfails,abortwithanerror(returninvalid).
2.SplitKintheform
K=KMAC||KSTREAM
suchthat|KMAC|=MAC.KeyLen.
Compute3.M=MAC(KMAC,C)
whethertestandM.M=Ifthisisnotthecase,abortwithanerror(returninvalid).
stringtheReturn4.C⊕STREAM(KSTREAM,|C|)
result.decryptionas

33

3.4TheSecurityoftheDHAESConstruction
Insection3.1,wehaveseenhowthesecurityofapublic-keyencryptionschemeagainst
adaptivechosen-ciphertextattackscanbecapturedquantitatively.TheDHAESconstruction
isdesignedtobesecureagainstsuchattacksprovidedthattheunderlyingprimitivesfulfill
notions.ysecuritcertainThepresentsectionfirstdefinesaccordingquantitativeexpressionsofsecurityforthe
primitivesusedintheDHAESconstruction(sections3.4.1,3.4.2,and3.4.3)andthengivesa
securityresultthatrelatestheIND-CCAsecurityofDHAEStothesecurityoftheseprimitives
3.4.4).(section

3.4.1SecurityoftheKeyEncapsulationMechanism
isSecuritexpressedyagainstthroughadaptivethefollowingchosen-ciphertextattackgameattacks(cf.for[30,theksectioney7.1.2]):encapsulationmechanismKEM
1.Theadversaryqueriesakeygenerationoracle,whichusesKEM.KeyGentocomputea
keypair(PK,SK)
andrespondswithPK(andsecretlystoresSK).
2.Theadversarymakesasequenceofqueriestoadecryptionoracle.Eachqueryisan
arbitrarystringsoflengthKEM.CipherLen;theoraclerespondswith
KEM.Decrypt(SK,s).
ThuseachoracleresponseiseitherastringoflengthKEM.OutLenorthespecial
.invalidaluev

34

HybridPublic-KeyEncryption:TheDHAESConstruction

3.Theadversaryqueriesakeyencapsulationoracle,whichworksasfollows:ituses

KEM.Encrypt(PK)

|toK0|=obtain|K1a|,cpairho(osesK0a,Koracleuniformly),itrandomgeneratesbitabKEMuniformly∈{0,1},randomlyandrespstringondsK1withsuchthat
(KbKEM,Koracle)

lenge.chalas4.Theadversaryagainmakesasequenceofqueriestoadecryptionoracleasinstage2,
wherethistimetheoraclerefusesthespecificqueryKoracle(andrespondsinvalidforthis
case).5.TheadversaryoutputsabitbKEM∈{0,1}.
TheCCAadvantageofanadversaryA(aninteractiveprobabilisticalgorithmwithbounded
runningtime)againstKEMinthisattackgameis
AdvCCAKEM,A=PrbKEM=1|bKEM=1−PrbKEM=1|bKEM=0.
Thiscanalsobewrittenas
22∙Pr[bKEM=bKEM]−1.
3.4.2SecurityoftheOne-TimeMessageAuthenticationCode
ToexpressthesecurityofMAC,weusethefollowingattackgame(cf.[30,section7.2.2]:
1.TherandomadversarystringKofsubmitslengthastringMAC.stoKeyLenaMAandCorrespacle.ondsThiswithoracleMAC(K,sgenerates).auniformly
2.Theadversaryoutputsalist(s1,t1),(s2,t2),...,(sm,tm)ofpairsofstrings.
AnadversaryAagainisaninteractiveprobabilisticalgorithmwithboundedrunningtime;
notethattherunningtimeboundimpliesaboundonthelengthmofthelist.Wesaythat
adversaryAhasproducedaforgeryif

MAC(K,sk)=tk
andsk=sforsomek(1≤k≤m).Theadversary’sadvantageagainstMAC,denoted
AdvForgeMAC,A,
istheprobabilitythatitproducesaforgeryintheabovegame.

3.4TheSecurityoftheDHAESConstruction

35

3.4.3SecurityofthePseudo-RandomBitStringGenerator
ToexpressthesecurityofSTREAM,weusethefollowingattackgame:
1.Theadversaryqueriesabitstringoracle.Thisoraclegeneratesauniformlyrandom
stringuniformlyKofrandomlengthstringSTREAMstre.am1KeyLenwith,|strecomputesam0|=str|estrame0am=1|,choSTREAMoses(aK),uniformlygeneratesran-a
dombitbSTREAM∈{0,1},andrespondswith
amestrb

lenge.chalas2.TheadversaryoutputsabitbSTREAM∈{0,1}.
TheadvantageofanadversaryA(againaninteractiveprobabilisticalgorithmwithbounded
isSTREAMagainsttime)running
AdvSTREAMA=PrbSTREAM=1|bSTREAM=1−PrbSTREAM=1|bSTREAM=0,
whichcanalsobewrittenas
22∙Pr[bSTREAM=bSTREAM]−1.
3.4.4SecurityResultfortheDHAESConstruction
LetAbeanadversarylaunchinganadaptivechosen-ciphertextattack(seetheattackgame
insection3.1)againstDHAESwithsomekeyencapsulationmechanismKEM,someone-time
messageauthenticationcodeMAC,andsomepseudo-randombitstringgeneratorSTREAM.
ItcanbeshownthatthereareadversariesA1,A2,A3againstKEM,MAC,STREAMallhaving
essentiallythesamerunningtimeasAsuchthat
AdvCCAPKE,A≤2∙AdvCCAKEM,A1+AdvForgeMAC,A2+AdvSTREAM,A3.
ThisquantitativesecurityresultcanbeinterpretedassayingessentiallythatifDHAESis
notsecure,thenthisisbecauseoneoftheunderlyingcryptographicprimitivesisnotsecure.
Intheremainderofthissection,wewillprovethisresult.LetG0denotetheattackgame
describedinsection3.1.Wewillmodifyitinmultiplesteps,essentiallydisablingtheunder-
lyingcryptographicschemes(keyencapsulationmechanism,one-timemessageauthentication
code,andpseudo-randombitstringgenerator)oneafteranother.
ForDHAES,stage3(invocationoftheencryptionoracle)intheattackgamefromsec-
tion3.1canbeexpressedasfollows.Firsttheadversarysubmitsmessagesm0andm1
suchthat|m0|=|m1|.TheencryptionoracleusesKEM.Encrypt(PK)togenerateapair
(Koracle,Koracle)andsplitsKoracleintheform
Koracle=KMAC||KSTREAM
suchthat|KMAC|=MAC.KeyLen.Thenitchoosesauniformlyrandombitb∈{0,1},com-
putesC=mb⊕STREAM(KSTREAM,|mb|)

36

HybridPublic-KeyEncryption:TheDHAESConstruction

M=MAC(KMAC,C),

andM=MAC(KMAC,C),
returnsandKoracle||M||C
aschallengeciphertext.Inthefollowing,whenwetalkabouttheencryptionoraclestage,it
isunderstoodthatwerefertothisprocedure.
G1islikeG0exceptthatauniformlyrandomstringisusedforKoracle,whereasKoracleis
stillgeneratedbyKEM.Encrypt(PK).Inthedecryptionoracle,Koracleissubstitutedwhenever
KEM.Decrypt(SK,Koracle)wouldhavetobecomputed.Thisappliestoboththefindandthe
guessstage,i.e.stages2and4intheattackgamefromsection3.1.Thus,theinvocation
ofKEM.Encrypt(PK)togenerateKoraclemustbeadvancedfromstage3toanearlierstage.
InG0,thisisonlyadescriptivechangeanddoesnotaffectthebehaviorobservedbythe
.ersaryadvG2islikeG1exceptthatthedecryptionoraclealwaysrespondswithinvalidwhenfaced
withanyqueryprefixedwithstringKoracle.
G3islikeG2exceptthattheencryptionoracleusesauniformlyrandomstringstreamof
theappropriatelengthinsteadofcomputingSTREAM(KSTREAM,|mb|).
NowweconsideranadversaryAasinsection3.1,exposedtothesedifferentattackgames
Gx,0≤x≤3,andlookattherespectivesuccessprobabilitiesPrGxb=b.BasedonA,
adversariesA1,A2,A3againstKEM,MAC,STREAMwillbebuiltallhavingessentiallythe
samerunningtimeasA.
A1attacksKEMasfollows(cf.section3.4.1).Atfirst,itgeneratesb∈{0,1}uni-
formlyatrandomandqueriesitskeyencapsulationoracletoobtainapair(Koracle,Koracle).
Then,itrunstheadversaryA,playingtherolesofthedecryptionoracleandencryp-
tionoracle:whenAqueriesitsdecryptionoracle,A1usesitsowndecryptionoracleto
computeKEM.Decrypt(SK,K)whenperformingthedecryptionalgorithmfromsection3.3,
substitutingKoraclewhenKEM.Decrypt(SK,Koracle)wouldhavetobecomputed;whenA
queriesitsencryptionoracle,A1performstheencryptionoraclestageusingthepregener-
atedpair(Koracle,Koracle)andthepregeneratedbitb.Finally,whenAoutputsitsbitb,A1
outputs1ifb=band0otherwise.Observethat

PrG1b=b−PrG0b=b=AdvCCAKEM,A1
(G0correspondstobKEM=0,G1correspondstobKEM=1insection3.4.1).
A2attacksMACasfollows(cf.section3.4.2).Atfirst,itgeneratesb∈{0,1}anda
stringKSTREAMoflengthSTREAM.KeyLenuniformlyatrandomandusesKEM.Encrypt(PK)
togenerateKoracle.Then,itrunstheadversaryA,playingtherolesofthekeygeneration
oracle(sothatA2knowsSK),decryptionoracle,andencryptionoracle.WheneverAsubmits
anyqueryK||M||Ctothedecryptionoracle,A2addsthepair(C,M)toitsownoutput;queries
prefixedwithKoraclearerefused,allotherquestionsareansweredusingSK.Intheencryption
oraclestage,A2substitutesthepregeneratedstringKSTREAMandthepregeneratedbitb,and
ciphertext.A’sfinaloutputbitbisignored.Observethat
itinvokesitsMACoracleonCinsteadofusingMACdirectlytoobtainMforthechallenge
PrG2b=b−PrG1b=b≤AdvForgeMAC,A2

3.4TheSecurityoftheDHAESConstruction

37

(A2runsAasingameG2,andAwouldobservedifferentbehavioringameG1onlyinthe
caseswhereaforgeryisproduced).
A3attacksSTREAMasfollows(cf.section3.4.3).First,itgeneratesb∈{0,1}andastring
KoracleoflengthKEM.OutLenuniformlyatrandom.Then,itrunstheadversaryA,playing
therolesofthekeygenerationoracle,encryptionoracle,anddecryptionoracle,substituting
thepregeneratedstringKoracleandthepregeneratedbitbintheencryptionoraclestage,and
refusinganydecryptionoraclequeryprefixedwithKoracle(bothinthefindstageandinthe
guessstage).WhenAoutputsitsbitb,A3outputs1ifb=band0otherwise.Observethat
PrG3b=b−PrG2b=b=AdvSTREAM,A3
(G2correspondstobSTREAM=0,G3correspondstobSTREAM=1insection3.4.3).
FinallyobservethatPrG3b=b=21.
Fromthisweobtaintheinequality
2AdvCCAPKE,A=2∙1−PrG0b=b
=2∙PrGxb=b−PrGx−1b=b
3≤x≤1≤2∙AdvCCAKEM,A1+AdvForgeMAC,A2+AdvSTREAM,A3,
whichconcludestheproof.

38

Hybrid

Public-Key

Encryption:

The

DHAES

Construction

4Chapter

APublic-KeyLength-PreservingCryptosystemChaumianforMixes

Chaum’smixconcept[24]isintendedtoallowuserstosenduntraceableelectronicmail
thatwithoutithasufficesvingfortojusttrustaoneofsingletheseauthorittobey.trustThewideaorthyisintouseorderatonumacbhievereofunintraceabilittermediatesy.sucTheh
besendercondovincedesnotthathavatetoleastdecideoneinwhicahgivenparticularlistinwillbehatermediateveasheexpisected.willingtoThesetrust,inhejusttermediates,must
thesizemixes,(shorteraremessagesremailerscanbeacceptingpadded,public-klongereymessagesencryptedcaninput.besplitMessagesintommustultiplebeofparts).afixedTo
sendpublicakeymessage,ofeachitismix;routedthenhethroughrecursivacelyhainofencryptsmixestheM1,..message.,Mn:the(includingsendertheobtainsaddresstheof
thefinalrecipient)yieldingEM1EM2(...EMn(payload)...)whereEMidenotesencryption
withMi’spublickey,andsendstheresultingciphertexttomixM1.Eachmixremovesthe
correspondinglayerofencryptionandforwardsthedecryptedmessagetothenextmix;thus
mixMnwillfinallyrecoverpayload.
Eachmixisexpectedtocollectalargebatchofmessagesbeforeforwardingthedecryption
Itresults.isimpTheortanttomessagesprevenintthereplabatcyhattacmustks:baemixreorderedmustnot(mixed)processtotheprevensametmessagemessagettracing.wice,
orcauseactivmeultipleadversariesdeliveryw.ouldbe(Timestampsabletocantracebeusedmessagestolimitbytheduplicatingtimespanthemforatwhichsubmissionmixeshavtoe
torememberwhichmessagestheyhavealreadyprocessed;see[24]and[29].)
Usuallyitisdesireabletoallowsourcerouting,i.e.letsenderschoosemixchainsona
per-messagebasis.Thisincreasestheflexibilityofthewholescheme:senderscanmakeuseof
newmixesthatgointooperation,andtheycanavoidmixesthatappearnottoworkproperly;
inparticular,theycanavoidmixesthatsuppressmessages(beitintentionallyorbecauseof
technicalproblems),whichmightbenoticedwhensendingprobemessagestooneselfovermix
caddresshains.Foforthesourcenextmixrouting,ininthethechainrecursivsothatelyeachencryptedmixknowsmessage,whereeachtolayforwermardustthecontainmessage.the
Aproblemwiththestraightforwardimplementationofsourceroutingisthatmessageswill
layshrinkerasthattheymustprobeceedincluded,throughbutthecalsohain,becausenotonlybpublic-kecauseeyoftheencryptionforwardingincreasesaddressmessageforeacsize.h
Forshouldoptimalessenuntiallylotraceabilitoklikye,wtheeneedresultinglength-prmessageseservingthatmixes:theyforwtheardmessagestootherthatmixes.mixesreceive

39

40

APublic-KeyCryptosystemforLength-PreservingChaumianMixes

Aconstructionforlength-preservingmixesisgivenin[24](avariantofthisisusedinthe
fieldedsystemMixmaster[56]):mixmessagesconsistofafixednumberofslotsofafixed
size.Thefirstslotispublic-keyencryptedsothatitcanbereadbythefirstmixinthe
chain.Besidescontrolinformationdirectedatthatmix(suchastheaddressofthenextmix
inthechainor,incaseofthelastmix,theaddressofthefinalrecipient),decryptionyields
asymmetrickeythatthemixusestodecryptalltheotherslots.Thenslotsareshiftedby
oneposition:thedecryptionofthesecondslotbecomesthenewfirstslot,andsoon.Anew
finalslotisaddedconsistingofrandom(garbage)datatoobtainamixmessageofthedesired
fixedlength,whichcanthenbeforwardedtothenextmix.Onthewaythroughthechain,
eachmixmessageconsistsofanumberofslotswithvaliddatafollowedbyenoughslotswith
garbagetofillallavailableslots;mixesareobliviousofhowmanyslotscontainvaliddata
andhowmanyarerandom.Eachmixinthechain,whendecryptingandshiftingtheslots,
will“decrypt”thegarbageslotsalreadypresentandaddanewfinalslot,thusincreasingthe
numberofgarbageslotsbyone.Wenotethatwhilethetransformationofanincomingmix
messagetothecorrespondingoutgoingmixmessageislength-preserving,thedecryptionstep
itselfisactuallylength-expandingbecausesomeofthedataobtainedbydecryptioniscontrol
dataintendedforthecurrentmix.
Theproblemwiththisslot-basedapproachforobtainingahybridpublic-keycryptosystem
withlength-expandingdecryptionisthatitisnotsecureagainstactiveattacks:assumethat
anadversarycontrolsatleastonemix,andthatallsenderssubmitwell-formedmessages.
Nowwhenthevictimsubmitsamessage,theadversarycanmarkitbymodifyingoneofthe
slots.Thismarkwillpersistasthemessageisforwardedthroughthemixchain:duetothe
decryptionandslotshiftingperformedbyeachmix,thecorrespondingslotwillalwaysbe
somehowdifferentfromwhatitshouldlooklike(whereasunmarkedmessageswillnotshow
suchdefects).Ifthefinalmixiscontrolledbytheadversary,theadversarymaybeableto
noticethemodification,e.g.detectaregionofgarbagebitsinanotherwisecomprehensible
message,andthusbreakuntraceability.
Toruleoutsuchattacks,thepublic-keycryptosystemshouldprovidesecurityagainst
adaptivechosenciphertextattacks(CCAsecurity).TheusualnotionofCCAsecurityfor
public-keyencryptionschemesaspresentedinsection3.1isnotapplicabletopublic-key
cryptosystemswithlength-expandingdecryptionbecausetheencryptionoperationmustbe
defineddifferentlyhere:encryptioncannotbetreatedasanatomicblack-boxoperationthat,
givenafixedpublickey,takesaplaintextandreturnsaciphertext(withinthisapproach,
length-expandingdecryptioncouldnotrecovertheoriginalplaintext).Rather,theencryp-
tionprocessthatwewillusefirstisinputpartofthedesiredciphertextanddeterminesa
correspondingpartofwhatwillbethedecryptionresult(itisthisstepthatprovideslength
expansion);thenitisinputthepayloadplaintextandfinallyoutputsthecompleteciphertext,
whichincludestheportionrequestedinthefirstinput.
Section4.1describesasecureandpracticalhybridconstructionforlength-preserving
mixes,whichisalsomoreflexiblethantheslot-basedapproach.Thestructureofeachlayer
ofencryptionresemblesthatofthepublic-keyencryptionschemeDHAES(seechapter3).
Section4.2discussesappropriatesecuritynotionsandgivesprovablesecurityresultsforthe
construction.ThischaptershowsessentiallyhowMixmaster([56],[64])shouldhavebeenspecifiedto
becryptographicallysecureagainstactiveattacks.(Notethatanentirelydifferentmodelof
operationformixnetworksisassumedbyOhkuboandAbe[68]andJakobssonandJuels[44]:
theseconstructionsassumetheexistenceofasharedauthenticatedbulletinboard,whereas

4.1TheMixEncryptionScheme

41

hereweareinterestedinanopensystemthatcanbeusedwithpoint-to-pointcommunication
cbyhaptere-mailonorthesimilarDHAESmeans.)Vconstructionariousareideasandtransferredtectohniquesfitthethatnewarenotionsfamiliaroffromsecurittheypreviousneeded
inthecontextoflength-preservingmixes.

4.1TheMixEncryptionScheme
Theconstructionpresentedinthefollowingallowsmuchflexibilityinthechoiceofcrypto-
graphicschemes,eveninasinglechain.Thesingleparameterthatmustbefixedforallmixes
isthedesiredmixmessagelength.Alsoitmaybedesireabletodefineamaximumlengthfor
theactualmessagepayload,i.e.thepartoftheplaintextasrecoveredbythefinalmixthat
canbechosenbythesender:asamessageproceedsthroughthemixchain,moreandmoreof
thedatawillbepseudo-randomgibberish;thelengthoftheusefulpartofthefinalplaintext
revealsthatchainsleavinglessthanthisamountcannothavebeenused.Thelengthnofthe
mixchain(i.e.thenumberofconsecutivemixes)neednotbefixed.
Forpurposesofexposition,wenumberthemixesM1,...,Mnaccordingtotheirposition
inthechainchosenbythesender.(Notethatinpracticethesamemixmightappearmultiple
timesinonechain.)ForeachmixMi,thefollowingmustbedefinedand,withtheexception
ofthesecretkeySKMi,knowntosenderswhowanttousethemix:
•Akeyencapsulationmechanism
KEMMi(seedefinition3.2)andakeypair

(PKMi,SKMi)
forthiskeyencapsulationmechanismasgeneratedby
KEMMi.KeyGen.

•Aone-timemessageauthenticationcode
CMAMi(seelengthdefinition−KEMM3.3)..InCipherLenour−MAconstruction,CM.OutLenMAC.Miwillonlybeusedforstringssoffixed
ii•Apseudo-randombitstringgenerator

STREAMMi(seedefinition3.4)withafixedoutputsize
STREAMMi.OutLen.
ThiswillbeusedforanXOR-basedstreamcipher.

42

APublic-KeyCryptosystemforLength-PreservingChaumianMixes

tegerinAn•PlainLenMispecifyingthelengthoftheprefixofeachdecryptedmessagethatisconsideredcontrol
datadirectedtomixMMiandwillnotbeforwarded.(Thisistheamountofmessage
expansion:thedecryptedmessageminustheprefixmustbeofsizebecausethatis
whatwillbesenttothenextmix.)
Theparametersmustfulfillthefollowingconditions:
KEMMi.CipherLen+MACMi.OutLen+PlainLenMi<(4.1)
KEMMi.OutLen=STREAMMi.KeyLen+MACMi.KeyLen(4.2)
STREAMMi.OutLen=PlainLenMi+(4.3)

Encryption4.1.1WenowdescribeencryptionforsendingamessagethroughachainM1,...,Mn.Letpayload
bethemessageoflength
|payload|=−(KEMMi.CipherLen+MACMi.OutLen+PlainLenMi)(4.4)
n≤i≤1let(messagesplainibeshortertheconthantrolthismessagemaximofumlengthshouldbePlainLenMrandomlyidirectedpaddedtoonthetheresprighectivt).eFormix.eachThei,
encryptionalgorithmfortheseargumentsisdenoted
chainencryptM1,...,Mn(plain1,...,plainn;payload)
orchainencryptM1,...,Mn(plain1,...,plainn;payload;λ)
whereλistheemptystring.Thealgorithmisdefinedrecursively.Let1≤i≤n,andletCi
beastringoflength
|Ci|=1≤k<i(KEMMk.CipherLen+MACMk.OutLen+PlainLenMk)(4.5)
(thusspecifically|C1|=0,i.e.C1istheemptystring).Thenalgorithm
chainencryptMi,...,Mn(plaini,...,plainn;payload;Ci)
ws:folloasorksw1.UseKEMMi.Encrypt(PKMi)togenerateapair(Ki,Ki).
2.SplitKiintheform
Ki=Ki,MAC||Ki,STREAM
suchthat|Ki,MAC|=MACMi.KeyLen(and,by(4.2),|Ki,STREAM|=STREAMMi.KeyLen).

4.1TheMixEncryptionScheme

43

3.ComputeSTREAMMi(Ki,STREAM)andsplitthisstringintheform
streami,L||streami,R
suchthattheleftpartstreami,Lisoflength
−|Ci|−KEMMi.CipherLen−MACMi.OutLen.
4.Fori=n(lastmix),by(4.4)and(4.5)itfollowsthat|streamn,L|=PlainLenn+|payload|.
setcase,thisInCn=streamn,L⊕(plainn||payload)||Cn.
letOtherwise,Ci+1=streami,R⊕(Ci||0KEMMi.CipherLen+MACMi.OutLen+PlainLenMi),
computerecursionybxi=chainencryptMi+1,...,Mn(plaini+1,...,plainn;payload;Ci+1),
letandCi=streami,L⊕(plaini||prefix|streami,L|−PlainLenMi(xi))||Ci.
5.ComputeMi=MACi(Ki,MAC,Ci).
ciphertexttheReturn6.Ki||Mi||Ci,
whichisoflength.
Thefollowingillustrationdepictsaciphertextgeneratedbytheencryptionalgorithmfora
chainoflengththree,namely
chainencryptM1,M2,M3(plain1,plain2,plain3;payload).
Intheillustration,wehaveconcatenationhorizontallyandXORvertically(i.e.boxesinthe
samerowrepresentbitstringsthatareconcatenated,andtheciphertextistheXORofthe
multiplerowsshown).
adaylopplain3plain2K3M3stream3,L
plain1K2M2stream2,L
K1M1stream1,L

Decryption4.1.2ThedecryptionalgorithmformixM(1≤i≤n)worksasfollows,givenalength-ciphertext
K||M||C(splitintoitsthreecompionentsaccordingtoparametersKEMMi.CipherLen=|K|
andMACMi.OutLen=|M|).Wedenoteit
mixdecryptMi(K||M||C).
ownRemempbositionerthatiinMitheinchain.generalisnotawareofthemixchainusedbythesenderorevenofits

44APublic-KeyCryptosystemforLength-PreservingChaumianMixes

Compute1.K=KEMMi.Decrypt(SKMi,K).
Ifthiscomputationfails,abortwithanerror(returninvalid).
2.SplitKintheform
K=KMAC||KSTREAM
suchthat|KMAC|=MACMi.KeyLen.
Compute3.M=MACMi(KMAC,C)
whethertestand.M=MIfthisisnotthecase,abortwithanerror(returninvalid).
stringtheCompute4.stream=STREAMMi(KSTREAM)
oflengthSTREAMMi.OutLen.
Compute5.stream⊕(C||0KEMMi.CipherLen+MACMi.OutLen+PlainLenMi)
andsplittheresultingstringintheform
P||plainiwhereplainiisoflengthPlainLenMi(andthus,by(4.3),Pisoflength).
6.Returnthepair(plaini,P).
Ifthisalgorithmfinisheswithoutanerror,plainiisacontrolmessagedirectedtothecurrent
mix,andPisthemessagetobeforwardedtoanothermixortothefinalrecipient(asrequested
bythecontrolmessage).
Itisstraightforwardtoverifythatforciphertextscomputedas
chainencryptM1,...,Mn(plain1,...,plainn;payload),
iterativedecryptionbymixesM1,...,Mnwillindeedworkwithoutanerrorandrecoverthe
respectivestringsplainiandfinallyalsothemessagepayloadconcatenatedwithsome(useless)
data.extraContinuingtheexampleattheendofsection4.1.2,welookatillustrationsfordecryption.
TheresultobtainedbymixM1whenapplyingthedecryptionalgorithmgivenabovetothe
asgeneratedciphertextchainencryptM1,M2,M3(plain1,plain2,plain3;payload)
iscomposedasfollows:
adaylopplain3plain2K3M3stream3,L
plain1K2M2stream2,L

stream1,R

4.2ProvableSecurity

45

Thestringplain1isdirectedtoM1.Theremainderofthedecryptionresultisaciphertextthat
shouldbeforwardedtothenextmixinthechain,M2,whichwillthenobtainthefollowing
result:adaylopplain3plain2K3M3stream3,L

stream2,R
stream1,R
Similarly,mixM3willobtainthefollowingfinaldecryptionresult:
plainadaylop3

stream3,R
stream2,R
stream1,R

4.2ProvableSecurity
bTheehavesmixcorrectlyconcept.is(Hoinwevtendedernotetoprothatvidesecuritdenial-of-serviceywhenatattacksleastbyonemixincorrectlycanopbeeratingtrustedmixesand
wecannotassumebethatruledsomeout;thesingleonlymixoptionMwisorkstoaasvoidexpmixesectedthatwhileappallearothertomixesmalfunction.)areconThtrolledus
ibytheadversaryandmaynotfollowtheprotocol(alsothecryptographicschemesKEMMj,
MACMj,andSTREAMMjassociatedwithmixesMj,j=i,mightbenotsecure,andKEMMj
mightevennotbeavalidkeyencapsulationmechanismaccordingtothedescriptiongivenin
4.1).sectionThisleavesonlyMitobeattacked:outerlayersofencryptionformixesthatappearbefore
MandiinainnermixlaycershainofareencryptioneasilyremoforvedmixesbythethatadvappearersaryafterandMthiusinaaremixnotcrelevhainanaretforinvolvsecuritediny;
cessproencryptionthechainencryptMi,...,Mn(plaini,...,plainn;payload;Ci)
describedinsection4.1.1,butcannotprovideprotectionagainsttheadversary.
Animportantsecuritypropertyformixesisunlinkability:anadversarywhoobservesa
batcmessageshofwhenencryptedthesearemessagesforwasardedtheseareelsewheresenttoshouldamixnotbandeablewhotoseestellthebetterresultingthanbycdecryptedhance
whichdecryptedmessagescorrespondtowhichencryptedmessages.
AsBeynotedondinthistheinbasictrosecuritductionythenotion,thewecurrenalsotcwanthapter,toacithievisecrucialsecurittoydetectagainstactivmessageeattacreplaks.y
andignorereplayedmessage.However,thisdoesnotruleoutactiveattacksbasedonmessage
modifications.Toshowthatourconstructionforlength-preservingmixesissecureagainst
thiskindofattacks,wewillmodelanactiveadversarywhoisabletolaunchanadaptive
chosenciphertextattack(CCA).
guaranWepteedointinoutthethatpresenceintheofmodelactiveofopattacerationks:anthatactivweeadvassume,ersaryunlinkwhoabilitysuppressescannotallbebutfullya
singleoneofthelegitimateencryptedmessagesinabatchandsubstitutesnewmessagesfor

46

APublic-KeyCryptosystemforLength-PreservingChaumianMixes

themcaneasilytracetheremaininglegitimatemessage.Thiscanbeavoidedonlyheuristically
(eachsenderofmixmessagesshouldoccasionallyrouteamessagetohimselftoseeifitgets
through).Toavoidrelatedfloodingattacks(whereanadversaryinjectslotsofmessagesto
causeamixtoprocessallmessagescurrentlyinthepool),mixesshouldnotstartanewbatch
wheneveracertainfixednumberofmessageshasarrived;instead,eachbatchshouldbekept
openforadditionalmessagesduringsometimeframe.
Sections4.2.1and4.2.2showhowthesecurityofthemixconstructioncanbecaptured
formallybydescribingunlinkabilityandCCAsecurity,respectively.Wehavealreadyseen
securitydefinitionsfortheunderlyingkeyencapsulationmechanism(section3.4.1),one-time
messageauthenticationcode(section3.4.2),andpseudo-randombitstringgenerator(sec-
tion3.4.3).Section4.2.3presentssecurityresultsthatrelatethesecurityofthemixencryp-
tionschemetothesecurityoftheseprimitives:wewillseethatifthemixencryptionscheme
isnotsecure,thenthisisbecauseoneoftheunderlyingcryptographicschemesisnotsecure.

4.2.1UnlinkabilityoftheMixEncryptionScheme
Anintuitiveapproachtodefiningunlinkabilityisasfollows:theadversaryseesabatchof
mciphertextsandarandompermutationoftheresultingmdecryptionresults;foreach
decryptionresult,theadversarymakesaguessontheindexofthecorrespondingciphertext.
Withrandomguessing,theexpectednumberofcorrectguessesisone.Anadversarywhocan
dobetterthanthisbreaksunlinkability.
Morespecifically,welettheadversaryselecttheplaintextsasfaraspossible(remember
thataswehavelength-expandingdecryption,itisnotpossibletochooseallofthedecryption
resultarbitrarilywhengeneratingaciphertext).Intheformaldefinition,weconfinetoa
settingwithtwoplaintextswhereonlyoneciphertextisshowntotheadversary(anadversary
intheunrestrictedsettingcanbeusedtobuildanadversaryinthissetting).Thisiscaptured
inthefollowingattackgame:
1.Theadversaryqueriesakeygenerationoracle,whichusesKEMMi.KeyGentocompute
paireyka)SK,PK(andrespondswithPK(andsecretlystoresSK).
2.Theadversaryusesanencryptionoracleasfollows(cf.theencryptionalgorithm
fromsection4.1.1inthecaseofalength-1mixchain,i.e.withnorecursionand|Ci|=0):

•Theadversarysubmitsapairofstringpairs
(plaini,0,m0),(plaini,1,m1)
where|plaini,b|=PlainLenMi

where|plaini,b|=PlainLenMi
and|mb|=−KEMMi.CipherLen−MACMi.OutLen−PlainLenMi
forb=0,1.

4.2ProvableSecurity

47

•Theencryptionoraclechoosesabitb∈{0,1}uniformlyatrandom.Thenituses
KEMMi.Encrypt(PK)togenerateapair(Koracle,Koracle)andsplitsKoracleinthe
formKoracle=KMAC||KSTREAM
suchthat|KMAC|=MACMi.KeyLen;itcomputesSTREAMMi(KSTREAM)andsplits
theresultingstringstreamintheform
stream=streamL||streamR
suchthat|streamL|=−KEMMi.CipherLen−MACMi.OutLen;anditcomputes
C=streamL⊕(plaini,b||mb)
andM=MACMi(KMAC,C).
pairtheoutputsitThen(Koracle||M||C,streamR).
3.Theadversaryoutputsabitb∈{0,1}.
Thebitboutputbytheadversaryissupposedtobeitsguessforthevalueofb.Notethat
thedecryptionresultcorrespondingtotheciphertextKoracle||M||Cis
(plaini,b,mb||streamR)
(seesection4.1.2),andallofthisexceptforthechoiceofthebitbisknowntotheadversary
intheabovegame.
LetAbeanyadversary(interactiveprobabilisticalgorithmwithboundedrunningtime)
inthisattackgame.ItsadvantageagainstunlinkabilityforMi’sinstantiationofthemix
ishemescencryptionAdvLinkMi,A=Prb=1|b=1−Prb=1|b=0
2=2∙Pr[b=b]−1.
4.2.2CCASecurityoftheMixEncryptionScheme
Duetotherecursivenatureofourencryptionalgorithmformixchains,wecannotdirectly
applytheusualdefinitionsofsecurityunderadaptivechosenciphertextattack(CCA)foror-
dinarypublic-keyencryptionaspresentedinsection3.1.Weadapttheattackgamedescribed
thereasfollowstotakeintoaccountthespecialpropertiesofourconstruction:
1.Theadversaryqueriesakeygenerationoracle,whichusesKEMMi.KeyGentocompute
paireyka)SK,PK(andrespondswithPK(andsecretlystoresSK).

48

APublic-KeyCryptosystemforLength-PreservingChaumianMixes

2.[Findstage.]Theadversarymakesasequenceofqueriestoadecryptionoracle.Each
queryisanarbitrarystringsoflength,andtheoraclerespondswith
mixdecryptMi(s),
usingthesecretkeySKfromstage1.Thatis,eachoracleresponseiseitherapair
(plain,P)where|plain|=PlainLenMiand|P|=,orthespecialvalueinvalid.
3.Theadversaryusesaninteractiveencryptionoracleasfollows(comparewiththeen-
4.1.1):sectioninalgorithmcryption•FirsttheadversarysubmitssomestringCisubjectonlytotheconditionthat
0≤|Ci|<−KEMMi.CipherLen−MACMi.OutLen.
•TheinteractiveencryptionoracleusesKEMMi.Encrypt(PK)togenerateapair
(Koracle,Koracle)andsplitsKoracleintheform
Koracle=KMAC||KSTREAM
suchthat|KMAC|=MACMi.KeyLen;itcomputesSTREAMMi(KSTREAM)andsplits
theresultingstringstreamintheform
stream=streamL||streamR
suchthat|streamL|=−|Ci|−KEMMi.CipherLen−MACMi.OutLen;anditcomputes
Ci+1=streamR⊕(Ci||0KEMMi.CipherLen+MACMi.OutLen+PlainLenMi)
andsendsCi+1totheadversary.
•Theadversarysubmitsapairofstringpairs
(plaini,0,m0),(plaini,1,m1)
satisfying|plaini,b|=PlainLenMi
and|mb|=−|Ci|−KEMMi.CipherLen−MACMi.OutLen−PlainLenMi
forb=0,1.
•Theinteractiveencryptionoraclechoosesauniformlyrandombitb∈{0,1},de-
terminesC=streamL⊕(plaini,b||mb)||Ci
andM=MACMi(KMAC,C),
andrespondswiththechallengeciphertext
Koracle||M||C.

4.2ProvableSecurity

49

4.[Guessstage.]Theadversaryagainmakesasequenceofqueriestoadecryptionoracle
asinstage2,wherethistimethedecryptionoraclerefusesbeingaskedforthechallenge
ciphertextKoracle||M||Cfromstage3(itreturnsinvalidforthiscase).
5.Theadversaryoutputsabitb∈{0,1}.
Thebitboutputbytheadversaryisitsguessforthevalueofb.
Theessentialdifferencetotheadaptivechosenciphertextattackgameforordinarypublic-
keyencryptionisthatwehavemadetheencryptionoracleinteractivetoreflecttherecursive-
nessoftheencryptionalgorithmformixchains,whereencryptiontomixeslaterinthechain
thanMicanhavepotentiallyarbitraryeffectsonalargepartoftheplaintext.
Welookatillustrationsfortheciphertextresultingfromtheinvocationoftheinteractive
encryptionoracle.Asinpreviousillustrations,wehaveconcatenationhorizontallyandXOR
vertically.Thestructureofthechallengeciphertextreturnedbytheinteractiveencryption
oracleintheadaptivechosenciphertextattackgameisasfollows:
plaini,bmbCi
KoracleMstreamL
ApplyingalgorithmmixdecryptMifromsection4.1.2tothisciphertextwouldyieldthefol-
result:wingloplaini,bmbCi
amestrRThiscanalsobewrittenasfollows:
plaini,bmbCi+1
LetAbeanyadversary(interactiveprobabilisticalgorithmwithboundedrunningtime)
intheaboveattackgame.ItsCCAadvantageagainstMi’sinstantiationofthemixencryption
ishemescAdvCCAMi,A=Prb=1|b=1−Prb=1|b=0
2=2∙Pr[b=b]−1.
ResultsySecurit4.2.3FirstletAbeanadversaryagainsttheunlinkabilityofthemixencryptionscheme,attacking
amixMiasdescribedinsection4.2.1.ItcanbeshownthatthereareadversariesA1andA2
againstKEMMiandSTREAMMi,respectively,withessentiallythesamerunningtimeasA
thathsucAdvLinkMi,A≤2∙AdvCCAKEMMi,A1+AdvSTREAMMi,A2.
Detailsoftheproofofunlinkabilityfollowbelow.
NowletAbeanadversaryagainsttheCCAsecurityofthemixencryptionscheme,
attackingamixMiasdescribedinsection4.2.2.Itcanbeshownthatthereareadversaries
A1,A2,A3againstKEMMi,MACMi,STREAMMiallhavingessentiallythesamerunningtime
thathsucAasAdvCCAMi,A≤2∙AdvCCAKEMMi,A1+AdvForgeMACMi,A2+AdvSTREAMMi,A3.


50

APublic-KeyCryptosystemforLength-PreservingChaumianMixes

DetailsoftheproofofCCAsecurityfollowbelow.

ProofofUnlinkability
Weprovethesecurityresultfortheunlinkabilityofthemixencryptionscheme.LetG0denote
theattackgamefromsection4.2.1.LetG1belikeG0exceptthatauniformlyrandomstring
isusedforKoracle,whereasKoracleisstillgeneratedbyKEMMi.Encrypt(PK).LetG2belikeG1
exceptthattheencryptionoracleusesauniformlyrandomstringstreaminsteadofcomputing
STREAMMi(KSTREAM).
NowweconsideranadversaryAasinsection4.2.1,exposedtothesedifferentattack
gamesGx,0≤x≤2,andlookattherespectivesuccessprobabilitiesPrGxb=b.Based
onA,adversariesA1andA2againstKEMMiandSTREAMMi,respectively,willbebuilt,each
withessentiallythesamerunningtimeasA.
A1attacksKEMMiasfollows(cf.section3.4.1;notethatthisA1neveractuallyusesits
decryptionoracle).Atfirst,itgeneratesb∈{0,1}uniformlyatrandom.Then,itrunsthe
adversaryA;whenAqueriesitsencryptionoracle,A1queriesitskeyencapsulationoracleto
obtainapair(Koracle,Koracle)andperformsstage2fromsection4.2.1usingthispairandthe
pregeneratedbitb.Finally,whenAoutputsitsbitb,A1outputs1ifb=band0otherwise.
thateObservPrG1b=b−PrG0b=b=AdvCCAKEMMi,A1
(G0correspondstobKEM=0,G1correspondstobKEM=1insection3.4.1).
A2attacksSTREAMMiasfollows(cf.section3.4.3).First,itgeneratesb∈{0,1}anda
stringKoracleoflengthKEMMi.OutLenuniformlyatrandom.Then,itrunstheadversaryA,
playingtheroleofthekeygenerationoracleandtheroleoftheencryptionoracle,whereinit
substitutesthepregeneratedstringKoracleandthepregeneratedbitbinstage2ofsection4.2.1.
WhenAoutputsitsbitb,A2outputs1ifb=band0otherwise.Observethat
PrG2b=b−PrG1b=b=AdvSTREAMMi,A2
(G1correspondstobSTREAM=0,G2correspondstobSTREAM=1insection3.4.3).
FinallyobservethatPrG2b=b=21.
Fromthisweobtaintheinequality
2AdvLinkMi,A=2∙1−PrG0b=b
=2∙PrGxb=b−PrGx−1b=b
1≤x≤2
≤2∙AdvCCAKEMMi,A1+AdvSTREAMMi,A2,
whichconcludestheproof.

ProofofCCASecurity
WeprovetheCCAsecurityresultgivenabove.(Thisproofissimilartothesecurityproof
mofordifyDHAESitininmultiplesectionsteps,3.4.4.)essenLettiallyG0denotedisablingthetheattackunderlyinggamefromcryptographicsectionsc4.2.2.hemesWe(kwilley

4.2ProvableSecurity

51

encapsulationmechanism,one-timemessageauthenticationcode,andpseudo-randombit
another.afteronegenerator)stringG1islikeG0exceptthatauniformlyrandomstringisusedforKoracle,whereasKoracle
isstillgeneratedbyKEMMi.Encrypt(PK).Inthedecryptionoracle,Koracleissubstituted
wheneverKEMMi.Decrypt(SK,Koracle)wouldhavetobecomputed.Thisappliestoboththe
findandtheguessstage,i.e.stages2and4intheattackgamefromsection4.2.2.Thus,
theinvocationofKEMMi.Encrypt(PK)togenerateKoraclemustbeadvancedfromstage3to
anearlierstage.InG0,thisisonlyadescriptivechangeanddoesnotaffectthebehavior
observedbytheadversary.
G2islikeG1exceptthatthedecryptionoraclealwaysrespondswithinvalidwhenfaced
withanyqueryprefixedwithstringKoracle.
G3islikeG2exceptthattheinteractiveencryptionoracleusesauniformlyrandomstring
streaminsteadofcomputingSTREAMMi(KSTREAM).
NowweconsideranadversaryAasinsection4.2.2,exposedtothesedifferentattack
gamesGx,0≤x≤3,andlookattherespectivesuccessprobabilitiesPrGxb=b.Based
onA,adversariesA1,A2,A3againstKEMMi,MACMi,STREAMMiwillbebuiltallhaving
essentiallythesamerunningtimeasA.
A1attacksKEMMiasfollows(cf.section3.4.1).Atfirst,itgeneratesb∈{0,1}uni-
formlyatrandomandqueriesitskeyencapsulationoracletoobtainapair(Koracle,Koracle).
Then,itrunstheadversaryA,playingtherolesofthedecryptionoracleandencryption
oracle:whenAqueriesitsdecryptionoracle,A1usesitsowndecryptionoracletocom-
puteKEM.Decrypt(SK,K)whenperformingthedecryptionalgorithmfromsection4.1.2,
substitutingKoraclewhenKEM.Decrypt(SK,Koracle)wouldhavetobecomputed;whenA
queriesitsencryptionoracle,A1performstheencryptionoraclestageusingthepregener-
atedpair(Koracle,Koracle)andthepregeneratedbitb.Finally,whenAoutputsitsbitb,A1
outputs1ifb=band0otherwise.Observethat
PrG1b=b−PrG0b=b=AdvCCAKEMMi,A1
(G0correspondstobKEM=0,G1correspondstobKEM=1insection3.4.1).
A2attacksMACMiasfollows(cf.section3.4.2).Atfirst,itgeneratesb∈{0,1}andastring
KSTREAMoflengthSTREAMMi.KeyLenuniformlyatrandomandusesKEMMi.Encrypt(PK)to
generateKoracle.Then,itrunstheadversaryA,playingtherolesofthekeygenerationoracle
(sothatA2knowsSK),decryptionoracle,andinteractiveencryptionoracle.WheneverA
submitsanyqueryK||M||Ctothedecryptionoracle,A2addsthepair(C,M)toitsown
output;queriesprefixedwithKoraclearerefused,allotherquestionsareansweredusingSK.In
stage3ofsection4.2.2(encryptionoracle),A2substitutesthepregeneratedstringKSTREAM
andthepregeneratedbitb,anditinvokesitsMACoracleonCinsteadofusingMACMi
directlytoobtainMforthechallengeciphertext.A’sfinaloutputbitbisignored.Observe
thatPrG2b=b−PrG1b=b≤AdvForgeMACMi,A2
(A2runsAasingameG2,andAwouldobservedifferentbehavioringameG1onlyinthe
caseswhereaforgeryisproduced).
A3attacksSTREAMMiasfollows(cf.section3.4.3).First,itgeneratesb∈{0,1}anda
stringKoracleoflengthKEMMi.OutLenuniformlyatrandom.Then,itrunstheadversaryA,
playingtherolesofthekeygenerationoracle,interactiveencryptionoracle,anddecryption

52

APublic-KeyCryptosystemforLength-PreservingChaumianMixes

oracle,substitutingthepregeneratedstringKandthepregeneratedbitbinstage3of
section4.2.2andrefusinganydecryptionoracleoraclequeryprefixedwithK(bothinthefind
stageandintheguessstage).WhenAoutputsitsbitb,A3outputs1ifob=racleband0otherwise.
thateObservPrG3b=b−PrG2b=b=AdvSTREAMMi,A3
(G2correspondstobSTREAM=0,G31correspondstobSTREAM=1insection3.4.3).
FromFinallythisobservweeobtainthatPrtheG3binequalit=by=2.
AdvCCAMi,A=2∙21−PrG0b=b
=2∙PrGxb=b−PrGx−1b=b
3≤x≤1≤2∙AdvCCAKEMMi,A1+AdvForgeMACMi,A2+AdvSTREAMMi,A3,
whichconcludestheproof.

Part

I

I

Practice

53

54

5Chapter

ExpMulti-Exponentiationonenandtiationin
yCryptographPublic-Key

Manyschemesinpublic-keycryptographyrequirecomputingpowers
egjg(exponentiation)orpowerproductse
1≤j≤kj
(multi-exponentiation)inacommutativesemigroupGwithneutralelement1G,e.g.inthe
group(Z/nZ)∗ormoregenerallyinthemultiplicativesemigroup(Z/nZ)forsomeintegern,
inthegroupofrationalpointsonanellipticcurveoverafinitefield[12],orintheclassgroup
ofanimaginary-quadraticorder[40].Theexponentse,ejarenon-negativeintegerswitha
typicallengthofafewhundredorafewthousandbits.
(protoAspcolsecific2.2,2.3exampleandfor2.4),thewhicusehofcanexpbeonenusedastiationanthatessenwtialehaveprimitivseeneinismoreDiffie-Hellmancomplex
cryptographicschemessuchasDHAES(seechapter3)orthemixencryptionschemefrom
chapter4.Anotherwell-knownexampleisRSA[76],whichcanbeusedbothforpublic-key
encryptionandfordigitalsignatures.Multi-exponentiationwithk=2isusede.g.forverifica-
tionofDSAsignatures[66]ingroups(Z/nZ)∗,andforverificationofECDSAsignatures[4]
kin=3groupsisusedofe.g.rationalforvpoinerificationtsonofellipticElGamalcurvesovsignatureserfinite[35]infields.groups(ZMulti-exp/nZ)∗.onenLargertiationvalueswith
ofkappearinprotocolseiofBrands[16].Fork≥2,ingeneralitisunnecessarilyinefficientto
computethepowersgiseparatelyandthenmultiplythem.Instead,specificalgorithmsfor
multi-exponentiationcanbeapplied.
oftenBasesadvang,gjtageous∈Gtopsometimeserformaaresinglefixedbettimewaeenpmanossiblyyrelativcomputations.elyexpensivWitheprfixedecbases,omputationitis
inordertoprepareatablethatcanbeusedtospeedupexponentiationsinvolvingthose
bases.(Formulti-exponentiation,someofthebasesmaybefixedwhileothersarevariable:
forexample,verifyingaDSA[66]orECDSA[4]signatureinvolvescomputingtheproductof
twopowerswhereoneofthebasesispartofdomainparametersthatcanbesharedbetween
alargenumberofsignerswhiletheotherbaseisspecifictoasinglesigner.)

55

56

ExponentiationandMulti-ExponentiationinPublic-KeyCryptography

Weassumethattheexponentsconsistofindependentrandombitsuptoarespective
maximumbit-length;i.e.,eandeacheiisauniformlydistributedrandomintegerinsome
interval[0,2L−1].Inpracticetheactualdistributionmaydiffer,butfortypicalcasesthis
simplifiedassumptionisreasonablyclose.Inthissetting,weconsidergeneralalgorithmsfor
arbitraryexponents;wedonotexaminealgorithmsbasedontailor-madeadditionchainsin
Zkforgiveneore1,...,ek(cf.[14]).
Inthefollowingchapters,welookatefficientalgorithmsforexponentiationandmulti-
exponentiationbasedoneitherjustmultiplicationinthegivensemigrouporoptionally,in
thecaseofagroup,onmultiplicationanddivision.Thisamountstoconstructingaddition
chainsoraddition-subtractionchainsfortheexponenteforexponentiation,andtoconstruct-
ingvectoradditionchainsorvectoraddition-subtractionchainsforthevectorofexponents
(e1,...,ek)formulti-exponentiation(seee.g.thesurvey[38]).
Forpurposesofperformanceanalysis,wedistinguishbetweensquaringsandgeneralmul-
tiplications,astheformercanoftenbeimplementedmoreefficiently.Ifweallowdivision,
ourperformanceanalysisdoesnotdistinguishbetweendivisionsandmultiplications;thisis
reasonablee.g.forpointgroupsofellipticcurvesandforclassgroupsofimaginary-quadratic
numberfields,asinversionisalmostimmediateinsuchgroups.Ifinversionisexpensive(e.g.in
(Z/nZ)∗),thegroupshouldbetreatedasasemigroup,i.e.inversionshouldbeavoided.
Chapter6considersthecaseofasingleexponentiation.Bothleft-to-rightexponentiation
andright-to-leftexponentiationmethodsaredescribed.TheslidingwindowandwindowNAF
techniqueand,asanimprovementtothestateoftheart,thefractionalwindowtechnique
arepresented.Thefractionalwindowtechniqueisageneralizationoftheslidingwindow
andwindowNAFapproach;itcanbeusedtoimproveperformanceindeviceswithlimited
storage.Chapter7presentsdifferentapproachesforcomputingpowerproducts.Itlooksatthe
conventionalsimultaneousexponentiationapproachandpresentsanalternativestrategy,in-
terleavedexponentiation.Thecomparisonshowsthatingeneralgroups,sometimesthecon-
ventionalmethodandsometimesinterleavedexponentiationismoreefficient.Ingroupswhere
invertingelementsiseasy(e.g.ellipticcurves),thewindow-NAFbasedinterleavedexpo-
nentiationmethodusuallywinsovertheconventionalmethod.Exponentiationandmulti-
exponentiationwithprecomputationisalsoconsideredinthatchapter.
Finally,chapter8considersspecifictechniquesthatcanbeusedinellipticcurvecryptogra-
phyifside-channelattacksareaconcern.Followingtheconventiontotreatpointgroupsas
additiveratherthanmultiplicative,wespeakofpointmultiplication(byascalar)insteadof
exponentiation.Two2w-arymethodsarepresentedthatimplementpointmultiplicationin
afixedsequenceofbasicpointoperationstoavoidexposingspecificinformationonscalars:
aleft-to-rightmethodbasedonspecialrepresentationsofscalars,andaright-to-leftmethod
employingaspecialinitializationstage.

tionsenvConNotationalWewritee[j]forbitjofanon-negativeintegere;thuse=je[j]2j.Fornegativej,we
definethate[j]=0.Wewritee[j...j]fortheintegerconsistingoftheconcatenationofbits
jdowntojofe;e.g.,if
e=101112=23,
then

e[3...1]=0112=3

and

e[1...−2]=11002=12.

57

LSBm(e)=e[(m−1)...0]=emod2mistheintegerformedbythemleastsignificantbits
ofc,andLSB(e)=LSB1(e).
understoWhenodtowritingbeapdigits,ositivweeinuseteger;theforconvenexample,tionthat101b2=2denotes2−2a0=digit3.ofvalue−bwherebis

forconvenexample,tionthat101b2=2denotes2−2a0=digit3.

of

aluev

−b

where

b

is

58

Exp

tiationonen

and

Multi-Exp

tiationonen

in

Public-Key

yCryptograph

6Chapter

tiationonenExptEfficien

Inthischapter,welookatthebasiccaseofexponentiation,computingge.Wewillexamine
methodsformulti-exponentiationafterwardsinchapter7.Specialstrategiesforexponentia-
tionwithprecomputationwherethebasegisfixedformultipleexponentiationswillalsobe
presentedthere(insection7.4)becauseanimportantbasicapproachforexponentiationwith
precomputationessentiallyturnsexponentiationsintomulti-exponentiations.
Section6.1givesaframeworkforexponentiationalgorithms.Section6.2describeswithin
theframeworktheslidingwindowexponentiationmethodandthewindowNAFexponentia-
tionmethod.Section6.3presentsanimprovementtothestateoftheart,fractionalwindows,
atechniquethatclosesagapintheslidingwindowandwindowNAFmethodsandisuseful
fordeviceswithlimitedstorage:itcanimprovetheperformancebymakinguseofmemory
thatwouldhavetoremainunusedwiththepreviouslyknownmethods.Thensection6.4
discusseshowtheexponentrepresentationsemployedbythistechniquecanbeimplemented
withsmallmemoryoverhead.

6.1AFrameworkforExponentiation
Rememberthatweareinterestedinalgorithmsthatcomputegeusingjustmultiplicationin
thesemigroupathand,andoptionallyalsodivisioninthecaseofagroup.(Inspecificgroups,
additionalusefulefficientlycomputableendomorphismsmaybeavailablebesidessquaringand
possiblyinversion;seee.g.[82].Thismayleadtobetterexponentiationalgorithmsforthese
groups.Wewillnotconsiderthespecialtechniquesforsuchgroups.)
Manyalgorithmsforcomputinggeforarbitrarylargepositiveintegerseinthissettingfit
intooneoftwovariantsofacommonframework,whichwedescribeinthissection.Expo-
nentsearerepresentedinbase2as
e=bi∙2i,
≤i≤0usingdigitsbi∈B∪{0}whereBissomesetofintegerswith1∈B.WecallthisaB-
representationofe.Detailsofitareintrinsictothespecificexponentiationmethod.(Note
thatforgivenB,B-representationsareusuallynotcanonical.)TheelementsofBmustbe
non-negativeunlessGisagroupwhereinversionispossibleinreasonabletime.Givena
B-representation,left-to-rightorright-to-leftmethodscanbeusedforexponentiation.Left-
to-rightmethodslookattheelementsbistartingatbandproceeddowntob0;right-to-left

59

60

EfficientiationonenExpt

methodsstartatb0andproceeduptob.Dependingonhowthevaluesbicanbeobtained
fromaninputvaluee,itmaybeeasytocomputethemontheflyinsteadofstoringtheB-
representationbeforehand.Left-to-rightmethodsandright-to-leftmethodscanbeconsidered
dualtoeachother(cf.thedualityobservationforrepresentationsofarbitraryadditionchains
asdirectedmulti-graphsin[47,p.481]);bothinvolvetwostages.

dsMethotLeft-to-Righ6.1.1Forleft-to-rightmethods,first,intheprecomputationstage,powersgbforallb∈Bare
computedandstored;ifdivisioninGispermissible(becauseinversionisfast)and|b|∈B
foreachb∈B,itsufficestoprecomputegbforthoseb∈Bthatarepositive.Wereferto
thiscollectionofprecomputedpowersgbastheprecomputedtable.Howtoimplementthe
precomputationstageefficientlydependsonthespecificchoiceofB.Incertainsemigroups,in
ordertoacceleratetheevaluationstage,precomputedelementscanberepresentedinaspecial
waysuchthatmultiplicationswiththeseelementstakelesstime(forexample,precomputed
pointsonanellipticcurvemaybeconvertedfromprojectiveintoaffinerepresentation[27]).
NotethatifboththebaseelementgandthedigitsetBarefixed,theprecomputationstage
neednotberepeatedformultipleexponentiationsiftheprecomputedtableiskeptinmemory.
Incaseswithoutsuchfixedprecomputation,Bisusuallyasetconsistingofsmallintegers
suchthattheprecomputationstagerequiresonlyamoderateamountoftime.If
B=1,3,...,βorB=±1,±3,...,±β
withβ≥3odd,theprecomputationstagecanbeimplementedwithonesquaringand(β−1)/2
multiplicationsasfollows:firstcomputeg2;theniterativelycomputeg3=g∙g2,...,gβ=
gβ−2∙g2.Thisappliestoallencodingtechniquesthatwillbepresentedinthischapter.
Intheevaluationstage(orleft-to-rightstage)ofaleft-to-rightmethod,giventheprecom-
putedtableandtherepresentationofeasdigitsbi,thefollowingalgorithmisexecutedto
computethedesiredpowerfromtheprecomputedelementsgb:
1←AGfori=downto0do
2A←Aifbi=0thenb
A←A∙gi
AreturnIfdivisionispermissible,thefollowingmodifiedalgorithmcanbeused:
1←AGfori=2downto0do
A←Aifbi=0then
ifbi>0then
A←A∙gbi
elseA←A/g|bi|
Areturn

6.1AFrameworkforExponentiation

61

NotethatinthesealgorithmssquaringscanbeomittedwhileAis1G;similarly,thefirst
multiplicationordivisioncanbereplacedbyanassignmentoranassignmentfollowedby
inversionofA.

dsMethot-to-LeftRigh6.1.2Forright-to-leftmethods,noprecomputedelementsareused.Instead,firsttheright-to-left
stageyieldsvaluesinanumberofaccumulatorsAb,oneforeachpositiveelementb∈B.
Ifdivisionispermissible,Bmaycontainnegativedigits;werequirethat|b|∈Bforeach
b∈B.Second,theresultstagecombinestheaccumulatorvaluestoobtainthefinalresult.
Thefollowingalgorithmdescriptioncomprisesbothstages,buttheresultstageiscondensed
intojustthe“return”line:howtoimplementitefficientlydependsonthespecificchoiceofB.
Forbrevity,weshowjustthealgorithmwithdivision(ifBdoesnotcontainnegativedigits,
the“else”-branchwillneverbetakenandcanbeleftout).
}stageright-to-left{forifbb∈>B0dothen
A←Agb←1G
fori=0todo
ifbi=0then
ifbi>0then
Abi←Abi∙A
elseA|bi|←A|bi|/A
2A←Ab{resultstage}
returnbb>∈0BAb
ThesquaringoperationmaybeomittedinthefinaliterationastheresultingvalueofAwill
notbeused.ForeachAb,thefirstmultiplicationordivisioncanbereplacedbyanassignment
oranassignmentfollowedbyinversion(implementationscanuseflagstokeeptrackwhichof
theAbstillcontainthevalue1G).IncasesomeAbarestill1Gattheendoftheright-to-left
stage,operationscanbesavedintheresultstage.
IfB=1,3,...,βorB=±1,±3,...,±β
withβodd(asinallencodingtechniquesthatwewillconsiderinthischapter),theresult
stagecanbeimplementedasfollows([90],[47,exercise4.6.3-9]):
forb=βto3step−2do
Ab−3←Ab−23∙Ab
A1←A1∙Ab
Areturn1Thisresultstagealgorithmrequires(β−1)/2squaringsandβ−1multiplications.

62

tiationonenExptEfficien

6.2SlidingWindowExponentiationandWindowNAFExpo-
tiationnenAwell-knownmethodforexponentiationinsemigroupsistheslidingwindowtechnique
(cf.[84,p.912]and[38,section3]).Theencodingisparameterizedbyasmallpositive
integerw,thewindowsize.ThedigitsetisB={1,3,...,2w−1}.Encodingsusingthese
digitscanbecomputedontheflybyscanningtheordinarybinaryrepresentationoftheexpo-
nenteitherinleft-to-rightorinright-to-leftdirection:intherespectivedirection,repeatedly
lookoutforthefirstnon-zerobitandthenexaminethesequenceofwbitsstartingatthis
bitposition;oneoftheodddigitsinBsufficestocoverthesewbits.Forexample,given
e=88=10110002,forwindowsizew=3,left-to-rightscanningyields
10110002→510002,
yieldsscanningt-to-leftrighand10110002→10030002.
Thelengthoftheresultingrepresentation
e=bi∙2i
≤i≤0isatmostthatofthebinaryrepresentation,i.e.amaximumindexsufficestorepresentany
(+1)-bitexponent.Theaveragedensityofnon-zerodigitsis1/(w+1)fore→∞.(Amore
preciseanalysisshowsthattheaveragenumberofnon-zerodigitsintherepresentationfor
(+1)-bitexponentsis
+1+1−w(w+3)2+O(−)
w+12(w+1)
forarealnumber>1[26,Proposition2.12]).
IncludingnegativedigitsintoBallowsdecreasingtheaveragedensity:a{±1}-represen-
tationsuchthatnotwoadjacentdigitsarenon-zero(“propertyM”from[75])iscalleda
non-adjacentformorNAF.Moregenerally,let
B=±1,±3,...,±(2w−1);
thenthefollowingalgorithm(from[82])generatesaB-representationofesuchthatatmost
oneofanyw+1consecutivedigitsisnon-zero.Thereisauniquerepresentationwiththis
property,thewidth-(w+1)NAFofe.WeusethetermwindowNAF(wNAF)ifwis
understood(awidth-2NAFcansimplybecalledaNAF).Thisideaisalsoknownasthe
signedwindowapproach;w+1canbeconsideredthewindowsize.
e←c0←ido0>cwhileifLSB(c)=1then
b←LSBww+1(c)
then2≥bifb←L−2w+1

6.2SlidingWindowExponentiationandWindowNAFExponentiation

63

b−c←celse0←bbi←b;i←i+1
2c/←creturnbi−1,...,b0
Comparedwiththebinaryrepresentation,thelengthcangrowatmostbyonedigit,soa
maximumindexissufficienttorepresentany-bitexponentasawindowNAF.Width-
(w+1)NAFshaveanaveragedensityof1/(w+2)fore→∞([78],[81],[57],[82]).(Herea
morepreciseanalysisshowsthattheaveragenumberofnon-zerodigitsintherepresentation
for-bitexponentsis
+1−w(w+3)+O(−)
w+22(w+2)2
forarealnumber>1[26,Proposition2.6]).
Forleft-to-rightexponentiationusingtheslidingwindoworwindowNAFtechnique,the
precomputationstagehastocomputegbforb∈{1,3,...,2w−1},whichforw>1canbe
achievedwithonesquaringand2w−1−1multiplications(seesection6.1.1).
Forright-to-leftexponentiationusingtheslidingwindoworwindowNAFtechnique,the
Aresultstagehastocomputeb
bb∈{1,3,...,2w−1}
givenaccumulatorvaluesAbresultingfromtheright-to-leftstage.Thiscanbedonein2w−1−1
squaringsand2w−2multiplications(seesection6.1.2).
6.2.1ModifiedWindowNAFs
TheefficiencyofexponentiationgivenaB-representationdependsonthenumberofnon-
zerodigitsandthelengthoftherepresentation(i.e.theminimumindexIsuchthatbi=0
fori≥I).WindowNAFsmayhaveincreasedlengthcomparedwiththeordinarybinary
representation:e.g.,the(width-2)NAFfor3=112is1012,andtheNAFfor7=1112is
10012.(Rememberthatbdenotesadigitofvalue−b.)
Suchlengthexpansioncaneasilybeavoidedinabouthalfofthecasesandthusexponen-
tiationmademoreefficientbyweakeningthenon-adjacencyproperty(cf.[15]forthecaseof
width-2NAFs).AmodifiedwindowNAF(moreprecisely,amodifiedwidth-(w+1)NAF)isa
B-representationobtainedfromawidth-(w+1)NAFasfollows:ifthew+2mostsignificant
digits(ignoringanyleadingzeros)havetheform
zerosw100...0b,
substitutethenzeros1−w010...0β
whereβ=2w−b.Fortheaboveexamples,weseethatthemodified(width-2)NAFfor3is
112,whichisshorterthantheNAF;however,themodifiedNAFfor7remains1001:thisis
acasewherelengthexpansioncannotbeavoidedwithoutincreasingthenumberofnon-zero
digits.

64

ExptEfficientiationonen

wsWindoractionalF6.3Insmalldevices,thechoiceofwforexponentiationusingtheslidingwindoworwindowNAF
techniquedescribedinsection6.2maybedictatedbymemorylimitations.Theexponentiation
algorithmsgiveninsection6.1needstoragefor1+2w−1elementsofG,andthusmemorymay
bewasted:e.g.,ifsufficientstorageisavailableforuptofourelements,onlythreeelements
canactuallybeused(w=2).
Inthissection,wewillseehowtheefficiencyofexponentiationcanbeimprovedbyusing
fractionalwindows,ageneralizationoftheslidingwindowandwindowNAFtechniques.
Section6.3.1describesthisnewencodingtechniqueforthecasethatnegativedigitsare
allowed(signedfractionalwindows).Section6.3.2describesasimplervariantforthecase
thatonlynon-negativedigitsarepermissible(unsignedfractionalwindows).

6.3.1SignedFractionalWindows
wLetwadditionally≥2beallowaninthetegerthebandordermancasesoddm=in−teger1andsuchm=that2w1−≤1,mwhic≤h2w−ould3.turn(Weoutcouldto
yieldthewidth-(w+1)andwidth-(w+2)NAF,respectively.)Thedigitsetforthesigned
fractionalwindowrepresentationwithparameterswandmis
B=±1,±3,...,±(2w+m).
mappingtheLetdigit:{0,1,...,2w+2}→B∪{0}
bedefinedasfollows:
•Ifxiseven,thendigit(x)=0;
•otherwiseif0<x≤2w+m,thendigit(x)=x;
•otherwiseif2w+m<x<3∙2w−m,thendigit(x)=x−2w+1;
•otherwisewehave3∙2w−m≤x<2w+2andletdigit(x)=x−2w+2.
Observethatifxisodd,thenx−digit(x)∈{0,2w+1,2w+2}.Thefollowingalgorithmencodese
intosignedfractionalwindowrepresentation:
cd←←e/LSB2ww+2+2(e)
0←iwhiled=0∨c=0do
b←digit(d)
bi←b;i←i+1
b−d←dd←LSB(c)∙2w+1+d/2
c←c/2
returnbi−1,...,b0

wsWindoractionalF6.3

65

ThisalgorithmisadirectvariantofthewindowNAFgenerationalgorithmshowninsec-
wationy6.2,thatbutshowsbasedthatonthetheloopnewisessenmappingtiallydigita.finiteHerestatewehamacvehineexpressed(with2wthe+1+1algorithmstatesinfora
0≤storing,d≤2wafter+2);bnewhasbbitseentakensubtractedfromcarefromtheconsideredpreviousinputvaluesymbofolsd,andthetheevenngeneratedumberddigitswithbi
areconsideredoutputsymbols.
Thefollowingtableshowswhatcanhappenintheloopintheexamplecasew=2,
1.=m

db=digit(d)d−b
0000100010011223000022
0000501012201112−110002
1000110012210112−5100002
11012−3100002
11112−1100002
Theaveragedensityachievedbythesignedfractionalwindowrepresentationwithparam-
eterswandmis1
w+m2w+1+2
fore→∞.(Assumethatanendlesssequenceofrandombitsistheinputtothefinite
statemachinedescribedabove:wheneverthestatemachineisabouttooutputanon-zero
digit,theintermediatevaluedmod2w+2consistsofw+1independentrandombitsplusthe
leastsignificantbit,whichisnecessarilyset.Thuswithprobabilityp=1−mw+1+1,wehave
d−digit(d)=2w+1,andwithprobability1−p,wehaved−digit(d)∈2{0,22w+2}.Inthe
firstcase,thenextnon-zerooutputdigitwillfollowafterexactlywintermediatezeros;in
thesecondcase,thenextnon-zerooutputdigitwillfollowafterw+2intermediatezeroson
average.m+1Thusthetotalaverageforthenumberofintermediatezerosisp∙w+(1−p)∙(w+2)=
w+2w+1,whichyieldstheaboveexpressionforthedensity.)Comparingthiswiththe
1/(w+2)densityforwidth-(w+1)NAFs,weseethattheeffectivewindowsizehasbeen
increasedby(m+1)/2w,whichiswhywespeakof“fractionalwindows”.
Asinsection6.2.1,lengthexpansioncanbeavoidedinmanycasesbymodifyingthe
representation.Themodifiedsignedfractionalwindowrepresentationisobtainedasfollows:
ifthew+2mostsignificantdigitsareoftheform
zerosw100...0b,
substitutethen010...0β
zeros1−wwhereβ=2w−b;ifthew+3mostsignificantdigitsareoftheform
100...0b
zeros1+w

66

tEfficientiationonenExp

Table6.1:Left-to-rightexponentiationwithwindowNAFsorsignedfractionalwindows,
=160w=2w=3w=4
wNAFs.fract.wNAFs.fract.s.fract.s.fract.wNAF
m=1m=1m=3m=5
stage:precomputationtableentries2345678
squarings1111111
multiplications1234567
stage:aluationevsquarings≤160≤160≤160≤160≤160≤160≤160
multiplications≈40.0≈35.6≈32.0≈30.5≈29.1≈27.8≈26.7

withb>2w,thensubstitute
zerosw010...0β
whereβ=2w+1−b;andifthew+3mostsignificantdigitsareoftheform
1w00+01..zeros.0b
withb<2w,thensubstitute
zeros1−w0030...0β
whereβ=2w−b.
Precomputationforleft-to-rightexponentiationcanbedoneinonesquaringand2w−1+
(mation−1)can/2bemimplemenultiplicationstedin(see2w−1section+(m−6.1.1),1)/2andthesquaringsresultand2stagew+form−righ1mt-to-leftultiplicationsexponen(seeti-
6.1.2).sectionsignedTable6.1fractionalshowswindoexpwectedmethopdinerformancecomparisonfiguresforwiththeleft-to-righusualtexpwindoonenwNAFtiationmethousingdthefor
ev160-bitaluationscalars;stageamtypicalultiplicationsapplicationforis-bitellipticscalarscurviseapprocryptographximatelyy.(Theexpectednumberof
w+m2w+1+2
forthesignedfractionalwindowmethod,and
2+wacforhievtheesanwindoevwaluationNAFstagemethospd.)eed-upTheofsignedabout2.3fractional%comparedwindowwithmethothedwindowithww=NAF2,mmetho=d1
withw=2,assumingthatsquaringstakeasmuchtimeasgeneralmultiplications.Infact,
squaringscanbefaster,whichwillincreasetherelativespeed-up(thisisusuallythecase
whenprojectivecoordinatesareusedforrepresentingpointsonanellipticcurve).
theTrighable6.2t-to-leftisforstagerighnotedt-to-leftinexpsectiononen6.1.2.tiation;(Asitonetakesmintoultiplicationaccountcanthebesavedoptimizationsforeactoh

wsWindoractionalF6.3

67

Table6.2:Right-to-leftexponentiationwithwindowNAFsorsignedfractionalwindows,
=160w=2w=3w=4
wNAFs.fract.wNAFs.fract.s.fract.s.fract.wNAF
m=1m=1m=3m=5
stage:t-to-leftrighsquarings≤160≤160≤160≤160≤160≤160≤160
multiplications≈39.0≈33.6≈29.0≈26.5≈24.1≈21.8≈19.7
stage:resultinputvariables2345678
squarings1234567
multiplications2468101214

additionalaccumulator,usuallyintheright-to-leftstage,theexpectednumberofright-to-left
stagemultiplicationsfor-bitscalarsisapproximately
w+mw+1+2+1−2w−1−m2−1
2forthesignedfractionalwindowmethod,and
w+2+1−2w−1
forthewindowNAFmethod.)Thetableshowsthatatthisexponentbitlength,forw=3
fractionalwindowsbringhardlyanyadvantageforright-to-leftexponentiationduetothe
relativelyhighcomputationalcostoftheresultstage.For=160,thefractionalwindow
methomethoddwithwithww==2,2,m=assuming1achievthatesa1.squarings2%totaltakespasmeed-upuchtimecomparedasgeneralwithmthewindoultiplications.wNAF

6.3.2UnsignedFractionalWindows
Theunsignedfractionalwindowrepresentationusesthedigitset
B={1,3,...,2w+m}
andcanbeobtainedbyavariantofthetechniquefromsection6.3.1.Here,letthemapping
digit:{0,1,...,2w+1}→B∪{0}
bedefinedasfollows:
•Ifxiseven,thendigit(x)=0;
•otherwiseif0<x≤2w+m,thendigit(x)=x;
•otherwiseletdigit(x)=x−2w.
Ifxisodd,thenx−digit(x)∈{0,2w}.Thefollowingalgorithmencodeseintounsigned
tation:represenwwindofractional

68

onenExptEfficientiation

Table6.3:Left-to-rightexponentiationwithslidingwindowsorunsignedfractionalwindows,
=1023w=2w=3w=4
slid.w.u.fract.slid.w.u.fract.u.fract.u.fract.slid.w.
m=1m=1m=3m=5
stage:precomputationtableentries2345678
squarings1111111
multiplications1234567
stage:aluationevsquarings≤1023≤1023≤1023≤1023≤1023≤1023≤1023
multiplications≈341.0≈292.3≈255.8≈240.7≈227.3≈215.4≈204.6

d←LSBww+1+1(e)
c←e/2
0←ibwhile←ddigit=0(d)∨c=0do
bdi←←db;−ib←i+1
d←LSB(c)∙2w+d/2
c←c/2
returnbi−1,...,b0
Similarlytothesignedcase,itcanbeseenthattheaveragedensityoftheunsignedfractional
istationrepresenwwindo1w+m2w+1+1
fore→∞.Theprecomputationorresultstageisasbefore.
Table6.3showsexpectedperformancefiguresforleft-to-rightexponentiationusingthe
forunsigned1024-bitfractionalscalars;awindotypicalwmethodapplicationiniscomparisonexponenwithtiationtheinusualthemslidingultiplicativwindoewsemigroupmethod
(Z/nZ)foranintegern.(Theexpectednumberofevaluationstagemultiplicationsfor(+1)-
bitscalarsisapproximately
w+m2w+1+1
fortheunsignedfractionalwindowmethod,and
1+wfortheslidingwindowmethod.)Ifsquaringstakeasmuchtimeasgeneralmultiplications,
thetheslidingunsignedwindowfractionalmethodwindowithwwmetho=d2.withw=2,m=1isapproximately3.7%fasterthan
Tmizationsableto6.4theshowsrighthet-to-leftfiguresstageforrighnotedint-to-leftsectionexponen6.1.2.(Astiation,onemtakinginultiplicationtoaccouncantbtheesavopti-ed

dingsEncoCompact6.4

69

Table6.4:Right-to-leftexponentiationwithslidingwindowsorunsignedfractionalwindows,
=1023w=2w=3w=4
slid.w.u.fract.slid.w.u.fract.u.fract.u.fract.slid.w.
m=1m=1m=3m=5
stage:t-to-leftrighsquarings≤1023≤1023≤1023≤1023≤1023≤1023≤1023
multiplications≈340.0≈290.3≈252.8≈236.7≈222.3≈209.4≈197.6
stage:resultinputvariables2345678
squarings1234567
multiplications2468101214

foreachadditionalaccumulator,usuallyintheright-to-leftstage,theexpectednumberof
right-to-leftstagemultiplicationsfor(+1)-bitscalarsisapproximately
w−1m−1
w+mw+1+1+1−2−2
2fortheunsignedfractionalwindowmethod,and
+1−2w−1
w1+

fortheslidingwindowmethod.)

dingsEncoCompact6.4WhenstoringawindowNAForfractionalwindowrepresentationwhereasingledigitmay
takew+1bitsofmemory(asitisthecaseforwidth-(w+1)NAFsifwetakeintoaccount
thatthedigitmaybezero,andforsignedfractionalwindowrepresentations),thenitisnot
necessarytostoredigitsseparatelyinw+1bitseach.Ifmemoryisscarce,itispossible
toexploitthepropertiesoftherepresentationtoobtainamorecompactencodingintobit
strings(cf.[45],wherethistechniqueisintroducedforwidth-2NAFs).
Wecanencodeazerodigitasasinglezerobit,andanon-zerodigitasaonebitfollowedby
arepresentationoftherespectivedigit,whichtogethertakesw+1bitsinthecaseofwindow
NAFsandw+2bitsinthecaseofsignedfractionalwindowrepresentations.Aftereach
non-zerodigit,therewillbewzerodigits(unlessconversionintoamodifiedwindowNAFhas
takenplace),andthesecanbeomittedfromtheencoding.Thus,comparedwiththeusual
binaryrepresentationofthenumber,inthecaseofwindowNAFsweonlyhavegrowthbya
smallconstant;inthecaseofsignedfractionalwindowrepresentations(andsimilarlyinthe
caseofunsignedfractionalwindowrepresentations),wealsohavegrowthbyanadditionalbit
foreachnon-zerodigitoftherepresentation.
Thisbitstringencodingcaneasilybeadaptedtothecasethatthebitstringwillberead
inthereverseofthedirectioninwhichitwaswritten(forexample,non-zerodigitsshouldbe
encodedasarepresentationoftherespectivedigitfollowedbyaonebitratherthantheother
around).yaw

70

tEfficien

Exp

tiationonen

7Chapter

tiationonenMulti-ExptEfficien

Inthischapter,wecomparedifferentapproachesforcomputingpowerproducts
ei1≤i≤kgi
incommutativesemigroupswithneutralelementwhereeacheisauniformlychosenrandom
integerinaninterval[0,2Li−1].LetLbethebit-lengthofithelongestoftheei(i.e.,ei∈
[0,trivial2L−1]approacforhalltoip,anderformmthereulti-expisanionensuchtiationthatbyei≥computing2L−1).theItpoiswwersellgeiknownseparatelythatandthe
ithenmultiplyingthemis,ingeneral,unnecessarilyinefficientcomparedwithspecificmethods
fornotationmulti-expforthisponentiation.owerproToductillustratewillbehowemplotheseyedmetho(comparedswork,withthethefollonotationwingforalternativmatrixe
products):e1
g1,...,gk•...
ekinRepthiseatedchaptersinglebexpecauseonenmtiationsulti-expwithonentiationprecomputationtechniquesforcanabfixedeusedbaseforwillthisalsotask.beconsidered
Likeleft-to-rightmethodsforsingleexponentiations(seesection6.1.1),themulti-expo-
nentiationmethodsthatwewilllookatworkintwostages:first,intheprecomputation
stage,anauxiliarytableofsemigroupelementsiscomputedfromtheelementsgi;then,in
theevaluationstage(orleft-to-rightstage),thefinalresultiscomputedusingtheseauxiliary
alues.vAnoften-usedapproachformulti-exponentiationcombinesallinputelementsgiwith
eacexphonenothertsinsimtheultaneouslyprecomputation.Wereferstageto([35],thesem[83],ulti-exp[91]);onenthenthetiationevmethoaluationdsasstagelosimultaneoksatousall
simexpultaneousonentiation.2w-arySectionmetho7.1d[83]describandestthewovsimariantsultaneousofsimslidingultaneouswindowexponenmethodtiation:ofYen,Straus’sLaih,
andLenstra[91].(Themethoddescribedin[35],whichisknownas“Shamir’strick”,appears
asaspecialcaseofbothofthese.)Forthesemethods,weassumethatLiisthesameforalli.
thegSectionseparately7.2preseninthetsanprecomputationalternativestageapproach,andinterlewhereavethedevexpaluationonentiation,stagewhicuseshantreatsin-
iiterleasimvingultaneouslyofthe.Thisgeneratorsapproacandhcanexpbonenetsusedforwiththevthevariousariousiratherencodingthantechandlinghniquesmthatultiplewe

71

72

tiationonenMulti-ExptEfficien

haveexaminedinchapter6.Specifically,thebasicinterleavedexponentiationmethodisthe
combinationofinterleavedexponentiationwiththeleft-to-rightslidingwindowtechnique,
andthewindow-NAFbasedinterleavedexponentiationmethodisthecombinationofinter-
leavedexponentiationwiththewindowNAFtechnique.Theformermethodcanbeusedfor
arbitrarycommutativesemigroupswithneutralelement,thelattermethodisapplicablefor
groupswhereinvertingelementsiseasy.
Insection7.3,wecomparetheefficiencyofsimultaneousexponentiationmethodsand
interleavedexponentiationmethods.Ourcomparisonshowsthatingeneralsemigroups,
sometimessimultaneousexponentiationandsometimesinterleavedexponentiationismore
efficient.Ingroupswhereinvertingelementsiseasy(e.g.ellipticcurves),window-NAFbased
interleavedexponentiationusuallywinsoversimultaneousexponentiation.
Section7.4discussesvariantsthatcanbeadvantageouswhenthebasesgiarefixedfor
manymulti-exponentiations.Insuchcases,precomputationneednotberepeated,soit
canpayouttoinvestmoreworkinprecomputationtoobtainspeed-ups.Notethatsingle
exponentiationisaspecialcaseofmulti-exponentiation(k=1),andthatthesevariantscan
beveryusefulforthiscase.OneofthetechniquespresentedthereiswindowNAFsplitting,
whichcanbeusedforefficientexponentiationormulti-exponentiationwithprecomputation
ingroupswhereinversioniseasy;itprovidesaconvenientalternativetothepatentedLim-Lee
d.metho

7.1SimultaneousExponentiation
Welookattwomulti-exponentiationmethodsusingsimultaneousexponentiation(asopposed
tointerleavedexponentiation,whichwillbeintroducedinsection7.2):Straus’s2w-arymethod
(section7.1.1)andtheslidingwindowmethodofYen,Laih,andLenstra(section7.1.2).
Asnotedintheintroductiontothischapter,allalgorithmsthatweconsiderarerelatedand
workintwostages:first,theprecomputationstagepreparesanauxiliarytableofsemigroup
elements;then,theevaluationstage(left-to-rightstage)computesthefinalresultusingthis
table.Forcomparingdifferentmethods,weexaminethetwostagesseparately.
Parameterwisalwaysapositiveinteger,thewindowsize;largerwindowsizesmakethe
precomputationstagelessefficient,butspeeduptheevaluationstage.Itisnotpossibleto
giveageneralruleforselectinganoptimalw(cf.section7.3).
mRelevultiplicationsantfeaturesrequiredoftheforcomputingprecomputationthestageauxiliaryaretable,thenandumbertheofnumbersquaringsoftableandengeneraltries.
Theprecomputedtableswillalwayscontainthevaluesg1,...,gk,allofwhicharetrivially
available.Itwillbevisiblethatcomputingeachadditionaltableentryrequiresonemultipli-
cationor,forsomeofthetableentriesinthesimultaneous2w-arymethod,onesquaring.In
additiontothis,ksquaringsareneededbythesimultaneousslidingwindowmethodifw>1.
Theevaluationstagerequiresbothsquaringsandmultiplications.Foreachmulti-expo-
nentiationmethod,welookatthenumberofsquaringsandtheexpectednumberofgeneral
multiplicationsforgivenk,L,andw.Inthissection,weassumethatthemaximumbit-length
Liisthesameforalli.
Thewindowsizewisassumedtobesmallincomparisonwiththemaximumbit-lengthL
(otherwisetheprecomputationstagewouldbecomeunreasonablyexpensive).
Itshouldbenotedthataslightoptimizationfortheprecomputationstageispossibleinall
methodsbyfirstlookingwhichtableentriesareactuallyneeded(eitherduringtheevaluation

7.1SimultaneousExponentiation

73

depstage,endoronbecausethem)andotherlimitingprecomputedprecomputationtableentriestothatthese.areAsthisneededinoptimizationtheevaluationwillusuallystage
onlyForhavetheanumsmallbereffectofinsquaringspractice,inwtheeevneglectaluationitinstage,ourwecomparisons.assumethatthefollowingopti-
mizationsquaringsiscanused:easilyasbeainitiallyvoidedvunariabletilaAisdifferen1Gtv(thealuehasneutralbeenelementassignedofGto)inA.allalgorithms,
inFtheormfolloulaswingforaretheexpactuallyectednumasymptoticsberofmforlargeultiplicationsL/wratherduringthantheevprecisealuationvaluesstage(wegivdoen
expnotonentakets).intoAsinaccountpracticethewspwillecialbemprobabilituchysmallerdistributionsthanL,theencounerrorteredcanbatebothneglectedendsforofourthe
oses.purpplicationJustasofAbsquaringsyatablecanbenetrycaneliminatedbeinreplacedtheevbyanaluationassignmenstaget.whileThisAisminor1G,theoptimizationfirstmulti-is
cnothapterusedin(andourdoesfiguresnotbaffectelow;noteasymptotics),thatitsoappliescomparisonssimilarlybtoetwalleenalgorithmsdifferentmethodiscusseddsinremainthis
alid.vasjust

7.1.1Simultaneous2w-AryExponentiationMethod
Straus’ssimultaneous2w-aryexponentiationmethod[83](seealso[53])looksatwbitsof
eachoftheexponentsforeachevaluationstagesemigroupmultiplication,i.e.kwbitsintotal.
Thespecialcasewherew=1isalsoknownas“Shamir’strick”sinceitwasdescribedin[35]
withareferencetoShamir(butnotethat[83]isamuchearlierpublication).

StagePrecomputationPrecompute1≤i≤kgiEiforallnon-zerok-tuples(E1,...,Ek)∈{0,...,2w−1}k.
Numberoftableentries:2kw−1.Ofthese,karetriviallyavailable;2k(w−1)−1canbe
computedbysquaringothertableentries(alltheEiareeven);theremaining2kw−2k(w−1)−k
entriesrequireonegeneralmultiplicationeach.

StagealuationEvFinortegerthefolloconsistingwingofalgorithm,therememconcatenationberofthatbitsforjadownnon-negativtojofeein.tegere,e[j...j]denotesthe
1←Aforj=G(L−1)/w∙wdownto0stepwdo
forn=12towdo
A←AA←A∙igiei[j+w−1...j]{multiplyAbytableentry}
ife1[j+w−1...j],...,ek[j+w−1...j]=(0,...,0)then
AreturnNumberofsquarings:Lw−1∙w.
Expectednumberofmultiplications:L∙1−w2k1w.

74

tEfficientiationonenMulti-Exp

ExampleThesimultaneous2w-aryexponentiationmethodcanbeillustratedasfollowsinasmalltoy
exampleforthecasek=3withe1=10110102,e2=110012,e3=10010112andwindowsize
2:=w010110102
g1,...,gk•000110012
010010112
Eachboxcorrespondstooneevaluationstagemultiplication.

7.1.2SimultaneousSlidingWindowExponentiationMethod
ThesimultaneousslidingwindowexponentiationmethodofYen,Laih,andA.Lenstra[91]
isanimprovedvariantofthe2w-arymethoddescribedinsection7.1.1.Duetotheuseofa
slidingwindow,tableentriesarerequiredonly2forthosetuples(E1,...,Ek)whereatleast
oneoftheEiisodd.(Notethatwhilevaluesginolongerappearintheprecomputedtable,
theprecomputationstagenowneedsthemasintermediatevaluesunlessw=1.)Alsothe
expectednumberofmultiplicationsrequiredintheevaluationstageisreduced.Likethe2w-
arymethod,thismethodlooksatwbitsofeachoftheexponentsforeachevaluationstage
semigroupmultiplication(kwbitsintotal).Forw=1,thisagainis“Shamir’strick”.For
k=1,thisistheusualslidingwindowmethodforasingleexponentiation(seesection6.2).

StagePrecomputationPrecompute1≤i≤kgiEiforallk-tuples(E1,...,Ek)∈{0,...,2w−1}kwhereatleastoneof
theEiisodd.
Numberoftableentries:2kw−2k(w−1).
Numberofsquarings:kifw>1;noneotherwise.
Numberofgeneralmultiplications:2kw−2k(w−1)−k.

StagealuationEv1←Aj←LG−1
do0≥jwhileif∀i∈{1,...,k}:ei[j]=0then
A←A2;j←j−1
elsejnew←max(j−w,−1)
J←jnew+1
while∀i∈{1,...,k}:ei[J]=0do
1+J←J{nowj≥J>jnew}
fori=1tokdo
Ei←ei[j...J]
doJ≥jwhileA←A∙igiEi{multiplyAbytableentry}
A←A2;j←j−1

7.2InterleavedExponentiation

75

whilej>jnewdo
A←A2;j←j−1
AreturnNumberofsquarings:L−wuptoL−1.11
Expectednumberofmultiplications:L∙w+n≥12k1n=L∙w+2k1−1.
ExampleThesimultaneousslidingwindowexponentiationmethodcanbeillustratedasfollowsina
smalltoyexampleforthecasek=3withe1=10110102,e2=110012,e3=10010112and
windowsizew=2:10110102
g1,...,gk•00110012
10010112
Eachboldboxcorrespondstooneevaluationstagemultiplication.Thethinboxindicatesa
rangeofbitsthatisscannedbythealgorithmaspartofonewindow,andwheretheright-most
columnofbitsisfoundtocontainallzerossothatthecaseoccursthatJ>jnew+1.

7.2InterleavedExponentiation
LetaBj-representation
ej=bj,i∙2i
0≤i≤j
begivenforeachoftheexponentsinapowerproduct
ej1≤j≤kgj,
bywhereinterleeachavingBjistheadigitleft-to-righsetastinsectionalgorithms6.1.forThenthethemindividualulti-expexponenonentiationtiationscangejb.eFporeacerformedhj,
jprecomputedelementsgjbareneededasinsection6.1.1.
Letbethemaximumofthej.Wemayassumethat=1=...=k(padwithleading
zeroswherenecessary).WhentheBj-representationshavebeenobtainedbythesliding
windowtechnique(section6.2)ortheunsignedfractionalwindowtechnique(section6.3),we
canassume=L−1;whentheBj-representationshavebeenobtainedbythewindowNAF
technique(section6.2)orthesignedfractionalwindowtechnique(section6.3),wecanassume
.L=Ifdivisionispermissible,interleavedexponentiationtocompute1≤j≤kgjejcanbeper-
ws:folloasformed1←AGfori=2downto0do
A←Aforj=1tokdo
ifbj,i=0then
ifbj,i>0then

76

tiationonenMulti-ExptEfficien

A←A∙gjbj,i
elseA←A/g|jbj,i|
AreturnAsinsection6.1.1,initialsquaringscanbeomittedwhileAis1G,andthefirstmultiplication
ordivisioncanbereplacedbyanassignmentpossiblyfollowedbyinversion.Thealgorithm
variantwithoutdivisionisobvious.
Inthefollowing,welookattwospecificinterleavedexponentiationmethodsmoreclosely:
thebasicinterleavedexponentiationmethod(section7.2.1),whichusestheslidingwindow
techniqueandissuitableforarbitrarycommutativesemigroupswithneutralelement,andthe
window-NAFbasedinterleavedexponentiationmethod(section7.2.2),whichusesthewindow
NAFtechniqueandcanbeappliedforgroupswhereinvertingelementsiseasy.
Thecommentsintheintroductiontosection7.1applysimilarly,withtheexceptionthat
wenolongerassumealltheLitobeidentical.Insteadofasinglewindowsizew,inthis
sectionwehavekpossiblydifferentwindowsizeswi(1≤i≤k)usedfortherespectiveparts
ofthemulti-exponentiation;eachwiisasmallpositiveinteger.Againweassumethatinitial
squaringsareeliminatedwhileAis1G.
Notethatforthealgorithmsdescribedinthissection,theprecomputedtablehasdisjoint
partsfordifferentbasesgi.Ifmultiplemulti-exponentiationshavetobeperformedandsome
ofthebasesgiappearagain,thenthecorrespondingpartsofearlierprecomputedtablescan
reused.ebObservethatitiseasytoimplementinterleavedexponentiationforavariableparameterk.
Asthethespecialcasek=1ofthebasicandwindow-NAFbasedinterleavedexponentiation
methodsyieldstheusualslidingwindowsexponentiationmethodandwindow-NAFbased
exponentiationmethod,respectively,thismakesitunnecessarytoimplementtheseseparately.

7.2.1BasicInterleavedExponentiationMethod
Thebasicinterleavedexponentiationmethodisageneralizationoftheleft-to-rightsliding
windowmethodforasingleexponentiation(seesections6.1.1and6.2),towhichitcorre-
spondsinthecasek=1.Weshowhowitcanbeusedwithoutcomputingslidingwindow
representationsofallexponentsbeforehand.

StagePrecomputationFori=1,...,k,precomputegiEforalloddEsuchthat1≤E≤2wi−1.
Numberoftableentries:1≤i≤k2wi−1.
Numberofgeneralmultiplications:1≤i≤k2wi−1−k.
Numberofsquarings:#i∈{1,...,k}|wi>1.
StagealuationEv1←AGfori=1tokdo
windowhandlei←nil
forj=L2−1downto0do
A←A

7.2InterleavedExponentiation

fori=1tokdo
ifwindowhandlei=nilandei[j]=1then
J←j−wi+1
whileei[J]=0do
1+J←J{nowj≥J>j−wiandJ≥0}
windowhandlei←J
Ei←ei[j...J]
ifwindowhandlei=jthen
A←A∙giEi{multiplyAbytableentry}
windowhandlei←nil
Areturn

Numberofsquarings:L−max1≤i≤k(wi)uptoL−1.
Expectednumberofmultiplications:
111≤i≤kwi+n≥12n1≤i≤kwi+1
Li∙1=Li∙.

77

ExampleThebasicinterleavedexponentiationmethodcanbeillustratedasfollowsinasmalltoy
exampleforthecasek=3withe1=10110102,e2=110012,e3=10010112andparameters
w1=w2=w3=3:
10110102
g1,...,gk•00110012
10010112
Eachboldboxcorrespondstooneevaluationstagemultiplication.Eachthinboxindicatesa
rangeofbitsthatisscannedbythealgorithmaspartofonewindow.

7.2.2Window-NAFBasedInterleavedExponentiationMethod
Thewindow-NAFbasedinterleavedexponentiationcanbeusedingroupswhereelements
canbeinvertedveryefficientlysothatdivisionisnotsignificantlymoreexpensivethanmul-
tiplication:itappliesthewindowNAFtechniquedescribedinsection6.2forinterleaved
exponentiation.NotethatmodifiedwindowNAFscanbeemployed(seesection6.2.1).

StagePrecomputationFori=1,...,k,precomputegiEforalloddEsuchthat1≤E≤2wi−1.
Numberoftableentries:1≤i≤k2wi−1.
Numberofgeneralmultiplications:1≤i≤k2i−k.
Numberofsquarings:#i∈{1,...,k}|wi>w1−.1

78

aluationEvStage

tiationonenMulti-ExptEfficien

Seepage75fortheinterleavedexponentiationalgorithm.
Numberofsquarings:L−max1≤i≤k(wi)uptoL.
Expectednumberofmultiplications:1≤i≤kLi∙wi1+2.
Theslidingwindowencodingtechniqueusedbythebasicinterleavedexponentiation
avmethoeragedindensitysectiongoes7.2.1downhasto1an/(awvi+erage2)fordensityexactlyof1/the(wisame+1).Withprecomputation.windowThNAFs,ususingthe
windowNAFseffectivelyincreaseswindowsizesbyone.

7.3ComparisonofSimultaneousandInterleavedExponenti-
dsMethoation

Thereisnogeneralruleforselectingwindowsizesforthemulti-exponentiationalgorithmsthat
westrainhatsvelocanokedimpat.oseVlimitsariousonpfactorsossiblehavewindotobwesizes.considered:Second,firstevenofifall,aabsoluteparticularwindomemorywcon-size
appearstominimizethetotalamountofcomputationforamulti-exponentiation,sometimes
slightlysmallerwindowsmayimprovetheactualperformance;thisisbecauselargerwindow
sizesmeanlargerprecomputedtables,i.e.possiblyadditionalmemoryallocationoverhead
andlesseffectivememorycaching.Lastbutnotleast,implementationscanusedifferentrep-
reseninstance,tationsextraforeffortsemigroupmaybespelemenenttsduringduringthedifferentprecomputationstagesofthestageminulti-expordertoonenobtaintiation:repre-for
sentationsofprecomputedelementsthatspeedupmultiplicationwiththemintheevaluation
stage(e.g.affineratherthanprojectiverepresentationsofpointsonellipticcurves[27]).
atTheseconcreteeffects,cases:howweevcaner,docomparenotmeandifferenthattwaspeectscannotseparatelycompare(tablealgorithmssize,withoutprecomputationlooking
stageefficiency,evaluationstageefficiency)andlookifanalgorithmwinsonallcounts.
Forthefollowingcomparisons,weassumethatallmaximumexponentlengthsLiarethe
same(anassumptionthatwemadeinsection7.1onsimultaneousexponentiation,butnot
insection7.2oninterleavedexponentiation).Asbefore,letLbethelengthofthelargestof
theexponentsei.
Insection7.3.1,wecomparethesimultaneous2w-arymethodwiththebasicinterleaved
methodandshowthatthelatterisusuallymoreefficientfork=2ifsquaringsareabout
ascostlyasmultiplications.Insection7.3.2,wecomparethesimultaneousslidingwindow
methoefficiendtforwithk=the2windoandk=w-NAF3based(assuminginterleathatvedcomputingmethodandandshostoringwthatthethewindolatterwisNAFsmoreis
nottoocostly).Section7.3.3brieflydiscussesthealternativemulti-exponentiationmethod
from[34]andshowsthatisobviatedbyourinterleavedexponentiationmethods;section7.3.4
showsanexamplefortheuseoffractionalwindowswithinterleavedmulti-exponentiation.In
sectiondifferent7.3.5,methowedsloforokatexamplesomevaluesconcreteofkfiguresandLfortheassumingnumberthatofmwindowultiplicationssizechoicesrequiredarenotby
dictatedbyscarcememory.Section7.3.6givesconclusions.

7.3ComparisonofSimultaneousandInterleavedExponentiationMethods79

7.3.1ComparisonbetweentheSimultaneous2w-AryMethodandtheBasic
InterleavedMethod
Whilethesimultaneousslidingwindowmethodismoreefficientthanthesimultaneous2w-ary
method,thissectionfocusesonthelatter.Thereasonsisthatthe2w-arymethodisoftenused
inpractice(e.g.[18]),possiblybecauseitisperceivedtobesimplertoimplement.Thebasic
interleavedexponentiationmethodisquitesimple(inparticular,indexesintotheprecomputed
tableareeasytohandle),andaswewillsee,isoftenmoreefficientthanthesimultaneous
2w-aryexponentiationmethod.Sowhentheintentionistoavoidthesimultaneoussliding
windowmethod,thebasicinterleavedmethodappearspreferableformanyapplications.
Assumethat,givenkandL,acertainwturnsouttoprovideoptimalefficiencyfor
thesimultaneous2w-aryexponentiationmethod(section7.1.1)whenperformedinaspecific
environment.Thentheprecomputedtablehas2kw−1entries(includingthektrivialentries
g1,...,gk),2k(w−1)−1ofwhichcanbecomputedwithonesquaringeach,whileeachofthe
remaining2kw−2k(w−1)−knon-trivialentriesrequiresonegeneralmultiplication.
Forthebasicinterleavedexponentiationmethod(section7.2.1),wecanuseuniformwin-
dowsizesw1=...=wk=kw.Thentheprecomputedtablehask2kw−1entries,k2kw−1−kof
whichrequireonegeneralmultiplicationeach;alsokadditionalsquaringsareneeded(unless
1).=w=kThusincasek=2,thenumberoftableentriesgrowsfrom22w−1to22w,andinstead
of22w−3semigroupoperationsofwhich22(w−1)−1aresquarings,weneed22wsemigroup
operationsofwhichonly2aresquarings.Ifsquaringsareaboutasexpensiveasgeneral
multiplications,thenfork=2theoverallcostofprecomputationiscomparableforthesetwo
multi-exponentiationmethods.
ThenumberofsquaringsintheevaluationstageisalwaysnearlyLforbothmethods.
Theexpectednumberofgeneralmultiplicationsintheevaluationstageissmallerforthe
interleavedmethod(exceptifk=w=1,inwhichcasebothalgorithmsperformexactlythe
sameoperations):dividingthevalueforthebasicinterleavedexponentiationmethodbythe
valueforthesimultaneous2w-aryexponentiationmethodyields
kwkw2kw
kw+1∙1−2k1w=kw+1∙2kw−1,
andthisislessthan1forkw>1(theminimumis64/75atkw=4).
Notethatusingw1=...=wk=kwisnotnecessarilyanoptimalchoiceofwindow
sizesforthebasicinterleavedexponentiationmethod;usingsmallerorlargerwindowsmight
leadtobetterperformance.(Indeed,ifwelookjustatthenumberofoperationsandignore
memoryusage,thenthereisnoreasonwhywindowsizesshoulddependonk.)Whilethe
aboveproofonlycoversthecasek=2,thereareactuallymanwyothercaseswherethebasic
interleavedmethodismoreefficientthanthesimultaneous2-arymethod,evenifgeneral
multiplicationsaremuchmoreexpensivethansquaring;seetable7.1insection7.3.5.Also
notethattheprecomputationeffortgrowsexponentiallyinkforsimultaneousmethods,but
notforinterleavedmethods.

7.3.2ComparisonbetweentheSimultaneousSlidingWindowMethodand
theWindow-NAFBasedInterleavedMethod
mSimilarlyultaneoustoslidingsectionwindo7.3.1,wexpassumeonenthattiationamethocertaindw(sectionprovides7.1.2)optimalforgivenefficiencykandforL.Inthethesi-

80

tEfficientiationonenMulti-Exp

followinganalysis,werequirek>1.Theprecomputedtablehas2kw−2k(w−1)entries(includ-
ingktrivialones),2kw−2k(w−1)−kofwhichrequiresonegeneralmultiplicationtocompute.
Inadditiontothis,ksquaringsarerequiredforprecomputationunlessw=1.
Forthewindow-NAFbasedinterleavedexponentiationmethod(section7.2.2),wecanuse
windowsizesw1=...=wk=kw−1.Thisleadstoaprecomputedtablewithk2kw−2entries,
wherekofthesearetriviallyavailableandthek2kw−2−knon-trivialonesrequireonegeneral
multiplicationeach.Inadditiontothis,weneedksquaringsunlesskw=2.
Thedifferencebetweenthenumberoftablesentries(andbetweenthenumberofgeneral
multiplications)forthesetwomethodsis
(2kw−2k(w−1))−k2kw−2=2kw1−2−k−k.
4Thisispositivefork≤3andnegativefork≥4.Thus,withthewichosenlikethis,the
precomputationstageofthewindow-NAFbasedinterleavedexponentiationmethodismore
efficientifk=2ork=3(exceptforthecasek=3,w=1,wherethewindow-NAF
basedinterleavedexponentiationmethodsavesonegeneralmultiplication,butrequiresthree
squarings).additionalTheevaluationstagerequiresclosetoLsquaringsforbothmethods.Theexpectednumber
ofgeneralmultiplications1issmallerforthewindow-NAFbasedinterleavedmethod:L/(w+
1/k)insteadofL/(w+).
Thewindow-NAF2kbased−1interleavedmethodwiththischoiceofwindowsizeswilloften
providebetterperformancethanthesimultaneousslidingwindowmethodfork≥4aswell:
ifadditionalmemoryallocationisnotaproblem,thentheefficiencygainoftheevaluation
stageusuallycompensatesforthegrowthoftheprecomputedtable.
Similartothesituationintheprecedingsection,w1=...=wk=kw−1isnotnecessarily
anoptimalchoice,andsmallerorlargerwindowsizesmightbebetter(seesection7.3.5).

7.3.3ComparisonbetweentheDimitrov-Jullien-MillerMulti-Exponentia-
tionMethodandInterleavedExponentiation
Amulti-exponentiationmethodforcomputingg1e1g2e2thatrequiresaprecomputedtablecon-
tainingfourvalues(includingg1andg2)ifinvertingiseasy,oreightvaluesifinversionshave
tobedoneduringtheprecomputationstagetoavoidthemintheevaluationstage,wasde-
scribedbyDimitrov,Jullien,andMillerin[34].Thisalgorithmisrelatedtothesimultaneous
slidingwindowexponentiationmethodofYen,Laih,andLenstra[91](seesection7.1.2),but
usesasignedencodingofexponentsinordertoreducethesizeoftheprecomputedtable.
WhiletheYen-Laih-Lenstramethodwithawindowsizeof1requiresanexpectednumber
ofL∙0.75generalmultiplicationsduringtheevaluationstage,thenewmethodrequiresonly
aboutL∙0.534multiplicationsaccordingto[34](thenumberofsquaringsstaysaboutthe
same).Yen-Laih-Lenstrawithawindowsizeof2needsonlyL∙3/7≈L∙0.429multiplications
(table3of[34]erroneouslyassumesavalueofL∙0.625),buthasthedisadvantageofrequiring
moreprecomputedelements,whichmaybeaprobleminconstrainedenvironments.
Wedonotexaminethealgorithmof[34]indetail;notethatitisoutperformedbythe
window-NAFbasedinterleavedmethodofsection7.2.2withw1=w2=2ifinversionischeap
(precomputedtablewithfourelements,L∙0.5evaluationstagemultiplications)andbythe
basicinterleavedmethodofsection7.2.1withw1=w2=3otherwise(precomputedtable
witheightelements,L∙0.5evaluationstagemultiplications).

7.3ComparisonofSimultaneousandInterleavedExponentiationMethods

81

7.3.4Multi-ExponentiationwithFractionalWindows
Assumewehavetocomputeapowerproductg1e1g2e2inagroupwhereinversioniseasy,
andthatwehavestorageforfiveprecomputedelements.Forusinginterleavedexponenti-
ationasdescribedinsection7.2,wecanrepresente1asawidth-3NAFande2insigned
fractionalwindowrepresentation(section6.3.1)withw=2,m=1.Thismeansweuse
approximately4+4+1/2L=36Lmultiplicationsonaverage,comparedwith2Lmultipli-
precomputed1elements1g1,g13,g2,17g23,g25.TheevaluationstageneedsatmostL1squaringsand
cationsforin3terleav3edexponentiationwithwidth-3NAFsforbothexponents(precomputed
elementsg,g,g,g).
(Asimilar112scenario2isconsideredin[77],usingadifferentmulti-exponentiationalgorithm;
forgroupswhereinversioniseasy,thattechniqueusingthesameamountofstorageasneeded
inouraboveexamplerunsslightlysloweraccordingtotheheuristicalresultsin[77,table12].)

Examples7.3.5wAsenotedignorebefore,memoryendlessusagevandariationssquaringsarepandossibletheforissuedefiningofdifferentoptimizationelementgoals.represenInthistations;section,we
makecomparisonsbasedjustontheexpectednumberofgeneralmultiplicationsrequired
bythevariousmethods,precomputationandevaluationstagecombined.Windowsizesare
chosensuchthatthiscostmeasureisminimized.Notethatthenumberofsquaringsis
appromethod,ximatelyandthethewindosameforw-NAFthesimbasedinultaneousterleavedslidingmethowindod:wnomethomored,thanthekbasicinsquaringsterleavareed
stage.neededinThethesimultaneousprecomputation2w-arystage,methoanddcloserequiresto2Lk(w−1)squarings−1aresquaringsneededforintheevprecomputationaluation
andagainclosetoLevaluationstagesquarings;soignoringthecostofsquaringtendsto
favorthismethod.
forvTablearious7.1kandcomparesLvalues,thenusingumbertheoffollogeneralwingmestimates:ultiplicationsneededbythesefourmethods
1c1=2kw−2k(w−1)−k+L∙1−2kw
wforthesimultaneous2w-aryexponentiationmethod,
c2=2kw−2k(w−1)−k+L∙w+11
k1−2forthesimultaneousslidingwindowexponentiationmethod,
c3=k∙2w−1−1+L
1+wforthebasicinterleavedexponentiationmethod,and
c4=k∙2w−1−1+L
2+wforthewindow-NAFbasedinterleavedexponentiationmethod,whereinterleavedexponen-
methotiationdsusesinaaparticularuniformwindowconfigurationsizew1are=.prin..=tedwinkb=old:w.forTheengroupstrieswherefortheinvmostersionisefficieneasyt

82

tiationonenMulti-ExptEfficien

sothatthewindow-NAFbasedmethodcanbeused,itwinsinalloftheseexamples;for
generalsemigroups,sometimesthesimultaneousslidingwindowmethodandsometimesthe
basicinterleavedmethodrequirestheleastnumberofmultiplications.(Rememberthatfor
w=1thereisnodifferencebetweenthesimultaneous2w-arymethodandthesimultaneous
slidingwindowmethod;forw>1,theformerisalwayslessefficient.)

Conclusions7.3.6Inmanycases,thebasicinterleavedexponentiationmethodcomparesfavorablytothesimul-
taneous2w-arymethod,inparticularifk=2andsquaringsareaboutascostlyasgeneral
multiplications.Ingroupswhereinvertingelementsiseasysothatthewindow-NAFbased
interleavedexponentiationmethodisavailable,itsefficiencyissuperioreventothesliding
windowvariantofsimultaneousexponentiationbothintheprecomputationstageandthe
evaluationstageifk=2ork=3,anditisusuallymoreefficientforlargerkaswell.
Inallcases,interleavedexponentiationprovidesthefollowingadvantagesoversimultaneous
tiation:onenexp•Improvedefficiencyifthebit-lengthsoftheexponentseidiffersignificantly.
•Moreflexibilityinchoiceofthesizeoftheauxiliarytable(and,hence,thetimespent
onprecomputation),particularlyifkislarge.
•Betterhandlingofsituationswhereoneormoreofthegiarefixedwhileothersare
variablebetweenmultiplemulti-exponentiation:acorrespondingpartoftheprecompu-
tationhastobedoneonlyonce.(ThisisthecaseinDSA[66]andECDSA[4]signature
verificationifmultiplesignaturesareverifiedthatarebasedonthesameunderlying
parameters.)Thus,dependingoncircumstances,eitherthesimultaneousslidingwindowmethodoroneof
theinterleavedexponentiationmethodsmaybeadvantageous.

7.4ExponentiationandMulti-ExponentiationwithPrecom-
BasesFixedforputationWhenmanymulti-exponentiationsusethesamebasesg1,...,gk,itissufficienttoexecutethe
precomputationstagejustonce,andwecantrytomaketheevaluationstagemoreefficient
byinvestingmoreworkinprecomputation.(Thisalsoappliestothespecialcasek=1,i.e.to
repgeneraleatedmsingleultiplicationsexponenintiationstheevusealuationthesamestage,base.)butwWeecancannotreduceeasilythenreduceumbertheofnumbsquaringserof
bywindousingwNAFexponensplittingtsplitting(section(section7.4.3).7.4.1),WhichtheapproacLim-Leehisthe“commostb”methoefficiendtdep(sectionendson7.4.2),detailsor
ofrelativtheecostsituationofsuchsquaringsasexpversusonentgenerallengths,mthepultiplications,ermissibleandsizeofwhethertheinexpprecomputedensiveinvtable,ersiontheis
availablesothatwindowNAFmethodsareapplicable.
Letmbeanarbitrarypositiveinteger.AssumingthatefixediexponentlengthboundsLiare
knostagewn,wesquaringsshow(orhowotoevccasionallyaluatempowersquaringsproductsin1section≤i≤kgi7.4.3),withatusingmostam−precomputed1evaluationtable
independentofthespecificexponentsei.

7.4ExponentiationandMulti-ExponentiationwithPrecomputationforFixedBases83

Table7.1:Expectednumberofgeneralmultiplicationsforamulti-exponentiation1≤i≤kgiei
withexponentsuptoLbits(c1:simultaneous2w-arymethod,c2:simultaneousslidingwindow
method,c3:basicinterleavedmethod,c4:window-NAFbasedinterleavedmethod)
kL=160L=256L=512L=1024L=2048
c144.5(w=4)64.6(w=5)114.2(w=5)199.0(w=6)353.3(w=7)
c239.0(w=4)57.7(w=5)100.3(w=5)177.3(w=6)319.0(w=7)
1c339.0(w=4)57.7(w=5)100.3(w=5)177.3(w=6)319.0(w=7)
c433.7(w=4)49.7(w=4)88.1(w=5)159.0(w=6)287.0(w=6)
c185.0(w=2)130.0(w=2)214.0(w=3)382.0(w=3)700.0(w=4)
c278.6(w=2)119.7(w=2)199.6(w=3)353.2(w=3)660.4(w=3)
2c378.0(w=4)115.3(w=5)200.7(w=5)354.6(w=6)638.0(w=7)
c467.3(w=4)99.3(w=4)176.3(w=5)318.0(w=6)574.0(w=6)
c1131.8(w=2)179.0(w=2)305.0(w=2)557.0(w=2)1061.0(w=2)
c2127.7(w=2)172.5(w=2)291.9(w=2)530.9(w=2)1008.7(w=2)
3c3117.0(w=4)173.0(w=5)301.0(w=5)531.9(w=6)957.0(w=7)
c4101.0(w=4)149.0(w=4)264.4(w=5)477.0(w=6)861.0(w=6)
c1161.0(w=1)251.0(w=1)491.0(w=1)746.0(w=2)1256.0(w=2)
c2161.0(w=1)251.0(w=1)483.7(w=2)731.5(w=2)1227.0(w=2)
4c3156.0(w=4)230.7(w=5)401.3(w=5)709.1(w=6)1276.0(w=7)
c4134.7(w=4)198.7(w=4)352.6(w=5)636.0(w=6)1148.0(w=6)
c1181.0(w=1)274.0(w=1)522.0(w=1)1018.0(w=1)2010.0(w=1)
c2181.0(w=1)274.0(w=1)522.0(w=1)1018.0(w=1)1994.7(w=2)
5c3195.0(w=4)288.3(w=5)501.7(w=5)886.4(w=6)1595.0(w=7)
c4168.3(w=4)248.3(w=4)440.7(w=5)795.0(w=6)1435.0(w=6)
c1214.5(w=1)309.0(w=1)561.0(w=1)1065.0(w=1)2073.0(w=1)
c2214.5(w=1)309.0(w=1)561.0(w=1)1065.0(w=1)2073.0(w=1)
6c3234.0(w=4)346.0(w=5)602.0(w=5)1063.7(w=6)1914.0(w=7)
c4202.0(w=4)298.0(w=4)528.9(w=5)954.0(w=6)1722.0(w=6)
c1278.8(w=1)374.0(w=1)628.0(w=1)1136.0(w=1)2152.0(w=1)
c2278.8(w=1)374.0(w=1)628.0(w=1)1136.0(w=1)2152.0(w=1)
7c3273.0(w=4)403.7(w=5)702.3(w=5)1241.0(w=6)2233.0(w=7)
c4235.7(w=4)347.7(w=4)617.0(w=5)1113.0(w=6)2009.0(w=6)
c1406.4(w=1)502.0(w=1)757.0(w=1)1267.0(w=1)2287.0(w=1)
c2406.4(w=1)502.0(w=1)757.0(w=1)1267.0(w=1)2287.0(w=1)
8c3312.0(w=4)461.3(w=5)802.7(w=5)1418.3(w=6)2552.0(w=7)
c4269.3(w=4)397.3(w=4)705.1(w=5)1272.0(w=6)2296.0(w=6)
c1661.7(w=1)757.5(w=1)1013.0(w=1)1524.0(w=1)2546.0(w=1)
c2661.7(w=1)757.5(w=1)1013.0(w=1)1524.0(w=1)2546.0(w=1)
9c3351.0(w=4)519.0(w=5)903.0(w=5)1595.6(w=6)2871.0(w=7)
c4303.0(w=4)447.0(w=4)793.3(w=5)1431.0(w=6)2583.0(w=6)
c11172.8(w=1)1268.8(w=1)1524.5(w=1)2036.0(w=1)3059.0(w=1)
c21172.8(w=1)1268.8(w=1)1524.5(w=1)2036.0(w=1)3059.0(w=1)
10c3390.0(w=4)576.7(w=5)1003.3(w=5)1772.9(w=6)3190.0(w=7)
c4336.7(w=4)496.7(w=4)881.4(w=5)1590.0(w=6)2870.0(w=6)

84

tiationonenMulti-ExptEfficien

SplittingtonenExp7.4.1Exponentsplitting(cf.[17]and[31];theideagoesbackto[73])constructsanewpower
productrepresentationbyrewritingeachfactorasfollows:
giei=(gi2jm)ei[jm+m−1...jm]
0≤j<Li/m
Thisleadstopowerproductsconsistingof1≤i≤kLi/mfactors.Anymulti-exponentiation
methodcanbeusedforevaluatingthesepowerproducts.
Itisevidentthatforthemulti-exponentiationmethodsthatwehavelookedat,exponent
splittingdoesnothelpifkisalreadylargeandtherearemanylargeexponents:savingsome
evaluationstagesquaringswillnothavealargeoverallimpactinsuchcases.(Then,instead
ofTheusingevaluationprecomputedstagewilltablerequireentriesmoreforsquarings,additionalbutbases,fewerwindogeneralwmsizesshouldultiplicationsbethanincreased.with
splitting.)tonenexp

PrecomputationLim-Lee7.4.2ToapplytheLim-Lee“comb”method[51],foreveryiwechoosewisuchthatLi≤wimand
precomputeGi(S):=gij∈S2j
forallsubsetsS⊆{0,m,2m,...,(wi−1)m}.NotethattheneveryexponentuptoLibitsof
lengthcanbewrittenas
ei=bj,i∙2j
<mj≤0whereeachbj,iisanintegeroftheformj∈S2jwithSasabove.Thuswecanusethe
interleavedexponentiationalgorithmfromsection7.2(wherewehavenoneedfordivisions
bbj,ivecausealuesallfordigitseachareiterationnon-negativneednote)bwithestoredtheninumbadverofance,looptheycaniterationsbeextractedreducedtofromm.theTheei
byAtappingrefinementheirtofbitsthisin(alsocomfromb-shap[51])edispatterns;basedonhencethetheobservnicationknamethatofthethismethoprecomputedd.table
canbereducedinsizeinexchangeforadditionalevaluationstagemultiplications:partition
bewrittenas1≤n≤viSnwithSn=S∩Ti,n,andthenwehaveGi(S)=1≤n≤viGi(Sn).
{0,m,2m,...,(wi−1)m}intovisubsetsTi,1,...,Ti,vi;noweachoftheabovesetsScan
Thusprecomputeditsufficesdata,toGi(S)precomputecanbeGi(Sncomputed)forallinatnon-zeromostvi−1subsetsmSn⊆ultiplicationsTi,nforwhenallnit;isfromneededthis
stage.aluationevtheinWhileLim-Leeprecomputationreducesthenumberofsquarings,theexpectednumberof
generalmultiplicationsislargerthanforthebasicinterleavedexponenwtiationi−1methodwith
asimilarlysizedprecomputedtable.(Inthebasicinterleavedmethod,2precomputed
tableentriessufficetomakesurethateachevaluationstagemultiplicationcoverswiexponent
bits,andwecanskipmanyadditionalWzerobitsthankstotheslidingwindow.WithLim-Lee
exponenprecomputation,tbitswithweeachneedevataluationleast2stage−1multiplication,precomputedandtableweenlosetriesthetoadvbeanabletagetoofacoverslidingW
window.)Thusifkislarge,usingLim-Leeprecomputationisadisadvantage.

7.4ExponentiationandMulti-ExponentiationwithPrecomputationforFixedBases85

Noteprecomputationthatitis(aspinossiblesectiontouse7.2)forLim-Leeothers.precomputationThisdoesfornotsomehelpofforthembasesulti-expandonenstandardtiation
inthesemixedcases,butprecomputeddatacanthenprofitablybereusedforpureLim-Lee
cases.TheLim-Leemethodcanbeconsideredanapplicationofexponentsplittingusingspecific
mLim-Leeulti-expmethoonendtiationusesalgorithms“Shamir’stricsuitedk”,fori.e.simsmallexpultaneousonents:expforonenexample,tiationifwithk=a1,windothewsimplesize
of1.Furtheralgorithmicvariationsarepossible.

SplittingNAFwWindo7.4.3Forgroupswhereinversioniseasy,exponentsplittingasdescribedinsection7.4.1could
beusedwithwindow-NAFbasedinterleavedexponentiation:thatis,eachofthelength-
mexponentpartsisencodedasawindowNAFasdescribedinsection6.2,andthenan
interleavedexponentiationusingthesewindowsNAFsisperformedasdescribedinsection7.2.
Withwidth-(wi+1)NAFs,thiscomputationshouldtakeaboutmsquaringsandLi/(wi+2)
multiplicationsusing(Li+1)/m∙2wi−1precomputedelements.However,ifmisvery
small,theexpectednumberofmultiplicationswillbenoticeablyhigherbecausetheestimate
thatthedensityofwindowNAFsisapproximately1/(wi+2)becomesaccurateonlyifthe
encodednumberissufficientlylong.(WindowNAFsusuallywastepartofonewindow;the
moreindividualintegersmustbeencodedintowindowNAFs,themoreiswastedintotal.)
AnimprovedtechniquethatavoidsthisdrawbackiswindowNAFsplitting.Insteadof
splittingthebinaryrepresentationofanexponenteiintopartialexponentsoflengthmand
determiningwindowNAFsforthese,wefirstdeterminethewindowNAFofeiandthensplit
thisnewrepresentationintopartsoflengthm.Thecomputationcontinuesasabove,using
theinterleavedexponentiationalgorithmshowninsection7.2.Toavoidlengthexpansion
ifpossible,thistechniqueshouldbeusedwithmodifiedwindowNAFs(section6.2.1)The
leftmostpartcanbemadelargethantheothersifonemorepartwouldhavetobeadded
otherwise;e.g.forintegersupto160bitswithm=8:

b160b159∙∙∙b152b151∙∙∙b144∙∙∙b7∙∙∙b0
9digits8digits8digits
isMostrelativoftheelyraretime,(forthemoadditionaldifiedwindodigitwoftheNAFsofleftmostpositivparteinwillbtegersezerouptosincealengthlengthofLiexpansionbits
withwi=4,onlyaboutoneoutoffivecaseshasanon-zerodigitatmaximumindexLi).
WithwindowNAFsplitting,singleexponentiations(k=1)forL1-bitexponentscan
beperformedwin−m1−1squaringsandonaverageaboutL1/(w1+2)multiplications,using
ab(Lo1ve,+1)L1/m/m∙2∙12w1−1precomputedprecomputedelemenelements.Iftstheareleftmostsufficient,partandgetstheannumextraberofdigitassquaringsdescribgoedes
uptomforsomecases.
ThismethodcancompetewiththeLim-Leemethodevenwhenmuchspaceisavailablefor
precomputedelements(whereasexponentsplittingwithwindow-NAFbasedinterleavedex-
ponentiationisbetterthantheLim-Leealgorithmonlyforcomparativelysmallprecomputed
tables).Forexample,ifL1=160,thenwithm=8andw1=4(160precomputedelements
ifwithweallowindowwanNAFextrasplittingdigitinneedstheableftmostout7.2windosquaringswNAFand26part),.7mourexpultiplications.onentiationThemethorefinedd

86

tiationonenMulti-ExptEfficien

versionoftheLim-Leemethod(withv1=2and#T(1,1)=#(T1,2)=w1/2)canperform
such160-bitexponentiationsin13squaringsandabout26.6multiplicationsusing126pre-
computedelements(m=14,w1=12),orin11squaringsandabout22.8multiplications
using254precomputedelements(m=12,w1=14).
ItispossibletousewindowNAFsplittingwithaflexiblewindowsize:whilegenerating
digitsusingthealgorithmdescribedinsection6.2,parameterwicanbechanged.Thisshould
bedigitsdoneonlygeneratedatsothebfariseginningamofultipleaofnewm).partFofortheexample,windoifwinNAFthek(i.e.,=1,whenL1=then160umbersettingof
weareusingm=8andallowinganextradigitintheleftmostpart,the(modified)window
NAFwillbesplitinto20parts;wecanstartwith4w1=35forthefirst12ofthese,thenswitch
ptow1erform=4expforonenthetiationsremainingin8.aboutThen7.2weneedsquarings12∙2and+8∙122∙8=+8256∙8≈24.precomputed4multiplications,elementsandwhiccanh
isusually(dependingontherelativeperformanceof5+2squarings4+2andgeneralmultiplications)
betterthantheperformanceoftheLim-Leemethodwith254precomputedelements.

8Chapter

EllipticCurvePointMultiplication
againstResistancewithSide-ChannelksttacA

Aphy,typeofcryptographpublic-kyeyusingthecryptographgroupyofthatisrationalgainingpoinmtsuconhpanopularitellipticyiscurveleolipticveracurvefinitecryptofieldgrFqa-.
Fordetailsonthemathematicsandonimplementationaspects,seee.g.[12]and[41].An
ellipticcurveisspecifiedbyacurveequationEovervariablesX,Y.Therelevantgroup
E(Fq)consists(whenusingtheaffinerepresentationofpoints)ofthosepairs(X,Y)offield
elemeninfinity.tsSevthateralfulfillstylessaidofprojeequation,ctiverpluseprtheesentationsneutralareelemenoftentO,usedwhicforhbisettercalledtheefficiencypoint(ap-at
propriaterepresentationscansignificantlycutdownthenumberoffieldinversions,andthese
w).sloratherareoftenplicativTheely,groupandoptheerationpresenistccommhapterutativfolloe.wsItthisisconusuallyvention.writtenThefolloadditivwingelyoprathererationsthanmarise:ulti-
•Pointaddition,i.e.computingP+QgivenapairofpointsP,Q.
•Pointdoubling,i.e.computing2PgivenapointP.
•Pointinversion,i.e.computing−PgivenapointP.
Typically,pointadditionalgorithmshavetodetectthecaseswhereoneofthepointsP,Qis
orthepwhereointPat=Qinfinit(soyorthatwherethePpoin=t−Qaddition(sothatisathepoinsumtofPdoubling)andQandisthetreatpointhemtatspinfiniteciallyy).
ThealgorithmfortheremainingcaseofpointadditionwhereP,Q=OandP=±Qisin
generalnotsuitableforpointdoubling,andthuspointadditionandpointdoublingcanbe
considereddistinctoperationsaslongasthosespecialcasesareavoided.
thePcaseointofinvaersionfieldisofaovdderycquickharacteristic,operationand(itbycanabfieldeimplemenadditiontedinbytheacasefieldofinvaersionfieldinof
characteristictwo),socomputingP−QisessentiallythesameworkascomputingP+Q.
Asweswitchfrommultiplicativetoadditivenotation,exponentiationbecomesmultipli-
cationofapointPbyascalare,orpointmultiplicationforshort.Themethodsdescribedin
theprecedingchapterscanbeusedtocomputeeP.

87

88EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

Ellipticcurvesusedforcryptographyareusuallyrequiredtohavealargeprime-order
subgroup.Wedenoteitsorderbypandassumethatonlyoneorder-psubgroupexists.In
thissetting,cryptographicprotocolstypicallyemployonlypointsoforderp.Theinteger
h=#E(Fq)/p,thecofactor,istypicallyverysmall,e.g.h≤4asrequiredby[22].
Thepresentchapterfocusesonanadditionalaspectforpointmultiplication,namelyside-
channelattacks([48],[49])whereadversariestrytousepowerconsumptionmeasurements
orsimilarobservationstoderiveinformationonsecretscalarseinpointmultiplicationseP.
PointPisusuallynotsecret,andindeedmayoftenbechosenbytheadversary.Multipliere
mayeitherbeephemeralorserveasalong-timekey.
Onedistinguishesbetweendifferentialside-channelattacks,whichrequirecorrelatedmea-
surementsfrommultiplepointmultiplications,andsimpleside-channelattacks,whichdirectly
interpretdataobtainedduringasinglepointmultiplication.Sinceusuallyexecutionsofthe
pointadditionalgorithmcanbedistinguishedfromexecutionsofthepointdoublingalgo-
rithm,ellipticcurvecryptographyisparticularlyvulnerabletothiskindofattackwhenside-
channelinformationisavailabletoanadversaryunlesspointmultiplicationisimplemented
termeasures.counappropriatewithVariousside-channelattackcountermeasuresforellipticcurvepointmultiplicationhave
beenproposedintheliterature.Thecontributionsofthepresentchapteraretwodifferent
methodsthatuseauniformpatternofpointdoublingsandpointadditions(avoidingthe
specialcaseslistedabove)inordernottorevealinformationone.Bothmethodsarevery
general(insteadofrequiringspecificallychosenellipticcurvesassomeothermethods,they
workwithconventionalellipticcurvearithmeticimplementationsandcanbeusedwithstan-
dardcurvessuchastheonesrecommendedbyNISTandSECGin[67]and[23],whoseuseis
oftenencouragedinordertoeaseinteroperability)andprovidegoodefficiency(unlikeearlier
proposalsintheliterature,theyare2w-aryratherthanbinary).Thefirstmethodisaleft-to-
rightmethodbasedonspecialrepresentationsofscalars.Thesecondmethodisaright-to-left
methodemployingaspecialinitializationstage;incontrastwiththefirstmethod,itdoes
notuseaninherentlyfixedtable,thusreducingpotentialinformationleakageavailableto
adversaries,anditiseasilyparallelizableontwo-processorsystems,whereitprovidesmuch
erformance.pedvimproSection8.1presentssomepreviousside-channelattackcountermeasuresforellipticcurve
cryptography.Section8.2discussesassumptionsofthesecuritymodelunderlyingthecoun-
termeasuresinthepresentchapterandlooksintocertainimplementationdetails.Section8.3
describesthenew2w-aryleft-to-rightmethod,andsection8.4describesthenew2w-aryright-
to-leftmethod.Section8.5providesefficiencycomparisons.Section8.6showsanideafor
scalarrandomizationinside-channelattackcountermeasures.

8.1PreviousSide-ChannelAttackCountermeasures
Randomizationcanbeusedasacountermeasureagainstdifferentialside-channelattacks.In
particular,forellipticcurvecryptography,projectiverandomizationisasimpleandeffective
[28]:oltoif(X,Y,Z)
represents(inJacobianprojectivecoordinates)thepointwhoseaffinecoordinatesare
(X/Z2,Y/Z3),

8.1PreviousSide-ChannelAttackCountermeasures

89

thenanotherrepresentationofthesamepointthatcannotbepredictedbytheadversaryis
substitutingybobtained(r2X,r3Y,rZ)
witharandomlychosensecretnon-zerofieldelementr.Whenstartingfromanaffinerepre-
sentation(X,Y),thissimplifiesto(r2X,r3Y,r).Othercountermeasureshavebeenproposed
thatrandomizethecomputationwithoutdependingontherepresentationofgroupelements:
•ePcanbeexpressedase(P−Q)+eQwhereQisarandompoint.
•ePcanbeexpressedas(e+np)Por(e−n)P+nPwherenisarandominteger.
(Rememberthatpdenotesoftheorderofthesubgroupthatisused.Seesection8.6for
anewproposalforsuchscalarrandomization.)
However,whilethesecountermeasuresmayprovideprotectionagainstdifferentialside-channel
attacks,theyarenotlikelytoprovidesufficientprotectionifsimpleside-channelattacksare
possible.Notethatstraightforwardimplementationsofellipticcurvesystemsareparticularly
vulnerabletosimpleside-channelattacks:asaddinganddoublingrequiredifferentalgorithms,
thebitsofemaybeplainlyvisibleinapowerconsumptiontraceifasimplebinaryalgorithm
isusedforpointmultiplicationandtheadversarycantellapartpointdoublingsfromgeneral
pointadditions.Improvedpointmultiplicationalgorithmsusingotherscalarrepresentations
(seee.g.section6.2)willobscureetosomedegree,butmaystillrevealplentyofinformation.
Thisvulnerabilitycanbeavoidedbyimplementingpointmultiplicationinafixedsequence
ofpointoperationsthatdoesnotdependontheparticularscalar.Notethatitisreasonable
toassumethatpointadditionandpointsubtractionareuniformtotheadversaryaspoint
inversionisnearlyimmediate(dummyinversionscanbeinsertedtoobtainthesamesequence
ofoperationsforpointadditionsasforpointsubtractions).
Variouspointmultiplicationmethodshavebeenproposedthatuseanalternatingsequence
ofdoublingsandadditions.Thesimplestapproachistouseabinarypointmultiplication
methodwithdummyadditionsinsertedtoavoiddependenciesonscalarbits[28];howeveras
wewillseeinsection8.2.2,itmaybeeasyforadversariestodeterminewhichadditionsare
dummyoperations,soitisnotclearthatthismethodprovidessufficientsecurity.Forodd
scalars,avariantofbinarypointmultiplicationcanbeusedwherethescalarisrepresented
inbalancedbinaryrepresentation(digits−1and+1withoutanydigitsofvaluezeroother
thanleadingzeros)[86].AlsoMontgomery’sbinarypointmultiplicationmethod[65],which
maintainsaninvariantQ1−Q0=PwhilecomputingePusingtwovariablesQ0,Q1,canbe
adaptedforimplementingpointmultiplicationwithafixedsequenceofpointoperations([87],
[69],[10],[43],[36]).Withthisapproach,specifictechniquescanbeusedtospeeduppoint
arithmetic:thedoublingandadditionstepscanbecombined;y-coordinatesofpointsmay
beomittedduringthecomputation([65],[10],[43],[36]);andonsuitablehardware,parallel
executioncanbeconvenientlyusedforimprovedefficiency([43],[36]).
Alloftheabovepointmultiplicationmethodsarebinary.Givensufficientmemory,effi-
ciencycanbeimprovedbyusingthe2w-arypointmultiplicationmethodsproposedinsections
8.3and8.4.Inthesemethods,theuniformoperationpatterninthemainloopofthepoint
multiplicationalgorithmhasoneadditionaftereachwdoublings.
Multipleside-channelattackcountermeasurescanbecombined;thenewpointmultiplica-
tionmethodsproposedinthecurrentchaptercanbeusedtogetherwithoneormultipleofthe
randomizationmethodsmentionedabove.Inparticular,randomizedprojectivecoordinates

90EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

shouldlong-timebekeyused,it(cf.should[70])beasnotedrandomizedintheasfollodescribwingedinmethodsection8.6.descriptions.Ifthescalareisa

8.2SecurityagainstSide-ChannelAttacks

toThebegoalusedtoforacthehievesecuritsecurityyanalysis.againstWhileside-cahannelcompleteattacmoksdelwofarranalltsside-csomehannelnotesontheinformationmodelis
hardlyeverattainable(and,inanycase,wouldbecloselytiedtoaspecificimplementation),
ittoispobtainossibletoreasonabledescribeassurancethewthatorkingsofinformationthepointleakmageultiplicationwillnotbealgorithmusefultoinanenoughadversarydetail.
Beforelookingattheactualpointmultiplicationmethodsinsections8.3and8.4,wediscuss
curvdesiredepointfeaturesopanderations,howtowhereachievcertainethem.specialThecasesmostshouldprominenbetavitemoided;tothisconsiderisarediscussedellipticin
section8.2.1.Atalowerlevel,wehavetheindividualfieldoperationsusedtoimplement
pointoperations.Section8.2.2showsthatpointmultiplicationimplementationsintendedto
besecureagainstside-channelattacksshoulduserandomizedprojectivecoordinates,andthat
left-to-rightpointmultiplicationmethodswithafixedtableshouldusecertainextendedpoint
representations.Thatsectionalsoexplainswhyinsertingdummypointadditionstoachieve
uniformbehaviorappearsquestionable.

8.2.1EllipticCurvePointOperations
Asdifferentalgorithmsareusuallyrequiredforpointdoublingandpointaddition,weassume
thatside-channeldatarevealsthesequenceinwhichtheseoperationstakeplace.Thusthe
pointmultiplicationalgorithmshouldusedoublingsandadditionsinauniformpatternin-
depthatmendenusttbofetheexpspectedecifictombeultiplier.visibleWethroughalsohasidevectohannelstakeinwhentoaccountheytoccurcertain(ifspconvecialentionalcases
implementationsofthepointoperationsareemployed):

•Pointdoubling2PrequiresconditionalstatementsforthecasethatPisthepointat
infinityorthatPisapointofordertwo.Ifthesecasesareavoided,then,expressedin
fieldoperations,pointdoublingrunsasafixedroutine.

•Asmentionedbefore,pointadditionP+Qrequiresconditionalstatementsforthecase
thatoneofthepointsisthepointatinfinity,orthatP=−Q,orthatP=Q.For
othercases,ittoocanbeimplementedasafixedroutine.

ple,NoteanthatadditionthesePsp+ecialQinvcasesokesdoaspalsoecialapplycasewhenwhenproPjectivcoincidesecowithordinatesQevareenitusedthe(forprojectivexam-e
representationsdiffer).Detailsofthesequencesoffieldoperationsusedforpointdoubling
theandcpoinhoicetofpadditionointdeprepresenendontationsthe(e.g.underlyingeitherfieldaffine(oddcocordinatesharacteristicoroneorcofmharacteristicultiplest2)ylesandof
protionisjectivthatecotheordinates,respectivcf.e[27]),algorithmsoalwimplemenaysbehatationsvesmatheyvarysameaswidelylong.Theastheessenabtialovespobserveciala-
arecasesoided.va

8.2SecurityagainstSide-ChannelAttacks

91

erationsOpField8.2.2Whileitisreasonabletoassumethatside-channelobservationsfor,say,afieldmultiplication
donotimmediatelyrevealthefactorsinvolved,itwouldnotbeprudenttoassumethatall
multiplicationslookthesametoanadversary.Thisiswhyprojectiverandomizationisuseful
([28],[70]):if,e.g.,Jacobianprojectivecoordinatesareused,arepresentation(X,Y,Z)ofthe
pointwithaffinecoordinates(X/Z2,Y/Z3)canbereplacedby(r2X,r3Y,rZ)foranyfield
elementr=0.Ifrissecretlychosenatrandom,then,providedthatX=0andY=0,
noneofthecoordinatesofthenewrepresentationwillbepredictabletotheadversary.Point
doublingorpointadditionusingprojectivecoordinatesresultsinapointrepresentedwith
aZ-coordinatethatistheproductoftheZ-coordinate(s)oftheinputpoint(s)andashort
polynomialinvolvingoneormoreothercoordinatesoftheinputpoints;thustheoutputpoint
isagaininarandomizedrepresentation.
However,forapointwithX=0orY=0,everyequivalentprojectiverepresentation
willhaveanaccordingzerocoordinate.AnadversarywhocanchoosetheinputpointPto
apointmultiplicationalgorithmmaybeabletoexploittheexistanceofsuchspecialpoints
byselectingPsuchthatintermediatepointsduringthepointmultiplicationwilllhaveazero
coordinateifaguessforpartofthescalareiscorrect[39].Assumingthatthezerocoordinate
becomesvisiblethroughsidechannels,thenifeisconstantformanypointmultiplications,
thiscanbeusedtodetermineallofe.Similarattackscanbepossiblebasedonintermediate
fieldelementsthatappearduringindividualpointoperations[3].Acountermeasureforcurves
wheresuchattacksarepossibleistorandomize,ifpointPmaybechosenbytheadversary,
thepointratherthanjustitsprojectiverepresentation,i.e.computeePas
e(P+Q)−eQ
forarandompointQ.ThepointsQandeQcanbestoredinmemoryconstantly(Qmust
bekeptsecret).Asthefullattacksrequireaconstante,theycanalsobecounteredbyscalar
8.6).section(seerandomizationWhenrandomizedprojectivecoordinatesareusedtopreventtheadversaryfromguessing
thespecificinputstofieldoperations(andthusfromdirectlyverifying,forexample,whichof
severalknownpointsarecurrentlybeingadded),theadversarymaystillbeabletorecognize
ifthesamefieldoperationwiththesameinputvaluesisperformedmultipletimes.Evenif
thesevaluesarenotknown,thismayleakessentialinformation,soitshouldbeavoided.We
nowlookwhatshouldbetakencareof.
Manyleft-to-rightalgorithmsforpointmultiplicationeP,includingtheonethatwillbe
presentedinsection8.3,canbeoutlinedasfollows(cf.section6.1.1):
[Precomputationstage.]First,independentlyofthespecificmultipliere,certainsmall
multiplesofParecomputedandstoredinatable.
[Evaluationstage.]Second,theproductePisevaluatedasfollows:avariableAisinitial-
izedtooneofthetablevalues;then,manytimes,Aeitherisdoubledoratablevalue
isaddedtoA,replacingthepreviousvalueofA.Finally,AcontainstheresulteP.
Unlessaprojectiverandomizationofthetablevaluethathasbeenusedisperformedwhenever
thetableisaccessed(whichwillavoidafixedtableatthepriceofreducedefficiency),theuse
ofafixedtablemayallowforstatisticalattacks.Forsuchalgorithmswithafixedtable,each
entryoftheprecomputedtableshouldcontainnotonlytherepresentationofthepoint,but

92EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

additionallyanyfieldelementsthatwouldhavetobecomputedeachtimethepointisadded
toA.IfJacobianprojectivecoordinatesareused,thismeansthat(X,Y,Z,Z2,Z3)shouldbe
stored(ChudnovskyJacobiancoordinates,see[18])ratherthanjust(X,Y,Z)(cf.theaddition
forformtheulasinprecomputed[12,Chaptertable,IV.2]theoradv[41]).ersaryIfmasucyhbeextendeabletodpguessointrepreasilywhicesentationshpoinaretnotadditionsused
involvethesametablevalue.
additionsThereareonlypifointmdummyultiplicationadditionsarealgorithmsinsertedthatintocantheacevhievealuationafixedstage.patternThatofis,doublingssometimesand
atablevalueisaddedtoA,buttheresultisthrownawayandAisleftunchanged.The
ignored:problemforwithJacobiandummyproadditionsjectiveiscothatordinates,theadveachersarypoinmatyopbeerationabletorequirestellthatsquaringtheirtheresultZis-
coordinateofA;ifAisnotchanged,thentwoconsecutivepointoperationsinvolvethevery
samesquaring.Thepointmultiplicationalgorithmspresentedinsections8.3and8.4achieve
uniformbehaviorwithoutresortingtodummyadditions.

8.32w-AryLeft-to-RightMethod
Left-to-rightpointmultiplicationalgorithmslookatthedigitsofsomerepresentationofthe
scalarstartingatthemostsignificantpositionandproceeddowntotheleastsignificantone
(seesection6.1.1).Asimplewaytoobtainauniformsequenceofdoublingsandadditions
(namely,oneadditionaftereachwdoublingsinthemainloopofthepointmultiplication
algorithm)inleft-to-rightpointmultiplicationistousea2w-aryscalarencodingandto
insertadummyadditionwheneverazerodigitisencountered.However,aswehaveseen
insection8.2.2,usingdummyadditionstoachieveuniformbehaviorisquestionablebecause
itmaybevisibletotheadversarywhichadditionsaredummyadditions.Herewewilllook
atamodified2w-aryleft-to-rightpointmultiplicationmethodthatdoesnotneeddummy
additionsforuniformbehavior.
Thismethodmayfailinsomecasesinthatanadditionstepmayturnouttobeapoint
doublingormayinvolvethepointatinfinity(whichbothrequiresspecialtreatmentandis
potentiallyclearlyvisiblethroughsidechannels).However,wewillshowthattheprobability
ofthishappeningisclosetozeroifmultipliersareappropriatelyselected:randomlychosene
safe.isSection8.3.1describeshowtoencodethemultipliereintospecialsigned-digitrepresenta-
tions.Section8.3.2discussesthemultiplicationalgorithmsimpliedbytheserepresentations.
Section8.3.3showsthat,unlesseisill-chosen,thispointmultiplicationalgorithmindeed
limitsinformationleakageasintended.

AlgorithmsdingReco8.3.1Letthepositiveintegerebegivenin2w-arydigitswherew≥2isasmallinteger;namely,
e=bi∙2wi
=0iwithbi∈{0,1,...,2w−1}.Wedemandthatbechosenminimal,i.e.b=0.Fori>,we
definethatbi=0.

8.32w-AryLeft-to-RightMethod

93

Thefirst(basic)recodingalgorithmconvertsthisintoarepresentation
e=bi∙2wi
=0ithathsucbi∈{−2w,1,2,...,2w−1}.
Thismeansthatwedisallowdigitvalue0andinsteadwintroducethenewvalue−2w.Intu-
itively,therecodingalgorithmreplaces0digitsby−2andincrementsthemoresignificant
neighbordigittoadjustthevalue.Aslightlymorecomplicatedvariantofthemultiplier
recodingalgorithmproducesdigits
bi∈−2w,±1,±2,...,±(2w−1−1),2w−1
instead.Notethatthesetofpossibledigitvaluesstillhas2welements.Aswewillseein
section8.3.2,thisalternativerepresentationleadstoimprovedefficiency.
Itiseasytoseethatforbothrecodingtechniques,bisnecessarilypositive(otherwisee
wouldbenegative)andthattherepresentationofeneedstogrowbyatmostonedigit,i.e.
=or=+1.
Weexpresstherecodingwalgorithmsrecursively,usingauxiliaryvaluesciandtisuchthat
0≤ci≤2and0≤ti≤2+1:let
0,=c0andfori=0,...,+1,let
ti=bi+ci
whereforthebasicrecodingalgorithmwehave
(1,−2w)ifti=0
(0,ti)if0<ti<2w
(ci+1,bi)=(2,−2w)ifti=2w
(1,1)ifti=2w+1
andforthevariantwehave
(1,−2w)ifti=0
(0,ti)if0<ti≤2w−1
(ci+1,bi)=(1,−2w+ti)if2w−1<ti<2w
(2,−2w)ifti=2ww
(1,1)ifti=2+1.
Notethatci+1∙2w+bi=tialwaysholds.
Ifb+1=−2w,then
+1e=bi∙2wi;
=0iinthiscase,weset=+1.Otherwise,wehave
e=bi∙2wi
=0i

94EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

andb=−2w,andweset=.
wAsObservaecounthatiftermeasureb=1(andagainst>side-c0),thenhannelb−1attac=ks−2on.therecodingalgorithmitself,assign-
mentscanbeimplementedbytablelookupsinsteadofusingconditionalstatements.
withtheStoringoriginaltheconvrepresenertedtation:represendigittationvofaluesecanrequiresbestoredalmostnomoduloadditional2w.Ifwmemoryisunderstocomparedod,
thisignorednewbecauserepresenbistationnevercan−b2ew).storedThisasinantegerisordinaryatmostintwtegerobits(leadinglonger0thandigitse;canthemaximsimplybume
pItossiblemaylengthbegrodesirablewthotoccursifensure=that+1theandencob=ded2.formhasapredeterminedmaximum
indexbinary.Flengthorourofpgroupointmorderpultiplication,thisiseasyapplication,todo:ififwisnecessarylarge,enoughadjustebycomparedaddingwithporthea
.pofultiplembitsIfcanaberandomusedmdirectlyultipliertoisrequiredgenerateandthearecouniformdedformofdistributione.Inisthisnotcase,essentotial,o,itthenshouldrandombe
ensuredthatb−1=−2wifb=1.

8.3.2PointMultiplicationAlgorithm
RememberthatwewanttocomputeePwherepointPshouldhaveorderp,pbeingalarge
primethatdividestheorderoftheellipticcurveE(Fq).Forourpointmultiplicationalgorithm
toworkasintended,ord(P)maybeanypositivemultipleofp.
IfpointPcanbechosenbytheadversary,wemustbeawarethatitmighthaveincorrect
order.Incasethat#E(Fq)=p,then(besidestestingthatPisindeedapointonthecurve)
wesanitjustychahecvk.etoLetvherifybethatthePiscofactornotoftheptheointellipticatinfinitcurvye,,Oi.e..theOtherwise,integerw#eEneed(Fq)an/p.additionalCurves
usedforcryptographyareusuallyselectedsuchthathisverysmall([22]requiresh≤4).
ThushPcanbecomputedquickly;ifitisnotO,thenweknowthatpdividesord(P).
IfPhasincorrectorder,computingePmustberejected.Otherwise,givenarepresentation
e=bi∙2wi
=0iofeasdeterminedbyoneoftherecodingalgorithmsfromsection8.3.1,ePcanbecom-
orputedbalgorithmythe8.2proinceduretheshocasewnofinthevalgorithmariant.F8.1orinboththecasecases,ofwhattheisbasicshorecownisdingahigh-levalgorithmel
descriptionofthealgorithm:asexplainedinsection8.2.2,implementationsshoulduseran-
domizedprojectivecoordinates,andvaluescomputedintheprecomputationstageshouldbe
storedinextendedpoinw−t1representation.Thealgorithmforthebasiccaserequires2w−1+w
poinextendedtdoublingsuseofandthe2easeof−1in+vpersionointinellipticadditions;curvtheegroups,algorithmforrequiresthev2w−arian2+t,1+whicwhpmakoinest
doublingsand2w−2−1+pointadditions.(Whencomparingtheefficiency,notethatfor
thevariantalargerchoiceofwmightbepreferable.)
TheobviouswaytoimplementA←2wAinthisprocedureisw-folditerationofthe
statementA←2A,butdependingontheellipticcurve,moreefficientspecificalgorithmsfor
w-foldpointdoublingmaybeavailable(see[42]).
tionDuringshouldbtheepproerformedceduretshowice.wninFirst,ifalgorithmthe8.1precomputedoralgorithmtableof8.2,maultiplesprojectivofPeisstoredrandomiza-in

8.32w-AryLeft-to-RightMethod

Algorithm8.1Computei=0bi∙2wiPwherebi∈{−2w,1,2,...,2w−1}
{Precomputationstage}
P←P1forn=2to2w−2step2do
Pn←2Pn/2
Pn+1←Pn+P
{nowPn=nP,Pn+1=(n+1)P}
P−2w←−2P2w−1
{nowP−2w=(−2w)P}

}stageEvaluation{P←Abforj=−1downto0do
wA2←AA←A+Pbj
Areturn

95

projectivecoordinates,therepresentationofPshouldberandomizedbeforethetableiscom-
puted(ifthetableofmultiplesofPisstoredinaffinecoordinatestospeeduptheevaluation
stagebyusingmixedadditionofaffineandprojectivepoints[27],thisfirstrandomization
obviouslyisnotnecessary;butusingsuchfixedandpredictabletableentriesmayhelpdiffer-
entialside-channelattacksandthuscannotberecommended).Second,atthebeginningofthe
evaluationstage,aftertheinitialvaluehasbeenassignedtoA,therepresentationofAshould
berandomized.Forbestassuranceagainststatisticalattacks,aprojectiverandomizationof
thetablevaluethathasjustbeenusedcanbeperformedwhenevertheevaluationstageac-
cessestheprecomputedtable.However,unlesseisconstantovermanypointmultiplications,
thisshouldnotbenecessary;seesection8.6forhowaconstantecanbeavoided.

8.3.3UniformityofthePointMultiplicationAlgorithm
Itisapparentthatalgorithms8.1and8.2usedoublingsandadditionsinaregularpattern.
Asdiscussedinsection8.2,toshowthattheprocedurehasuniformbehaviorandthusis
thatsuitabletheforfollowinglimitingspecialinformationcasesofleakpoinagetduringdoublingtheandpoincomputationtadditionofePcan,wbeeaalsovhaoided:vetoshow
O2••2Awhereord(A)=2

•A+OorO+B
A+A••A+(−A)
Wehaverequiredthatord(P)beapositivemultipleofp.Withoutlossofgenerality,here
wemayassumethatord(P)=p.(Otherwise,multiplyPbythecofactorh=#E(Fq)/p

96EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

Algorithm8.2Computei=0bi∙2wiPwherebi∈{−2w,±1,±2,...,±(2w−1−1),2w−1}
{Precomputationstage}
P←P1forn=2to2w−1−2step2do
Pn←2Pn/2
Pn+1←Pn+P
P2w−1←2P2w−2
P2w←2P2w−1

}stageEvaluation{ifb>0then
elseA←Pb
P−←Aforj=−|b1|downto0do
wA2←Aifbj>0then
A←A+Pbj
elseA←A−P|bj|
Areturn

toobtainapointoforderp.InthealgorithmperformedforP,theabovespecialcasescan
occuronlywhenoneofthemwouldoccurinthealgorithmperformedforhP;inparticular,
ord(A)=2wouldimplyhA=O,sopointsoforder2arenotanissueifwecanshowthatthe
pointatinfinitycanbeavoided.)Then,as2wcanbeexpectedtobemuchsmallerthanp,all
precomputedpointsPbj=bjPinalgorithms8.1and8.2willbeoforderp.Thus,initiallywe
haveA=O;andaslongasweavoidadditionsoftheformA+(−A),itwillremainlikethis.
Sowhatislefttobecheckediswhetherintheevaluationstageofalgorithms8.1and8.2we
canavoidthatA=bjPorA=−bjPbeforeanadditionorsubtractiontakesplace.
Withej=bi∙2w(i−j),
j=ithepointwadditionstepintheevaluationstageloopofalgorithm8.1or8.2performsthepoint
addition(2∙ej+1)P+bjP.Thuswearesafeif
2w∙ej+1≡±bj(modp).
Since|ej|≤2(1+−j)wand|bj|≤2w,formanyindicesjwehave|2w∙ej+1|+|bj|<p,meaning
thatreductionmodulopdoesnotmatteranditsufficestocheckwhether2w∙ej+1=±bj.
Thelargestindextoconsiderisj=−1;forthiscase,thequestioniswhetherwecan
besurethat2w∙e=±b−1.Indeedwecan,ase=bandifb=1,thenb−1=−2w(see
section8.3.1).Itfollowsthatej≥2(−j)w,whichshowsthattheincongruenceissatisfiedfor
indicesj<−1tooaslongaswedonothavetoconsiderreductionmodulop.
Forindicesjsosmallsuchthatthismodularreductionisrelevant,wearguethatifeis
sufficientlyrandom,thentheprobabilityofpickinganesuchthattheaboveincongruence

8.42w-AryRight-to-LeftMethod

97

isguessednotinsatisfiedamodestcannbeumberneglected:ofattempts,itiswhiccomparablehcanbtoethepresumedprobabilittobeythatpracticallyemodimppcanossiblebe
(otherwise,side-channelattacksshouldnotbeaconcernsinceecouldnotreallybeconsidered
sufficientlysecretinthefirstplace).

8.42w-AryRight-to-LeftMethod
Right-to-leftpointmultiplicationalgorithmslookatthedigitsofsomerepresentationofthe
scalarstartingattheleastsignificantpositionandproceeduptothemostsignificantone
(seesection6.1.2).Aregularsequenceofdoublingsandadditions(withoneadditionafter
eachwdoublingsinthemainloopofthepointmultiplicationalgorithm)canbeobtainedin
right-to-leftpointmultiplicationbyusinga2w-aryscalarencodingandtreating0likeany
otherdigitvalue.However,thisapproachisnotfullysufficientforobtaininguniformbehavior
becausethespecialcasesofpointaddition(seesection8.2.1)wouldrevealinformationonthe
scalars.The2w-aryright-to-leftpointmultiplicationmethodpresentedinthefollowingisbased
ontheobservationthataspecialrandomizedinitializationstagecanbeusedtoavoidthe
problematicspecialcases.Theright-to-leftmethodiseasilyparallelizableandcanprovide
muchimprovedperformanceontwo-processorsystems.
ThemethodforcomputingePisparameterizedbyanintegerw≥2andadigitsetB
consistingof2wintegersofsmallabsolutevaluesuchthateverypositivescalarecanbe
formtheintedrepresene=bi2wi
≤i≤0usingdigitsbi∈B;forexample
B={0,1,...,2w−1}
orB={−2w−1,...,2w−1−1}.
Arepresentationofeusingthelatterdigitsetcanbeeasilydeterminedontheflywhen
scanningthebinarydigitsofeinright-to-leftdirection.Ifeisatmostnbitslong(i.e.0<
e<2n),=n/wissufficient.
LetBdenotetheset{|b||b∈B}ofabsolutevaluesofdigits,whichhasatleast2w−1+1
andatmost2welements.Thepointmultiplicationmethoduses#(B)+1variablesforstoring
pointsontheellipticcurveinprojectiverepresentation:onevariableAbforeachb∈B,and
oneadditionalvariableQ.
Themethodworksinthreestages,whichwecallinitializationstage,right-to-leftstage,
andresultstage.Wewillfirstlookatahigh-levelviewofthesestagesbeforediscussingthe
details.LetAbInitdenotethevalueofAbattheendoftheinitializationstage,andletAbsum
denotethevalueofAbattheendoftheright-to-leftstage.
TheinitializationstagesetsupthevariablesAb(b∈B)inarandomizedwaysuchthat
AbInit=Oforeachb,but
bAbInit=O.
B∈b

98EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

Thentheright-to-leftstageperformscomputationsdependingonPandthedigitsbi,yielding
newvaluesAbsumofthevariablesAbsatisfying
Absum=AbInit+2wiP−2wiP
0bi≤i=≤bb0i≤=i−≤b
foreachb∈B.Finally,theresultstagecomputes
sum,bAb∈B\{0}b
whichyieldsthefinalresultePbecause
bAbsum=bAbInit+b2wiP−2wiP
Ob∈B\{0}b∈B\{0}b∈B\{0}0bi≤i=≤bb0i≤=i−≤b
=bi2wiP=eP.
≤i≤0Section8.4.1discussestheinitializationstage,section8.4.2theright-to-leftstage,and
section8.4.3theresultstage.Section8.4.4presentssomevariants.
StageInitialization8.4.1Theinitializationstagecanbeimplementedasfollows:
1.Foreachb∈B\{1},generatearandompointontheellipticcurveandstoreitin
.Aariablevb2.Computethepoint−b∈B\{0,1}bAbandstoreitinvariableA1.
3.Foreachb∈B,performaprojectiverandomizationofvariableAb.
TheresultingvaluesofthevariablesAbaredenotedbyAInit.
Iftheellipticcurveisfixed,precomputationcanbebusedtospeeduptheinitialization
stage:runsteps1and2justonce,e.g.duringpersonalizationofasmartcard,andstorethe
resultingintermediatevaluesAbforfutureuse.WedenotethesevaluesbyAbfix.Thenonly
step3(projectiverandomizationofthevaluesAfixtoobtainnewrepresentationsAInit)hasto
beperformedaneweachtimetheinitializationbstageiscalledfor.ThepointsAbfixbmustnot
berevealed;theyshouldbeprotectedlikesecretkeys.
Generatingarandompointonanellipticcurveisstraightforward.ForeachelementX
oftheunderlyingfield,therearezero,oneortwovaluesYsuchthat(X,Y)istheaffine
representationofapointontheellipticcurve.GivenarandomcandidatevalueX,itis
possibletocomputeanappropriateYifoneexists;theprobabilityforthisisapproximately
1/2byHasse’stheorem.IfthereisnoappropriateY,onecansimplystartagainwitha
.XnewComputinganappropriateYgivenXinvolvessolvingaquadraticequation,whichusually
(dependingontheunderlyingfield)iscomputationallyexpensive.Thismakesitworthwhile
touseprecomputationasexplainedabove.Itisalsopossibletoreusethevaluesthathave

8.42w-AryRight-to-LeftMethod

99

remainedinthevariablesAb,b=1,afterapreviouscomputation,andstartatstep2ofthe
stage.initializationTodetermine−b∈B\{0,1}bAbinstep2,itisnotnecessarytocomputeallthein-
dividualproductsbAb.Algorithm8.3canbeusedinsteadtosetupA1appropriatelyif
B={0,1,...,β},β≥2.(Notethatbothloopswillbeskippedinthecaseβ=2.)This
Algorithm8.3ComputeA1←−b∈{2,...,β}bAbintheinitializationstage
fori=β−1downto2do
Ai←Ai+Ai+1
Afor1i←=22A2toβ−1do
Ai←Ai−Ai+1
A1←A1+Ai+1
A1←−A1
algorithmtakesonepointdoublingand3β−6pointadditions.Whenithasfinished,the
variablesAbfor1<b<βwillcontainmodifiedvalues,whicharerepresentationsofthe
pointsoriginallystoredintherespectivevariables.Ifsufficientmemoryisavailable,afaster
forbalgorithm>1can(usebeusedadditionaltovcomputeariablesAQ1withoutinstead;ininthistermediatecase,moseedificationsectionof8.4.3theforvapariablesossibleAb
badditionalimprovementifpointdoublingsarefasterthanpointadditions).
TheprojectiverandomizationofthevariablesAb(b∈B)instep3hasthepurposeto
preveninitializationtadversariesstagewithfromobservcorrelatingationsfromobservtheationsfollomadewingrighduringt-to-leftthestage.computationIfofalgorithmA1inthe8.3
hasbeenusedtocomputeA1andthepointsarenotreusedformultipleinvocationsofthe
initializationstage,thennoexplicitprojectiverandomizationofthevariablesAbfor1<b<β
isnecessary;andifβ>2,noexplicitprojectiverandomizationofA1isnecessary:thevariables
haveautomaticallybeenconvertedintonewrepresentationsbythepointadditionsusedto
alues.vfinaltheirdetermine

Staget-to-LeftRigh8.4.2Algorithm8.4implementstheright-to-leftstageusingauniformpatternofpointdoublings
andpointadditions.sumInitially,foreachb,variableAbcontainsthevalueAbInit;thefinalvalueis
denotedbyAb.Duetospecialcasesthatmustbehandledinthepointadditionalgorithm
Q←AlgorithmP8.4Right-to-leftstage
forifib=≥00tothendo
iAbi←Abi+Q
elseA|bi|←−(−A|bi|)+Q
wQ2←Qof(see±Q;sectionthe8.2.1),randomizationuniformityinofthethisinitializationalgorithmisstageviolatedifensuresA|bi|thatisatheprojectivprobabiliteyrepresenofthistationis

100EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

fixclosesecret:toadvzero.ersariesThismisustwhynotinbesectionableto8.4.1chowoseePrequireddependingthatontheprecomputedvaluesvAfixalues,orAbtheybekmigheptt
beabletotriggerthespecialcases.b
IfBcontainsnonegativedigits,thecorrespondingbranchinthealgorithmcanbeomitted.
Otherwise,implementationsshould1usedummypointinversionstoachieveuniformbehavior
forthetwoconditionalbranches.w
statemenThetobQvious←2Qw,aybuttodepimplemenendingtonQthe←2ellipticQincurvthise,morealgorithmefficienistwsp-foldecificiterationalgorithmsofthefor
w-foldpointdoublingmaybeavailable(see[42]).
Inthefinaliterationoftheloop,theassignmenttoQmaybeskipped(thevalueQisnot
usedaftertheright-to-leftstagehasfinished).Withthismodification,thealgorithmusesw
pointdoublingsand+1pointadditions.
intheObservboedyofthattheontlowopo-promaycessorbepsystemserformedtheinpointparallel:additionneitherandopthewerations-folddeppoinendstondoublingthe
result.other’s

StageResult8.4.3SimilarlytothecomputationofA1intheinitializationstage,theresultstagecomputation
sumbAbb∈B\{0}
canbeperformedwithoutcomputingalltheindividualproductsbAbsum.Intheresultstage,it
isanswnotertonecessaryexercisetopreserv4.6.3-9])ethecanbeoriginalusedvifaluesBof={the0,1v,...,ariablesβ}Awhenb,soinitiallyalgorithmeach8.5variable(fromA[46,b
containsthevalueAbsum.Thisalgorithmuses2β−2pointadditions.
Algorithm8.5Computeb∈{1,...,β}bAbsumwheninitiallyAb=Absum
fori=β−1downto1do
Ai←Ai+Ai+1
fori=2toβdo
Areturn1←AA11+Ai

Ellipticcurvepointarithmeticusuallyhasthepropertythatpointdoublingsarefaster
thanpointadditions.Thenthevariantgiveninalgorithm8.6isadvantageous.Thisalgorithm
usesβ/2pointdoublingsand2β−2−β/2pointadditions.

tsarianV8.4.4Inhefollowing,wediscusssomevariationsoftheright-to-leftpointmultiplicationmethod.
1outInthetheproblempublicationthatthen[61],iftheadvsecondersariesbrancarehwableastowrittenpredictasAthe|bi|←represenA|bi|−tationsQ.ofQKatsuyukiand−OkQey,atheyhaspmaoinybtede
ableadditionstolodistinguishoklikepbetoinwteenthesubtractions.twoNoteconditionalthatbrancthishesproblemevenisifavdummoidedypwhenointainproversionsjectiveareusedrandomizationtoletpofoinPt
isperformedbeforebeginningtheright-to-leftstage.

8.42w-AryRight-to-LeftMethod

Algorithm8.6Computeb∈{1,...,β}bAbsumwheninitiallyAb=Absum(variant)
fori=βdownto1do
if2i≤βthen
Ai←Ai+A2i
ifiiseventhen
thenβ<iifAi←Ai+Ai+1
Ai←2Ai
elsethen1>iifA1←A1+Ai
Areturn1

101

ProjectiveRandomizationofP
Whileitdoesnotappeartobestrictlynecessary,itcanberecommendedtoperforma
projectiverandomizationofPbeforebeginningtheright-to-leftstage(algorithm8.4).At
psmallotentialadvcomputationalersaries.cost,thiswillfurtherreducetheside-channelinformationavailableto
0DigitoidingAvvInariablethepAoin0tismessenultiplicationtiallyadummmethoydvasariable:describitsedvinaluedosectionsesnot8.4.2affectandthe8.4.3,finalif0result.∈B,Nothew
tationassumethatfaults.anIfadvtheseersaryfaultsispoccurerformingonlyaduringfaultattackcomputations[13]bypurpaffectingosefullyA,theinducingresultofcompu-the
pointmultiplicationwillstillbecorrect.Thus,verifyingtheresultcannot0revealthatafault
attackhastakenplace.Thereforeitmaybeusefultoavoidthedummyvariable.
ThepointmultiplicationmethodcanbeusedwithadigitsetBthatdoesnotincludethe
e.g.0,aluevB=−2w,±1,±2,...,±(2w−2),2w−1
asinthevariantinsection8.3.1.Comparedwithdigitset{−2w−1,...,2w−1−1},thisrequires
modificationstothealgorithmsusedinstep2oftheinitializationstage(section8.4.1)andin
theresultstage(section8.4.3).Ifweassumethattheinitializationstageusesprecomputed
pointsAbfix,onlythechangestotheresultstagewillincreasethecomputationalcostofapoint
multiplication.Theresultstageforsaiddigitsethastocomputethesum
sumb∈{1,...,2w−1,2w}bAb;
theadditionalcostisonepointdoublingandonepointaddition(setA2w−1←A2w−1+2A2w
beforerunningalgorithm8.5or8.6).
Variantforw=1
Theright-to-leftpointmultiplicationmethodasdescribedbeforeworksonlyforw≥2because
oftherequirementthatAbInit=Oforeachb∈B,butb∈BbAbInit=O.Themethodcanbe

102EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

adaptedtothecasew=1with
B={0,1}
byrelinquishingthelatterpartoftherequirement;instead,savethevalueA1Initandcompute
A1sum−A1Initintheresultstage.2IfA1Initisjustaprojectiverandomizationofaprecomputed
randompointA1fix,thereisnoneedtosaveA1Init:theresultstagecansimplycomputeA1sum−
fix.A1

ApplicationtoModularExponentiation
Theright-to-leftmethodwitharandomizedinitializationstagecansimilarlybeusedfor
asmomodulardularexpinvonenersiontiation.isanForexpthisensivepurpopose,eration.digitsetBwillonlycontainnon-negativedigits

ComparisonEfficiency8.5ForellipticcurvecryptographyoverprimefieldsusingJacobianprojectivecoordinates,a
pointadditioncanbedonein16fieldmultiplications(herewecountsquaringsasmultipli-
cations),andcurvesareusuallychosensuchthatapointdoublingcanbedonein8field
multiplications[41].Thecostforaprojectiverandomization,transforming(X,Y,Z)into
(r2X,r3Y,rZ),is5field2m3ultiplications.Convertingapoint(X,Y,Z)intoextendedpoint
representation(X,Y,Z,Z,Z),ChudnovskyJacobiancoordinates,takes2fieldmultiplica-
intions.ChAudnopoinvskytadditionJacobiancostsco14ordinatesfieldmandtheultiplicationsresultisifoneneededoftheinpoinJacobiantstobcoeaddedordinates,isgivorenif
bnoothvskypointsJacobianaregivcoeninordinatesChudnoaswvskyell;apJacobianointcodoublingordinatesinChandudnothevskyresultisJacobianneededcoinordinatesChud-
representationcosts9fieldmultiplications[18].
inaWesmallfirstexamineconfigurationthewithefficiencyw=of2.thealgorithmsforperformingapointmultiplicationeP
wpointsTheP,22P-ary,4Ptoleft-to-rightprecompute)methodusesfromoneprosectionjectiv8.3ewithrandomizationdigitsetfollo{−4w,ed−1b,e1,t2w}op(threeoint
doublingsforprecomputationandthenoneprojectiverandomization,2pointdoublings,and
pointadditionsfordeterminingtheresult.
NowonepossibilityistouseChudnovskyJacobiancoordinatesfortheprecomputedtable.
forThenthetheevcostaluationforthestageis∙precomputation14+2∙8+stage5=is302∙9++55+field2=m25fieldultiplications,mandultiplications,thetotalthecostcost
is30+30fieldmultiplications.Alternatively,toavoidconcernsaboutkeepingthetableconstantduring
andoneppoinerformtmaproultiplication,jectivewecanrandomizationuseusualoftheJacobiantablecovalueordinatesusedforaftertheeachexceptprecomputedthevtableery
thelastevpointaluationaddition.stageisThen∙16the+2cost∙8for+the∙5=37∙precomputation,andthestagetotalis2cost∙8b+5ecomes=21,thecostfor
21+372ThisvariantwassuggestedbyTsuyoshiTakagi.

ComparisonEfficiency8.5

103

fieldmultiplications.Assuming160-bitscalars(=80),wehave2430fieldmultiplications
forthefirstimplementationchoiceor2981forthesecond.
Forthe2w-aryright-to-leftmethodfromsection8.4withdigitsetB={−2,−1,0,1}
(i.e.fourvariablesA0,A1,A2,Q),weassumethatpointsA0fix,A1fix,A2fixsuchthatA1fix=−2A2fix
havebeenprecomputedsincegeneratingarandompointonthecurvewouldberatherexpen-
sive.Inthisscenario,theinitializationstagehastoperformthreeprojectiverandomizations,
i.e.15fieldmultiplications;theright-to-leftstageuses2pointdoublingsand+1point
additions,i.e.(+1)∙16+2∙8=32+16fieldmultiplications;andtheresultstagecanbe
implementedinonepointdoublingandonepointaddition,i.e.16+8=24fieldmultiplica-
iscosttotalThetions.55+32fieldmultiplications;assuming160-bitscalars(=80),wehave2615fieldmultiplications.
Withtwoprocessors,intheloopoftheright-to-leftstage,thetwopointdoublings(2∙8=
16fieldmultiplications)canbeperformedinparallelwiththeonepointaddition(also16field
multiplications),andsowecanremove16fieldmultiplicationsfromthetally.(Weignore
thesmalladditionalsavingsthatcanbeachievedthroughparallelizationintheotherstages.)
Only55+16fieldmultiplicationsremain;for160-bitscalars,thisis1335fieldmultiplications.
Nowweconsidersimilarscenarioswitharbitrarywindowsizesw≥2andarbitraryscalar
bitlengthsn.Theleft-to-rightmethodfromsection8.3(againusingtheefficiency-improving
variantoftherecodingalgorithm)withChudnovskyJacobiancoordinatesfortheprecom-
putedtableusesoneprojectiverandomization,oneconversionintoChudnovskyJacobian
coordinates,2w−2+1pointdoublings,and2w−2−1pointadditionsforprecomputation,
i.e.5+2+(2w−2+1)∙9+(2w−2−1)∙14=2w−2∙23+2fieldmultiplications;andonepro-
jectiverandomization,n/w∙wpointdoublings,andn/wpointadditionsforcomputing
theresult,i.e.5+n/w∙w∙8+n/w∙14=n/w∙(w∙8+14)+5fieldmultiplications.
n∙(w∙8+14)+2w−2∙23+7
Thetotalcostofthisis
wfieldmultiplications.Theleft-to-rightmethodwithadditionalprojectiverandomizationsto
avoidafixedtableusesoneprojectiverandomization,2w−2+1pointdoublings,and2w−2−1
pointadditionsforprecomputation,i.e.5+(2w−2+1)∙8+(2w−2−1)∙16=2w−2∙24−3
fieldmultiplications;andn/wprojectiverandomizations,n/w∙wpointdoublings,and
n/wpointadditionsforcomputingtheresult,i.e.n/w∙5+n/w∙w∙8+n/w∙16=
n/w∙(w∙8+21)fieldmultiplications.Thetotalcostofthisis
n∙(w∙8+21)+2w−2∙24−3
wultiplications.mfieldForarbitrarywindowsizew≥2andscalarbitlengthn,theright-to-leftmethodfrom
section8.4withascalarencodingusingdigitsfromtheset{−2w−1,...,2w−1−1}(with
=n/w,β=2w−1)performs2w−1+1projectiverandomizationsintheinitializationstage
(2w−1∙5+5fieldmultiplications);n/w∙wpointdoublingsandn/w+1pointadditions
intheright-to-leftstage(n/w∙w∙8+n/w+1∙16=n/w∙(w∙8+16)+16field

104EllipticCurvePointMultiplicationwithResistanceagainstSide-ChannelAttacks

Table8.1:Numberoffieldmultiplicationsfora160-bitpointmultiplication
w23456
L-to-Rmethod,Chud.Jac.coordinates24302067193919191987
L-to-Rmethod,proj.rand.toavoidfixedtable29812430221321412175
R-to-Lmethod26152241217323092709
R-to-Lmethod,twoprocessors13351393153317972293

w−2w−2
(2mw−2∙8ultiplications);+(3∙2w−and2−22)∙p16oin=t2w−2∙doublings56−32and3field∙2m−2pultiplications).ointadditionsTheintotalthecostresultisstage
n∙(w∙8+16)+2w−2∙66−11
wultiplications.mfieldNotethatfortheright-to-leftmethodinthecasewithparallelization,w=2provides
betterperformancethanlargervaluesofw(theright-to-leftstageprovidesessentiallythe
sameamountofworktobothprocessorsifw=2).Comparedwiththeone-processorvariant,
wealwayssaven/w∙16fieldmultiplications,and
wn∙w∙8+2w−2∙66−11
remain.ultiplicationsmfield160-bitTablescalars.8.1Tcomparesable8.2theprovidesefficiencyaofsimilarthemethocomparisondsforforvarious256-bitwindoscalars.wsizes(Noteinthethatcasetheseof
efficiencycomparisonsdonottakeintoaccounttheadditionalcostofgeneratingrandomfield
elementsforprojectiverandomization;onlyfieldmultiplicationsarecounted.)Tableentries
areprintedinboldiftherespectivewindowsizewprovidesalowerfieldmultiplicationcount
thansmallervaluesofw,i.e.ifwisoptimalforcertainboundsonmemoryusage.
Theright-to-leftmethodneedsread-writememoryforthesamenumberofpointsasthe
left-to-rightmethodwiththesamewindowsize.(Theright-to-leftmethodneedsadditional
read-onlymemoryfortheprecomputedpointsAbfix.)Thetablesshowthatfortheexample
bit-lengths,whenusingasingleprocessor,theleft-to-rightmethodwithChudnovskyJacobian
coordinatesisalwaysthefastest;butrememberthatthetablecontains23morefieldelements
b(X,ecauseY,Z);ChsoifudnovskymemoryisJacobianscarce,cothisordinatesmethodhavvearianthetmaformy(notX,beY,Z,Zapplicable.,Z)Theratherthanleft-to-righjustt
methodwithadditionalprojectiverandomizationstoavoidafixedtablecanbefasterthan
thetherighleft-to-right-to-lefttmethomethodd,butneedswillw=need5(17moretablevread-writealues)tomemoryoutptoerformachievtheerighthis:thist-to-leftvarianmethotofd
4.=wwith

RandomizationScalar8.6OkeyaandSakurai[71]describeasecond-orderpoweranalysisattackonthefixed-tablepoint
multiplicationmethodofsection8.3(aspublishedin[59]).Theattackrequirespowercon-
sumptiontracesfrommanypointmultiplicationsusingthesamescalare(andthusthesame
additionchain).Thebasisoftheattackistodetecttable-valuereusebyobservingside-channel

8.6RandomizationScalar

105

Table8.2:Numberoffieldmultiplicationsfora256-bitpointmultiplication
w234567
L-to-Rmethod,Chud.Jac.coordinates387032833043294529793263
L-to-Rmethod,proj.rand.toavoidfixedtable475738703485330032793537
R-to-Lmethod415135213325337337334693
R-to-Lmethod,twoprocessors210321612301255730614117

datathatleaksinformationontheHammingweightofrepresentationsofpoints(cf.[54]):
toeachfindpowouterwhetherconsumptionthei-thtraceandthej-thpdifferenceointbetadditionweenusethe(normalized)samepotablewervalue,consumptioncomputemea-for
surementsatthetwopointsoftimewhentherespectivetableentriesarereadfrommemory;
oversufficientlymanypointmultiplications,thesamplevarianceofthesepowerconsumption
differencesshouldconvergetooneoftwovaluesdependingonwhetherthei-thandj-thpoint
additionusethesametablevalueordifferenttablevalues.
Noexperimentalresultsaregivenin[71].Ifthisattackispractical,similarattacksmaybe
possibleagainstmostpointmultiplicationmethodsusingaconstantsequenceofoperations
astheitmaoutputybeofptheossiblei-thtooptraceerationvisaluesusedbasedasoninputtheirtothejHamming-thopweigheration).t(i.e.Acoundeterminetermeasurewhetheris
torandomizetheadditionchain.Thiscanbedonebyrandomizingthescalare:computeeP
withtwopointmultiplicationsandonepointsubtractionas
(e+mN+m)P−mP
long).bits32(e.g.whereNistheorderoftheellipticcurvegroupandm,mareone-timerandomnumbers
Thiscanalsobeexpressedasfollows:
(e+mN+m)P+m(−P)
fromWhensectioncomputing8.4,thethissuminitializationofprostageductsandwithresulttherighstaget-to-leftneedtopoinbetrunmjustultiplicationonce;onlymethothed
right-to-leftstageneedstoberuntwice.Thefinalresultstagewillautomaticallyyieldthe
result.binedcom(Addingamultipleofthegrouporderwasoriginallyproposedin[48],butitleavessome
biasintheleastsignificantdigits[70].ScalarsplittingintheformeP=(e+m)P−mPas
wpropouldoseddoublein[25]theavcostoidsofthisapoinbias,tmbutisultiplication.onlysufficienBytcomifmbiningisofthesethetwsameoideas,lengthweasaev,oidwhictheh
biaswhilekeepingtheoverheadlow.)

106

Elliptic

eCurv

toinP

Multiplication

with

Resistance

against

Side-Channel

ksttacA

yBibliograph

[1]Abdalla,M.,Bellare,M.,andRogaway,P.DHAES:Anencryptionscheme
basedontheDiffie-Hellmanproblem.SubmissiontoIEEEP1363a.http://grouper.
1998.,ieee.org/groups/1363/P1363a/Encryption.html

[2]Abdalla,M.,Bellare,M.,andRogaway,P.TheoracleDiffie-Hellmanassump-
tionsandananalysisofDHIES.InProgressinCryptology–CT-RSA2001(2001),
D.Naccache,Ed.,vol.2020ofLectureNotesinComputerScience,pp.143–158.

[3]Akishita,T.,andTakagi,T.Zero-valuepointattacksonellipticcurvecryptosystem.
InInformationSecurity–ISC2003(2003),LectureNotesinComputerScience.To
ear.app

[4]AmericanNationalStandardsInstitute(ANSI).Publickeycryptographyfor
thefinancialservicesindustry:Theellipticcurvedigitalsignaturealgorithm(ECDSA).
1998.X9.62,ANSI

[5]Bellare,M.,Canetti,R.,andKrawczyk,H.Keyinghashfunctionsformessage
authentication.InAdvancesinCryptology–CRYPTO’96(1996),N.Koblitz,Ed.,
vol.1109ofLectureNotesinComputerScience,pp.1–15.

[6]Bellare,M.,Desai,A.,Jokipii,E.,andRogaway,P.Aconcretesecuritytreat-
mentofsymmetricencryption.In38thAnnualSymposiumonFoundationsofComputer
Science(FOCS’97)(1997),IEEEComputerSociety,pp.394–403.

[7]Bellare,M.,Kilian,J.,andRogaway,P.Thesecurityofcipherblockchaining.In
AdvancesinCryptology–CRYPTO’94(1994),Y.G.Desmedt,Ed.,vol.839ofLecture
NotesinComputerScience,pp.341–358.

[8]Bellare,M.,Kilian,J.,andRogaway,P.Thesecurityofthecipherblockchaining
messageauthenticationcode.JournalofComputerandSystemSciences61(2000),362–
399.

[9]Bellare,M.,andRogaway,P.Randomoraclesarepractical:Aparadigmfordesign-
ingefficientprotocols.InFirstAnnualConferenceonComputerandCommunications
Security(1993),ACM,pp.62–73.
[10]Bier,´E.,andJoye,M.Weierstraßellipticcurvesandside-channelattacks.InPublic
KeyCryptography–PKC2002(2002),D.NaccacheandP.Paillier,Eds.,vol.2274of
LectureNotesinComputerScience,pp.335–345.

107

108

yBibliograph

[11]Black,J.,Halevi,S.,Krawczyk,H.,Krovetz,T.,andRogaway,P.UMAC:
Fastandsecuremessageauthentication.InAdvancesinCryptology–CRYPTO’99
(1999),M.Wiener,Ed.,vol.1666ofLectureNotesinComputerScience,pp.216–233.
[12]Blake,I.F.,Seroussi,G.,andSmart,N.P.EllipticCurvesinCryptography,
vol.265ofLondonMathematicalSocietyLectureNoteSeries.CambridgeUniversity
1999.Press,[13]Boneh,D.,DeMillo,R.A.,andLipton,R.J.Ontheimportanceofeliminating
errorsincryptographiccomputations.JournalofCryptology14(2001),101–119.
[14]Bos,J.,andCoster,M.Additionchainheuristics.InAdvancesinCryptology–
CRYPTO’89(1989),G.Brassard,Ed.,vol.435ofLectureNotesinComputerScience,
400–407.pp.[15]Bosma,W.Signedbitsandfastexponentiation.DepartmentofMathematics,University
ofNijmegen,ReportNo.9935,1999.
[16]Brands,S.RethinkingPublicKeyInfrastructuresandDigitalCertificates–Building
inPrivacy.MITPress,2000.
[17]Brickell,E.F.,Gordon,D.M.,McCurley,K.S.,andWilson,D.B.Fast
exponentiationwithprecomputation.InAdvancesinCryptology–EUROCRYPT’92
(1993),R.A.Rueppel,Ed.,vol.658ofLectureNotesinComputerScience,pp.200–207.
[18]Brown,M.,Hankerson,D.,L´opez,J.,andMenezes,A.Softwareimplementation
oftheNISTellipticcurvesoverprimefields.InProgressinCryptology–CT-RSA2001
(2001),D.Naccache,Ed.,vol.2020ofLectureNotesinComputerScience,pp.250–265.
[19]Canetti,R.Personalcommunication,2003.
[20]Canetti,R.,Goldreich,O.,andHalevi,S.Therandomoraclemethodology,
revisited.In30thACMSymposiumonTheoryofComputing(STOC)(1998),pp.209–
218.[21]Canetti,R.,Goldreich,O.,andHalevi,S.Therandomoraclemethodology,
revisited.E-printcs.CR/0010019,2000.Availablefromhttp://arXiv.org/abs/cs/
.0010019[22]CerticomResearch.Standardsforefficientcryptography–SEC1:Ellipticcurve
cryptography.Version1.0,2000.Availablefromhttp://www.secg.org/.
[23]CerticomResearch.Standardsforefficientcryptography–SEC2:Recommended
ellipticcurvecryptographydomainparameters.Version1.0,2000.Availablefromhttp:
.//www.secg.org/[24]Chaum,D.Untraceableelectronicmail,returnaddresses,anddigitalpseudonyms.
CommunicationsoftheACM24(1981),84–88.
[25]Clavier,C.,andJoye,M.Universalexponentiationalgorithm–afirststeptowards
provableSPA-resistance.InCryptographicHardwareandEmbeddedSystems–CHES
2001(2001),¸C.K.Ko¸c,D.Naccache,andC.Paar,Eds.,vol.2162ofLectureNotesin
ComputerScience,pp.300–308.

yBibliograph

109

[26]Cohen,H.Analysisoftheflexiblewindowpoweringalgorithm.http://www.math.
1999.,bordeaux.fr/%7Ecohen/window.dviu-[27]Cohen,H.,Ono,T.,andMiyaji,A.Efficientellipticcurveexponentiationusing
mixedcoordinates.InAdvancesinCryptology–ASIACRYPT’98(1998),K.Ohtaand
D.Pei,Eds.,vol.1514ofLectureNotesinComputerScience,pp.51–65.
[28]Coron,J.-S.Resistanceagainstdifferentialpoweranalysisforellipticcurvecryptosys-
tems.InCryptographicHardwareandEmbeddedSystems–CHES’99(1999),¸C.K.Ko¸c
andC.Paar,Eds.,vol.1717ofLectureNotesinComputerScience,pp.292–302.
[29]Cottrell,L.Mixmaster&remailerattacks.http://web.archive.org/web/
essay.19961112194057/http://www.obscura.com/%7Elok%i/remailer/remailer-1996.,html[30]Cramer,R.,andShoup,V.Designandanalysisofpracticalpublic-keyencryption
schemessecureagainstadaptivechosenciphertextattack.Manuscript,http://shoup.
2001.,net/papers/[31]deRooij,P.Efficientexponentiationusingprecomputationandvectoradditionchains.
InAdvancesinCryptology–EUROCRYPT’94(1995),T.Helleseth,Ed.,vol.950of
LectureNotesinComputerScience,pp.389–399.
[32]Diffie,W.,andHellman,M.E.Multiusercryptographictechniques.InProceedings
ofAFIPSNationalComputerConference(1976),pp.109–112.
[33]Diffie,W.,andHellman,M.E.Newdirectionsincryptography.IEEETransactions
onInformationTheory22,6(1976),644–654.
[34]Dimitrov,V.S.,Jullien,G.A.,andMiller,W.C.Complexityandfastalgorithms
formultiexponentiation.IEEETransactionsonComputers49(2000),141–147.
[35]ElGamal,T.Apublic-keycryptosystemandasignatureschemebasedondiscrete
logarithms.IEEETransactionsonInformationTheory31(1985),469–472.
[36]Fischer,W.,Giraud,C.,Knudsen,E.W.,andSeifert,J.-P.Parallelscalar
multiplicationongeneralellipticcurvesoverFphedgedagainstnon-differentialside-
channelattacks.CryptologyePrintArchiveReport2002/007,2002.Availablefrom
.http://eprint.iacr.org/[37]Goldwasser,S.,andMicali,S.Probabilisticencryption.JournalofComputerand
SystemSciences28(1984),270–299.
[38]Gordon,D.M.Asurveyoffastexponentiationmethods.JournalofAlgorithms27
129–146.(1998),[39]Goubin,L.Arefinedpower-analysisattackonellipticcurvecryptosystems.InPublic
KeyCryptography–PKC2003(2003),Y.G.Desmedt,Ed.,vol.2567ofLectureNotes
inComputerScience,pp.199–211.
[40]Hamdy,S.,andM¨oller,B.Securityofcryptosystemsbasedonclassgroupsof
imaginaryquadraticorders.InAdvancesinCryptology–ASIACRYPT2000(2000),
T.Okamoto,Ed.,vol.1976ofLectureNotesinComputerScience,pp.234–247.

110

yBibliograph

[41]InstituteofElectricalandElectronicsEngineers(IEEE).IEEEstandard
specificationsforpublic-keycryptography.IEEEStd1363-2000,2000.
[42]Itoh,K.,Takenaka,M.,Torii,N.,Temma,S.,andKurihara,Y.Fastim-
plementationofpublic-keycryptographyonaDSPTMS320C6201.InCryptographic
HardwareandEmbeddedSystems–CHES’99(1999),¸C.K.Ko¸candC.Paar,Eds.,
vol.1717ofLectureNotesinComputerScience,pp.61–72.
[43]Izu,T.,andTakagi,T.Afastparallelellipticcurvemultiplicationresistantagainst
sidechannelattacks.InPublicKeyCryptography–PKC2002(2002),D.Naccacheand
P.Paillier,Eds.,vol.2274ofLectureNotesinComputerScience,pp.280–296.
[44]Jakobsson,M.,andJuels,A.Anoptimallyrobusthybridmixnetwork.In20th
AnnualACMSymposiumonPrinciplesofDistributedComputing(PODC2001)(2001),
284–292.pp.Press,CMA[45]Joye,M.,andTymen,C.Compactencodingofnon-adjacentformswithapplications
toellipticcurvecryptography.InPublicKeyCryptography–PKC2001(2001),K.Kim,
Ed.,vol.1992ofLectureNotesinComputerScience,pp.353–364.
[46]Knuth,D.E.TheArtofComputerProgramming–Vol.2:SeminumericalAlgorithms
(2nded.).Addison-Wesley,1981.
[47]Knuth,D.E.TheArtofComputerProgramming–Vol.2:SeminumericalAlgorithms
(3rded.).Addison-Wesley,1998.
[48]Kocher,P.C.TimingattacksonimplementationsofDiffie-Hellman,RSA,DSS,and
othersystems.InAdvancesinCryptology–CRYPTO’96(1996),N.Koblitz,Ed.,
vol.1109ofLectureNotesinComputerScience,pp.104–113.
[49]Kocher,P.C.,Jaffe,J.,andJun,B.Differentialpoweranalysis.InAdvances
inCryptology–CRYPTO’99(1999),M.Wiener,Ed.,vol.1666ofLectureNotesin
ComputerScience,pp.388–397.
[50]Krovetz,T.,Black,J.,Halevi,S.,Hevia,A.,Krawczyk,H.,andRog-
away,P.UMAC:Messageauthenticationcodeusinguniversalhashing.Internet-Draft
2000.,http://www.cs.ucdavis.edu/~rogaway/umac/,draft-krovetz-umac-01.txt[51]Lim,C.H.,andLee,P.J.Moreflexibleexponentiationwithprecomputation.In
AdvancesinCryptology–CRYPTO’94(1994),Y.G.Desmedt,Ed.,vol.839ofLecture
NotesinComputerScience,pp.95–107.
[52]Lipmaa,H.,Rogaway,P.,andWagner,D.CommentstoNISTconcerningAES
modesofoperation:CTR-modeencryption.http://csrc.nist.gov/encryption/
2000.,ctr.pdfmodes/workshop1/papers/lipmaa-[53]Menezes,A.J.,vanOorschot,P.C.,andVanstone,S.A.HandbookofApplied
Cryptography.CRCPress,1997.
[54]Messerges,T.S.Usingsecond-orderpoweranalysistoattackDPAresistantsoftware.
InCryptographicHardwareandEmbeddedSystems–CHES2000(2000),¸C.K.Ko¸cand
C.Paar,Eds.,vol.1965ofLectureNotesinComputerScience,pp.238–251.

yBibliograph

111

[55]Miller,V.S.Useofellipticcurvesincryptography.InAdvancesinCryptology–
CRYPTO’85(1986),H.C.Williams,Ed.,vol.218ofLectureNotesinComputerScience,
417–428.pp.[56]Mixmasteranonymousremailersoftware.http://sourceforge.net/projects/
.mixmaster/[57]Miyaji,A.,Ono,T.,andCohen,H.Efficientellipticcurveexponentiation.In
InternationalConferenceonInformationandCommunicationsSecurity–ICICS’97
(1997),Y.Han,T.Okamoto,andS.Qing,Eds.,vol.1334ofLectureNotesinComputer
282–290.pp.,eScienc[58]M¨oller,B.Algorithmsformulti-exponentiation.InSelectedAreasinCryptography–
SAC2001(2001),S.VaudenayandA.M.Youssef,Eds.,vol.2259ofLectureNotesin
ComputerScience,pp.165–180.
[59]M¨oller,B.Securingellipticcurvepointmultiplicationagainstside-channelattacks.In
InformationSecurity–ISC2001(2001),G.I.DavidaandY.Frankel,Eds.,vol.2200of
LectureNotesinComputerScience,pp.324–334.
[60]M¨oller,B.Securingellipticcurvepointmultiplicationagainstside-channelattacks,
addendum:Efficiencyimprovement.http://www.informatik.tu-darmstadt.de/TI/
2001.,isc01.pdfsca-Mitarbeiter/moeller/ecc-[61]M¨oller,B.Parallelizableellipticcurvepointmultiplicationmethodwithresistance
againstside-channelattacks.InInformationSecurity–ISC2002(2002),A.H.Chan
andV.Gligor,Eds.,vol.2433ofLectureNotesinComputerScience,pp.402–413.
[62]M¨oller,B.Improvedtechniquesforfastexponentiation.InInformationSecurityand
Cryptology–ICISC2002(2003),P.J.LeeandC.H.Lim,Eds.,vol.2587ofLecture
NotesinComputerScience,pp.298–312.
[63]M¨oller,B.Provablysecurepublic-keyencryptionforlength-preservingchaumian
mixes.InTopicsinCryptology–CT-RSA2003(2003),M.Joye,Ed.,vol.2612of
LectureNotesinComputerScience,pp.244–262.
[64]M¨oller,U.,andCottrell,L.Mixmasterprotocolversion2.http://www.eskimo.
com/~rowdenw/crypt/Mix/draft-moeller-v2-01.txt,2000.
[65]Montgomery,P.L.SpeedingthePollardandellipticcurvemethodsoffactorization.
MathematicsofComputation48(1987),243–264.
[66]NationalInstituteofStandardsandTechnology(NIST).DigitalSignature
Standard(DSS).FIPSPUB186-2,2000.
[67]NationalInstituteofStandardsandTechnology(NIST).DigitalSignature
Standard(DSS).FIPSPUB186-2,2000.
[68]Ohkubo,M.,andAbe,M.Alength-invarianthybridmix.InAdvancesinCryptology
–ASIACRYPT2000(2000),T.Okamoto,Ed.,vol.1976ofLectureNotesinComputer
178–191.pp.,eScienc

112

yBibliograph

[69]Okeya,K.Methodofcalculatingmultiplicationbyscalarsonanellipticcurveand
apparatususingsame.EuropeanPatentEP1160661,2001.
[70]Okeya,K.,andSakurai,K.Poweranalysisbreaksellipticcurvecryptosystems
evensecureagainstthetimingattack.InProgressinCryptology–INDOCRYPT2000
(2000),B.K.RoyandE.Okamoto,Eds.,vol.1977ofLectureNotesinComputerScience,
178–190.pp.[71]Okeya,K.,andSakurai,K.Asecond-orderDPAattackbreaksawindow-method
basedcountermeasureagainstsidechannelattacks.InInformationSecurity–ISC2002
(2002),A.H.ChanandV.Gligor,Eds.,vol.2433ofLectureNotesinComputerScience,
389–401.pp.[72]Pedersen,T.,andPfitzmann,B.Fail-stopsignatures.SIAMJournalonComputing
291–330.(1997),26[73]Pippenger,N.Ontheevaluationofpowersandrelatedproblems(preliminaryversion).
In17thAnnualSymposiumonFoundationsofComputerScience(1976),IEEEComputer
Society,pp.258–263.
[74]Rackoff,C.W.,andSimon,D.R.Non-interactivezero-knowledgeproofofknowl-
edgeandchosenciphertextattack.InAdvancesinCryptology–CRYPTO’91(1992),
J.Feigenbaum,Ed.,vol.576ofLectureNotesinComputerScience,pp.433–444.
[75]Reitwiesner,G.W.Binaryarithmetic.AdvancesinComputers1(1960),231–308.
[76]Rivest,R.L.,Shamir,A.,andAdleman,L.Amethodforobtainingdigitalsigna-
turesandpublic-keycryptosystems.CommunicationsoftheACM21,2(1978),120–126.
[77]Sakai,Y.,andSakurai,K.Algorithmsforefficientsimultaneousellipticscalarmul-
tiplicationwithreducedjointHammingweightrepresentationofscalars.InInformation
Security–ISC2002(2002),A.H.ChanandV.Gligor,Eds.,vol.2433ofLectureNotes
inComputerScience,pp.484–499.
[78]Schroeppel,R.,Orman,H.,O’Malley,S.,andSpatscheck,O.Fastkeyex-
changewithellipticcurvesystems.InAdvancesinCryptology–CRYPTO’95(1995),
D.Coppersmith,Ed.,vol.963ofLectureNotesinComputerScience,pp.43–56.
[79]Shannon,C.E.Communicationtheoryofsecrecysystems.BellSystemTechnical
656–715.(1949),28Journal[80]Shoup,V.AproposalforanISOstandardforpublickeyencryption.Version2.1,
December20,2001.http://shoup.net/papers/.
[81]Solinas,J.A.Animprovedalgorithmforarithmeticonafamilyofellipticcurves.
InAdvancesinCryptology–CRYPTO’97(1997),B.S.Kaliski,Jr.,Ed.,vol.1294of
LectureNotesinComputerScience,pp.357–371.
[82]Solinas,J.A.EfficientarithmeticonKoblitzcurves.Designs,CodesandCryptography
195–249.(2000),19

yBibliograph

113

[83]Straus,E.G.Problemsandsolutions:Additionchainsofvectors.AmericanMathe-
maticalMonthly71(1964),806–808.

[84]Thurber,E.G.Onadditionchainsl(mn)≤l(n)−bandlowerboundsforc(r).Duke
MathematicalJournal40(1973),907–913.

[85]Tsiounis,Y.,andYung,M.OnthesecurityofElGamal-basedencryption.InPublic
KeyCryptography–PKC’98(1998),H.ImaiandY.Zheng,Eds.,vol.1431ofLecture
NotesinComputerScience,pp.117–134.

[86]VPatenadekar,tCoopA.,erationandTreatLamberyt,(PCT)R.J.PublicationTimingWOattack00/05837,resistant2000.cryptographicsystem.

[87]Vanstone,S.A.,andGallant,R.P.Powersignatureattackresistantcryptography.
PatentCooperationTreaty(PCT)PublicationWO00/25204,2000.

[88]Vernam,G.S.Cipherprintingtelegraphsystemsforsecretwireandradiotelegraphic
communications.JournaloftheAmericanInstituteofElectricalEngineersXLV(1926),
109–115.

[89]cationWegman,andsetM.N.,equalitandy.CarJournalter,ofJ.L.ComputerNewandhashSystemfunctionsSciencandes22theiruse(1981),inauthen265–279.ti-

[90]Yao,A.C.-C.Ontheevaluationofpowers.SIAMJournalonComputing5(1976),
100–103.

[91]–Yen,ComputersS.-M.,andLaih,DigitalC.-S.,TeandchiquesLenstra,141(1994),A.K.325–326.Multi-exponentiation.IEEProceedings

114

yBibliograph

Index

adaptivechosen-ciphertextattack,28,33,
473521,,Adv21tage,anadv4934,29,CCA,21A,CP35generator,stringbitpseudo-random47,yabilitunlink4934,29,,AdvCCA21,AAdvCP34,rgeoAdvF87tation,represenaffinealmoststronglyuniversalhashfunction,31
18,ycryptographasymmetric23,ysecuritasymptoticbasicinterleavedexponentiationmethod,
7635oracle,stringbitCCAadvantage,29,34,49
3534,hallenge,c4829,21,ciphertext,28k,attachosen-ciphertextc4733,28,e,adaptivchosen-plaintextattack,21
ChudnovskyJacobianprojectiverepresen-
92tation,30,CipherLen2918,17,ciphertext,4829,21,hallenge,c88cofactor,24collision,20,ysecuritcomputational21,ysecuritconcrete32de,motercounCPAadvantage,21
ycryptograph18asymmetric,

115

18,eypublic-k17symmetric,decryptionoracle,28,29,33,34,48,49
5519,DH,3227,DHAES,27DHIES,5519,Diffie-Hellman,18signature,digital5520,parameters,domain8255,DSA,8255,ECDSA,ElGamal2920,encryption,55signatures,ellipticcurvecryptography,56,87
4629,21,oracle,encryptionevaluationstage,60,71,72,95,96
55tiation,onenexp64ws,windofractionalinterleaved,71,75
76basic,77based,w-NAFwindo60t,left-to-righ84Lim-Lee,71tiation,onenulti-expm61t-to-left,righ71k,tricShamir’s64ws,windofractionalsigned62ws,windosigned71ultaneous,sim62ws,windosliding67ws,windofractionalunsigned55precomputation,with20hemes,scsignaturefail-stopfindflexiblestage,windo28,w29,size,4886
64ws,windofractional

116

24k,attacgeneric4929,28,stage,guess2419,function,hashalmostcollision,24stronglyuniversal,31
31C,HMA27encryption,ybridh29IND-CCA,21A,IND-CPyindistinguishabilitunderchosen-ciphertextattack,29
underchosen-plaintextattack,21
initializationinformation-theoreticstage,97security,18
interactiveencryptionoracle,48
interleavedexponentiation,71,75
Jacobianprojectiverepresentation,88
3018,KEM,key,17public,18,28,30
3028,18,secret,keyderivationfunction,31
keyencapsulationmechanism,18,30
34oracle,encapsulationeykkeygenerationalgorithm,28,30
keygenerationoracle,21,29,33,46,47
left-to-rightexponentiation,60
left-to-rightstage,60,71,72
40decryption,length-expanding39mix,length-preserving84tiation,onenexpLim-Lee57LSB,57,LSBm31C,MA34oracle,CMAmessageauthenticationcode,31
39mix,modifiedsignedfractionalwindowrepre-
65tation,senmodifiedwidth-(w+1)NAF,63
modifiedwindowNAF,63
multi-exponentiation,55,71

Index

62NAF,23negligible,62form,tnon-adjacenone-timemessageauthenticationcode,31
17pad,one-timeoracle35string,bitdecryption,28,29,33,34,48,49
4629,21,encryption,keyinteractivencapsulation,e,4834
keygeneration,21,29,33,46,47
34C,MA24random,17,OTPpplainointtext,17,18,29
87addition,87,yinfinitat87doubling,87ersion,vin87ultiplication,m55precomputation,precomputationstage,60,71,72,95,96
60table,precomputed3022,es,primitiv88randomization,ejectivproprojectiverepresentation,87
92Jacobian,vskyudnoCh88Jacobian,31generator,stringbitpseudo-randompublickey,18,28,30
public-keycryptography,18
18encryption,eypublic-kpublic-keyencryptionscheme,28
24del,mooraclerandomreduction-basedsecurityproof,22
tationrepresen87affine,87e,jectivpro92Jacobian,vskyudnoCh88Jacobian,9861,stage,resultright-to-leftexponentiation,61
9861,stage,t-to-leftrigh

Index

55RSA,

secretkey,18,28,30
23parameter,ysecurit71k,tricShamir’s88ks,attachannelside-c64ws,windofractionalsigned62ws,windosignedsimultaneousexponentiation,71
62ws,windosliding39routing,,source31,STREAM17,ycryptographsymmetric

31UHASH,45,yabilitunlink67ws,windofractionalunsigned

17encryption,ernamV

width-(w+1)NAF,62
63dified,mo62NAF,wwindo63dified,mowindowindowwsize,NAF62,72splitting,85
86flexible,window-NAFbasedinterleavedexponenti-
77d,methoation62wNAF,

117

  • Accueil Accueil
  • Univers Univers
  • Livres Livres
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents