上海交通大学硕士学位论文基于对偶理论的APPA组合协商研究及最佳投标策略算法的实现姓名：陆青申请学位级别：硕士专业：软件工程指导教师：曹珍富;李振武20070601上海交通大学硕士学位论文上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：陆青日期：年月日第III页上海交通大学硕士学位论文上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本学位论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：陆青指导教师签名：曹珍富日期：年月日日期：年月日第IV页上海交通大学硕士学位论文摘要当今世界，移动电子商务正在对经济和社会发展产生着深刻影响，传统商务模式正在转向以企业信息化和社会信息化为基础的电子商务模式。由于移动电子商务的发展，商品拍卖更趋方便可行。商品拍卖也由简单的单一商品拍卖，逐步过渡到复杂的多种商品的组合拍卖。如何实现组合商品拍卖中的自动协商（自动撮合）也就是研究的一个焦点。关于移动电子商务中组合商品拍卖的自动协商机制的研究，本文给出了一种拍卖方确定商品分配方案具有较低的计算复杂度，且参与投标的agent具有较低复杂度的组合协商机制。提出一种可同时进行多件商品交易的组合协商（组合拍卖）机制APPA（AscendingPricePacketAuction），APPA是由拍卖方同时组织多项不同的商品进行拍卖，它允许agent对于商品的组合进行投标。在APPA中每个agent都具有简单而且又是最佳的投标策略，它能够在降低agent投标风险的同时使拍卖方获得最大的拍卖收入。由于移动终端存在着处理能力低，存储能力小,电源容量小等弱点，因此移动终端并不能给用户提供足够的安全保障。针对上述安全技术问题，本文重点研究Chameleonsignatures中的Chameleonhash函数，特别是基于身份标志的Chameleonhash函数（ID-BasedChameleonhashfunction）。ChameleonSignatures是基于hash-and-sign模式的签名方案。Chameleonhash函数是一个单向陷上海交通大学硕士学位论文门函数：如果不知道陷门信息，Chameleonhash函数无法计算她的原项和碰撞；然而拥有陷门信息，Chameleonhash函数容易计算出碰撞。它可以使用离散对数方法或者大整数分解方法来实现。研究利用离在线数字签名构造一个数字签名方案，并将ID-BasedChameleonhash函数引入到APPA的离在线数字签名方案中,从而应用到移动电子商务拍卖中。离在线数字签名方案是将数字签名分为两个阶段，第一个阶段是离线阶段（消息被签名前），该阶段执行对系统资源要求较多的计算；第二个阶段是在线阶段（将被签名消息与预计算结果进行在线签名）。实验证明该方案可以比较快速地实现在线阶段的签名。从而确保整个拍卖过程的安全性。关键词：自私agent，自动协商，组合拍卖，对偶理论，Chameleonsignatures，离在线数字签名，数字签名,移动商务，信息安全上海交通大学硕士学位论文StudyonBilateralAgentNegotiationforM-CommerceandBiddingStrategyArithmeticABSTRACTTheresearchonautomatednegotiationmechanismofcombinatorialresourcesallocationamongmultipleself-centredagents,liesinprovideanautomatednegotiationmechanism,whichwith