（应用数学专业论文）群签名技术在电子拍卖中的应用研究.pdf

中山大学硕士学位论文 论文题目：群签名技术在电子拍卖中的应用研究 专业：应用数学 硕士生：黄秀姐 指导教师：王燕鸣教授 摘要 本文概括了群签名技术和电子拍卖方案的发展现状，并具体研究分析了群签 名技术在电子拍卖协议中的应用情况。由此，基于最新被提出的k + l 平方根假设 【1 】和线性d i f f i e h e l l m a n 假设【2 】，本文提出了一类新的群签名方案。一个是静态 的群签名，也就是群成员一次性都加入某个群，之后就不再有新的成员加入；一 个是动态的群签名，也就是新成员可以随时加入群组织，而其他群成员的证书和 私钥没有受到影响。这两个群签名方案的一个显著的优点就是签名的长度短，少 于2 5 0 b y t e s ，而且它们都是在随机应答模型之下可证明安全的，即满足了完全匿 名性和完全可追踪性【3 】。另外，本文还把新的动态群签名方案的一个变形运用 到电子拍卖系统中，提出了一个新的公开的电子拍卖方案。与其它的拍卖方案相 比，该拍卖方案不仅满足了公开电子拍卖的性能要求；而且，由于每个投标者的 签名都是一个短群签名，整个拍卖系统的计算和通信耗费大大降低了。 关键字：群签名，电子拍卖，k + l 平方根假设，随机应答模型 中山大学硕士学位论文 t i t l e ：ar e s e a r c ho na p p l i c a t i o n so fg r o u p s i g n a t u r e si na u c t i o n s m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：x i u j i eh u a n g s u p e r v i s o r ：p r o ly a n m i n gw a n g a b s t r a c t g r o u ps i g n a t u r ep l a y sa ni m p o r t a n tr o l e i nc r y p t o g r a p h i ca p p l i c a t i o ns u c ha s a u c t i o n i nt h i st h e s i s ，o v e r v i e w so fg r o u ps i g n a t u r e sa n da u c t i o ns c h e m e sa r eg i v e n ， a n da p p l i c a t i o n so fg r o u ps i g n a t u r e si na u c t i o n sa r ed i s c u s s e d t h e n ，w ep r o p o s et w o g r o u ps i g n a t u r es c h e m e sa n ds h o wh o w t ou s et h e mt oc o n s t m c tas e c u r ee - a u c t i o n t h et w og r o u ps i g n a t u r es c h e m e sa r eb o t hb a s e do nt h e ( k + 1 ) s q u a r er o o t a s s u m p t i o n 1 】p r o p o s e dr e c e n t l ya n dd e c i s i o nd i f f i e - h e l l m a na s s u m p t i o n 2 t h e f u - s ti sas t a t i co n e ，i nw h i c ha l lm e m b e r sj o i ni nt h eg r o u pi nt h ei n i t i a ls t a g ea to n c e a n dn oo n ec a nj o i ni ni tl a t e r ；t h es e c o n di sad y n a m i co n e ，i nw h i c hu s e rc a nj o i ni n t h eg r o u pa n db e c o m e sag r o u pm e m b e ra ta n yt i m e ，w h i l eo t h e rg r o u pm e m b e r s c e r t i f i c a t i o n sa n dp r i v a t ek e y sa r en o tc h a n g e d o n eo ft h eg r e a t e s ta d v a n t a g e so f t h e mi st h a tn o to n l yt h el e n g t ho f s i g n a t u r e si ss h o r t ，l e s st h a n2 5 0 b y t e s ，b u ta l s ot h e s e c u r i t yo fs c h e m e sc a nb ep r o v e dw i t hr a n d o mo r a c l e s m o r e o v e r , an e wp u b l i c e l e c t r o n i ca u c t i o np r o t o c o li sp r o p o s e d ，w h i c hb a s e do nav a r i a t i o no ft h ed y n a m i c g r o u ps i g n a t u r es c h e m e c o m p a r i n gw i t ho t h e ra u c t i o ns c h e m e s ，t h en e wo n ec o s t s l o w e rc o m m u n i c a t i o na n ds m a l l e rc o m p u t a t i o n , a sw e l la ss a t i s f i e st h em a i n p r o p e r t i e so f p u b l i ce l e c t r o n i ca u c t i o ns c h e m e s k e y w o r d s ：g r o u ps i g n a t u r e , e l e c t r o n i ca u c t i o n , ( k + 1 ) s q u a r er o o ta s s u m p t i o n , r a n d o mo r a c l e s i i 群签名技术在电子拍卖中的应用研究 引言 二十世纪末，随着人类信息技术的飞速发展，互联网从一个科研应用的计 算机连网系统发展成为全面商务化的全球信息网，并预示着网络经济时代的到 来。进入新世纪后，在短短的几年时间里，网络经济已经显现出了其广阔的发 展前景，一个全新的网络化商业环境也在逐渐形成和完善。“电子商务” ( e l e c t r o n i cc o m m e r c e 或e l e c t r o n i cb u s i n e s s ) 作为网络经济的一个新生儿，以难 以估量的速度在兴起，并改变着社会经济生活的各个方面。电子商务作为一种 新的经营方式，影响着各行各业，在企业的经营模式、政府的管理模式、人们 的生活方式等各方面进行着类似工业革命的一次信息革命。电子商务是在互联 网上传递信息、产品和服务，进行支付的商务活动，其核心是买卖双方利用数 字过程交易数字产品。电子商务以互联网为支撑平台，可以在提高产品质量和 加快产品服务交付速度的同时降低服务的成本。网上拍卖作为电子商务活动的 一种重要的交易形式，是从1 9 9 5 年e b a y 的建立开始兴起的，并逐渐在全球流 行。十多年来，随着电子商务活动的发展，网站拍卖也在不断发展，全球拍卖 网站的数量正以惊人的速度增长着。 电子商务协议是面向应用层( 即用户) 的网络安全协议，其主要作用就是 在既不安全又不可靠的网络中，保证通信消息的机密性、完整性、真实性、匿 名性和不可否认性等性质。它是电子商务研究的一个重要方面，是实施电子商 务的技术基础。随着互联网的飞速发展，网络安全问题不断出现并困扰威胁着 人们的生活和生产活动；电子商务活动是深受其影响的一个领域。因此，电子 商务协议的设计和安全性研究成为电子商务最核心的理论和最关键的技术。作 为电子商务的一个重要组成部分，电子拍卖是现实拍卖系统的电子化。随着实 际应用的要求和研究的发展，各种各样的拍卖协议相继出现，各种密码技术也 不断地被运用到协议的设计过程中。经常用到的密码工具有盲签名和公平盲签 名技术、群签名和公平群签名技术、零知识证明理论、不可否认协议、最优公 平交换协议、秘密分享和可验证秘密分享协议、h a s h 函数和h a s h 链技术、多 巾山大学硕士学位论文 方安全计算、百万富翁协议、b i t 承诺等。 群签名技术是设计电子拍卖协议的一个重要工具。群签名的概念是由 c h a u m 和v a nh e y s t 4 两人于1 9 9 1 年提出的，群签名允许群成员代表其所在的 群签名，而除群管理者外的任何人均不知道究竟是群中的哪个成员代表群签了 名。由于群管理者的强管辖能力、签名本身的安全性和群成员的撤销等问题， 群签名往往不能直接被应用到电子拍卖协议的设计中。因此，基于群签名的电 子拍卖协议的研究的文章为数并不多。f 5 n 用一个可转化的群签名方案提出一 个密封式的电子拍卖协议。但是， 5 】中的群签名方案的理论安全性未能得到证 明，而且投标者的身份撤销代价很高，因为如果拍卖中心要撤销某个投标者的 身份，就得重新选择群公私钥对。 6 】的拍卖方案利用的是 7 中的签名方案，虽 然该签名方案在安全性方面得到了证明，但由于其计算量和通信量非常大，使 得拍卖方案的效率很低。 8 n 用的是 9 】中的群签名方案，它利用公告栏技术来 降低计算量和通信量，而且成员也是容易被撤销的。但由于签名长度较长以及 群签名技术在电子拍卖中的应用研究 提出一个新的公开电子拍卖方案。与其他的拍卖方案相比，该拍卖方案不仅满 足了公开电子拍卖的性能要求；而且，由于每个投标者的签名都是一个短群签 名，整个拍卖系统的计算和通信耗费大大降低了。 中山大学硕士学位论文 1 1r s a 模 第1 章预备知识 一个整数刀称为r s a 模，如果以= p q ，p 和q 是大素数，而且p = 2 p + 1 ， q = 2 q + 1 ，其中p 和q 7 也是大素数。 1 2r s a 密钥对 已知r s a 模n ，如果e d 三1 ( m o d ( ，1 ) ) ( 矽( 刀) 为n 的e u l e r 函数) ，则( p ，d ) 称 为r s a 密钥对。 1 3 鲫( ，z ) 子群 q r ( n ) 表示模，z 的所有二次剩余组成的集合，即对于任意的yf t q r ( n ) 有 y o ( m o d n ) 且存在元素x z ：使得少= x 2 ( m o d n ) 。由 9 】知道q 尺( ，1 ) 是z ：的阶为 p q 的循环子群。 1 4 双线性群 g 。和g ：是两个素数阶( 阶数为p ) 的乘法循环群，g ，与g ：分别是g 。与g ： 的生成元；是从g ：到g 。的一个同态映射，且( g ：) = g 。；e 是一个映射p ： g l g 2 一g r ，且e 满足以下性质： ( 1 ) 双线性：对g 。和g 2 中的任意元素u 和v 有e ( u a , v 6 ) = e ( u ，v ) ”，其中以，b z ， 群签名技术在电子拍卖中的应用研究 称( g l ，g 2 ) 是一对双线性群，如果g 。和g 2 中的群运算，映射妙以及双线性映射 e 都是能够有效运算的。 如果g l = g 2 ，就称g 。是一个双线性群。 1 5 函数v ( k ) 是可忽略的 如果对任意的一个多项式p ( ) ，当k 充分大的时候，总有v ( k ) 1 ) ，且它们满足u 。= z ( m o d n ) 。 s r s a 假设：对任意一个多项式时间的概率算法a ，若a 能够解决s r s a 问题，则其成功的概率是可以忽略的。 1 8l r s w 假设 1 5 l r s w 问题：已知群g = ( g ) ，彳( = g ) 和】，( = g y ) ；对任意给定的一个 值m z 。，要求得到一个三元数组( 口，口y ，口”唧) ，其中口g 。 l r s w 假设：如果存在一个多项式时间的概率算法能够解决l r s w 问题， 则其成功的概率是可以忽略的。 5 中山大学硕士学位论文 1 9c d h 假设 1 6 c d h 问题：已知群g 和g 中三个元素组成的数组( g ，g x , g ，) ，要求计算 出g 叫的值。 c d h 假设：对任意的多项式时间的概率算法a ，能够成功解决g 中的 c d h 问题的概率是可以忽略的。 1 1 0d d h 假设 1 6 d d h 问题：已知群g 和g 中四个元素组成的数组( g ，g x ，g v g ：) ，要求 判断等式g 掣= g ：是否成立。 d d h 假设：如果存在一个多项式时间的概率算法a 能够解决d d h 问 题，则其成功的概率是可以忽略的。 显然，在双线性群中，d d h 问题是容易解决的。 1 1 1s d h 假设 1 7 q - s d h 问题：假设g i 和g 2 是两个素数阶( 阶数为p ) 的乘法循环群( g 。 与g 2 可以取一样的群) ，g i 与9 2 分别是g l 与g 2 的生成元。给定一个( q + 2 ) 元 组( g 。，g ：，g ；，g ：7 , 2 ，g ；9 ) ，要求得到一对满足等式彳，= g 。的数组 ( 彳，x ) z ：) 。 q - s d h 假设：不存在一个多项式时间的概率算法能够以不可忽略的概率 解决g 。和g 2 的q - s d h 问题。 。 1 12 线性d i f f i e - h e l l m a n 假设 2 决策线性问题：在群g 。中，g 。是它的生成元，“，v ，h 也是g 。的任意生 成元；( “。，v 6 ，h 。) 是一组给定的数，要求判断等式口+ 6 = c 是否成立。 6 群签名技术在电子拍卖中的应用研究 决策线性假设( l a ) ：不存在多项式时间的概率算法，能够以不可忽略 的概率解决群g ，中的决策线性问题。 线性加密( l e ) 方案：在阶数为大素数p 的群g 。中，“，1 ，h 是g 。的任 意生成元，而且j l l = u 。= ，；公钥为( g l ，u ，y ， ) ，私钥是( x ，y ) ；对任意明文m 加 密后的密文是( 互，互，乃) = “，y b , m h a + b ) ，其中( 口，6 ) 是从z p 中随机选择的；解 密时，利用私钥( x ，j ，) 计算正( 墨。巧) 恢复出明文m 。 线性d i f f i e h e l l m a n 假设：若决策线性假设( l a ) 成立，则线性加密( l e ) 对选择明文攻击来说是语义安全的。 1 1 3 ( k + 1 ) 平方根假设 1 ( k + 1 ) 平方根问题：已知有两个群g 和g r ，g 是双线性群。给定数组 ( g ，口= g x , h l ， 2 ，h z p ；g j + ，t ) 1 12 ，g z 2 ，g 肿“n ) ；要求输出一个满足 a = g ”2 的二元数组( j l ，彳) ，且j i l 萑 j l l i ，h k 。 ( k + 1 ) 平方根假设：如果有一个多项式时间的概率算法能够解决( k + 1 ) 平方根问题，那么其成功的概率是可以忽略的。 1 1 4 公告栏系统( b b s ) 一个公告栏系统是指任何人能够从上面读取信息，但是只有某些合法的组 织才能写入或修改其信息的一个系统。 中山大学硕士学位论文 第2 章群签名技术概述 2 1 群签名技术的研究现状 群签名的概念是由c h a u m 和v a nh e y s t 4 两人于1 9 9 1 年提出的，他们同时 实现了第一个群签名方案。群签名技术允许群成员代表其所在的群签名，而除 了群管理者之外的任何人均不知道究竟是群中的哪个成员代表群签了名。设计 一个群签名方案时，通常要考虑以下几点： 群公钥的长度： 群签名的长度； 群签名算法和验证算法的效率。 自 4 】后，很多改进的群签名方案相继被提出来，0 h 1 s ，1 9 ，2 0 ，2 l ，7 】。其中 【1 8 ，1 9 ，2 0 ，2 1 都有这样的缺点： 群公钥的长度和签名的大小都是取决于群成员的个数， 当有新的成员加入的时候，至少需要修改群公钥。 而【7 】同时运用双离散对数、离散对数表示和离散对数e 次根的知识签名技术克 服了上面的两个缺点，提出第一个公钥和签名的长度都是为固定常数的群签名 方案，而且当新成员加入时，公钥仍然保持不变；每个签名的生成和验证所需 的 史 证 假 d i 密 性 群签名技术在电子拍卖中的应用研究 答模型之下满足【3 】提出的完全匿名性和完全可追踪性；如果应用一个c l 撤销 机制【2 3 】， 2 】也满足了成员的可撤销性。 第一个在标准模型之下可证明安全的群签名方案 3 】是b e l l a r e ，m i c c i a n c i o 和w a r i n s c h i 三人提出的，他们提出利用非交互的零知识技术从任意的数字签名 方案构造群签名的思想。本文的另一贡献就是对群签名的性质做了一个很好的 归一化，提出完全匿名性和完全可追踪性这两个性质：只要这两个性质满足， 而先前提出的诸多性质( 如匿名性、不可伪造性、可追踪性、抗联合陷害性、 不可连接性等) 都能成立。但是，由于非交互的零知识技术的效率问题导致在 实际应用中的效率不高。 2 4 提出了一个标准模型之下的有效群签名方案，其 安全性的证明是基于一个新的强假设。f 2 5 也提出了一个基于c d h 假设的标准 模型下可证明安全的紧凑的群签名方案。 2 5 】中方案采用【2 6 】的分级签名方案的 思想，先对群成员的身份做一次签名，再对待签的消息签名；同时为了隐藏签 名者的身份，还运用 2 7 】【2 8 】中的非交互零知识技术的一个变形：但是，方案的 效率很低。 2 5 提供了一种新的构造群签名的思想，开辟了一条新的研究群签 名技术的道路。 最近几年，基于身份( i d e n t i t y - b a s e d 或i d b a s e d ) 的密码体制理论受到学术 界关注而迅速发展起来。基于身份的密码体制思想 2 9 】是由s h a m i r 于1 9 8 4 年提 出的。其主要观点是：系统中不需要证书，可以使用用户的标识如姓名、i p 地 址、电子邮件地址等作为公钥，用户的私钥通过一个被称作私钥生成器 p k g ( p r i v a t ek e yg e n e r a t o o 的可信任第三方进行计算得到。群签名作为一个重 要的密码技术，基于身份的群签名技术正是一个新的研究方向。自1 9 9 7 年以来， 专家学者们相继提出了很多方案，j t i 3 0 ，3 1 ，3 2 ，3 3 ，3 4 ，3 5 。p a r k ，k i m 和w o n 三 人于1 9 9 7 年提出了第一个基于身份的群签名 3 0 】，但是群公钥和签名的长度与 群成员的个数成正比。1 9 9 8 年，t s e n g 和j a n 提出的基于身份的群签名方案【3 1 是不安全的，可以被伪造的。2 0 0 2 年，p o p e s c u 提出的基于身份的群签名方案 【3 1 是借助于椭圆曲线上的双线性对，但其签名还是用r s a 签名体制。而已知 要达到相同的安全水平，在平均水平下e c c 5 1 2 会比1 5 3 6 0 - b rr s a 快4 0 0 倍。 2 0 0 3 年c h e n ，z h a n g 和k i m 等人提出了一个新的基于身份的群签名【3 3 】，在这 个方案中，采用一个不需要多个分布式的p k g 就能解决密钥托管问题的新的 9 q 山大学硕士学位论文 i d b a s e d 的系统，而且群公钥的长度和签名的长度都和群的大小无关；但是方 案只允许一个密钥对做一次签名，当要进行下一次签名的时候，成员必须重新 注册得到一个新的密钥对。 2 0 0 4 年，h a n ，w a n g 和l i u 等人提出了一个椭圆 曲线上的基于身份的群签名f 3 4 ，虽然群公钥的长度和签名的长度都和群的大 小无关，但是要求成员的i d 是不能暴露成员的真正的身份。2 0 0 5 年w e i ，y u e n 和z h a n g 等人提出了一个新的有效群签名方案 3 5 ，该方案中群管理者、群成 员以及打开身份的机构均是基于身份的。 然而，从双线性对出发，设计一个i d b a s e d 的群签名仍然是一个开放性问 题。原因有以下几点： 1 密钥托管问题由于可信第三方( p k g ) 知道每个成员的密钥，那么 不诚实的p k g 就能够伪造群成员的签名，这是一个致命的缺点。 2 身份匿名性问题作为成员公钥的i d 不能泄漏成员真正的身份信息， 否则群签名的匿名性就不能得到保证。 2 2 群签名方案的模型设计 本小节定义了群签名方案的一般模型。假设q = 只，罡，e ) 是一个群成员 集合，m 是群管理者。群签名方案的模型一般包括五个阶段： 1 系统初始化阶段( s e t u p ) ：给定一个算法，输入一个安全参数，输出主 密钥g m s k 、群公钥g p k ；然后把g m s k 发送给群管理者m 作为追踪签名时的私 钥，公开群公钥g p k 。 2 成员加入阶段( j o i n ) ：群成员和群管理者之间的一个交互协议，该协 议输出每个群成员的证书和私钥伊庀 力；再把c e r t i g s k i 发送给相应的 成员p 。 3 签名生成阶段( s i g n ) ：给定一个概率算法，以待签消息m 、群公钥g p k 和某个成员只的证书c e r t , 和私钥g s k i 为输入，输出消息m 的签名 盯= s i g ( 8 ，m ) 。 | o j 以准确无误地追踪到对应的签名者身上，则称此群签名方案是正确的。 2 完全匿名性( f u l la n o n y m i t y ) 已知一个群签名方案，如果告诉任意的一个具有多项式时间攻击能力的攻击 者a ：待签消息m 、可能对m 签名的两个群成员昂和曰的身份信息( 或者签名 私钥) 和其中一个成员只( b = 0 或者1 ) 对消息，l 的群签名盯= s i 6 ( 忍，m ) ，而 攻击者a 不能判断出盯= s i g ( g ，m ) 对应的签名者是圪，则称该群签名方案是完 全匿名的。我们可以通过游戏l 来详细说明这一性质。在此，我们考虑的攻击者a 中山大学硕士学位论文 的能力是很强的，他可以与所有的群成员勾结。 游戏l ( 1 ) 攻击者a 访问签名算法的系统设置机制( s e t u p ) ，得到群公钥g p k 。 ( 2 ) 攻击者a 可以访问成员加入机制( j o i n ) 得到群成员的证书和签名私 钥，攻击者也可以访问签名打开机制( o p e n ) 。 ( 3 ) 攻击者a 随机选择一个消息m 和两个群成员1 。o 和片的证书和签名私 钥：c e r t o 和g s k o 、c e r t 。和鄹七 1 】，并询问签名算法( s i g n ) 。先随机选择一个 指标b ( b = 0 或者b = 1 ) ，签名算法再生成群签名仃+ = s l g ( g ，m ) ，最后把仃返 回给攻击者。 ( 4 ) 攻击者a 可以继续随机选择消息m ；，访问签名生成算法( s i g n ) ，得 到消息m ；的一个群签名盯；而且攻击者可以访问签名打丌机制。( o p e n ) 得到对 应的签名者身份，要求仃仃。这个步骤可以重复进行。 ( 5 ) 攻击者a 输出一个值b 。如果b 7 = b ，则攻击成功。 如果攻击者a 成功的概率是可以忽略的，则称该群签名方案满足完全匿名 性。 3 完全可追踪性( f u l lt r a c e a b i l i t y ) 已知一个群签名方案，如果一个串谋的群成员组织生成的一个群签名盯 一定能够被追踪到这个串谋组织中的成员身上，而不会被追踪到诚实的签名 者身上；而且当群管理者也参与了串谋活动的时候，这一性质仍然保持，我们 就称此签名方案是完全可追踪的。我们通过游戏2 来详细说明这一性质。 游戏2 ( 1 ) 串谋组织访问系统设置机制( s e t u p ) ，得到群公钥g p k ，群管理者 的主密钥g m s k 。 ( 2 ) 串谋组织随机选择消息m ，询问签名算法( s i g n ) ，得到消息m 的 群签名。 ( 3 ) 串谋组织选择指标f ，访问成员加入机制( j o i n ) ，得到群成员的证 群签名技术在电子拍卖中的应用研究 书和签名私钥，和g s k i 。也就是，此成员加入了串谋组织。 ( 4 ) 串谋组织伪造一个群签名c r 0 。验证算法对该签名做验证，如果通 过验证，游戏则继续进行；如果不通过验证，则宣告失败，停止游戏。 ( 5 ) 利用签名打开算法( o p e n ) 打开伪造的群签名，得到一个签名 者的身份。如果此签名者不是串谋组织里面的成员，则串谋得逞了。如果此 签名者就是里面的成员，则串谋失败了。 如果串谋组织串谋得逞的概率是可以忽略的，则群签名方案就满足了完 全可追踪性。 中山大学硕士学位论文 第3 章电子拍卖系统概述 3 1 电子拍卖协议的研究情况 3 1 1 电子拍卖系统的相关研究 二十世纪末，随着人类信息技术的飞速发展，互联网从一个科研应用的计 算机连网系统发展成为全面商务化的全球信息网，并预示着网络经济时代的到 来。进入新世纪后，在短短的几年时间里，网络经济已经显现出了其广阔的发 展前景，一个全新的网络化商业环境也在逐渐形成和完善。“电子商务” ( e l e c t r o n i cc o m m e r c e 或e l e c t r o n i cb u s i n e s s ) 作为网络经济的一个新生儿，以难 以估量的速度在兴起，并改变着社会经济生活的各个方面。电子商务作为一种 新的经营方式，影响着各行各业，在企业的经营模式、政府的管理模式、人们 的生活方式等各方面进行着类似工业革命的一次信息革命。电子商务是在互联 网上传递信息、产品和服务，进行支付的商务活动，其核心是买卖双方利用数 字过程交易数字产品。电子商务以互联网为支撑平台，可以在提高产品质量和 加快产品服务交付速度的同时降低服务的成本。网上拍卖作为电子商务活动的 一种重要的交易形式，是从1 9 9 5 年e b a y 的建立开始兴起的，并逐渐在全球流 行。十多年来，随着电子商务活动的发展，网站拍卖也在不断发展，全球拍卖 网站的数量e 以惊人的速度增长着。 拍卖最初就是一种某些特殊商品( 如古玩或珍贵的艺术品) 进行交易的方 法，通常这些商品是没有确定的价格的。由于各种不同情景的需要，拍卖的形 式也不尽相同，比如：在一些限量版的商品交易的时候，出价一般是一个比一 个高的；而在购买个人计算机的时候，随着时间的推移，价格一般是一点一点 地降低的；而在一些大型的购买或工程竞标的时候，为了保护投标者的利益， 出价不是公开的而是秘密的。电子拍卖是现实拍卖系统的电子化，是电子商务 活动的一个重要组成部分。随着各种应用环境的变化和电子拍卖研究的发展， 1 4 群签名技术在电子拍卖中的应用研究 各种各样的电子拍卖协议相继出现了。一般地，电子拍卖方式分为英式拍卖、 荷式拍卖、第一价位的密封式拍卖和第二价位的密封式拍卖。 英式拍卖是目前拍卖活动使用最多的一种方式。这主要是因为：投标者可 以自己根据市场决定价格，活动规则很好地反映市场竞争机制。在英式拍卖中， 投标者的出价是公开的，而且可以多轮投标，新一轮的出价要比前一轮确定出 的最高价高，当最高价位的投标者只有一个人的时候，投标结束；最后确定的 最高价位者就是中标者，他以此最高价把商品买走。由此也可以看出要确定出 最终的中标者，要花费较多的时间。由于网络对信息的巨大搜集能力，保护投 标者的个人信息( 如个人交易历史记录和购买意愿等) 将是非常重要的。因此， 要求英式拍卖中，投标者是匿名投标的。对英式拍卖协议的研究较多，有 3 6 ，3 7 ，3 8 ，3 9 ，4 0 ，4 1 ，6 ，4 2 1 等。 3 6 要求投标是实时的。 3 7 ，3 8 只是列出了几种设计 英式拍卖的方法，而没有考虑到公开电子拍卖的安全性要求。【3 9 采用h a s h 链 技术提出的英式拍卖方案解决t 4 0 1 中未实现的可公开验证的性质。【4 1 的拍卖 方案利用h a s h 链技术来实现拍卖的公平性。但是， 4 1 存在着两个缺点：一是 拍卖行a m 能从标书中知道投标者的身份，二是投标点的离散分布带来的多次 计算等问题。n g u y e n 和t r a o r 6 两人提出一个基于群签名的英式拍卖方案【6 】，但 是该方案存在者效率低下和投标者撤销困难的问题。我们将在4 2 节中详细讨 论 6 】中的方案。 第一价位的密封式拍卖中，投标者是一次性提交标书，而且出价是秘密的， 价格隐藏在标书之中；在打开标书阶段，拍卖行确定出最高价位及相应的投标 者；最后，最高价位投标者以此价位买走拍卖品：由于标价是密封的，除了中 标者之外，其他投标者的出价都没有泄漏出去，这就保护了投标者的隐私性。 对于密封式的拍卖来说，如何确定最高价位是一个关键问题，目前采用的方法 也是多种多样的。密封式的电子拍卖因常用到更多的密码工具而被认为更有挑 战性，因此出现了很多相关的研究，如 5 ，4 3 ，4 4 ，4 5 ，4 6 ，4 7 ，4 8 ，4 9 ，5 0 ，5 l ，5 2 】。为了 保证标书的匿名性，密封式拍卖常常采用多个拍卖管理者共同主持拍卖活动来 限制各自的权利。 4 3 ，4 4 ，4 5 ，4 6 等方案要求标书 4 3 ，4 4 ，4 5 或者打开函数 4 6 1 利用 秘密共享技术【5 3 】把信息提交给多个拍卖行。然而，利用秘密共享技术的时候， 在特定的情况下，秘密就会被泄漏出去，从而破坏了匿名性；而且多个拍卖管 中山大学硕士学位论文 理者的存在要求更多的计算量【4 6 】和通信量 4 3 ，4 4 ，4 5 。尽管方案 4 7 ，4 8 实现了 a m 的匿名性，但是所有的标书在开标阶段都被打开了，因此对于未中标者来 说，秘密性就得不到保证。 4 9 ，5 0 使用两个拍卖管理者，但是 4 9 】并未实现单个 拍卖管理者的匿名性，而且还泄漏了所有投标者的顺序。 5 , 4 4 ，4 5 ，4 6 ，4 9 ，5 0 ，5 1 ，5 2 】 的密封式电子拍卖方案中，事先确定好了投标的价位列表，投标者的出价只能 是这个列表中的某个值。f 5 1 ，5 2 采用单向h a s h 函数和h a s h 链技术来降低了计算 复杂度。f 5 ，4 5 ，5 1 ，5 2 方案中的标书的大小依赖于价位表中的价位的数目，而 4 9 ，5 0 贝l j 对此做了改进。 4 6 应用消息加密的思想提交标书，但是这样使得开标 时需要花费很多时间。 第二价位的密封式拍卖也称为v i c k r e y 拍卖。1 9 6 1 年经济学家v i c k r e y 结合 英式拍卖与密封式标价拍卖的优点，设计出了一种新的拍卖方式第二价位 拍卖 5 4 1 。在第二价位拍卖系统中，投标者也是一次性地秘密地把标价提交给 拍卖行，第一价位( 最高价格) 提交者中标，但中标者只付出第二价位( 次高 价位) 的价格。第二价位原理支持商品分配最优化的特点，v i c k r e y 因此获得了 1 9 9 6 年的n o b e l 经济学奖。理想的拍卖模式应该是第二价位的拍卖。因此许多 学者对v i c k r e y 拍卖的性质进行了研究，并提出了诸多成果，如 5 5 ，5 6 ，5 7 ，5 8 ，5 9 ，6 0 等。1 9 9 5 年，v a r i a n 等人提出了广义的v i c k r e y 拍卖( g v a ) ，它解决了组合分 配问题( c a p ) ，即“如果同时得到b 而只想要a ”。2 0 0 1 年，k i k u c h i 提出了 m + i 价位拍卖的安全协议【5 5 】。该协议可用于多个同种商品的拍卖，m 个最高 价位投标者获胜得到商品，但他们只付出m + i 价位。m + i 价位拍卖是v i c k r e y 拍卖的一种推广：当m = i 时，该拍卖模式就成为v i c k r e y 拍卖。 3 1 2 电子拍卖协议的分类 电子拍卖协议按照不同的标准有多种分类方法，下面介绍几种常见的分类： 1 ) 按照拍卖叫价的方式分为：价格递增拍卖( 英式拍卖) ，价格递减拍卖 ( 荷式拍卖) 。 2 ) 按照标价是否公开分为：公开标价拍卖和密封式标价拍卖。 3 ) 按照拍卖进行的轮数可分为：单轮拍卖( 如密封式标价拍卖) 与多轮拍 卖( 英式拍卖，荷式拍卖) 。 1 6 群签名技术在电子拍卖中的应用研究 ) 拍卖( 如英式拍卖和荷式 4 ) 按照获胜价位可分为：第一价位( 最高价位 拍卖) 和第二价位拍卖。 5 ) 按照投标次数可分为：单标价拍卖和多标价拍卖。单标价拍卖投标者只 进行一次投标，通讯时间少，效率高；然而风险也高。多标价拍卖进行实时考 虑，风险低，但通讯时间长。 6 ) 按照拍卖成交的次数可分为：单级拍卖和分级拍卖。在某些情况下，有 必要先进行子拍卖，子拍卖的胜利者进入下一级拍卖。 7 ) 按照拍卖标的物的个数可分为：单个物体的拍卖和组合拍卖。 3 2 电子拍卖系统的模型 一般情况下，电子拍卖方案的具体过程可以分为以下四个步骤。( 符号说明： r m 表示注册中心，a m 表示拍卖行，q = 届，色) 表示，1 个投标者集合。) 1 拍卖系统设置阶段( s e t u p ) 注册中心r m 和拍卖行a m 选择参数并公布这些参数及有关拍卖品的信息 ( 如拍卖编号、拍卖时间等) 。r a m 主要负责用户的身份管理工作，只有r m 承 认后的用户才能参加拍卖活动：a m 主持着整个拍卖活动的进行，投标者向a m 提交标书。 2 注册认证阶段( r e g i s t r a t i o n ) 每个用户发送其相关的身份信息到注册中心r m 进行注册，r m 向合法的 用户颁发一个证书，只有成功注册后的用户才能参加拍卖活动。 3 投标阶段( b i d d i n g ) 投标者8 利用其拍卖私钥进行投标，向拍卖行a m 提交标书。 4 中标者确定阶段( w i n n e ra n n o u n c e m e n t ) 拍卖行与注册中心通过计算判断得到中标者的身份及出价，并通知给商家。 3 3 电子拍卖系统的性能要求 对于一个电子拍卖协议，我们从以下几方面来考虑其性能。 巾山大学硕十学位论文 a 拍卖的公平性( f a i r n e s s ) 所有的投标者地位一样，没有一方比其他方有更有利的条件。特别地，对 于公开的电子拍卖来说，可以从两个方面来考虑：一是拍卖行不能否认任何一 个高于当前价位的合法标书，二是拍卖行不能否认某一个投标者的标书。 b 不可伪造性( b i du n f o r g e a b i l i t y ) 投标者的投标不能被伪造，即使a m 和r m 相互勾结也不能伪造投标者的 标书。 c 投标者的匿名性( b i d d e ra n o n y m i t y ) 投标者的身份必须保密，无论是公开的电子拍卖还是密封式的电子拍卖， 从标书上都不能判断出相应的投标者的身份。 d 标价保密性( b i ds e c r e c y ) 投标者的标价必须保密，这个性质是对密封式的电子拍卖而言的，也就是 说从投标者提交的标书是判断不出投标者的标价以及投标者的身份等信息。 e 不可否认性( w i n n e rn o n r e p u d i a t i o n ) 根据标书，中标者不能否认自己的投标，而且其身份能够被追踪到。 不可联系性( b i d su n l i n k a b i l i t y ) 其他参与者无法将同一个投标者的两次投标联系在一起。对于多轮的电子 拍卖，这个性质分为两种情况考虑：在同一轮投标中，同一个投标者的两次投 标是能够被联系在一起的；而不同轮的任何两个投标是不可联系的。 g 可公开验证性( p u b l i cv e r i f i a b i l i t y ) 广义地说，可公开验证性要求拍卖活动的有效性是任何人都能验证的；狭 义地说，可公开验证性要求中标者的合法性是能够被验证的。 h 可追踪性( t r a c e a b i l i t y ) 投标者投标后不能否认其投标，在需要的时候，标书能够被打开从而得到 相应的投标者身份。 i 拍卖的效率( e f f i c i e n c y ) 高效是一个好的电子拍卖协议不可缺少的性能。 公开标价的电子拍卖方案满足性质a ，b ，c ，e ，f ，g ，h ，i ；密封式的电 子拍卖一般要满足性质a ，b ，c ，d ，e ，g ，h ，i 。 群签名技术在电子拍卖中的应用研究 3 4 设计电子拍卖系统的各种技术 根据电子拍卖系统的性能要求，凡是能够实现参与者身份保密、防止参与 者抵赖的技术和手段以及预防作弊和违约的办法都可以用来设计安全的电子拍 卖方案。从已经发表的有关文献看，常用到的基本工具有：盲签名和公平盲签 名技术、群签名和群盲签名技术、零知识证明理论、不可否认协议、最优公平 交换协议、秘密共享和可验证秘密分享协议、h a s h 函数和h a s h 链技术、多方 安全计算、百万富翁协议、b i t 承诺等。 6 l 】曾介绍了其中的一些技术，本文在 此基础之上又介绍了秘密共享技术和h a s h 技术。 ( 1 ) 群签名和群盲签名技术 一个群签名方案允许群中成员代表其所在的群对信息进行匿名签名，但只 有群管理者能够在发生争议时给出签名者的身份，而任何其他方不知道签名者 的身份。本文第2 章和第4 章分别对群签名技术及其在电子拍卖系统中的应用 情况做详细的介绍。群盲签名技术就是群签名技术和盲签名技术结合起来的一 种签名方案【6 2 】。一个群盲签名方案除了具有群签名的特征外，签名还具有盲 性。如果签名者后来发现了自己的签名，他也不知道他什么时候为谁签发了该 签名。群盲签名被广泛地应用于电子商务【6 3 的各个方面，例如，可以把这种 签名技术应用于安全的分布式电子银行、安全的具有多个选举中心的电子选举 和安全电子拍卖协议设计中。 ( 2 ) 零知识证明 零知识证明理论【6 4 】首先由g o l d w a s s e r ，m i c a l i 和r a c k o 等提出，它是一种 交互式概率证明方法，示证者( p r o v e r ) 能使验证者( v e r i f i e r ) 相信他确实掌 握某种信息而不暴露该信息。而且在零知识证明过程完成后，验证者无法单独 使第三方相信示证者掌握该信息。z e r o - k n o w l e d g es y s t e m si n c 6 5 根据零知识证 明理论等设计的零知识证明系统为客户提供了比较广泛的隐私和安全产品及服 务，它为消费者和商业行为提供了安全和个人隐私工具和策略。 ( 3 ) 不可否认协议 6 6 】 不可否认协议能够使通信双方交换信息，而在交换后双方无法抵赖。每一 个参与者在通信的同时都收集有证据，这些证据将来能够在法庭上证明双方确 1 9 中山大学硕士学位论文 实发送或接受了某种信息。同认证协议和密钥交换协议相比，不可否认协议并 不关心两个互相信赖的实体通信时攻击者是否出现，而是用来解决在相互不完 全信赖的情况下需要通信时的自我保护问题。不可否认协议被广泛地应用在不 会被单方或第三方操纵的、而一方有可能不诚实的被动通信中，因而可用在安 全电子拍卖方案的设计 5 中，以防止中标人的抵赖行为。 ( 4 ) 最优公平交换协议 6 7 】 最优公平交换协议允许两个互不信赖的实体以一种公平的方式交换信息， 在协议进行后，要么双方都得到了对方的信息，要么都没有得到双方的信息。 被交换的信息的形式可以是一个文件，也可以是一个签名，还可以为别的形式。 最优公平交换协议假定离线可信赖第三方( t t p ) 的存在，但t t p 仅在出现争 议的情况下才出现。最优公平交换协议利用了可验证的加密技术：可验证的加 密由使用t t p 的公钥加密的密文和一个非交互式的证明组成，该证明指出和密 文相对应的明文是真的。最优公平交换协议可用于电子商务的很多领域 6 7 ，6 8 ， 在安全拍卖系统中，最优公平交换协议一般用在宣布结果阶段，用来确定中标 者身份的真实性 6 9 】。 ( 5 ) 秘密共享和可验证秘密分享协议 秘密共享的概念 5 3 】是由s h a m i r 提出的，秘密分享系统是将秘密s 在一组 参与者p 中进行分配。目前常用的是( f ，z ) 门限秘密共享机制，也就是将秘密s 分 成以份并分配给甩个参与者，使得p 的任何的成员子集a ( 1 a i t ) 能够重构秘 密s ，而任何成员子集b ( 1 b l t ) 不能重构秘密s 。在电子拍卖系统中，秘密 共享技术成为一种实现投标者匿名和标价