《电子现金系统设计代码 .pdf》由会员分享，可在线阅读，更多相关《电子现金系统设计代码 .pdf（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Department Of Computer Science University of Bristol Compact E-Cash Alireza Hajabbasgholi A.Hajabbasgholi.05bristol.ac.uk A dissertation submitted to the University of Bristol in accordance with the requirements of the degree of Bachelor of Science in the Faculty of Engineering 名师资料总结-精品资料欢迎下载-名师精心整
2、理-第 1 页，共 49 页 -2 Declaration A dissertation submitted to the University of Bristol in accordance with the requirements of the degree of Bachelor of Science in the Faculty of Engineering.It has not been submitted for any other degree or diploma of any examining body.Except where specifically acknowl
3、edged,it is all the work of the Author.Alireza Hajabbasgholi,April 2006名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 49 页 -AcknowledgementsFirstlyand foremostly,I would like to thank Professor Nigel Smart,who hasbeen the best tutorand supervisorone could wish for.As well as going out ofhis way to help me when di?c
4、ultiesarose,his moral supportkept me on therightpath.I am very gratefulfor havinghad his supervisionthroughoutmydegree.Secondly,I would like to thank Dr.TatsuakiOkamotoof NTTlabs,for hispromptassistance and recommendationson his paper.Finally,I wouldlike to thank all of the authorsmentionedin the re
5、ferencessectionof thisthesis.Completingthisthesis wouldhave notbeen possiblewithoutaccess to their previouswork(s).3名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 49 页 -AbstractE-cash or electronic cash has been the focus of?nancial cryptographerssince the 1980s.Every year,one or more E-Cash protocolsare presenteda
6、t majorcryptographyconferences aroundthe world.A goal common toall these schemes is to improveupon the e?ciencyof theirpredecessorswhile o?eringthe same level of anonymity.Buthow e?cientare theseprotocols?We aim to analyse this and other trends thatE-Cashhas seen sinceits conception.Originally,the a
7、nalysis method considered for this projectwas to verifythe e?ciencyand securityof the mostrecent protocolasan aid to our analysis.However,implementingthe most recent protocolsproves to be extremelytime-consuming.Therefore,our new strategy aimsto implementan older protocolthat has never been implemen
8、tedbefore.We shall also use it as a basis for a briefanalysisof some more recentschemes.We shall provide an implementationof one of the most in?uentialprotocolsin divisible,transferableand o?ineE-Cashs historyon whichmany other protocolsare based.We shall also provide the reader withabrief analysis
9、of the performanceof other importantprotocols,includingthe most recent paper presented at Eurocrypt05.This allows the readerto draw objectiveconclusions on the need for new schemes as well as thefutureof E-Cash.4名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 49 页 -Contents1Background71.1Introduction.71.1.1De?nition
10、and History.71.1.2Realisationsof E-Cash.91.2PreviousWork.91.2.1A Simple Protocol.91.2.2More AdvancedProtocols.121.3Our Contribution.131.4PreliminaryPreparations.142Analysis152.1TheoreticalDesign.152.1.1HierarchicalStructureTables.152.1.2Protocol1(Basic DivisibleUniversalElectronicCash).172.1.3Protoc
11、ol2(TransferableUniversalElectronicCash).212.1.4TheoreticalE?ciency.222.2Practicaldesign.242.2.1Protocols1 and 2(DivisibleUniversalElectronicCash).252.2.2PracticalE?ciency.282.2.3AlternativeApproaches.333ResultComparisons353.1Okamotos Second Scheme.353.2ProjectCAFE.363.3Brands Scheme.363.4CompactE-C
12、ash.364ConcludingRemarks374.1PotentialUses for Our E-Cash Implementation.374.2Futureof E-Cash.374.3FutureWork.384.4Final Words.385References406AppendixA:SelectedCodeSegments435名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 49 页 -Listof Figures1Basic E-Cash Circulation.72A More AdvancedExchange Protocol.113Hierarchi
13、calStructureTable.164Table.165The State of Table after Spending$18.246名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 49 页 -1Background1.1Introduction1.1.1De?nitionandHistoryE-Cash or as more generally known DigitalCash/Money1has been extensivelystudiedsince around25 years ago.E-Cash was inventedby DavidChaumetal 1,
14、2.Most E-Cash schemes are builtaround the core of Chaum sinventionof blindsignatures.Since its invention,E-Cash has received great attentionbycryptographersand a great deal of research has been undertakenin makingitmore secure and e?ciente.g.12,4,5,6,7,8,9,10,11.The main idea behind E-Cash is to rep
15、lace hard money by a series of binaryform of data.In its simplestform(Figure12),circulationof E-Cash is as follows33:1.A user obtains a wallet withsome money from her bank.2.The user then spends the money with a merchant.3.The merchantretrieves the money from the bank later.Figure1:Basic E-Cash Circ
16、ulationIt can be clearly seen thatthere are many securitythreatsassociated withthis model.We shall take a look at cryptographicallymore advanced protocolslater in this paper.Thereare two typesof E-Cashthathave so farbeen developed:onlineand o?ine.In the online scenario,we alreadyhave more securityas
17、 we havea Bank online who supervises transactions.However,in this paper,we aremainlyconcerned with the o?inescenario of E-Cash4.In the o?inescenario,weeliminatethe banks supervisionby introducingsome cryptographictechniques.1Fromnow on,we use the termE-Cashfor simplicityof use.2Source:cui.unige.ch/d
18、eriazm/Softs/ECash/images/ECash.PNG3Here,we are referringto the O?inemodeof E-Cash.4Fromnow on,by E-Cashwe are referringto the o?inescenariounlessstatedotherwise.7名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 49 页 -Thereason for our interestin theo?inescenario has arisenfrom the needfor physicalcash alike digitalm
19、oney as it o?ers anonymityand e?ciency(workuse,communicationslag and etc.).A complete E-Cash protocolmust satisfy the followingsix conditions12:1.Independence:As E-Cashis principallyin the form of data,its securitymust not depend on any physical conditions.2.Security:E-Cash is secure.I.e.it cannot b
20、e duplicated.3.Privacy:Also known as un-traceability;as withphysical cash,it must beanonymous;i.e.the bank cannot reveal the identityof the purchaserormerchantunless one of the twohas cheated.In a more secure context,even if the bank and merchantcollaborateto reveal the identityof anhonest purchaser
21、,thisshould not be possible,unless the purchaserhascheated.4.O?ineoperation:Transactionsbetween users and merchantsshouldbecompletedo?ine,i.e.the merchantdoes not need to establish a linktothe bank.5.Transferability:Just like real cash,E-Cashcan be transferredfrom oneholder to another.6.Divisibility
22、(multipledenominations):Althoughnot exactly physicalcashalike,divisibilitysimulatespossession of cash withdi?erentface values,i.e.if we have a walletof value S,we can dividethe walletintomanypieces such thatthe totalvalue of the small pieces equals S.The typicalplayers in a transactionare:1.A user U
23、:This is a customer who withdrawsa wallet from his/herbank.2.A bank :The bank is responsible for signing the money order and givingit to U.is also responsiblefor giving the paymentof the money to themerchantwho has received the money order.3.A merchantM:The merchantis essentiallythe same as the user
24、 in thesense thatthey can both hold digitalmoney.The only di?erence is thatthe merchant is the receiver of the money from U.Some protocolsintroducean extraentitycalled the“Trustedthirdparty”or“TTP”.A TTPis essentiallya supervisorthatcan trace all the coins of acheatinguser.However,thiscontradictswit
25、hthe anonymityprincipalof E-Cash.To a TTP,the user is known and therefore one must achieve the security8名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 49 页 -of a TTPwithouta TTP.Thishowever,does come at the cost of increasedspace complexityfor transactionsas a single coin is circulated.Thise?ect isdemonstratedin ou
26、r implementation.1.1.2Realisationsof E-CashOver the past 15 years,there have been many companies o?eringE-Cash ser-vices to customers.Examples of these companies include:DigiCash,Visa cash,Mondex,Interacnetwork(Canada),Octopuscard(HongKong),Micromint,projectCAFEand others.Some of these mentionedo?er
27、 online cash and someo?inewithoutrelyingon online veri?cation.So far many of these companieshave been unsuccessful(such as DigiCashwhichdeclaredbankruptcyin 1998 and sold 16 patentsand the companytoE-Cash systems who is experiencingdi?cultiestoo)and some have been so suc-cessful that the use of thei
28、r productshave surpassed physical cash transactionsin their countryof operation(such as the Interac networkwhich surpassed cashas a paymentmethodin 2000)5.Althoughthere have been many opinions regarding the reasons for failure ofthose companies,the issues of trustand securitytop the pollshere6.Despi
29、tethis,many online services such as online casinos and small-valueonline-deliv-erable items(such as E-Magazines,E-Books and PDAsoftware)accept E-Cashas a paymentmethod.Therefore,the need for a provably secure and completelyanonymousproto-col still exists and there is much research to be done in this
30、?eld.1.2PreviousWorkIn thissection we brie?yreview the research thathas been undertakenon E-Cash.We willalso describethe simplestprotocolthatis the core of mostadvanced E-Cashprotocols.Of course the newer protocolshave more math-ematicallyand cryptographicallyadvancedideas behindthemand are muchmore
31、 sophisticated.In order to get a betteroverview of E-Cash,we will intro-duce some concepts and algorithmsthatare used most commonlyin E-Cashimplementations.1.2.1A SimpleProtocolBelow is an outlineof a simple protocol37thato?ers anonymityand securityto the user and merchant,unless they have cheated.5
32、Source:http:/en.wikipedia.org/wiki/Electronicmoney6Source:http:/osaka.law.miami.edu/froomkin/articles/ocean.htm7Here,we are concernedwithprotocol#4of the bookreferredto.9名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 49 页 -1.The user places n money orders in an envelope(achieved by using a blind-ing protocol1).Each
33、 money order containsa randomlong stringthatguarantees the uniqueness of the money order(i.e.two money orders willnot have the same string).On each order,there are also n pairs of identitybit-stringsthat when correctlymerged,reveal the identityof the user8.2.The user then blinds all of her money ord
34、ers using a blind signatureproto-col(thiscan be seen in the account opening part of our implementation).3.The moneyorders are thentakentothe bank.Inorderto maintainanonymityof the user and at the same time verifythe user shonesty,thebank asks the user to un-blindn-1 of the orders at randomand to rev
35、ealall of their identitystrings.Thereforethe chance of a cheating user gettingaway with a fake order is 1/n.If n is large,this chance is close to zero.4.Providedthe user veri?cationis successful and the user shonestyis con-?rmed,the bank signs the one remainingblinded money order and handsit back to
36、 the user.The value of the order is then deducted from the user saccount at the bank.5.The user then spends the money witha merchantby un-blindingit andpassing it to the merchant.6.The merchantthen checks the signatureof the bank on the order.If it isa genuine signatureof the bank,the merchantprocee
37、ds to the next step.7.The merchantthen gives the user a randomn-bit long selector string(i.e.series of 0s and 1s).The user then reveals either lefthand or the righthand bit of each of her identitystrings(not both sides;otherwise the user sanonymityis breached).8.The merchantthen takes the order to t
38、he bank.The bank veri?es thatanorder withthe same uniqueness stringhas not been spent previously.Ifno cheating has occurred,the bank deposits the money to the merchant saccount.If either the merchantor the user cheat,the bank will know thisby checking whetherthe identitystring of the previouslyused
39、order is thesame as the new order.If it is,then the merchanthas copied the order,otherwise the user is guilty.In order to reveal the identityof the cheatinguser,all the bank has to do is to XORthe two identitystrings.Notes:8Thiscan be achievedusingsecretsplittingand bitcommitmentprotocols.10名师资料总结-精
40、品资料欢迎下载-名师精心整理-第 10 页，共 49 页 -1.The protocolintroduceddoes not satisfythe 6thconditionof a completeprotocol12(however,we can modifythe protocolso thatwe can achievethis).We shall introduceprotocols that claim to meet this conditionalongwith the others,later in this paper.2.Also the reader should not
41、e thatthe e?ciencyof the protocolabove isnot feasible.In fact the data requirementfor a single purchase wouldbearound200megabytes9.3.In the protocolabove,if double spending occurs,it is only discovered whenthe merchanthas taken the money order to the bank.However,we arenot concerned about this as th
42、e same issue exists with physical cash.4.Just like real cash,if someone copies and spends the user smoney beforeshe does,the user will be identi?edas guilty.Figure2:A More AdvancedExchange ProtocolFigure210shows the presentationof one such scheme.Theprotocolabovedoes satisfy the conditionsfor a comp
43、leteE-Cash protocol(divisibilitycan beachieved using this protocolbut some changes are requiredin order to do this.Our implementationof Okamotos scheme in this paper shows how).Howeverwe need to do betterby improvingthe e?ciencyof the protocol.As a result,we will be looking at some other protocolsth
44、athave been regarded as completeand e?cient,and we shall take a more in depth look at one such protocoland9Reference3,Page 147.10Source:elab.vanderbilt.edu/research/studentprojects/secure.payment.systems/ecash.jpg11名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 49 页 -analyse it by implementation.We shall present m
45、athematicalideas behindourselected scheme in sub-section1.4 of thispaper,as before one moves to theinternalsof protocols,obtaininga general overview of each is necessary.1.2.2MoreAdvancedProtocolsA quick review of the submissions between 1989 and 2005 reveals a set of mostreferred-toE-Cashschemes,e.
46、g.3,9,11,10,13,4,and etc.As we areconcerned withe?ciency,we willreview the three most relevantsubmissions:12,14,and 15.In 12,Okamotoclaimsthathis scheme is the?rst completeand e?cientprotocolthatsatis?es all six requirementsof E-Cash11.He also shows thatthesecurity of his scheme relies on the di?cul
47、tyof factoring12.He also demonstratesthat divisibilityis feasible by introducing“MoneyStructures”.These structuresare principallythe same as a binarytree withsome usage rules.He achievesdivisibilityby using two identicalmoney structurescalledand tables re-spectively.Okamotothen moves on to introduce
48、two protocolsof whichthesecond is transferable.Double expenditureis preventedby the idea of“dispos-able Zero-Knowledgeauthenticationprotocol”which was inventedby Okamotohimself 8.E?ciency:In his paper,Okamotoclaims thathis protocoltakes on aver-age 20kilobytesof data transmissionto completea transac
49、tion.Moreover,heestimates the average speed of his protocol(assuminga Rabinscheme chip of30kbps is present)to be several seconds.Thiswillbe evaluatedin the perfor-mance section(2.2.2)of this paper.The authoralso con?rms in his submission,that his scheme is not uncondi-tionallyun-traceable.In 15,Ferg
50、uson claims that his scheme is more e?cientthan the others pre-viously known13.He claims that his withdrawalprotocol(the part in which userswithdrawwallets from theirbanks)is the?rst thattakes advantage of a directconstructionand does not rely on the cut-and-choosealgorithm14.Ferguson alsoclaims tha