《A Graduate Coursse in Applied Cryptography》chapter ２ Encryption （2）

亦凉 2023-01-20 08:08 21阅读 0赞

# 《A Graduate Coursse in Applied Cryptography》chapter ２ Encryption （2） #

*原文教材：*

*        Boneh D, Shoup V. A graduate course in applied cryptography\[J\]. Recuperado de https://crypto. stanford. edu/~ dabo/cryptobook/BonehShoup\_0\_4. pdf, 2017.*

*Boneh D, Shoup V. A Graduate Course in Applied Cryptography\[J\].*

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

### 语义安全（semantic security） ###

本书在第二章节加密部分最主要探讨的内容为：语义安全   并且该书从两个方面给出了语义安全的定义。

说起语义安全，我们还是要回到最开始的安全性定义“完美保密”。

首先回顾一下：完美保密的定义

完美保密：当我们获得一个密文C时，我们不能获得该密文对应的明文的任何信息（即使是关于对应明文的1比特信息）。或者说，我们得到一个明文，我们无法从该明文上获得任何的密文信息（即使是关于密文的1比特信息）。

然而，我们都知道完美保密实现上是困难的，所以一般使用完美保密的弱化定义，例如语义安全，语义安全要求就是敌手获得信息的概率是可忽略的，并非严格定义不可能。所以我们更加关注的是语义安全。

形式化如下所示：

设存在一个谓语或者断言，能够从密文获取获取某些信息。

完美保密要求如下：

![20210512164010934.png][]

**         ** 语义安全要求如下：

![20210512164638279.png][]

显然，安全性定义得到了放宽。

### 如何描述语义安全？ ###

任何的安全性定义往往都是对敌手攻击方式的抽象描述，语义安全也有其安全模型定义。

第一种描述方法：

设存在两个挑战者，敌手每次与挑战者交互，猜测是与哪一个挑战者运行的系统交互并尝试破坏该挑战者运行的方案。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

![2021051217011297.png][]

第二种描述方法：

在上述内容中，简单来看就是运行两个挑战者，然后让敌手来测试运行的是哪一个实验，（这两个实验也是不可区分的，必须是不可区分的在此处）。

另一种语义安全描述方式，由挑战者来选择 b = 0,1。然后由敌手进行猜测挑战者到底选择了哪一条消息进行加密。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

此时，敌手的优势为：![SSadv\*=|Pr\[w\]-1/2|][SSadv_Pr_w_-1_2]

这两种语义安全的描述优势具有如下的关系：

![20210512193700833.png][]

推导过程在该书 定理 2.10 部分，此处不在赘述。

那么这里存在一个问题，为什么会有这个2倍的关系？

对于这个问题的答案，我个人认为是因为第一种优势描述方式是用赢得游戏概率减去失败的概率作为优势的刻画数学描述，而第二种描述方式只是针对赢得游戏的概率进行计算。

### 语义安全模型中几个重要组件概念 ###

有效的交互式机器（efficient interactive machine），在密码学协议中，每一个参与方都可以被抽象成为一种机器（machine）,有点类似图灵机的概念，如果说随着计算复杂性这门学科的发展将密码学

从一门艺术变成了一门科学，那么密码学协议的形式化分析就是“科学化”的过程。将参与方抽象成为一种机器的这种做法出现在很多的密码学论文与书籍中，特别是密码学协议的部分，例如安全多方计算，UC等。

这里，该书只给出了一个最为基础的描述，顺便说一句，在UC通过可组合等其他密码学协议中，还存在大量的复杂的机器及其描述。

![20210512212630698.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

一个有效的交互式机器存在两个缓冲区，一个是接受消息的缓冲区，一个是发送消息的缓冲区，该机器与其他的机器的交互都是通过这两个缓冲区来进行，并且该机器的逻辑功能必须可以有效的执行完成。

机器可以组合成为新的机器，有的内部的机器可以与外部环境交流，有的内部机器则只能和内部的机器交流。

例如，我们可以封装机器的功能，具体描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

通过构造一个接口M\` ，令该接口作为机器M与外界封装的唯一接口，则此时我们可以认为我们将机器M封装为了一个新机器，可以定义该机器为B=<M\`,M>。

**单词表**

Instead of insisting that....  不去坚持......                 By itself: 单独的，自动的                    back and forth : 反复的，来回的

as specified : 按照说明                                           comprise: 包含，由...组成                   slightly:  轻微的

if any:  若有的话，即便要                                       with respect to : 关于                          particular <adj/n> 特别的，详细

but nothing else: 没有其他的                                  catastrophic: <adj> 灾难的                  tedious: <adj> 沉闷的

spontaneous： 自然的                                           enlightening: <adj>使人领悟，有启发的     axiom <n> 公理

as before : 依旧                                                      forward to ： 转发                               essential : 必要的

contrapositive: <adj> 逆反                                     trun into : 转换为                                 motivate<v> 刺激，动机

dummy:  <n> 假的 <adj> 仿真的                           be placed in: 被放置在....                     take away from : 从....拿走

scavenged from ：来自于                                    make use of:  利用                               just as： 正像

As it turn out: 结果是，正如结果                          discipline: <v><n> 学科训练                 complicated <adj> 复杂

headlong <adv> 头朝前                                       crudely: <adj> 粗糙                               associate with: <v> 联合，联系在一起

exceed: 超过                                                        mismatch: <v,n> 错配                           take as: 把...看做

incoming message buffer： 输入消息缓冲区          outgoing message buffer: 输出消息缓冲区

analogous:类似的                                                salient : 显著的，突出的                        start out : 出发，着手进行

fit into：适合，适应                                            violating: 违反                                           forum : 论坛

nested  : 嵌套

[20210512164010934.png]: /images/20221021/88e6a8144fe84d2d92207f94b3c73027.png
[20210512164638279.png]: /images/20221021/bc5e5905fe934916a83ebf3ad86586f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221021/5ccc1b4c596342b79e3075b1499334ef.png
[2021051217011297.png]: /images/20221021/e68d92efd8104689835587b142e634e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221021/52093f1f404240619d1a7d77a7cc87bc.png
[SSadv_Pr_w_-1_2]: https://latex.codecogs.com/gif.latex?SSadv*%3D%7CPr%5Bw%5D-1/2%7C
[20210512193700833.png]: /images/20221021/501106943cd14aadad2a5e84abb50185.png
[20210512212630698.png]: /images/20221021/2f024923501a4c3ab0a0bcad0dc397a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221021/f7decff4c7bc404c8fa13f6d5eb73ca4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221021/4c89d63b653748bba74242efb2b2e847.png