（计算机软件与理论专业论文）陷门承诺、陷门hash函数及其应用研究.pdf

陷门承诺、陷f - h a s h 函数及其应用研究摘要 论文题目：陷门承诺、陷f h a s h 函数及其应用研究 专业：计算机软件与理论 博士生：伍春晖 指导教师：龙冬阳教授陈晓峰副教授 摘要 承诺( c o m m i t m e n t ) 是一个重要的密码原型，它提供隐藏性和绑定性两个基本性 质，成为现代密码学许多协议和应用的重要构造元素，如零知识证明、数字签名、身 份鉴别、电子投票、电子拍卖等。承诺方案包括承诺和打开两个阶段，在发送者对消 息做出承诺而在打开之前，承诺的消息对于接收者是隐藏的，即接收者无法从承诺值 中获得相应的消息；在打开阶段中，发送者无法打破绑定性，即发送者无法改变之前 承诺的消息。陷门承诺( t r a p d o o rc o m m i t m e n t ) 是一种特殊的承诺方案，其允许知道 陷门信息的人以不同的方式打开承诺，即在给定陷门信息的条件下，陷门承诺方案不 满足传统承诺方案的绑定性。陷门承诺与陷f h a s h 函数的概念密切相关，陷f - h a s h 函数 使用一些特定的信息来产生一个固定的h a s h 值，陷门承诺的不同打开对应于陷f h a s h 函 数的不同碰撞。本文对基于i d 的陷门承诺、承诺的非延展性、陷f 3 h a s h 函数的密钥泄 露性、陷f - h a s h 函数在数字签名中的应用及陷门承诺在电子商务( 电子投票电子拍 卖) 中的应用进行了系统的研究，并取得了相应的研究成果。 1 在研究承诺方案的安全定义、安全模型及敌手模型的基础上，提出基于i d 的非延 展陷门承诺的新概念并构造了两个有效的方案。之前文献定义的基于i d 的陷门承 诺只针对某一个特定的i d ，即其公开参数与某一特定的i d 相关，不满足基于i d 的 密码系统的要求，我们修正了这一定义。结合构造多陷门承诺的思想和构造非延 展承诺的技术，我们首次提出了两个基于离散对数系统的有效的基于i d 的非延展 陷门承诺方案，分别基于随机预言模型和标准模型。 2 以往的在线离线门限签名方案往往存在密钥泄露问题，从而在离线阶段必须为 一i 陷门承诺、陷f - h a s h 函数及其应用研究摘要 每个消息计算相应的陷f h a s h 和签名，计算和存储开销仍过大。本文利用无密钥 泄露的陷f h a s h 函数，提出了一个新颖有效的在线离线门限签名方案，由于陷 f h a s h 值可以重复使用，从而大大降低了计算和存储复杂度。 3 为了提高聚合签名的响应速度，本文提出在线离线聚合签名的新概念。然而， 如果直接利用密钥泄露的陷f - h a s h i 函数构造在线离线聚合签名方案，仍然存在计 算和通信开销过大的问题。本文利用无密钥泄露的陷f h a s h 函数，构造了一类有 效的在线离线聚合签名方案，从而在突发性的聚合签名需求中有较好的应用。 4 最后，我们讨论了陷门承诺在无收据电子投票电子拍卖中的应用，指出一类采 用密钥泄露的陷门承诺构造的电子投票和电子拍卖方案并不满足其声称的无收据 性。同时，我们提出指定验证者可链接环签名的新概念，利用陷门承诺构造了一 个具体的方案，并基于此签名构造了一个新的无收据电子投票方案。 关键词：陷门承诺、陷f h a s h 函数、变色龙h a s h 函数、基于i d 的陷门承诺、非延展、无 密钥泄露、在线离线签名、电子商务 i i 陷门承诺、陷f - h a s h 函数及其应用研究a b s t r a c t t i t l e ： m a j o r ： n a m e ： t r a p d o o rc o m m i t m e n t ，t r a p d o o rh a s ha n dt h e i ra p p l i c a t i o n s c o m p u t e rs o f t w a r ea n dt h e o r y c h u n h u i 、v u s u p e r v i s o r ：p r o f e s s o rd o n g y a n gl o n ga n da s s o c i a t ep r o f e s s o rx i a o f e n gc h e n a b s t r a c t c o m m i t m e n ti sa ni m p o r t a n tc r y p t o g r a p h i cp r i m i t i v e ，i tp r o v i d e st w ob a s i cp r o p e r - t i e sa sh i d i n ga n db i n d i n g c o m m i t m e n tm a k e su pa ni m p o r t a n tb u i l d i n gb l o c kf o rm a n y s c h e m e sa n da p p l i c a t i o n si nm o d e r nc r y p t o g r a p h y , s u c ha sz e r o - k n o w l e d g ep r o o f ，d i g i t a l s i g n a t u r e ，i d e n t i f i c a t i o n ，e - v o t i n g ，e - a u c t i o na n ds oo n ac o m m i t m e n ts c h e m ec a nb e d i v i d e di n t ot w op h a s e sa sc o m m i t m e n tp h a s ea n do p e n i n gp h a s e a f t e rt h es e n d e rc o i n - m i t t i n gt oam e s s a g e ，t h em e s s a g ek e e p sh i d i n gu n t i lh eo p e n si t ，s ot h er e c e i v e rc a ng e t n o t h i n gf r o mt h ec o m m i t m e n t o nt h eo t h e rh a n d ，t h es e n d e rc a n n o tb r e a kt h eb i n d i n g p r o p e r t yi nt h eo p e n i n gp h a s e ，t h a ti s ，h ec a n n o tc h a n g eh i sm e s s a g ec o m m i t t e dp r e v i o u s l y t r a p d o o rc o m m i t m e n ti sac o m m i t m e n ts c h e m ew i t hs p e c i a lp r o p e r t i e s ，t h a ti s ， o n ew i t ht h et r a p d o o rk e yc a no p e nh i sc o m m i t m e n ti nd i f f e r e n tw a y s ，i no t h e rw o r d s ， g i v e nt h et r a p d o o rk e y , t h i st r a p d o o rc o m m i t m e n td on o ts a t i s f yt h eb i n d i n gp r o p e r t ya s t r a d i t i o n a lc o m m i t m e n ts c h e m e s t r a p d o o rh a s hi san o t i o nc l o s e l yr e l a t e dt ot r a p d o o r c o m m i t m e n t i tc o m p u t e sah a s hv a l u ef o rs o m eg i v e ni n f o r m a t i o n ，a n dd i f f e r e n to p e n i n g s i nt r a p d o o rc o m m i t m e n tc o r r e s p o n d i n gt oc o l l i s i o n si nt r a p d o o rh a s h t h i st h e s i si n v o l v e s o u rs y s t e m a t i cr e s e a r c hi ni d b a s e dt r a p d o o rc o m m i t m e n t ，t h en o n - m a l l e a b i l i t yo fc o m - m i t m e n t ，t h ek e y - e x p o s u r ep r o b l e mo ft r a p d o o rh a s h ，a n dt h ea p p l i c a t i o n so ft r a p d o o r h a s ha n dt r a p d o o rc o m m i t m e n ti nd i g i t a ls i g n a t u r e sa n de - c o m m e r c e ( s u c ha se - v o t i n g a n de - a u c t i o n ) o u rc o n t r i b u t i o n si n c l u d e ： 1 b a s e do nt h er e s e a r c ho fs e c u r i t yd e f i n i t i o n ，s e c u r i t ym o d e la n da d v e r s a r ym o d e l i nt r a p d o o rc o m m i t m e n t s ，w ed e f i n ean e wn o t i o nn a m e di d b a s e dn o n - m a l l e a b l e i i i 陷门承诺、陷f - h a s h 函数及其应用研究a b s t r a c t t r a p d o o rc o m m i t m e n ta n dp r o p o s et w oe f f i c i e n ts c h e m e s t h ed e f i n i t i o no fi d b a s e d t r a p d o o rc o m m i t m e n ti np r e v i o u sw o r k si sf o ro n es p e c i f i ci do n l y , w h i c hc a n n o t s a t i s f yt h er e q u i r e m e n to fi d b a s e dc r y p t s y s t e m ，s ow em o d i f yt h i sd e f i n i t i o n t h e n w eu s et h ei d e ao fc o n s t r u c t i n gm u l t i t r a p d o o rc o m m i t m e n ta n dn o n - m a l l e a b l ec o m - m i t m e n tt oc o n s t r u c tt h ef i r s tt w oe f f i c i e n ti d b a s e dn o n - m a l l e a b l et r a p d o o rc o m - m i t m e n ts c h e m e sb a s e do nd i s c r e t el o g a r i t h m ( d l ) s y s t e m ，w i t h w i t h o u tr a n d o m o r a c l er e s p e c t i v e l y 2 p r e v i o u so n - l i n e o f f - l i n et h r e s h o l ds i g n a t u r es c h e m e sa l w a y sh a v et h ek e y - e x p o s u r e p r o b l e m ，a n dw eh a v et oc o m p u t eat r a p d o o rh a s ha n dt h ec o r r e s p o n d i n gs i g n a t u r e f o re v e r ys i g n e dm e s s a g e ，s ot h ec o m p u t a t i o na n ds t o r a g ec o s ta r eal i t t l em o r e o v e r l o a d w ec o n s t r u c tan e we f f i c i e n to n l i n e o f f - l i n et h r e s h o l ds i g n a t u r es c h e m e u s i n gk e y - e x p o s u r ef r e et r a p d o o rh a s h ，w h i c hr e d u c e st h ec o m p u t a t i o na n ds t o r a g e c o s te v i d e n t l y , b e c a u s et h et r a p d o o rh a s hc a nb er e u s e da n dt r e a t e da sp u b l i ck e y 3 i no r d e rt oi m p r o v et h er e s p o n s ee f f i c i e n c yo fa g g r e g a t es i g n a t u r e s ，w ep r o p o s ea n e wn o t i o no fo n - l i n e o f f - h n ea g g r e g a t es i g n a t u r e h o w e v e r ，i fu s i n gk e y - e x p o s u r e t r a p d o o rh a s ht oc o n s t r u c tt h es c h e m ed i r e c t l y , t h ec o m p u t a t i o na n ds t o r a g ec o s t a r ea l s oo v e r l o a d w ec o n s t r u c ta ne f f i c i e n ts c h e m eu s i n gk e y - e x p o s u r ef r e et r a p d o o r h a s h s oi th a si m p o r t a n ta p p l i c a t i o n si na g g r e g a t es i g n a t u r e sw i t hb u r s t yt r a f f i c 4 w ed i s c u s st h ea p p l i c a t i o n so ft r a p d o o rc o m m i t m e n t si nc o n s t r u c t i n gr e c e i p t f r e e v o t i n ga n da u c t i o ns c h e m e s w ep o i n to u tt h a ts o m et y p e so fv o t i n ga n da u c - t i o ns c h e m e sc o n s t r u c t e db yk e y - e x p o s u r ef r e et r a p d o o rc o m m i t m e n t sa r en o tr e a l l y r e c e i p t f r e e i na d d i t i o n ，w ep r o p o s ean e wn o t i o no fl i n k a b l er i n gs i g n a t u r e f o r d e s i g n a t e dv e r i f i e r sa n dc o n s t r u c tac o n c r e t es c h e m eu s i n gt r a p d o o rc o m m i t m e n t ， t h e nw ec o n s t r u c tan e wr e c e i p t - f r e ev o t i n gs c h e m eb a s e do nt h i ss i g n a t u r e k e yw o r d s ：t r a p d o o rc o m m i t m e n t ；t r a p d o o rh a s h ；c h a m e l e o nh a s h ；i d b a s e dt r a p d o o r c o m m i t m e n t ；n o n - m a l l e a b l e ；k e y - e x p o s u r ef r e e ；o n - l i n e o f f - l i n es i g n a t u r e ；e - c o m m e r c e i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 学位论文作者签名：焦盔堡 日期：型l q ：6 ：3 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质 版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检 索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：伍各晖 日期：2 0 lo 年6 月弓曰 导师签名：态鎏黔盯 日期：乙p 【u 年6 月；日 陷门承诺、陷f h a s h 函数及其应用研究第1 章引言 第1 章引言 承诺( c o m m i t m e n t ) 是一个重要的密码原型，它提供隐藏性和绑定性两个基本性 质，成为现代密码学许多协议和应用的重要构造元素，如零知识证明、数字签名、身 份鉴别、电子投票、电子拍卖等。 1 1 课题背景 直观上看，我们可以把承诺方案描述为一个带锁的铁盒子。在承诺阶段，发送者 把消息放进盒子里，锁上之后交给接收者。一方面，接收者不能打开盒子以取得消 息；另一方面，发送者也不能改变消息。前一个性质称为隐藏性，后一个性质称为绑 定性。在打开阶段中，发送者把盒子的钥匙交给接收者，从而接收者可以打开盒子揭 开原始消息。更严格的说，一个承诺方案是两个概率多项式时间的算法( 发送方和接 收方) 之间所进行的一个交互式的协议，它包括两个阶段：1 、在承诺阶段，发送方输 入消息m 和冗余值r ，计算对消息m 的承诺值c 并将c 发送给接收方。2 、在打开阶段， 发送方泄露消息m 和冗余值r 给接收方，使得接收方相信c 确实是对消息m 的承诺。根 据发送方( 接收方) 是否具有无限计算能力，承诺方案可以分为无条件绑定( 隐藏) 和基于计算假设的绑定( 隐藏) 。一个承诺方案不能同时满足无条件绑定和无条件隐 藏。 陷门承诺( t r a p d o o rc o m m i t m e n t ) 是一种特殊的承诺方案，该概念由b r a s s a r d 等 人 1 于1 9 8 8 年首先提出。陷门承诺方案一个特有的性质是它允许知道陷门信息的人以 不同的方式打开承诺，即在给定陷门信息的条件下，陷门承诺方案不满足传统承诺方 案的绑定性，所以也称为变色龙承诺( c h a m e l e o nc o m m i t m e n t ) 。在陷门承诺的基础 上，k r a w c z y k 等人于2 0 0 0 年首次提出了陷f h a s h 函数 2 】( 也称为变色龙h a s h 函数) 的 概念。这两个概念的主要区别在于陷门承诺方案分为“承诺和“打开 两个阶段， 而陷f h a s h 函数使用一些特定的信息来产生一个固定的h a s h 值。然而，这两个概念又密 切相关，正女i l k r a w c z y k 等人所指出，一个陷门承诺方案在非交互的承诺阶段自然诱导 一个陷f - h a s h 函数，反之亦然。而且，陷门承诺方案中不同的打开方式恰好对应了陷 一1 一 陷门承诺、陷f h a s h 函数及其应用研究第1 章引言 f h a s h 函数不同的碰撞。 陷门承诺和陷f - h a s h 函数在现代密码学的许多领域中有着重要的应用。首先，陷 门承诺方案可以用来构造零知识证明协议，而b r a s s a r d 等人提出陷门承诺的概念最初就 是为了用于零知识证明系统中。在此之后，许多学者利用陷门承诺方案设计了各种用 途的零知识证明协议 娜】。最初的研究只考虑单个证明者和验证者之间的协议，在分 布式计算环境中d w o r k 等人 7 首先提出了同时零知识( c o n c u r r e n tz e r o - k n o w l e d g e ) 的 概念，它允许验证者并行地与多个证明者交互。d ic r e s c e n z o 等人 8 利用陷门承诺方案 提出了一个高效的同时零知识证明协议。c a n e t t i 等人提出重置零知识( r e s e t t a b l ez e r o - k n o w l e d g e ) 9 的概念，允许验证者把证明者重置到之前的某一步。类似的，b e l l a r e 等 人f 1 0 】通过陷门承诺实现了安全的重置身份鉴别协议。随后进一步的研究直接导致了 一些陷门承诺新概念的提出如多陷门承诺 1 1 1 ( m u l t i - t r a p d o o rc o m m i t m e n t ) 、混和承 诺 1 2 1 ( h y b r i dc o m m i t m e n t ) 等，而这些承诺方案反过来又促进了零知识证明技术的 发展。d a m g a r d 1 3 对承诺方案和零知识证明协议之间的关系和研究进展给出了一个很 好的综述。他们之间的一个等价关系见 1 4 1 。 陷门承诺在设计非延展的承诺方案中有重要的应用。d o l e v 等人 1 5 1 于1 9 9 1 年首次 提出了非延展的承诺的概念，而且基于单向函数给出了一个非延展的承诺方案。然 而，该方案需要复杂的交互式的零知识证明，因此不实用。在公用随机串模型下，d i c r e s c e n z o 等人1 6 1 给出了第一个非交互式的非延展的承诺方案。但是该方案的效率也 只具有理论上的价值。在公用参数模型下，f i s c h l i n 等人 17 首次给出了交互式的基于 标准假设( 如r s a 假设、离散对数假设) 的非延展的承诺方案。随后，d ic r e s c e n z o 等 人【1 8 给出了非交互式的基于标准假设的非延展的承诺方案。近来，对于非延展承诺所 依赖的密码学基础，学者们进行了深入的研究。1 9 i 正日月在单向函数存在的假设下，同 时非延展承诺方案存在。f 2 0 1 证明在单向函数存在的假设下，统计上隐藏的非延展承诺 方案存在。 陷门承诺和陷f - h a s h 函数在构造某些安全的数字签名中有着重要的作用。他们 在设计无需随机预言假设的签名方案中有重要的作用 2 1 ，2 2 】。另外，陷f h a s h 函 数可以用于构造变色龙签名f 2 。变色龙签名可以看作是一个非交互的不可否认签 名，可以更简单和更有效的实现不可传递性和不可否认性，从而在版权保护、匿 一2 一 陷门承诺、陷f h a s h 函数及其应用研究第1 章引言 名信用证书 2 3 2 5 1 中有着更广泛的应用。陷f h a s h 函数还可以用来构造在线离线签 名f 2 6 ，2 7 1 。在线一离线签名将一个签名过程分为两个阶段：1 、离线阶段，在签名消 息给出前就进行预计算；2 、在线阶段，即在签名消息给出后，计算对应的签名。 由于在线阶段一般只需要1 次模乘( m o d u l a rm u l t i p l i c a t i o n ) 运算，所以即使在一个 较弱的处理器( 如智能卡) 下也可以非常快的完成签名运算。目前，智能卡已广泛 地应用在移动电话、p d a 、银行卡等设备中，所以在线一离线签名在现实中有着非 常重要的应用价值。然而，传统的陷门承诺方案和陷f h a s h 函数一般都存在所谓的 密钥泄漏问题f 2 8 】，因此限制了它在实际中的进一步应用。陈晓峰等人 2 9 基于g a p d i f f i e - h e l l m a n 群于2 0 0 4 年给出了第一个完全的无密钥泄露的陷f h a s h 函数和对应的变 色龙签名方案。后来a t e n i e s e 等人f 3 0 1 对此工作进行了推广。同理，在线一离线签名中也 存在密钥泄漏的问题，该问题由陈晓峰等人 3 1 在2 0 0 7 年首次提出并解决。近来，在 线一离线签名一个新的安全模型被提出【3 2 ，3 3 。 ， 陷门承诺在安全电子商务协议中也有重要的应用。例如，密封式标价拍卖中要求 竞标结束前拍卖行不能知道投标者的标价，同时竞标结束后投标者不能改变其标价。 普通承诺方案的隐藏性和绑定性刚好满足此应用，而陷门承诺方案的特性使得它可以 进一步用来设计无收据的电子投票和电子拍卖协议 3 4 3 6 】。由于投票者( 投标者) 可 以利用陷门信息任意的打开承诺，从而无法构造一个证据来证明他提交了特定的选票 ( 标价) ，这样就防止了协议中的犯罪行为如买卖选票( 串标) 、强迫选举( 强迫投 标) 等。此外，陷门承诺方案在合同签署协议 3 7 ，3 8 中也有着重要的作用。 此外，陷门承诺在安全多方计算 3 9 】中也有着重要的应用。j a k o b s s o n 等人 4 0 应用 陷门承诺设计指定验证者证明系统，使证明者在向验证者证明某一陈述时，验证者无 法传递这一证明使其他人相信这一陈述。c a n e t t i 和f i s c h l i n 4 1 】以及d 锄g a r d 和n i e l s e n 4 2 应 用陷门承诺构造了广义可复合承诺方案，即此承诺方案可以和其他安全的方案安全地 复合。 1 2 研究内容 本文主要研究陷门承诺、陷f h a s h 函数及其在数字签名与安全电子商务协议中的 应用。 一3 一 陷门承诺、陷f - h a s h 函数及其应用研究 第1 章引言 在研究承诺方案的安全定义、安全模型及敌手模型的基础上，提出基于i d 的非延 展陷门承诺的新概念并构造了两个有效的方案。 4 3 中定义的基于i d 的陷门承诺 只针对某一个特定的i d ，即其公开参数与某一特定的i d 相关，不满足基于i d 的 密码系统的要求，我们修正了这一定义。结合构造多陷门承诺的思想 1 l ，4 4 和 构造非延展承诺的技术【l7 ，我们首次提出了两个基于离散对数系统的有效的基 于i d 的非延展陷门承诺方案，分别基于随机预言模型和标准模型。 以往的在线离线门限签名方案 4 5 往往存在密钥泄露问题，从而在离线阶段必须 为每个消息计算相应的陷f h a s h 和签名，计算和存储开销仍过大。本文利用3 1 1 中 无密钥泄露的陷f h a s h 函数，提出了一个新颖有效的在线离线门限签名方案，由 于陷f h a s h 值可以重复使用，从而与 4 5 中的方案相比，大大降低了计算和存储复 杂度。 为了提高聚合签名的响应速度，本文提出在线离线聚合签名的新概念。然而， 如果直接利用密钥泄露的陷门h a s h 函数构造在线离线聚合签名方案，仍然存在计 算和通信开销过大的问题。本文利用 4 6 中无密钥泄露的陷门h a s h 函数，构造了一 类有效的在线离线聚合签名方案，从而在突发性的聚合签名需求中有较好的应 用。 最后，我们讨论了陷门承诺在无收据电子投票电子拍卖中的应用j 指出一类采 用密钥泄露的陷门承诺构造的电子投票 3 6 署f l 电子拍卖 3 5 方案并不满足其声称的 无收据性；我们还提出了指定验证者可链接环签名的新概念，利用陷门承诺构造 了一个具体的方案，并基于此签名构造了一个新的无收据电子投票方案。 1 3 论文结构 本文的结构安排如下： 在第2 章中，参考 4 3 和 4 7 】的方法，我们给出了文中要用到的基本密码学定义及 承诺、陷门承诺、基于i d 的陷门承诺和陷f h a s h 函数的有关定义。其中第2 6 节给出了 完全的基于i d 陷门承诺的定义，与 4 3 中的定义不同，此定义更加符合基于i d 密码系 一4 一 陷门承诺、陷f h a s h 函数及其应用研究第1 章引言 统的要求，从而为第3 章基于i d 的非延展陷门承诺方案的提出做好了铺垫。在第2 8 节 中，我们介绍了基于具体数论假设的几个基本的陷门承诺方案，如基于离散对数假 设、r s a 假设和整数分解假设的方案，这些基本方案是后文构造具有更多更好性质的 承诺方案的基础。在第2 9 节中，我们还介绍了基于复杂性理论构造的陷门承诺方案， 如基于一般密码学假设一一单向函数存在的方案，这是理论密码学的重要研究方向， 旨在研究承诺所依赖的密码学基础，也是我们今后要进一步研究的方向。第2 1 0 节研究 了无密钥泄露陷f - h a s h 函数的构造思路，我们定义的完全的基于i d 陷门承诺可以转换 为无密钥泄露陷f - h a s h 函数。无密钥泄露陷f - j h a s h 函数在第4 章构造有效的在线离线签 名中具有重要作用。 在第3 章中，我们提出基于i d 的非延展陷门承诺的新概念，结合构造多陷门承诺的 思想1 1 ，4 4 】和构造非延展承诺的技术【1 7 】，首次提出了两个基于离散对数系统的有效的 基于i d 的非延展陷门承诺方案，分别基于随机预言模型和标准模型证明了其安全性。 我们将进一步研究基于其他具体数论假设的方案以及非交互的方案。 在第4 章中，我们研究了无密钥泄露的陷f h a s h 函数在在线离线签名中的应用。 本章主要讨论基于群体的在线离线签名。我们构造了一个新颖有效的在线离线门 限签名方案。从介绍利用无密钥泄露陷f h a s h 函数【3 1 构造在线离线签名方案开始， 利用可验证秘密分享技术，把其扩展为一个门限方案。我们分析了方案的安全性并 与 4 5 方案的效率做了比较。通过比较可知，本文的方案大大降低了计算和存储复杂 度。在该章中，我们还提出了在线离线聚合签名的新概念，此类签名在具有集中性聚 合签名需求的应用或在资源受限的应用中具有重要作用。我们利用一个变形的无密钥 泄露的陷i - h a s h 函数构造了一个具体的方案，并对方案的安全性和效率进行了分析。 在第5 章中，我们研究陷门承诺在电子商务中的应用，研究电子投票电子拍卖方 案的无收据性，指出一类利用密钥泄露陷门承诺构造的电子投票电子拍卖方案并不满 足其声称的无收据性。我们还提出了指定验证者可链接环签名的新概念，利用陷门承 诺构造了一个具体的方案，并基于此签名构造了一个新的无收据电子投票方案。 第6 章是总结和展望，对本文已完成的工作进行了总结，并提出了进一步的研究计 划。 一5 陷门承诺、陷f h a s h 函数及其应用研究第2 章陷门承诺的相关定义和基本构造 第2 章陷门承诺的相关定义和基本构造 在这一章中，前七小节介绍密码学的一些基本概念和文中使用的符号，然后给出 承诺和陷门承诺的形式化定义。我们只给出与陷门承诺有关的密码学基础，如单向 函数、离散对数假设、r s a 假设、整数分解假设以及承诺的概念，更全面的介绍请参 考4 7 1 。后三小节在相关定义的基础上，介绍了陷门承诺以及无密钥泄露陷f - h a s h 函数 ( 变色龙h a s h 函数) 的几个经典构造。第8 节介绍基于具体数论假设的陷门承诺方案的 构造，如基于离散对数假设、r s a 假设和整数分解假设的构造，分析这些构造有利于 我们构造新的陷门承诺方案；第9 节介绍基于复杂性理论的陷门承诺方案的构造，如 基于一般密码学假设一一单向函数存在的构造，旨在研究承诺所依赖的密码学基础； 第1 0 节给出了几个无密钥泄露陷f h a s h 函数的构造，可以看出其与基本陷门承诺方案 的紧密联系。 2 1 一些符号 令a 是一个概率算法，更准确地说，a 是一个有随机输入带的图灵机，如果存在一 个多项式p ( 他) ，使得对于长度为n 的输入，a 在p ( n ) 步内完成，则我们说a 是概率多项式 时间( p p t ：p r o b a b l ep o l y n o m i a l - t i m e ) 算法。如果a 对于其内部的随机硬币，平均在 多项式时间完成，则a 平均在多项式时间完成。 对于确定性算法a ，记a 卜a 0 ) 为输入z 时算法a 的输出a 。如果a 是概率算法， 贝3 j a ( x ) 为输入z 时，描述算法a 的输出的随机变量。其概率空间是由a 内部的随机硬币 决定的。在这种情况下，记陋 ) 】为输入z 时a m 支集，记a - a ( z ) 为输, k z 时，从算 法a 的输出随机变量a ( z ) 中取出样本a m 过程。 为了简化表示，常常把概率多项式时间算法看成确定性算法，并把随机硬币作为 输入的一部分，即为a ( x ，r ) 。在本文中，只讨论上述的图灵计算模型。 记为一个串z o ，1 ) + 的长度，记1 n 为n 个1 组成的串，记z r o ，1 ) 几为均匀选 择的一个佗一比特串z 。如果不特别说明，任何均匀选择都是独立于其他选择的。 函数5 ：n _ r + 称为可忽略的( n e g l i g i b l e ) ( 关于n ) ，如果它比任何多项式的倒 一7 一 陷门承诺、陷f - h a s h 函数及其应用研究第2 章陷门承诺的相关定义和基本构造 数都下降得快。更形式化地描述为，占是可忽略的，如果对任意多项式p ：n r + ，存 在n o n ，使得对所有n n o ，有6 ( 礼) 1 p ( n ) 成立。在后文中，把“存在n o n ，使 得对所有礼几o 简述为“对所有足够大的佗 。函数j ( 礼) 是显著的( n o t i c e a b l e ) ( 关于扎) ，如果它不是可忽略的；而把6 ( n ) 称为是压倒性的( o v e r w h e l m i n g ) ，如 果1 6 ( n ) 是可忽略的。 。 举例来说，存在一个函数( 数列) ，既不是可忽略的( 即为显著的) ，也不是 压倒性的，如：1 ，；，1 ，石1 ，从而显著的不一定是压倒性的，而反之压倒性的一定 是显著的。函数6 ( n ) = 2 咄是可忽略的。容易看出，乘积艿( 佗) p ( 佗) 也是可忽略的，其 中p ( 扎) 是任意的正多项式；如果6 ( n ) 是可忽略的，( 佗) 是显著的，则厂( 礼) 一6 ( 佗) 也是显 著的。 对于一个随机变量序列x = ( ) n n ，记z 卜k 为从随机变量中取的一个样 本z 。序列x 称为是可有效取样的，如果存在概率多项式时间算法a 使得k 与a ( 1 n ) 对 所有的n 是同分布的。算法a 的输入1 几表示允许4 的运行时间为输入长度1 1 n i = n 的多项 式。 两个随机变量序列x = ( ) 礼n 和y = ( k ) n n 称为计算上不可区分( c o m p u t a t i o n a l l y i n d i s t i n g u i s h a b l e ) ( x 毛y ) ，如果对任意概率多项式时间算法d ，其优势 a d v x y = l p r o b d ( 1 , z ) = 1 】- p r o b d ( 1 n , y ) = 1 】i 是可忽略的，其中的概率由d 的随机硬币，和随机选择z 卜和y 卜k 分别决定。算 法d 在输入z 和时，其输出在可忽略的情况下是一致的，也就是说，不存在多项式时间 算法区分两个随机变量k 和碥。 两个随机变量序列x = ( x 。) n n 和y = ( k ) n n 称为是统计上不可区分( s t a t i s t i c a l l y i n d i s t i n g u s i s h a b l e ) ( x 毛y ) ，如果 专i f r o b x n = s 卜p 础陬= s 】i 。 s e s 是可忽略的，其中& 是k 与k 的支集的交集。如果上式为0 ，则说明x 与y 是同分布 的，记为x 兰y 。 显然，同分布涵含统计上不可区分，统计上不可区分涵含计算上不可区分，反之 则不然。 - 8 - 陷门承诺、陷f - h a s h 函数及其应用研究第2 章陷门承诺的相关定义和基本构造 2 2 密码学假设 我们从一般的单向函数的定义开始，介绍与陷门承诺有关的密码学假设。简单地 说，单向函数即为正向计算容易，而对随机输入反向求逆困难的函数。单向函数存在 是密码方案存在的必要条件。 定义2 1 ( 单向函数) 一个函数，：【o ，1 ) + 一 o ，1 ) + 是单向函数，如果下面两 个条件成立： 有效计算：存在多项式时间算法e v a l ，使得对所有x o ，1 ) + ，有e v a l ( x ) = ，( z ) 。 单向性：对任意概率多项式时间算法a ，求逆成功的概率 l n v 二( n ) = p r o b a ( 1 n ，( z ) ) f - , ( ，( z ) ) 】 关于佗是可忽略的，其概率由z r o ，1 ) n 和a 的随机硬币决定。 另外的，如果对于所有n n ，有，( o ，1 ) n ) = o ，1 ) n ，则，为单向置换。 在此定义中，需要附加输入1 n ，这是因为如果i x f i f ( x ) l ，使得求逆算法仅仅 因为函数剧烈地压缩输入，而无法在关于i ，( z ) i 的多项式时间内输出函数的逆，这种 情况不能视为单向函数，必需排除在外。附加输入1 n 使得求逆算法可以在关于i x l 的 多项式时间内输出结果，从而排除了上述没有足够的时间输出逆的情况。以长度 函数f ( x ) = h 为例说明，因为i ，( z ) i = l 0 9 2 ，即使存在一个明显的求逆算法在关 于例的多项式时间内求得， ) 的逆( 如输出逆为o ) ，也没有算法能在关于i ， ) i 的多 项式时间内输出逆。 下面介绍几个单向函数的候选，一个是广为人知的粥a 函数4 8 1 。给定整数n = p 口和整数e ，其中p 、g 为两个不相等t 拘n 2 一比特长素数，e 与欧拉函数妒( ) = 一1 ) ( g 一 1 ) 互素，对于输a x z 知，其函数值) - j r s a n ，。( z ) = x 8m o dn 。注意到这是z 知上的 置换；并且在不知道的分解的情况下，给定r z 和多项式有界的e ，可以有效地计 算逆r 一1 z 和幂r 8 z 知。 一9 一 陷门承诺、陷f - h a s h 函数及其应用研究 第2 章陷门承诺的相关定义和基本构造 r s a 函数并不符合定义2 1 ，因为定义2 1 只针对单个函数厂，而r s a 函数是由指 标和e 定义的函数集合，并且定义域和值域z 都依赖于指标。然而，我们并不 严格讨论这种带指标的单向函数( i n d e x e do n e - w a yf u n c t i o n s ，也即，c o l l e c t i o n so f o n e - w a yf u n c t i o n s ) ，因为其形式化定义更加复杂；而是对定义2 1 作一个基本的处 理，即增加一个指标生成函数输出一个随机的指标i ( 如这里输出随机的和e ) ， 而a ( 1 n ，i ，五( z ) ) 求逆的概率则由随机选择的指标i ，定义域中随机选择的z 和a 的随机硬 币决定。 我们形式化地说明r s a 函数是单向函数。为此，如上所述，假设存在有效算 法i n d e x g e n ( 1 n ) 输出指标和e ，而不详细说明算法如何做到这一点，如得到安全素 鳓= 纠+ 1 ，q = 2 q 7 + 1 ，其中p ，、g ，为素数；又或者需要多大的e 等等。这些讨论超 出了本文的范围，而对于