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

不可区分性在公钥密码学中的应用

摘要：本文主要总结了不可区分性在公钥密码体制中的运用，这些运用主要包括如何刻画密码体制的安全性（语义安全性）、如何通过规约的方式利用不可区分实验证明密码体制的安全性、以及一些常见的密码体制中不可区分性的作用。全文主要分为三个部分，第一部分主要介绍了一些基础知识，包括密码体制的组成以及完善保密密码体制的含义，如何利用不可区分性来等价描述完善保密密码体制。第二部分主要介绍了不可区分实验（游戏）在公钥密码学中的应用。这一部分先对攻击者的层次进行了划分，之后介绍了如何用不可区分实验来给最基本的密码体制的语义安全性下定义。这一部分最后利用CCA2的语义安全性作为例子说明如何利用不可区分实验定义拥有特定防御功能的公钥密码体制的语义安全性。第三部分介绍了规约证明的相关内容，规约证明现如今已成为现代公钥密码学可证明安全理论常用的证明方法，而两个问题规约的过程中与不可区分性密不可分。第四部分主要举了一个例子来说明不可区分性在证明密码体制安全性中的应用。本文对公钥密码学中的不可区分性理论做了比较简单的总结和归纳，不可区分性在公钥密码学可证明安全理论中有着十分重要的地位，本文对刚刚接触不可区分性的学者有着一定的帮助。

第一部分：基础知识及不可区分性的定义

这一部分内容主要介绍一下有关于不可区分性的基础知识，包括密码体制的组成、完善保密密码体制、完美不可区分性的含义以及敌手不可区分性的含义。首先先给出密码体制的定义：

定义1.1 密码体制

[1]一个密码体制由三个部分构成：密钥产生算法Gen、加密

算法Enc、解密算法Dec。他们的功能如下：

（1）密钥产生算法Gen是一个概率算法，能够根据方案定义的某种分布选择并输出一个密钥k.

（2）加密算法Enc，输入为密钥k和明文m，输出为密文c。把使用密钥k加密明文m记为Enck(m).

（3）解密算法Dec，输入为密钥k和密文c，输出为明文m。把使用密钥k解密密文c记为Deck(c).

对任意的密码体制的基本要求是：对任意通过Gen输出的密钥k，每个明文消息m都满足

Deck(Enck(m))?m

密钥生成函数Gen输出的所有可能的密钥称为密钥空间，用K表示。所有明文消息的集合称为明文空间，记作M。集合K和M一起定义了所有可能的密文的集合C，称为密文空间。上述密码体制可记为明文空间为?的密码体制(Gen,Enc,Dec).

如何刻画一个密码体制的安全性，完善保密密码体制是所有密码体制中最理想的情况：

定义1.2 完善保密密码体制

[1] 明文空间为?的密码体制(Gen,Enc,Dec)是完

善保密密码体制，如果对于?上任意的概率分布，任何明文m?M，任何密文

c?C且Pr[C?c]?0，都有

Pr[M?m|C?c]?Pr[M?m]

下面给出完美不可区分性对于完善保密密码体制的等价刻画。记C(m)为加密

m?M时的密文概率分布。

定义1.3 完美不可区分性

[1] C的概率分布独立于明文。也就是说，对于任意

的m0,m1?M，C(m0)和C(m1)的分布是相同的。

由此，可以得到一下结论： 定理1.1

[1] 明文空间为?的密码体制(Gen,Enc,Dec)是完善保密密码体制当且

仅当对于任意?上的概率分布，m0,m1?M以及c?C，都有

Pr[C?c|M?m0]?Pr[C?c|M?m1]

证明：必要性显然。

下证充分性：记p?Pr[C?c|M?m0]由条件可知，对于任意的m?M，都有

Pr[C?c|M?m]?Pr[C?c|M?m0]?p，于是

Pr[C?c]??m?M?Pr[C?c|M?m]?Pr[M?m]?p?Pr[M?m]m?Mm?M

?p??p?Pr[M?m]?Pr[C?c|M?m0]由于m0的任意性，故对任意的Pr[M?m|C?c]?Pr[M?m]，即该密码体制是完善的。

以上使用完美不可区分性给出了完善保密密码体制的等价条件。而在现代公钥密码学领域更多研究的则是称之为“敌手不可区分性”与密码体制安全性的内在联系。在第二部分将给出敌手不可区分性的相关内容，这块内容将涉及不可区分实验（游戏），根据敌手能力的不同，游戏的进行方式也有所不同。

第二部分：不可区分实验（游戏）

在给出敌手不可区分性的定义之前，有必要对敌手的能力进行简单的分析和归类。下面首先介绍公钥密码体制中，敌手的攻击手段以及相应与这种攻击手段，敌手所具备的破译密码体制的能力：

（1）唯密文攻击(COA)：敌手只能通过考察一些密文来试图推导出解密密钥（即私钥）或这些密文对应的明文

（2）已知明文攻击(KPA)：敌手已知一定数量的明文和相对应的密文，试图推导出私钥或者其他密文对应的明文。

（3）非适应性选择明文攻击(CPA1)：敌手可以选择一些明文，通过访问加密谕言机，得到这些明文相对应的密文

（4）适应性选择明文攻击(CPA2)：敌手可以选择一些明文，通过访问加密谕言机，得到这些明文相应的密文，且明文的选可依赖于前面得到的密文。

值得注意的是，CPA1和CPA2的主要区别是在访问加密预言机的时候，CPA1 只能一次性提交所选择的所有明文，而CPA2 可以多次分阶段提交所选择的明文。所以从敌手能力的角度来说，CPA2的敌手能力更强。CPA1和CPA2统称为CPA。 但是CPA的敌手毕竟是属于被动的，下面两种攻击方式属于主动攻击：

（5）非适应性选择密文攻击(CCA1)即敌手拥有解密谕言机的访问权。 （6）适应性选择密文攻击(CCA2)

[5]：敌手可以选择密文，接着得到相应的明文。

[5]：敌手可以选择密文，得到相应的明文。且

在见到挑战密文之后还能继续访问解密谕言机。

在这里CCA2 与CCA1 的区别在于敌手是否拥有在见到挑战密文后还能访问解密谕言机的能力。CCA2 中敌手有这个能力，但CCA1 没有。CCA1 也称为“午餐攻击”，意味着过了“午餐”时间，就不能再访问解密谕言机了。

敌手的攻击能力基本上可以分为以上六种，但是随着科技的进步，敌手的能力在不断增强，需要我们对最新的攻击方式做出新的安全性分析和证明。下面将介绍近代公钥密码体制中对安全性（语义安全性）普遍刻画——不可区分实验（游戏）。首先需给出最基本的所谓窃听不可区分实验：

设任意对称密钥密码体制??(Gen,Enc,Dec) ，任何敌手A，对任意安全参数

eavn，定义窃听不可区分实验PrivKA,?(n)：

（1）敌手A输出两个长度相等的消息m0,m1。

（2）运行Gen函数生成密钥k，选择一个随机比特b??0,1?，将mb加密得到密文（c称为挑战密文） c，并将密文给敌手A。

（3）敌手输出b'，如果b'?b，则敌手攻击成功。（注意：这里的敌手默认为PPT的敌手）

定义2.1 敌手优势函数 参数为n的函数

[1]

AdvA,?(n)?Pr[b'?b]?1 2称为敌手优势函数。这个函数形象地刻画了敌手猜对那一比特b的优势。

利用敌手优势函数，我们可以非常自然地给出密码体制语义安全性的定义。不过在这之前，首先应该给出所谓函数“可忽略”的定义：

定义2.2

[2] 对于函数?(?):N??0,1?是可忽略的，如果?c?0，存在正整数

Nc使得?N?Nc时都有，