4.1 ：Introduction to Basic Concepts

4.1.1 Mathematical Primitives and Superstructures

1. 通过 数学原语 可以定义 数学难题 和 构建 密码学方案。

2. 分析 加密方案的安全性 要比 分析数学难题的困难程度 复杂的多。引入 安全归约 就是用来以相对简单的方式 来分析加密方案的安全性。

3. 在安全归约中，如果一个密码学方案 是基于 数学原语 构造的，那么 该方案 潜在的数学难题 也一定是基于这个数学原语定义的。

   
   
   relationship

4. 编写一个准确的安全归约 高度依赖于： the cryptosystem,
   security model, proposed scheme, and hard problem.

5. 简单来说，数学原语 就是将一个数学问题 以 string 的形式输入（个人理解，如有错误，请指正）。该 string 的 bit length 就是安全参数 λ 。

在基于群的密码学中，安全参数 λ 特指 群元素的bit长度。例如：1024bit

在本书中，当提到 一个密码学方案（或一个数学难题）是由安全参数 λ 生成的，就意味着：其底层的数学原语 是以 安全参数 λ 生成的。（即 该数学原语的字符串bit长度为 λ ）

4.1.2 Mathematical Problems and Problem Instances

数学问题 & 问题实例

1. 一个数学问题（在数学原语上定义的）就是一个 有确切 问题 和 答案 的数学对象。（a mathematical object representing certain questions and answers.）

2. 每个数学问题 都应该有对 输入（问题）和 输出（答案）的描述。

3. 数学问题 可以被分为：

• computational problems （计算问题）
• decisional problems （决策问题）
  其中，决策问题 可以看做是 计算问题 的特例（即 答案 只有 true & false 的计算问题）

4. 数学问题 的输入 即为 问题实例。（一个数学问题 应该有 无数个 问题实例），如：
   数学问题：大整数因式分解问题
   问题实例：给定14803，因式分解得到113和131

数学问题 和 问题实例 的关系，就类似于 Java 类（Class）和 实例对象（Object）的关系。

5. 在安全归约中，如果我们能找到 一个确切的 solution (answer) 来解决 一个数学问题 中 某个任意随机的问题实例，那么就表明，这个数学问题是 可以被 有效地解决的。

6. 如果一个 数学问题 是由安全参数 λ 生成的，那么就 以 函数 P(λ) 来表示 解决这个问题的难度等级。

7. 对于不同的问题，函数 P(λ) ——即解决问题的难度等级 是不同的。 即使 这些不同的问题 是在同一个 数学原语之上定义的。

4.1.3 Cryptography, Cryptosystems, and Schemes

密码学 & 密码系统 & 方案

introduction

4.1.4 Algorithm Classification 1

1. 算法可以被分为两类：

• 确定性算法(deterministic algorithms)
• 概率性算法(probabilistic algorithms)

确定性算法： 当输入一个问题实例时， 它总是返回一个正确的结果。
概率性算法： 当输入一个问题实例时， 得到的结果可能是正确的，也可能是不正确的

2. 我们用 (t,ε) 表示算法在时间 t 内以成功概率 ε 返回一个正确
   结果。
   • 具有 (t,ε) 的算法在密码学中 有如下两个不同的应用：
   ① 如果该算法用于衡量它返回正确结果的成功程度， 则将ε
   视为概率。
   ② 如果该算法用于衡量它攻破方案或解决困难问题的成功程
   度， 则ε被视为一个优势。
   在本书中， 算法主要用于应用②， 因此 ε 默认为优势（advantage）
   优势 可以理解为 是 概率 在 另一种情形下的定义

4.1.5 Polynomial Time and Exponential Time

（多项式时间 & 指数级时间）

1. 假设一个方案是由安全参数 λ 构造的（或者一个问题是由
   安全参数λ生成的） ， 令函数 t(λ) 为某算法攻破该方案或解决该问
   题的 时间成本 。

function

注意：多项式时间 和 指数级时间 中间多度 为亚指数时间(sub-exponential time)

4.1.6 Negligible and Non-negligible

（可忽略的 & 不可忽略的）

1. 假设一个方案是由安全参数λ构造的（或者一个问题是由
   安全参数λ生成的） ， 令函数 ε(λ)为一个算法攻破该方案或解决
   该问题的优势。
2. negligible

non-negligible

另一种定义方式：

4.1.7 Insecure and Secure

1. 所有方案可以分为 “不安全” 和 “安全” 两类

• 不安全： 在安全模型中， 如果 存在 能在多项式时间内 以不可忽略的优势 攻破方案的敌手， 则由安全参数λ生成的方案是不安全的。
• 安全： 在安全模型中， 如果 不存在 能在多项式时间内以不可忽略的优势攻破方案的敌手， 则由安全参数λ生成的方案是安全的。

方案的安全与否 与 安全参数 & 安全模型 均有关系，不能草率的 声明一个 方案 是否安全。

4.1.8 Easy and Hard

EasyOrHard

数学难题的 难易程度 是一个模糊的相对概念。我们无法准确的给出一个问题的 困难程度。
当下 困难的问题 以后可能会 变成 简单问题

4.1.9 Algorithm Classification 2

假设存在一个 算法，它可以在 时间 t 内, 以 ε 的优势 （in time t with advantage ε ）打破一个方案或解决一个难题（该方案或问题是由 安全参数 λ 生成的）

算法分类2

计算高效的算法也叫做 概率多项式时间算法(probabilistic polynomial-time (PPT) algorithm)

4.1.10 Algorithms in Cryptography

公钥密码学中的所有算法可以分为以下四种类型，每种类型 都有不同的定义 和 目的。

算法分类

• Scheme Algorithm： This algorithm is proposed to implement a cryptosystem. A scheme algorithm might be composed of multiple algorithms for different computation tasks.
  We require the scheme algorithm to return correct results except with negligible probability.
• Attack Algorithm： This algorithm is proposed to break a scheme. A scheme is secure if all attack algorithms are computationally inefficient.
• Solution Algorithm： This algorithm is proposed to solve a hard problem. Similarly, a problem is hard if all solution algorithms for this problem are computationally inefficient.
• Reduction Algorithm： This algorithm is proposed to describe how a security reduction works. A reduction algorithm at least consists of a simulation algorithm (how to simulate the scheme algorithm) and a solution algorithm (how to solve an underlying hard problem).

在上述算法中，我们只要求 攻击算法、求解算法和 归约算法 的优势e 是不可忽略，而方案算法 中的 概率e 接近于1。

如果敌手可以攻破方案或解决难题，就表示：
敌手已知的 相应的攻击算法 或 相应的求解算法 是计算高效的

4.1.11 Hard Problems in Cryptography

难题分类

4.1.12 Security Levels

安全等级

4.1.13 Hard Problems and Hardness Assumptions

难度假设

4.1.14 Security Reductions and Security Proofs.

• A security reduction is a part of a security proof focusing on how to reduce breaking a proposed scheme to solving an underlying hard problem. A security reduction consists of a simulation algorithm and a solution algorithm.
• • A security proof consists of all components required to convince us that a proposed scheme is indeed secure. Besides a given security reduction, it should also include a correctness analysis for the proposed security reduction.

安全归约： 是安全性证明的一部分， 重点是 如何将 攻破给定的方案 归约到 解决潜在困难问题 上。 安全归约包括 模拟算法 和 求解算法 。
安全性证明： 要使我们确信方案是安全的。除了安全归约之外， 安全性证明还应该包括 对 安全归约 的正确性分析。

致谢

本文主要内容 基本出自 于新颖 师姐之手。非常感谢她的帮助。
此处附上她的博客主页：yxy517