基于对偶理论的APPA组合协商研究及最佳投标策略算法的实现

上海交通大学硕士学位论文基于对偶理论的APPA组合协商研究及最佳投标策略算法的实现姓名：陆青申请学位级别：硕士专业：软件工程指导教师：曹珍富;李振武20070601IIIIV1agentAPPAAscendingPricePacketAuctionAPPAagentAPPAagentagent,ChameleonsignaturesChameleonhashChameleonhashID-BasedChameleonhashfunctionChameleonSignatureshash-and-signChameleonhash2ChameleonhashChameleonhashID-BasedChameleonhashAPPA,agentChameleonsignatures,3StudyonBilateralAgentNegotiationforM-CommerceandBiddingStrategyArithmeticABSTRACTTheresearchonautomatednegotiationmechanismofcombinatorialresourcesallocationamongmultipleself-centredagents,liesinprovideanautomatednegotiationmechanism,whichwithlowcomputationalcomplexityfortheauctioneerinthewinnerdetermination(allocationdetermination)onthesideofauctioneer,andatthesametimehaslowagentbiddingcomplexity.Inthispaper,theprimal-dualtheoryofcombinedoptimizationwasusedincombinatorialauctiondesign,andAPPA(AscendingPricePacketAuction)combinednegotiationwasproposedtodealwithbiddingandallocationincombinatorialresourceproblem.InAPPA,theagentusesbest-responsestrategyasitsbiddingstrategy,andcansimplybidtocombinedpacketsthatbringmaximumutilitiesatcurrentpricelevel.Whenthecomplementary-slackconditionissatisfiedtheAPPAwillendwiththeresultofanoptimalresourceallocationscheme.ThepropertiesofAPPAlieinkeepingtheefficiencyofallocation,andmeanwhilereducethecomputationalcomplexity.Facingtheseriousmobileenvironment,severalweaknessesinthemobilehandsetdevices,including:lesspowerfulCPUs,lessmemoryspace,restrictedpowerconsumptionManyresearchersoptimizethesecuritytechnologiesusedinfixednetworktoapplyinM-Commerce.Oneofthekeypointsinthispaperisthechameleonhashfunctionthatappliedinthechameleonsignaturesscheme.HereweemphaseontheID-BasedChameleonhashfunction.Chameleonsignaturesarebasedonthewellestablishedhash-and-signparadigm,whereachameleonhashfunctionisusedtocomputethecryptographicmessagedigest.Achameleonhashfunctionisaone-waytrapdoorhashfunction:Resistant4tocomputethepre-imagesandcollisionswithoutknowledgeoftheassociatedtrapdoor,yetefficientlycalculatethecollisionswithknowledgeofthetrapdoor.Itisafunctionthatcanbaseonfactoringordiscretelog.Thispaperwilldiscusstheon-line/off-linedigitalsignatureschemeswhichembedswithID-Basedchameleonhashfunction.TheAPPAusestheon-line/off-linedigitalsignaturetoimprovesecuritylevelforM-CommerceBidding.On-line/Off-linedigitalsignatureschemessplitasigningintotowphases:Theoff-linephaseisimplementedforpre-computation.Theon-linephaseusesthestoredpre-computationoftheoff-linephasetosignactualmessages.Theoreticalsecurityanalysisandpracticalimplementationprovethatthison-line/offlinedigitalsignatureschemesembeddedwithID-Basedchameleonhashfunctionperformancesefficientlyintheon-linesigningspeed.Keywords:Self-centredagent,automatednegotiation,combinatorialauction,primal-dualtheory,Chameleonsignatures,On-line/Off-linedigitalsignatures,digitalsignature,M-Commerce,Informationsecurity71.1InternetUbiquitousComputingAnytime,anywhereagentagentagentWAP[1]WirelessApplicationProtocolWAPWAP3GSSL[20]SecuritySocketLayer/TLSTransportLayerSecurityWAPWAPTLSWTLS[1]WirelessTransportLayerSecurityWTLSPKI[21]PublicKeyInfrastructurePKICA8WPKI[2]WirelessPublicKeyInfrastructureWPKIPKIECCX.509,(CA)WPKI1.2agentAPPAAscendingPricePacketAuctionAPPAagentAPPAagentagent,ChameleonsignaturesChameleonhashChameleonhashID-BasedChameleonhashfunctionChameleonSignatureshash-and-signChameleonhashChameleonhashChameleonhashID-BasedChameleonhashAPPA,1.3APPAAPPAChameleonhashID-BasedChameleonhash9functionAPPAAPPADEMOChameleonhash102.1ASystemModelforMobileCommerce[3]M-Commerceapplicationsmobilestationsmobilemiddlewarewirelessnetworkswirednetworkshostcomputers2-12-1Figure2-1AmobilecommercesystemstructureDeloitteConsulting[1]KaplanSawhney[4](1)(2)(3)(4)2.2111Confidentiality2Integrity3AuthenticationSimpleAuthenticationStrongAuthentication4Non-repudiationInternet5ResourceAccessControlandUserAuthorizationID[22]PINPersonalIdentificationNumber2.3Benson[5]Lai[6](1)12(2)(3)(4)Bazerman[7]1distributioninnegotiation2integrationinnegotiationtradeoff2.4APPAAPPAagentagentAPPAagentagentagent2.4.1APPAAPPAagent()()()iiiubvbpb=−agentagentagentagent2-1()ivS12SS⊆()()12iivSvS≤2.4.2APPAAPPA13APPAAPPAagentagentAPPAagentagentagentagentAPPAagentagentAPPAagent-XORXORagent11,SpXOR22,Spagent1S2S1S2SXORagent[12,38]11,Sp22,Sp1p2pagent1S2Sagentagentagentagent2.5APPAagentAPPAagentagentagentagentagent12M−agent2.614APPA2.6.1——KeKd/2-2Figure2-2TheSketch-MapofCryptographicSystem222-2(P,C,K,E,D)PCKk∈Kek∈Edk∈Dek:P→Cdk:C→Pdk(ek(x))=xx152.6.1.1ke=kd(,),(,)EMKCDCKM==2.6.1.2PublicKeyPrivateKeyRSADSA2.6.1.3One-WayFunctionxfxfxxHashFunctionlHash-Value2-3()HMMD1.H2.MH(M)3.HMDMH(M)=MDMH(M)M′(≠M)H(M′)=H(M)HOne-WayHashFunctionH4.MM′H(M′)=H(M)HCollisionFreeHashFunctionMIC16MDCMessageAuthenticationCodeMACMACDACMACMAC2.6.1.4Nonce2-4Pseudo-RandomBitGeneratorPRBGkllk“”PRBGSeedPRBGPRBG2k/2lPRBGNonceNonceNonceNonceNonceABABNbAB17NbBBNb::{}bbkBANABN→→NbDiffie-Hellman::xyABXgmodnBAYgmodn→=→=ABnggnxy()()yxKXmodnYmodn==2.6.1.5NonceNonce182.6.2APPAChameleonSignaturesChameleonhashIDChameleonh