（通信与信息系统专业论文）可证明安全性及其在公钥密码体制上的应用.pdf

摘要 本文对哥诞媚安全惶及其在公锈露赡体裁上兹应尉避行了研究。蓄先奔绍 了可证明安全性方法以及树关的知识；其次对公钥体制的各种安全术语以及它 们之间的关系做了深入的研究，较为寇整地总结了目前的各种达到i n d c c a 2 的方案；最后以卅r u 为例，讨论它的可证明安全性。 本文得到的燕黉成果如下： 1 对可证明安全性中归约的有效憾进行了讨论。 2 + 对公锈密潞傣翱瓣安全零瀑之秘戆关系 霉委了一令谬尽豹踅。 3 发现了o a e p + 安全性证明中的一个问题，并提l _ l 了解决办法。 4 比较完熬她总结了目前获得i n d c c a 2 的方法，发现了它们的一个般 同特点：熬于密文的某种“合法测试”；丽且对它们的证明中归约的商 效牲进行了淫论。 5 发现所有融知的达到i n d c c a 2 的方法在n t r u 上都不是狠有效，从 而找到了n t r u 公钥密码体制自身的一些缺陷。 关键谪：可诞翳安全性睫枫该意槐公钥密码体铡i n d c c a 2n t r u a b s t r a e t p r o v a b l es e c u r i t ya n di t sa p p l i c a t i o n so np u b l i c - k e yc r y p t o s y s t e ma r ed i s c u s s e d i nt h i st h e s i s p r o v a b l es e c u r i t ya n ds o m er e l a t e dk n o w l e d g eh a v eb e e ni n t r o d u c e d f i r s t l y ；ad e e pr e s e a r c ho nt h es e c u r i t yn o t i o n so fp u b l i c - k e yc r y p t o s y s t e ma n dt h e i r r e l a t i o n s h i p sa n daw h o l es u m m a r i z a t i o no f t h ee x i s t i n gs c h e m e sw h i c hh a v er e a c h e d i n d c c a 2h a v eb e e nm a d es e c o n d l y ；a n dt h ep r o b a b l es e c u r i t yo fn t r uh a sb e e n d i s c u s s e da sa ne x a m p l eo f p u b l i c k e yc r y p t o s y s t e mf i n a l l y t h em a i nr e s u l t so f t h i st h e s i sa r ea sf o l l o w s ： 1 t h ee f f i c i e n c yo f t h er e d u c t i o ni np r o v a b l es e c u r i t yh a sb e e nd i s c u s s e d 2 ad e t a i l e dg r a p ha b o u tt h er e l a t i o n s h i p sb e t w e e nt h es e c u r i t yn o t i o n so f p u b l i c k e yc r y p t o s y s t e mh a sb e e na c h i e v e d 3 ap r o b l e mi nt h es e c u r i t yp r o o fo fo a e p + h a sb e e nf o u n da n dt h e r e s p o n d i n gm e t h o d st os o l v ei th a v eb e e np r o p o s e d 4 aw h o l es u m m a r i z a t i o no f t h es c h e m e sw h i c hh a v er e a c h e di n d c c a 2h a s b e e nm a d e ，f r o mw h i c hw ef i n dac o m m o ni d e ao ft h e m ，i e t h e ya r ea l l b a s e do ns o m e “v a l i d i t yt e s t ”：a n dad i s c u s s i o no ft h ee f f i c i e n c yo ft h e r e d u c t i o n si nt h e i rs e e u f i t yp r o o f sh a sb e e nm a d e 5 w ef i n da l lt h es c h e m e st h a tc a nm a k eonep u b l i ck e yc r y p t o s y s t e m i n l ) c c a 2a r en o te f f e c t i v ee n o u 曲w h e nu s e dt on t r u ；t h e nw ef i n d s o m ed e f e c t si nn t r iji t s e l f k e yw o r d s ：p r o v a b l es e c u r i t y r a n d o mo r a c l e p u b l i c k e yc r y p t o s y s t e m 【n d - c c a 2n t r u 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一些相关责任。 本人签名：腺歹良日期：函刀弓7 ，5 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技 大学。学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布 论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保 密的论文在解密后遵守此规定) 本学位论文属于保密，在年后解密后适用本授权书。 本人签名：鏖，廛 翩签龟蕴笪 笨一鼋绪论 第一章绪论 8 0 年代早期g o | d w a s s e r 和m i e a l i 提出了一个非同寻常的恩想：在公认的计 簿复杂瘦理论缓设下，安全性是可敬嚣爨豹。这一方法魏称为哥涯暖安全性。 隧着对可证明安念我的迸一步研究，密璐学家发现它对密码学静影响重大，并 且对密码学实践也旃重要的意义。 1 1 可证明安全性的历史背景及其对现代密码学的意义 毒涯弱安全瞧燕g o l d w a s s e r 帮m i e a l i 于1 9 8 4 年挺囊豹 1 l ，它不莰是穆 证明方法，也是一种设计协议的方法。特别是人们对国际密码标准进行大量分 析之后，越来越意识到可证明安全性的熏要性，可证明安全性也已成为任何一 个密码协议的基本凝求。 在f 1 1 中g o t d w a s s e r 靼m i e a l i 提如了概率加密这一概念，文中提出了这样的 葱怒：对于具体憨方寰及其实瑰，缓浚数论中静菜望溺嚣，如大整鼗分解问题 或对模一个合数求二次剩余等闻题罴赡熊的，则证明一个问题是难问题就意昧 篇证明该问题与上述某一数论问题等价。换句话说，对【l 】中加密方案安全性的 威胁会产生一个求解模一个合数的二次剩余的有效算法。( 当我们认为该问题困 难的对候，也就意昧着 1 】中加密方案怒安全的。) 嚣对期的其意文章中也体现了胃谖明安全性，擞f 2 j 中，g o l d r e i c h 通过研究 随数随机性构造璎论提出了多项式随机饿这一概念，瑟：从个串集s 中醚缀 选择输入或从所有串之集中随机选择输入，多项式时间运行的结果相同，则称s 是多项式随机的。对于多项式时间计黪的攻击者来说，这暗示了下述协议设计 方法： 1 ) 莰计一拿使建粪随机函数的协议，并证明其蓬确瞧； 2 ) 霜麸多顼蔽麓撬函数族孛隧虢逸敬翡函数替代蠹麓橇螽数，两这一替役 可以证明对予多项式有界的敌葶保留了原来协议的所有安全性。 再比如 3 中b l u m 在d l p 阀题难于求解的象件下，构造了一个 c s p r b ( c r y p t o g r a p h i c a u ys t r o n gp s e u d o r a n d o mb i t ) 生成器，并说明了任何一个可 ；王以太子寥2 概率预测下一输出比特的莉效算法都可以容弱地转纯为一个解决 蒜教对数阔题懿“簿馀雾法”。鲡栗d l p 在概率多矮式懿闻举胃分簿，蕤不襻 在多项式时间的算法可以比投掷硬币更好地预测下一输出比特。更为重要的是 c s p r b 可以替代实际应用中的一次一镦。 简略地讲，对于个给定的问题，达到可证明安全性就是簧提供： 2 可证明安伞性及其在公钥密码体制：的应用 i )安全目标的定义； i i )使用某些较低水平的原型的协议； i i i )一个证明( 称为一个“归约”) ，证明如果该原型确实能起到它应有的 功能( 或类似定义的功能) ，则该协议可以达到该安全定义。 可证明安全性使密码学从一门艺术成为一门科学，并且也成为密码学领域中 理论工作的主线。但是，因为可征明安全性是在计算复杂度假设下建立的，强 调的是多项式时脚、可忽略概率等概念。所以密码学的实践家们即使完全懂得 可证明安全性的含义，也趋向于认为可证明安全性几乎没有应用价值。为此， b e l l a r e 和r o g a w a y 等人提出了面向实际的可证明安全性 4 】，强调的是确切的、 具体的安全性，使得可证明安全性中的定义和归约成为实际分析协议的强大工 具，并得到了很多实用的成果，如：o a e p 、d h i e s 、p s s 、p s s - r 等体制用于 支持a n s i 、i e e e 、i s ok p k c s 、s e c g 等标准。 1 。2 公钥密码体制的可证明安全性 公钥密码体制自1 9 7 6 年提出以来，已经得到了广泛的应用，1 9 8 4 年 g o l d w a s s e r 和m i c a l i 提出了概率加密的概念，使公钥密码体制有了更广泛的用 途。为了更好地使用和设计好的公钥密码体制，密码学家们对公钥的安全性进 行了大量的研究，他们提出了各种安全性目标( 定义) ，如：语义安全性( s e m a n t i c s e c u r i t y ：s s ) 、不可区分性( i n d i s t i n g u i s h a b i l i t y ：z n d ) 、不可展性( n o n m a l l e a b i l i t y ： n m ) 、明文可意识性( p l a i n t e x ta w a r e n e s s ：p a ) 等，以选择明文攻击( c p a ) 、选择 密文攻击( c c a l ) 和适应性选择密文攻击( c c a 2 ) 为攻击类型，得到了很多的安全 术语。对这些安全术语之间的关系目前已经有了很好的研究，并得到了 i n d c c a 2 确实是公钥密码体制的良好的安全性定义的结论【5 、6 、7 、8 、9 】。 而对选择密文攻击包括( c c a i 和c c a 2 ) 的安全性又是很多密码学协议中希望达 到的安全性，因此人们就要研究达到这种安全性的公钥体制，但遗憾的是这一 安全性很难达到。为此，近年来很多密码学家致力于研究能够使得现有的体制 达到这种安全性的技术，试图以最小的代价获得这一安全性 1 0 1 9 】。譬如， o a e p 技术应用到r s a 上就是a n s i 公钥加密标准，它采用了一些h a s h 函数， 构造密文的合法性，使得攻击者无法进行有效的选择密文攻击，从而达到了随 机预言机模型中的对c c a 2 的可证明安全性，即i n d c c a 2 。 证明一个体制是i n d c c a 2 时，我们使用可证明安全性的方法，即寻找一 个有效的归约，这也正是可证明安全性方法的难点，也是很多体制无法达到可 证明安全的原因。己知的在理论上对选择密文攻击可证明安全的公钥体制大多 第一章绪论 数都不实用，而且证明也是陶造性的，比较复杂，各种抗选择密文攻击的技术 和研究正是为了解决这一矛肟，人们实际采用的一般方法有：采用h a s h 函数构 造密文合法性的嵌入式系统采用单、双钥体制混合的方法，以及采用非交互 式零知识证明构造密文合法陀的方案等。 n t r u 是1 9 9 6 年j e f f r e yh o f f s t e i n 等提出的在截多项式环上构造的公钥密码 体制 2 0 ，它的安全性基于拼归约问题，即最短或最近向量问题。n t r u 以其公 钥短、速度快等显著的的优点得到了密码学界的广泛重视，是已知的最快的公 钥密码体制之一，它同时被多个标准考虑，如有效的嵌入式安全标准( e f f i c i e n t e m b e d d e ds e c u r i t ys t a n d a r d s ) 和i e e ep 1 3 6 3 未来公钥密码体制标准( f u t u r e p u b l i c k e y c r y p t o g r a p h ys t a n d a r d s ) 。但是由于它的安全性存在一些问题 2 1 - 3 2 ， 尤其是不能达到对选择密文攻击的安全性，因此很容易地在2 0 0 0 年被一种选择 密文攻击攻破 3 3 1 ，得到了相应的私钥。为此，人们将各种现有的抗选择密文攻 击的方法应用到n t r u 上，以图使得n t r u 这个低安全水平的“原型”获得高 的安全水平：选择密文安全性，但是这些方法并非都有效 3 4 、3 5 】。本文将以 n t r u 为例子，阐述公钥密码体制获得的可证明安全性的困难性。 1 3 论文的内容安排和主要结果 本文的内容安排如下： 第二章主要介绍可证明安全性以及相关的知识。首先介绍了可证明安全性 方法，其次简单介绍了一些与可证明安全性密切相关的定义，这些定义是我们 获得可证明安全性的基础，再次讨论了面向实际的可证明安全性，它是在传统 的可证明安全性在实际中很不实用的背景下提出的，最后主要讨论归约，这是 为了更好地理解可证明安全性。 第三章讨论公钥密码体制的安全性以及获得最好安全性的方法。首先简单 介绍了概率公钥加密方案这概念，其次对公钥体制的各种安全术语及它们之 间的关系做了详细的讨论，再次重点讨论了达到i n d c c a 2 的方案，在对目前 国际上各种方案的研究的基础上，将它们简单地进行了归类，最后对这些方案 进行了比较，并且对这些方案的安全性证明中的归约的有效性做了详细的讨论。 第四章以n t r u 为例，讨论它的可证明安全性。首先简要介绍了n t r u 公 钥密码体制，对它是否达到我们第三章给出的安全性定义进行了简短的分析， 其次介绍了对n t l w 的一种选择密文攻击，这表明了选择密文攻击确实威胁到 了几乎所有现有的公钥密码体制，再次我们将各种达到i n d c c a 2 的方法应用 到n t r u 上，发现并不能取得良好的效果，最后我们找到了n t r u 的一些问题 4 a n 正l 安伞性及其在公钥密码体制f ：的应用 和缺陷，并进行了一定的讨论。 本文得到的主要成果如下： 1 对归约和归约对安全性的保留做了明确的表述，对可证明安全性中的归 约及其有效性进行了讨论。 2 对公钥密码体制的安全术语之间的关系得到了一个详尽的旧，用该吲可 以很好地理解这些关系，而且容易看出在标准模型中i n d c c a 2 是公 钥密码体制的最强的安全性，也是“正确”的对选择密文安全的定义： 而在随机预言机模型中p a 严格地强于其它安全性。陔图也表明所有的 安全术语之间的关系都已经解决了。 3 发现了o a e p + 安全性证明中的一个问题，并提出了解决办法。 4 比较完整地总结了目前获得i n d c c a 2 的方法，这包括在! 随机预言机 模型中和在标准模型中的，对它们进行了归类，发现了它们的一个共同 特点：基于密文的某种“合法测试”：而且对它们的证明中归约的有效 性进行了讨论。 5 发现所有已知的达到i n d c c a 2 的方法在n t r u 、上都不是很有效，从 而找到了n t r u 公钥密码体制自身的一些缺陷。 第一二牵鳝疆镶安全性 第二章可证明安全性 为了介绍可溅嘲安全性，首先我们必须澄清两个概念：密码学协议( 或方 豢) 窝密玛学瑷戆横，型( 麓弦乐壅) 。为j 获零安全豹通笛，用户需要密妈学熬 协议( 或方案) ，躲为了秘密通信，蠢j 户需要加密方案：为了标记数据， 童接收 者可以确信数据怒发送者所发，并且谯发送过程中未被窜改，用户需要认证协 议。设计这些方案我们需要好的密码学原型，也就是设计密码学方案的工具， 这应该包括单向溺数、陷门单向函数、伪随机数生成器等等。我们称诸如d e s 、 r s a 等巍未令久臻羧地攻破豹薅裁为缎予藏鍪。事实上，r s a 裁是一个憝f 1 鼙 囱函数搬密方案，躜以有时我翻荠不嚣分淼予原型和原黧。毽是，本交为了明 确起见，使用“原子原型”这样的熟语。协议与原予原溅的区别就是：最开始 原子原型并不解决任何密码学的问题，而我们必须正确地遴用它们去构造协议 朱解决密码学问题，也就是说，原予原型是简单的构造“砖块”。 缓设好的厥予骚墅存在，如何设诗汝议? 这正是可淡骥安全性要髌决豹阍 麓。 2 1 可证明安全性 要知道一个密码体制是否安全裔两年申方法： 1 ) 经典豹方浚，帮设诗爨方案爱麓德攻疆，翔粟攻破，靛热一些蛰丁或徽 一些掺歪褥到薪的方案，再缵绥上述过程。 2 ) 归约方法，即可证明安全性方法，它在等待攻破之前就确定了攻击模型， 并给出安众性的证明，下文将做详细介绍。 经典的方法便我们总是处于被动的地位，而且找不到肖效的攻击并不是协 议安全爨毒力涯攒。爵汪臻安全性在好豹敌手模型秘安垒链定义下，可能可以 防止一些未知貔攻灏。 可证明安全性这概念的提出是在8 0 年代，此后有锻多密码学家致力于该 领域的研究，它是种将好的密码学原子原型变为好的密码学协议的方法。 譬如说，以通过加密获得秘密性为目标，可证明安全性的典型过程如下： 1 ) 确定一个栎猴韵致手模型费定义艇密方案安全鹩食义； 2 在1 ) 豹蒸_ 蘩l l 上，对基于某一缀予漾壅擒造魏其侮方豢，逮过宅是孬这 到定义的嚣求而加以分析： 3 ) 证明该豚予原型可以归约到该方案，这一归约表明墩破该方案的唯一方 法是攻破所用的原子原型。 6 町证嘲安奄穗授其在公铡密玛辱垂= 勰上的应用 换句话说，我们没有必要氲接分析具有可证明安全性的方案，如果发现了其 中的一个弱点，就发现了相应原予原型的弱点。如果我们相信后者是安全的， 那么不用分柝该方案，我们就知道它是安全的。对归约豹另一种看法是：给定 一令从r s a 麴肇囱缝到某个方案骢个归约，它是具有f 述性质的一个变换： 镁设p 是霹戳玻骏该方案兹一个程j 擎，剽该交矮辛霉舞l 程p 上髟成p ，辩p 西逶 明地攻破r s a 。所以，只要我们褶德r s a 不能被攻破就不会存在这样的p ， 也就是说，该方案是安全的。 具体到证明个密码方案的安众性，就是要搞清楚： a ) 算法蹰熬予的难度缓设，载嚣滋基于的原子原裂； b ) 要深诞鹣安全往； c ) 归约：捷到一个可以攻破难度假设的敌手。 “可证明蜜全性”这一术语有时可能会产生误导，所以有些密码学家不赞 成使用这一术谮 3 6 1 。在上述过程中，中一i i , 步骤可能是绘出一个模型和定义，这 劳不涉及到证明任秘事情，因此，我们不是“证明一个方案安全”，丽是给出蔡 一基本原子原鍪安全往到该方寨安全性的一令羟约。所以使鬻“ 趋约安全性” 可能更合适。 可证明寂龛的精确形式化有很多种，大多理论选择了复杂性理论体制束发 展它，此时用别的是“多项式时间”的敌手和变换，以及“可忽略概率”等概 念。 2 。2相关的知识 现代密码举是建立在保证合法用户算法的有效性和敌手恢复被保护信息的 不可行性之间的鸿沟之上。计算复杂性理论使得攻破的“不可能性”转化为“不 可 亍性”，可诞嬲安全蛙j 下是基于诗簿“不可季亍”丽梅建起来豹理论。为了研究 霹证明安全瞧，篱瑟学习与密舀掌籀笑豹一些基麓翔谈，瓣擎蠢蚤数、伪瓣壤 数生成器、伪随机函数、h a s h 函数、零知识证明等。 2 2 1 几个重要概念 菲常重要鲍计冀复杂度理论概念霉以下凡个。 定义2 2 1 ( 霹忽略函数) ：个涵数y ：n r 愚冒忽略豹，若薅予任意懿 多项式p ( ) ，存在一个n n ，使得对所有七行有：。，( 七) 轰石。 第二章可证明安全性 定义2 2 2 ( 多项式时间) ：设a 是一个算法，它以串工为输入，h 表示工的 串长，我们称a 是多项式时间的，如果存在一个多项式| 口( ) 使得a 至多在p ( 工1 ) 步就停止。 定义2 2 3 ( 概率多项式时间) ：称一个以工为输入的算法a 是概率多项式时 间的，如果a 是概率的，且总是存在一个多项式p ( ) ，使得a 至多在p ( 1 x i ) 步 就停止，而且a 的随机硬币投掷次数总是多项式有界的。 非一致多项式时间是一个比概率多项式时间强的概念，凡是由概率多项式 时间算法可以得到的结果，由非一致多项式时间算法都是可得的。 定义2 2 4 ( 多项式时间可抽样的) ：称一个概率分布x 是多项式时间可抽样 的，若存在一个概率多项式时间算法，当输入x 时，输出服从x 分布。 设x 和y 是两个概率分布，设x 服从兄y 服从y ：称x 和y 是相等的， 如果对于任意的x 的取值x ，有p r x - 一x = p r y = x 1 。 考虑由安全参数k 决定的两个分布族 x k ) 。和 y k ) 。，凰和y k 的值域相 同，即d o m x k = d o m y k 。对于固定的k ，设x 服从抵，y 服从y k ，称 x k i 。和 y k 。，统计相近，若存在一个可忽略函数y ( ) ，使得对于任意的k n ，有 i v r x = 小一p r y = x 私y ( | i ) 。 x t d o m x k 称 凰) 。和 k ) 。是计算不可区分的，若对于任意的多项式时间算法a ， 存在一个可忽略的函数y ( ) ，使得对于任意的k n ，有 p r x 一x k ；b a ( x ) ：b = l 】一p r y _ 曼一k ；b a ( y ) b = l 】r ( k ) 。 这里x 士魁表示从m 中随机选择一个x ，b a “) 是一个简单的赋值语 句。 统计相近可以推出计算不可区分性。 2 2 2 原型 单向函数( o 、v f ) 是易于计算，难于求逆的函数，如s h a - 1 ，( 工) = 9 1 等。 对于函数正x 寸y ，求逆器i 的成功率定义为： s u c c t ，( ，) = p r 工+ l 配_ ) ，一，( x ) x + 一，( y ) f ( x ) = j ，】。 ，的不安全性定义为：i n s e c 吖( 正f ) = m a x s u c c 芦( z ) ，i 的运行时间在f 吖证明安全性及其在公钊密码体制上的应用 内。若i n s e c 。盯( t ) 占，则称厂是一个( t ，占) 一安全的o w f 。 伪随机数生成器( p r g ) 是将输入“种子”扩键成更长的“看起来”随机的串。 没g ： 0 ，l 一 o ，l 。，则埘g 的一个区分器d 的成功率为： 一d v 善曙( d ) = p r 【x + l ：o 1 y , 4 - g ( x ) ：d ( y ) = l 】一p r y l o ，l ：d ( 、) = l 】。 g 的不安全性为h z s e c ”( g ：f ) = m a x s u c c ：, 9 ( d ) ，d 的运行时日j 舀：t 以内。 若h i s e c 9 8 ( g ；f ) s ，则称g 是一个( t ，引一安全的p r g 。 成功率是密码学中许多定义用到的一个概念。一个敌手a 的成功率定义为： a d v ( a ) = p r a 在背景a 下返回1 卜p r a 在背景b 下返回1 。它有如下性质： 1 1 一i a d v ( a ) + l ： 2 ) a d v ( a ) = 0 意味着敌手不能区分； 3 ) 负值表明该敌手是错误的。存在另一个使用伺样资源的敌手，但具有 正的成功率： 4 ) 若a 试图猜测某一个隐藏的比特b 。 o ，l ，则有 p r b 4 - a ：b ：b + 1 = 绁+ 一i 。 22 伪随机函数( p r f ) 整体( e n s e m b l e ) 和伪随机置换( p r p ) 整体在密码学中也非 常重要，它们的定义与p r g 类似，也是要考虑成功率，但是由于篇幅所限，这 罩不再赘述。需要注意的是p r p 也是好的p r f ，为证明这个结论要用到个非 常有用的引理： s h o u p 引理：设、e 和尸是定义在概率空间上的事件，它们满足 p r 【e 八- 、f = p r 【e 八_ 1f 】， 贝u 有p r 】一p r 【e 】| p r f 证明：p r 【e 】= p r e 八f + p r 八_ 1 f 】， p r 】= p r 7 八f + p r 【八1f ， 两式相减取绝对值有： i p r e 】- p r 【】pp r 【e 八f p r e 八，】i p r 【f 】a 撑 该引理在本文附录的证明中会用到，它是安全性证明中经常用到的个引 理，所以在这里给出他的证明。 h a s h 函数是非常有用的密码学原型，如m d 5 和s h a - i ，它们具有以下三 个特点：单向性、防碰撞、随机性。如果一个h a s h 函数具有上述好的性质，就 可以把它看作是一个“随机预言机”。 第二章可证明安伞性 2 + 2 3 阻难性假设 标准的困难性假设有f 列问题的困难性：i f p ( 整数分解问题) 、q r p ( - - 次剩 余问题) 、d l p ( 离散对数问题) 、r s a p ( r s a 问题) 、c d h ( 计算d i f f i e - h e l l m a n 问 题) 及其变形。q r 和p s a p 的困难性依赖于i f p 的困难性，但尚未证明解决q r 和r s a p 的算法是否可用f 分解整数。 这些困难问题都具有随机自归约性，即：该问题的一个例证可以变换成许 多不同的其它导出例证，而不改变该问题例证的概率分布，这样，对导出倒证 之一的解决方案将产生对最初例证的一个解决方案。自归约性质包含了这样的 含义：问题的“大多数”例证与最难的例证是一样难的。 譬如说r s a 问题的自归约性可以如下得到； 设n = p q ，设s ( n ，e ，y ) 能对“很多”y 的选择得到一个x ，使得x 。一y ( m o dn ) ， 否则就输出。上，那么下列概率多项式算法可以对任意y 解决模n 平方根提取 问题： a l g o r i t h ms o l v e l s a ( h ，e ，y ) ： r e p e a t x 山 l ，2 ，n 1 ) ； i f g c d ( x ，n ) = lt h e n y 一yx ”( m o dn 1 ： 工一s ( ”，e ，y ) ； i f x 上t h e nr e t u r nx 一“( m o d 山； f o r e v e r ； ( o - xe 三y 兰y 石。( m o dn ) ，xe ( x 川) 。三y ( m o d n ) ，( xe 工) 。三y ( m o d n 1 。) 2 2 4 零知识证明 零知识证明是获得可证明安全性的一个重要工具【4 1 、4 3 】，尤其是在人们认 识到对任何语言的交互式零知识证明都可以有效的转换成非交互式零知识证明 之后。对零知识证明的研究近年来取得了比较重要的进步。但是，我们对有关 零知识证明的研究尚在进行之中，所以有关定义和性质在这里都不多做说明。 2 3 面向实际的可证明安全性 传统的可证明安全性方法有很多的缺点，使得密码学的实践者认为它几乎 町引掰寂垒摊茂筵艇公钳密码律黜l ：的戍用 没有实舔徐筐。主鬃楚逶遥这魏方涟秘遣懿方寨效攀透露缀低，蘸霞麓梅途太 复杂或依赖于效率很低的原予原型。而且，复杂性理论的方法有时使w 证明安 全性与实繇越柬越远。例如，实际中人们可能需要这样的数据：该方絮能抵抗 黢手熬多少轮竣毒，安全参数楚多少魄特等，嚣这黪廷敷“多项式多豹”稻“鬻 忽路概率”精略地蠛是不实际的。 为了傻络；虿程溺安全程蜜爝，羟约稿安全性必缀蹩其髂瓣，霹鼗露了嚣两 实际的可 i e 明安全性f 4 1 。 面向实际的可诚明安全性还魁关于定义、协议和i 正明，核心没有黛，但目 辍不霜了。不簿繇突不蠢密璐学嚣拣熬霹涯饔安全羧之潮黪关系，瑟怒整这燕 定义和归约成为设计和分析实际协议的强大工具。它的切入点有以下几个： l 。搜蠲分缀密鹚 睾为爨约瓣出发杰。戳分组密鼹为瑷予缀型戆方案不在本 文的考虑范围之内，故不做详细的讨论。但要注意的是，这种方法酌关键在于 将分组密粥看作是伪随机函数旗。 2 。具体靛安全瞧 l ，芦l ，c 0 ，使得r ，( 坩) 掣： 。t 多项式保留的：若有常数l ，c 0 ，使得r ( n ) 墨d 兰； 线性傈留靛：整有常数。0 ，傻褥置，( ，1 ) 兰掣。 注l ：上进宓义中都有一个n ，因为通常r 。( ) 7 1 , ，所以它是一个煎 v 簧因素。 注2 ：上述定义楚j | 警约对安全魏戆绦磐程疫，线蛙绦露麴约是最栽爨蜜安念 经懿。 例：考虑从一个单向函数，到一个伪随机数生成器g 的归约，希望该姻约 保证g 是( 1 - r 。似) ) 安全的如果也( 腭) 不是很小，这三种归约之间的区别不 4 町静硝安全聿生驶其茬公蛰j 密玛体制j 瘴臻 大，但当r 。( n ) 以很快的速度趋于0 时，区别会很大如r 。( 月) = 2 ”2 ，口= = 2 ， ! c = 0 时，对予线性保留，如果没有对，的r r ( 月) = 2 ”。攻破敌手，g 是( 1 一尺。( ，1 ) ) ! 安金数；对于多矮式绦整。妇涎没蠢对，匏r y ) ；2 。攻破酸手，g 是( 1 一覆。) 安全的；对予徽保留，如梁没有对f 的r f ( 月) = 2 8 攻敝敬手，g 是( 1 一镌( ) ) ! 安全的。此时，r j ( n ) = r 。( m 。”，而不是兄。( ”) 的多项式，事实上，由于平儿的 原因，存在对厂的2 。”攻破放手，掰以，不管厂是多么安全的，微保留归约都不 i 旋保证g 是( t - 2 ”2 ) 安全酶。 线性保留归约具有很多的优越性，所以应设计尽可能强的归约，越强的归 约越能保留安念性，尚未做的一个麓要工作之一是在密码学原型中寻找比融知 的归约更强保帮的归约。一个具体的从弱单向置换到单向置换的线性保尉归约 可敬参看【3 9 】。 可涯鹾安全瞧中的蟊翁是驮寮鹳学藤子藤壁戮密溺学协议懿爨绞，它鸯类 似的定义，只怒需要定义原子原型和协议的敌手模型，而且敌手的成功率也不 能像定义2 4 4 中那么简单地给出。但在实际中，按照上述保留归约的定义讨论 归约的有效性，即对安全性的保麟性，很不方便。因为我们有时还要考虑黧法 联需的存德空阉，霹盈舂对密码学秘议豹安全参数不止个，这楚褥我们黉缮 餮豫定义2 4 5 辫群懿簿革关系缀鼹。魏第霆章串o a e p 黥哥证疆安全程审黪织 约就很难用这种定义衡量。所以，我们可能需要一个煲好的定义来衡量烟约对 安全性的保留问题。 2 。5 本章小结 本章主要介绍可证明安全髓暖及稿关的戋嚣谖。第一节在给出证暖一个方案 安全的传统方法的缺点之后介绍了可证明安全性方法，该方法可以使我们在 密码学背景下爨主动。第二节简单介绍了一些与可证明安全性密切相关的定义， 这些定义是我们获得可证明安全燃的基础。第三节讨论颟向实际的可证明安全 经，它是在传统戆霹涯秘安全性褒实际孛攫不实建豹鹜豢下提出豹，该节绘爨 了嚣离实际静霹诞唆安全性鹃足令磷究重点，鲡其薅懿安全程葙隧梳臻京穰模 型等。第四节擞樊讨论归约，因为作者发现研究可证明安全性的学者尚采对归 约给出一个定义，所以在这给出归约的定义，虽然我们引进的归约的定义燎 3 9 】 第二章可证j 安全性 呻的，该定义是两个原子原型之间归约的定义，但是我们可以由此理解可证明 安全性中的归约。归约对安全性的保留问题是安全性证明有效与否的一个衡量， 但是已有的定义在实际中似乎不实用，因此我们希望能给出一个有效的定义。 为了更好地研究可证明安全性，需要进一步研究的是密码学的各种原型， 当然这需要很多的努力。我们希望可以给出一个衡量原子原型到协议的归约有 效性的好的定义，这样有助于我们比较各种方案获得的可证明安全性是否是最 优的。 第三章公钥密码体制的可证明安全性 第三章公钥密码体制的可证明安全性 公钥密码体制自从1 9 7 6 年d i 箭e 和h e l l m a n 提出以来，得到了广泛的应用。 1 9 8 4 年，g o l d w a s s e r 和m i c a l i 提出了概率加密的概念【l 】，使得公钥密码体制有 了更好的安全性及应用，从此概率加密就被公认为设计密码体制的一个必要条 件。在 1 】中，他们提出了语义安全性，从此，为了获褥可证明安全性。密码学 家们开始寻求对公钥密码体制的更好的安全性定义，从而有了不可区分性、不 可展性和明文可意识性等安全目标的定义。( 有时人们把达到语义安全性以上安 全水平的体制称为是可证明安全的。) 以选择明文、非适应性选择密文和适应性 选择密文为攻击类型，人们开始讨论这些安全性之间的关系。1 9 9 8 年b e l l a r e 等人对这些术语之间的关系做了较为详细的讨论，但尚存在一些未解决的问题 【6 】。1 9 9 9 年b e l l a r e 和s a h a i 又解决了两种不可展性定义的等价性问题【8 】，2 0 0 2 年r 本学者y o d a iw a t a n a b e 等解决了语义安全性与不可区分性之间的完全等价 9 1 。这样各个安全术语之间的关系基本上都解决了。 对公钥加密最强的安全性是对适应性选择密文攻击的安全性，这也是人们 公认的对加密方