不可区分性在公约密码学中的应用介绍

1、不可区分性在公钥密码学中的应用摘要：本文主要总结了不可区分性在公钥密码体制中的运用，这些运用主要包括如何刻画密码体制的安全性（语义安全性）、如何通过规约的方式利用不可区分实验证明密码体制的安全性、以及一些常见的密码体制中不可区分性的作用。全文主要分为三个部分，第一部分主要介绍了一些基础知识，包括密码体制的组成以及完善保密密码体制的含义，如何利用不可区分性来等价描述完善保密密码体制。第二部分主要介绍了不可区分实验（游戏）在公钥密码学中的应用。这一部分先对攻击者的层次进行了划分，之后介绍了如何用不可区分实验来给最基本的密码体制的语义安全性下定义。这一部分最后利用CCA2的语义安全性作为例子说明如何

2、利用不可区分实验定义拥有特定防御功能的公钥密码体制的语义安全性。第三部分介绍了规约证明的相关内容，规约证明现如今已成为现代公钥密码学可证明安全理论常用的证明方法，而两个问题规约的过程中与不可区分性密不可分。第四部分主要举了一个例子来说明不可区分性在证明密码体制安全性中的应用。本文对公钥密码学中的不可区分性理论做了比较简单的总结和归纳，不可区分性在公钥密码学可证明安全理论中有着十分重要的地位，本文对刚刚接触不可区分性的学者有着一定的帮助。 第一部分：基础知识及不可区分性的定义 这一部分内容主要介绍一下有关于不可区分性的基础知识，包括密码体制的组成、完善保密密码体制、完美不可区分性的含义以及敌手不

3、可区分性的含义。首先先给出密码体制的定义：定义1.1 密码体制一个密码体制由三个部分构成：密钥产生算法Gen、加密算法Enc、解密算法Dec。他们的功能如下：（1）密钥产生算法Gen是一个概率算法，能够根据方案定义的某种分布选择并输出一个密钥. （2）加密算法Enc，输入为密钥和明文，输出为密文。把使用密钥加密明文记为Enc(). （3）解密算法Dec，输入为密钥和密文，输出为明文。把使用密钥解密密文记为Dec(). 对任意的密码体制的基本要求是：对任意通过Gen输出的密钥，每个明文消息都满足Dec(Enc() 密钥生成函数Gen输出的所有可能的密钥称为密钥空间，用表示。所有明文消息的集合称为

4、明文空间，记作。集合和一起定义了所有可能的密文的集合，称为密文空间。上述密码体制可记为明文空间为的密码体制(Gen,Enc,Dec). 如何刻画一个密码体制的安全性，完善保密密码体制是所有密码体制中最理想的情况：定义1.2 完善保密密码体制 明文空间为的密码体制(Gen,Enc,Dec)是完善保密密码体制，如果对于上任意的概率分布，任何明文，任何密文且，都有下面给出完美不可区分性对于完善保密密码体制的等价刻画。记为加密时的密文概率分布。定义1.3 完美不可区分性 的概率分布独立于明文。也就是说，对于任意的，和的分布是相同的。由此，可以得到一下结论：定理1.1 明文空间为的密码体制(Gen,En

5、c,Dec)是完善保密密码体制当且仅当对于任意上的概率分布，以及，都有证明：必要性显然。下证充分性：记由条件可知，对于任意的，都有，于是由于的任意性，故对任意的，即该密码体制是完善的。 以上使用完美不可区分性给出了完善保密密码体制的等价条件。而在现代公钥密码学领域更多研究的则是称之为“敌手不可区分性”与密码体制安全性的内在联系。在第二部分将给出敌手不可区分性的相关内容，这块内容将涉及不可区分实验（游戏），根据敌手能力的不同，游戏的进行方式也有所不同。第二部分：不可区分实验（游戏） 在给出敌手不可区分性的定义之前，有必要对敌手的能力进行简单的分析和归类。下面首先介绍公钥密码体制中，敌手的攻击手段

6、以及相应与这种攻击手段，敌手所具备的破译密码体制的能力：（1）唯密文攻击(COA)：敌手只能通过考察一些密文来试图推导出解密密钥（即私钥）或这些密文对应的明文（2）已知明文攻击(KPA)：敌手已知一定数量的明文和相对应的密文，试图推导出私钥或者其他密文对应的明文。（3）非适应性选择明文攻击(CPA1)：敌手可以选择一些明文，通过访问加密谕言机，得到这些明文相对应的密文（4）适应性选择明文攻击(CPA2)：敌手可以选择一些明文，通过访问加密谕言机，得到这些明文相应的密文，且明文的选可依赖于前面得到的密文。值得注意的是，CPA1和CPA2的主要区别是在访问加密预言机的时候，CPA1 只能一次性提交

7、所选择的所有明文，而CPA2 可以多次分阶段提交所选择的明文。所以从敌手能力的角度来说，CPA2的敌手能力更强。CPA1和CPA2统称为CPA。 但是CPA的敌手毕竟是属于被动的，下面两种攻击方式属于主动攻击：（5）非适应性选择密文攻击(CCA1)：敌手可以选择密文，接着得到相应的明文。即敌手拥有解密谕言机的访问权。（6）适应性选择密文攻击(CCA2) ：敌手可以选择密文，得到相应的明文。且在见到挑战密文之后还能继续访问解密谕言机。 在这里CCA2 与CCA1 的区别在于敌手是否拥有在见到挑战密文后还能访问解密谕言机的能力。CCA2 中敌手有这个能力，但CCA1 没有。CCA1 也称为“午餐攻

8、击”，意味着过了“午餐”时间，就不能再访问解密谕言机了。 敌手的攻击能力基本上可以分为以上六种，但是随着科技的进步，敌手的能力在不断增强，需要我们对最新的攻击方式做出新的安全性分析和证明。下面将介绍近代公钥密码体制中对安全性（语义安全性）普遍刻画不可区分实验（游戏）。首先需给出最基本的所谓窃听不可区分实验：设任意对称密钥密码体制(Gen,Enc,Dec) ，任何敌手，对任意安全参数，定义窃听不可区分实验：（1）敌手输出两个长度相等的消息。（2）运行Gen函数生成密钥，选择一个随机比特，将加密得到密文，并将密文给敌手。（称为挑战密文）（3）敌手输出，如果，则敌手攻击成功。（注意：这里的敌手默认为

9、PPT的敌手）定义2.1 敌手优势函数 参数为的函数称为敌手优势函数。这个函数形象地刻画了敌手猜对那一比特的优势。利用敌手优势函数，我们可以非常自然地给出密码体制语义安全性的定义。不过在这之前，首先应该给出所谓函数“可忽略”的定义：定义2.2 对于函数是可忽略的，如果，存在正整数使得时都有，定义2.3 密码体制(Gen,Enc,Dec)是语义安全的，如果对于任何PPT的敌手，敌手优势函数可忽略。 这个定义给出了一般密码体制的安全性刻画，下面针对于公钥密码体制，我们给出它的安全性定义，为了方便起见，我们将给出一个包含了不可区分实验以及敌手优势函数的全新定义：定义2.4 一个公钥密码体制是语义安全

10、的，如果对于所有的PPT敌手，函数是可忽略的。 在这个定义中，和对应着实验中的第一步（公钥密码体制中密钥是公开的，所以出现在第一步），和是实验中的第二步，则是实验中的第三步，最后考察的事件则是。以后如果不作说明，均已这个定义来阐述密码体制的语义安全性。 这里可以举一个例子来说明如何定义能够防御特定攻击能力的敌手的密码体制的安全性： 由上述对低收的分类我们知道适应性选择密文攻击即CCA2的敌手拥有比较强大的攻击能力，针对这样的敌手，我们应该如何定义相应的安全性呢？ 首先我们可以写出CCA2的不可区分实验：（1）运行Gen函数生成密钥，敌手获得公开钥。（2）敌手访问解密谕言机。（即敌手输入密文，谕

11、言机返回该密文对应的明文）（3）敌手输出两个长度相等的消息。（4）选择一个随机比特，将加密得到挑战密文，并将挑战密文给敌手。（5）敌手继续访问解密谕言机。（敌手输入的密文不能是挑战密文）（6）敌手输出，如果，则敌手攻击成功。从上面的过程中我们可以发现在CCA2的不可区分实验中，敌手可以随时访问解密谕言机，敌手试图通过这些访问的结果来增加自己猜对的可能。正是因为如此，我们要求敌手无法从这些访问的信息中得到挑战密文的任何信息或者得到可忽略的信息。因此，CCA2安全性定义如下：定义2.4.1 一个公钥密码体制是CCA2语义安全的，如果对于所有的PPT敌手，都有，有时，函数是可忽略的。类似的我们可以定

12、义很多密码体制的语义安全性，在这里不多作赘述。第三部分：规约证明 这一部分主要介绍如何证明一个密码体制安全性的一种方法规约证明。 定义3.1 所谓规约，其实是复杂性理论中的概念，一个问题规约到问题是指，已经解决问题的算法，我们能够构造另一个算法，可以以作为子程序，用来解决问题。如果我们将规约的方法运用到密码学领域中的话，则可以达到证明密码体制安全性的目的。 我们可以把敌手对密码体制的攻击规约到一个易经得到深入研究的密码本原。即如果敌手能够对该密码体制发动有效的攻击，就可以利用敌手构造一个算法来攻破密码本原，从而得出矛盾。 下面我们具体到对密码体制的安全性证明上来讨论规约。假设我们要证明一个密码

13、体制的安全性，我们可以将体制规约到体制上，即如果敌手能够攻击体制，则敌手能够攻击体制，其中体制是已经证明安全的，或是一个困难问题，或是一个密码本原。我们可以通过下图来描述两个方案之间的规约： 图中挑战者表示建立密码体制的一方，表示敌手。当敌手能够成功地攻击体制的时候，敌手模拟的挑战者，参考体制的挑战者对自己的训练去训练敌手，使攻破体制，从中敌手掌握了如何利用敌手攻破体制的方法以及挑战者对自己的训练来攻破体制。 规约证明的方法已经成为现代公钥密码学可证明安全性的基础，任何密码体制被提出必须对其进行安全性进行证明。而规约证明的方法则是目前一个非常实用的证明密码体制安全性的方法。下面一个部分我们将看

14、到如何使用规约证明的方法给出一些特殊的密码体制的安全性证明第四部分：一个例子这一部分将通过一个例子说明不可区分性在公钥密码学中的应用。例1. ElGamal加密算法在选择明文(CPA)攻击下的安全性分析ElGamal加密算法：密钥产生：设是阶为大素数的群，为其生成元，即。随机选择，计算。以为秘密钥，为公开钥。加密（Enc）：设消息，随机选择与互素的整数，计算密文为解密（Dec）： 在分析其安全性之前，我们首先验证一下加密算法的正确性，即是否满足式子Dec(Enc() 显然，满足式。 下面对其安全性进行分析：ElGamal加密算法的安全性是基于Diffie-Hellman判定性问题：设是阶为大素

15、数的群，为其生成元。没有多项式时间的算法可以区分以下两个分布： 随机4元组的分布； Diffie-Hellman 4元组的分布，其中，。 这里对次问题进行变形，我们做代换：，那么上述两个分布变形为： 随机3元组的分布； Diffie-Hellman 3元组的分布。， 那么ElGamal加密算法与Diffie-Hellman判定性问题不可区分。原因在于当挑战者与敌手进行CPA不可区分游戏时，敌手输出两个长度相同的消息，挑战者加密，得到密文。 如果，则为Diffie-Hellman 3元组。 如果，则也为Diffie-Hellman 3元组。两者不可区分。 不可区分性在公钥密码学中扮演着十分重要的角色，是可证明安全理论的基石，也是证明密码体制或者加密算法在某种意义下安全的必要手段。本文对于不可区分性内容的归纳尚未系统化，有些结论也只是适用于较平凡的情况。比如第四部分的例子中，ElGamal加密算法在CPA意义下已经能够证明是安全的，但是这是基于敌手完全被动的情况，如果敌手能够选择性的发动主动攻击，这个加密算法也是不安全的。例如敌手可以在得到的密文上进行更改，构造出新的密文，其中，解密询问以后得到，通过计算得到的明文。或者可以构造，其中，此时解密