《A Graduate Coursse in Applied Cryptography》chapter 3 Stream ciphers （3）

Bertha 。 2022-10-19 13:00 124阅读 0赞

A Graduate Coursse in Applied Cryptography》chapter 3  Stream ciphers （3）  
原文教材：

Boneh Dan , Shoup Victor . A Graduate Course in Applied Cryptography\[J\].

《概率论与数理统计教程》（第二版）茆诗松 程依明 濮晓龙

该书项目地址（可以免费获取）：http://toc.cryptobook.us/

系列博客为对该教材的学习笔记（只包括我认为重要的东西）

## 计算不可区分（Computational Indistinguishability） ##

计算不可区分在该书的定义如下：

![20210711111759661.png][]这个概念的被提出的目的，在于描述两个概率分布式不可区分的，那么如何刻画两个概率是不可区分的，借助“统计距离”（statistical distance）这个数学工具来刻画两个概率的接近程度。

在理解统计距离这个概念之前，我们从头开始理解一下目前这个计算不可区分的概念，我们得到以下的几个基础的问题与共识：

1.此处计算不可区分的概念针对的主体是两个概率分布。

2.什么是概率分布？

3.此处描述主体是什么分布？

4.什么是统计距离？

5.计算不可区分和统计距离之间的关系？

### 什么是分布？ ###

分布指的是随机变量的分布，只有随机变量才存在分布的概念，取值有限的变量称为离散随机变量，取值连续的变量称为连续随机变量。我们取一个随机变量值一定知道其分布情况，即为每个随机变量取值的概率是如何变化的。这些随机变量对应的概率称之为分布，有无分布是区分一般变量与随机变量的主要标志。离散随机变量一般使用分布列来描述其分布情况，连续随机变量一般使用概率密度函数来描述其分布情况。以上两种描述方法均遵循两个特性，非负性与正则性。非负性为任何概率不为负数。正则性表示所有变量概率和为1.

## 此处描述主体是什么分布？ ##

在此处的语境下，两种分布应该是在同一个有限域下的两种不同均匀分布。均匀分布又称为为平顶分布，即在区间(a,b)上每个变量对应的概率相同。古典概率中的几何概率就是一种均匀分布。均匀分布如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

## 什么是统计距离？ ##

统计距离是统计学上的概念，根据不同的对象有不同的距离描述方法，例如欧氏距离，曼哈顿距离，切比雪夫距离等。此处两个分布之间的统计距离定义如下：

![20210711180735705.png][]

这里介绍的是两个分布之间的统计距离，对于在有限集R中，所有的取值在两个概率分布中对应概率的差值求和定义为两个分布之间的距离。这里的二分之一系数，我个人理解为是对两个分布之间距离的细化描述，相当于是描述两个分布到他们之间的中心距离是多少，如果两个分布完全相同，那么这两个分布到他们距离的中心距离也是0。

另外，还有描述两个随机变量之间的统计距离，两个随机变量的统计距离SD描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

即为在同一个有限集合R中，两个随机的变量的统计距离。

## 计算不可区分和统计距离之间的关系？ ##

首先，我们回忆之前该书之间提及的一个攻击游戏3.3。

![20210712230211124.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

这里有两个实验，其中根据实验的不同，挑战者选择不同概率分布来生成挑战信息，并发送给敌手，然后由敌手来猜测并输出一个比特。定义敌手获得的信息为：![20210712232844411.png][]，此处的r 即为上图的挑战信息x。所以，我们可以得到事件Wb 发生的概率等于敌手持有信息R\`在分布Pb下的概率。

即为等式 ![20210712233109964.png][]

所以敌手的优势（计算不可区分）与统计距离的关系如下：

![20210712233232860.png][]

[20210711111759661.png]: /images/20221004/1a099ec0f4574016825ac083b0a6ace9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221004/c5813cda1b204164a063fd3f87bb98a3.png
[20210711180735705.png]: /images/20221004/f2856a9fb1104acdb1c3b896cc161ec8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221004/f059ccce42d14576bb842c1aa1c0c696.png
[20210712230211124.png]: /images/20221004/42dd7253c4f443beafebc74a86b3e5be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221004/f3fb4cc47feb4598ae2dd51a9a1b0b27.png
[20210712232844411.png]: /images/20221004/e03fd8c040be4d76be1a77f0347579c9.png
[20210712233109964.png]: /images/20221004/51489affa24344e08d0fdb1d0a0f9760.png
[20210712233232860.png]: /images/20221004/fb198b504c544d59b0dcf4505d06bbc8.png