w a ys to implemen - ANF

1 HowtoTime-StampaDigitalDocument , , ,andrequirenorecord-keepingbythetime-sta mpingservice. Appeared,withminoreditorialchanges,inJou rnalofCryptology, , , {111, 'sgloryistocalmcontendingkings,Tounmaskf alsehood,andbringtruthtolight,Tostampthe sealoftimeinagedthings,Towakethemorn,and sentinelthenight, , ,inintellectualpropertymatters,itissomet imescrucialtoverifythedateaninventor rstputinwritingapatentableidea, cideainvolvesdailynotationsofone' , ,sewn-inpagesofthenotebookmakeitdi , 'sideasislaterchallenged,boththephysical evidenceofthenotebookandtheestablishedpr ocedureservetosubstantiatetheinventor' , , ,thesemethodsmayensurethattherecordsareh andledbymorethanoneperson, , ,thereisanotherpartythatviewsthedocument whoseintegrityorimpartialityisseenasvouc hsa ,andthechangeneedn' ,onemust ndawaytotime-stampthedataitself.}

2 Withoutanyrelianceonthecharacteristicsof themediumonwhichthedataappears, ,itshouldbeimpossibletostampadocumentwit hatimeanddatedi ,we rstconsideranaivesolutiontotheproblem, ,perhapsrepresentingindividuals,di erentcompanies,ordivisionswithinacompany ; 'schallengetothevalidityofadocument' , ,underreasonableassumptionsaboutthecompu tationalabilitiesoftheusersoftheschemean daboutthecomplexityofacomputationalprobl em,andpossiblyaboutthetrustworthinessoft heusers,itisdi ,theweakertheassumptionsneeded, ,a\digitalsafety-depositbox," ,heorshetransmitsthedocumenttoatime-stam pingservice(TSS). 'sdocumentiseverchallenged, , ,thisapproachraisesseveralconcerns:Priva cyThismethodcompromisestheprivacyofthedo cumentintwoways:athirdpartycouldeavesdro pwhilethedocumentisbeingtransmitted,anda ftertransmissionitisavailableinde , ,itcouldbeincorrectlytime-stampedwhenita rrivesattheTSS,oritcouldbecomecorrupted1 Theauthorsrecentlylearnedofasimilarpropo salsketchedbyKanare[14].

3 ' :nothinginthisschemepreventstheTSSfromco lludingwithaclientinordertoclaimtohaveti me-stampedadocumentforadateandtimedi nalissue,trust, , rstsimpli :f0;1g !f0;1glcompressingbit-stringsofarbitrary lengthtobit-stringsofa xedlengthl, , ,givenoneofthesefunctionsh,to ndapairofdistinctstringsx;x0satisfyingh( x)=h(x0).(Suchapairiscalledacollisionfor h.)Thepracticalimportanceofsuchfunctions hasbeenknownforsometime,andresearchersha veusedtheminanumberofschemes;see,forexam ple,[7,15,16].Damg ardgavethe rstformalde nition,andaconstructiveproofoftheirexist ence,ontheassumptionthatthereexistone-wa y\claw-free"permutations[4].Forthis,any\ one-waygroupaction"issu cient[3].NaorandYungde nedthesimilarnotionof\universalone-wayha shfunctions,"whichsatisfy,inplaceofthese condconditionabove,theslightlyweakerrequ irementthatitbecomputationallyinfeasible ,givenastringx,tocomputeanotherstringx06 =xsatisfyingh(x)=h(x0) [17].

4 Rompelhasrecentlyshownthatsuchfunctionse xistifthereexistone-wayfunctionsatall[20 ]. ,forexamplethatofRivest[19], ,aclientwillsenditshashvalueh(x)= , , ,theremaybeasinglehashfunctionusedbyever ybody,ordi erenthashfunctionsfordi ,wewillspeakoftime-stampinghashvaluesy|r andom-appearingbit-stringsofa esh(x)=y; ,asignatureschemeisanalgorithmforaparty, thesigner,totagmessagesinawaythatuniquel yidenti eandHellman[18,7].Afteralongsequenceofpa persbymanyauthors,Rompel[20]showedthatth eexistenceofone-wayfunctionscanbeusedino rdertodesignasignatureschemesatisfyingth everystrongnotionofsecuritythatwas rstde nedbyGoldwasser,Micali,andRivest[10].Wit hasecuresignatureschemeavailable,whenthe TSSreceivesthehashvalue,itappendsthedate andtime, ,theclientisassuredthattheTSSactuallydid processtherequest,thatthehashwascorrectl yreceived, , , ,webelieve, , ,wewouldlikeamechanismwhichguaranteestha tnomatterhowunscrupuloustheTSSis,thetime sitcerti eswillalwaysbethecorrectones, ,iftheoutputofanalgorithmA,givenasinputa documentxandsometiminginformation ,isabit-stringc=A(x; )thatstandsasalegitimatetime-stampforx,w hatistopreventaforgersometimelaterfromco mputingthesametiminginformation andthenrunningAtoproducethesamecerti catec?

5 , erentapproacheswemighttake, rstapproachistoconstrainacentralizedbutp ossiblyuntrustworthyTSStoproducegenuinet ime-stamps,insuchawaythatfakeonesaredi cate, catealsocanbeusedtosolvetheproblemofcons trainingthetimeintheotherdirection,becau sethetime-stampingcompanycannotissuelate rcerti ;the rstone,slightlysimpler,highlightsourmain idea, ,theTSSwillmakeuseofacollision-freehashf unction, ' c,atime-stampingrequestconsistsofanl-bit stringy(presumablythehashvalueofthedocum ent)andaclientidenti ( ) ,sequentiallynumberedtime-stampcerti (yn;idn)fromourclient,thenthrequestinseq uence, cates= (Cn),wherethecerti cateCn=(n;tn;idn;yn;Ln)consistsofthesequ encenumbern,thetimetn,theclientnumberidn andthehashvalueynfromtherequest,andcerta inlinkinginformation,whichcomesfromthepr eviouslyissuedcerti cate:Ln=(tn 1;idn 1;yn 1;H(Ln 1)).

6 ,theTSSsendsourclienttheidenti cationnumberidn+ +1fromtheTSS,shechecksthatsisavalidsigna tureofagoodcerti cate, (n;t;idn;yn;Ln), ,thechallenger rstchecksthatthetime-stamp(s;idn+1)isoft hecorrectform(withsbeingasignatureofacer ti catethatindeedcontainsahashofx).Inordert omakesurethatourclienthasnotcolludedwith theTSS,thechallengercancallclientidn+1an daskhimtoproducehistime-stamp(s0;idn+2). Thisincludesasignatures0= (n+1;tn+1;idn+1;yn+1;Ln+1)ofacerti catethatcontainsinitslinkinginformationL n+ (Ln) +2andverifythenexttime-stampinthesequenc e; ,thechallengercanalsofollowthechainoftim e-stampsbackward,beginningwithclientidn ,observethattheuseofthesignaturehasthee ,becausethecerti catemustcontainbitsfromrequeststhatimmed iatelyprecededthedesiredtime, ,becausebitsfromthedocumentinquestionmus tbeembeddedincerti catesimmediatelyfollowingthatearliertime ,yetthesecerti ,correctlyembeddinganewdocumentintotheal ready-existingstreamoftime-stampcerti , ,clientsmustkeepalltheircerti , ,thecerti cateCnisoftheformCn=(n;tn;idn;yn;Ln),whe renowthelinkinginformationLnisoftheformL n=[(tn k;idn k;yn k;H(Ln k));:::;(tn 1;idn 1;yn 1.)]

7 H(Ln 1))] ,theTSSsendsourclientthelist(idn+1;:::;i dn+k).Aftercheckingthatthisclient'stime- stampisofthecorrectform,asuspiciouschall engercanaskanyoneofthenextkclientsidn+ ,histime-stampincludesasignatureofacerti catethatcontainsinitslinkinginformationL n+iacopyoftherelevantpartofthechallenged time-stampcerti cateCn,authenticatedbytheinclusionoftheh ashbyHofthechallengedclient' (idn+i+1;:::;idn+i+k),ofwhichthelastiare newones;thechallengercanasktheseclientsf ortheirtime-stamps, cates,thissecondvariantalsohasthepropert ythatcorrectlyembeddinganewdocumentintot healready-existingstreamoftime-stampcert i catesrequiresthecomputationofasimultaneo uslyk-wisecollisionforthehashfunctionH, ,weassumethatthereisasecuresignaturesche mesothateachusercansignmessages, ;inparticular, rststudiedbyBlumandMicali[2]andbyYao[22] .

8 Impagliazzo,Levin,andLubyhaveshownthatth eyexistifthereexistone-wayfunctions[12]. Onceagain, ,whoseoutputcanbeinterpretedinastandardw ayasak-tupleofclientidenti cationnumbers:G(y)=(id1;id2;:::;idk):6 Ourclientsendsherrequest(y;id) j(t;id;y) [(y;id);(s1;:::;sk)]. ,theonlywaytoproduceatime-stampeddocumen twithanincorrecttimeistouseahashvalueyso thatG(y) ofpossiblydishonestclients,theexpectednu mberofseedsythathavetobetriedbefore ndingak-tupleG(y)containingonlycollabora torsfromamongthisfractionis ,sincewehaveassumedthatGisasecurepseudor andomgenerator,thereisnofasterwayof 'sfurtherproblem,inmostreal-worldscenari os,of | couldbe90%| ,thelistofcorruptibleclientsneednotbe xed,aslongtheirfractionofthepopulationne verexceeds . ,andthattherebeapublicdirectoryofclients sothatitispossibletointerprettheoutputof G(y) ,forsuitablek0<k,thesystemmightacceptsig nedresponsesfromanyk0ofthekclientsnamedb yG(y)asavalidtime-stampfory(inwhichcasea greatervaluefortheparameterkwouldbeneede dinordertoachievethesamelowprobabilityof ndingasetofcollaboratorsatrandom).

9 SThereareanumberoftradeo ,ontheotherhand,theclienthasashortdelayw hileshewaitsforthesecondpartofhercerti cate; ,soitisbestsuitedtoasettinginwhichrelati velymanydocumentsaresubmittedfortime-sta mping, ,ifanyamountoftimemaypassbetweenthecreat ionofadocumentandwhenitistime-stamped, ,ingeneral, ,ifthetime-stampingeventcanbemadepartoft hedocumentcreationevent, , , ,attheendofthecall, ,thedocumentcreationevent(thephonecall)i ncludesatime-stampingevent,andsothetimeo fthephonecallcanbe nancialtransactions,suchasstocktradesorc urrencyexchanges, ,wesuggestthataprecisecomplexity-theoret icde nitionofthestrongestpossibleleveloftime- stampingsecuritycouldbegivenalongtheline softhede nitionsgivenbyGoldwasserandMicali[9],Gol dwasser,Micali,andRivest[10],andGalil,Ha ber,andYung[8] , ,andassumingaswelltheexistenceofone-wayf unctions(andthereforetheexistenceofpseud orandomgeneratorsandofasecuresignaturesc heme)

10 , ,wementionedthedi erencebetween\collision-free"and\univers alone-way" ,inordertoprovethesecurityofourtime-stam pingschemes,weapparentlyneedthestrongerg uaranteeofthedi cultyofproducinghashcollisionsthatisprov idedbythede ,astrongercomplexityassumption|namely,th eexistenceofclaw-freepairsofpermutations |isneededinordertoprovetheexistenceofthe sefunctions.(Seealso[5]and[6]forfurtherd iscussionofthetheoreticalpropertiesofcry ptographichashfunctions.) erence,perhapsanessential8one, 'sowninteresttoactcorrectlyinfollowingth einstructionsofasecuresignaturescheme(fo rexample,inchoosingahashfunctionatrandom fromacertainset).Fortime-stamping,ontheo therhand,adishonestuseroracolludingTSSma y nditconvenientnottofollowthestandardinst ructions(forexample,bychoosingahashfunct ionsothatcollisionsareeasyto nd).