4.1 ：Introduction to Basic Concepts
4.1.1 Mathematical Primitives and Superstructures
通過(guò) 數(shù)學(xué)原語(yǔ) 可以定義 數(shù)學(xué)難題 和 構(gòu)建 密碼學(xué)方案。
分析 加密方案的安全性 要比 分析數(shù)學(xué)難題的困難程度 復(fù)雜的多牍氛。引入 安全歸約 就是用來(lái)以相對(duì)簡(jiǎn)單的方式 來(lái)分析加密方案的安全性。
-
在安全歸約中堤舒，如果一個(gè)密碼學(xué)方案 是基于 數(shù)學(xué)原語(yǔ) 構(gòu)造的仅父，那么 該方案 潛在的數(shù)學(xué)難題 也一定是基于這個(gè)數(shù)學(xué)原語(yǔ)定義的慢哈。
relationship 編寫(xiě)一個(gè)準(zhǔn)確的安全歸約 高度依賴于： the cryptosystem,
security model, proposed scheme, and hard problem.簡(jiǎn)單來(lái)說(shuō)匣砖，數(shù)學(xué)原語(yǔ) 就是將一個(gè)數(shù)學(xué)問(wèn)題 以 string 的形式輸入（個(gè)人理解布朦，如有錯(cuò)誤腿倚，請(qǐng)指正）纯出。該 string 的 bit length 就是安全參數(shù) λ 。
在基于群的密碼學(xué)中猴誊，安全參數(shù) λ 特指 群元素的bit長(zhǎng)度潦刃。例如：1024bit
在本書(shū)中，當(dāng)提到 一個(gè)密碼學(xué)方案（或一個(gè)數(shù)學(xué)難題）是由安全參數(shù) λ 生成的懈叹，就意味著：其底層的數(shù)學(xué)原語(yǔ) 是以 安全參數(shù) λ 生成的乖杠。（即 該數(shù)學(xué)原語(yǔ)的字符串bit長(zhǎng)度為 λ ）
4.1.2 Mathematical Problems and Problem Instances
數(shù)學(xué)問(wèn)題 & 問(wèn)題實(shí)例
一個(gè)數(shù)學(xué)問(wèn)題（在數(shù)學(xué)原語(yǔ)上定義的）就是一個(gè) 有確切 問(wèn)題 和 答案 的數(shù)學(xué)對(duì)象。（a mathematical object representing certain questions and answers.）
每個(gè)數(shù)學(xué)問(wèn)題 都應(yīng)該有對(duì) 輸入（問(wèn)題）和 輸出（答案）的描述澄成。
數(shù)學(xué)問(wèn)題 可以被分為：
- computational problems （計(jì)算問(wèn)題）
- decisional problems （決策問(wèn)題）
其中胧洒，決策問(wèn)題 可以看做是 計(jì)算問(wèn)題 的特例（即 答案 只有 true & false 的計(jì)算問(wèn)題）
- 數(shù)學(xué)問(wèn)題 的輸入 即為 問(wèn)題實(shí)例畏吓。（一個(gè)數(shù)學(xué)問(wèn)題 應(yīng)該有 無(wú)數(shù)個(gè) 問(wèn)題實(shí)例），如：
數(shù)學(xué)問(wèn)題：大整數(shù)因式分解問(wèn)題
問(wèn)題實(shí)例：給定14803卫漫，因式分解得到113和131
數(shù)學(xué)問(wèn)題 和 問(wèn)題實(shí)例 的關(guān)系菲饼，就類(lèi)似于 Java 類(lèi)（Class）和 實(shí)例對(duì)象（Object）的關(guān)系。
在安全歸約中列赎，如果我們能找到 一個(gè)確切的 solution (answer) 來(lái)解決 一個(gè)數(shù)學(xué)問(wèn)題 中 某個(gè)任意隨機(jī)的問(wèn)題實(shí)例宏悦，那么就表明，這個(gè)數(shù)學(xué)問(wèn)題是 可以被 有效地解決的包吝。
如果一個(gè) 數(shù)學(xué)問(wèn)題 是由安全參數(shù) λ 生成的饼煞，那么就 以 函數(shù) P(λ) 來(lái)表示 解決這個(gè)問(wèn)題的難度等級(jí)。
對(duì)于不同的問(wèn)題诗越，函數(shù) P(λ) ——即解決問(wèn)題的難度等級(jí) 是不同的砖瞧。 即使 這些不同的問(wèn)題 是在同一個(gè) 數(shù)學(xué)原語(yǔ)之上定義的。
4.1.3 Cryptography, Cryptosystems, and Schemes
密碼學(xué) & 密碼系統(tǒng) & 方案
4.1.4 Algorithm Classification 1
- 算法可以被分為兩類(lèi)：
- 確定性算法(deterministic algorithms)
- 概率性算法(probabilistic algorithms)
確定性算法： 當(dāng)輸入一個(gè)問(wèn)題實(shí)例時(shí)嚷狞， 它總是返回一個(gè)正確的結(jié)果块促。
概率性算法： 當(dāng)輸入一個(gè)問(wèn)題實(shí)例時(shí)， 得到的結(jié)果可能是正確的床未，也可能是不正確的
- 我們用 (t,ε) 表示算法在時(shí)間 t 內(nèi)以成功概率 ε 返回一個(gè)正確
結(jié)果竭翠。
? 具有 (t,ε) 的算法在密碼學(xué)中 有如下兩個(gè)不同的應(yīng)用：
① 如果該算法用于衡量它返回正確結(jié)果的成功程度， 則將ε
視為概率即硼。
② 如果該算法用于衡量它攻破方案或解決困難問(wèn)題的成功程
度逃片， 則ε被視為一個(gè)優(yōu)勢(shì)。
在本書(shū)中只酥， 算法主要用于應(yīng)用②褥实， 因此 ε 默認(rèn)為優(yōu)勢(shì)（advantage）
優(yōu)勢(shì) 可以理解為 是 概率 在 另一種情形下的定義
4.1.5 Polynomial Time and Exponential Time
（多項(xiàng)式時(shí)間 & 指數(shù)級(jí)時(shí)間）
- 假設(shè)一個(gè)方案是由安全參數(shù) λ 構(gòu)造的（或者一個(gè)問(wèn)題是由
安全參數(shù)λ生成的） ， 令函數(shù) t(λ) 為某算法攻破該方案或解決該問(wèn)
題的 時(shí)間成本 裂允。
注意：多項(xiàng)式時(shí)間 和 指數(shù)級(jí)時(shí)間 中間多度 為亞指數(shù)時(shí)間(sub-exponential time)
4.1.6 Negligible and Non-negligible
（可忽略的 & 不可忽略的）
- 假設(shè)一個(gè)方案是由安全參數(shù)λ構(gòu)造的（或者一個(gè)問(wèn)題是由
安全參數(shù)λ生成的） 损离， 令函數(shù) ε(λ)為一個(gè)算法攻破該方案或解決
該問(wèn)題的優(yōu)勢(shì)。 - negligible
另一種定義方式：
4.1.7 Insecure and Secure
- 所有方案可以分為 “不安全” 和 “安全” 兩類(lèi)
- 不安全： 在安全模型中绝编， 如果 存在 能在多項(xiàng)式時(shí)間內(nèi) 以不可忽略的優(yōu)勢(shì) 攻破方案的敵手僻澎， 則由安全參數(shù)λ生成的方案是不安全的。
- 安全： 在安全模型中十饥， 如果 不存在 能在多項(xiàng)式時(shí)間內(nèi)以不可忽略的優(yōu)勢(shì)攻破方案的敵手窟勃， 則由安全參數(shù)λ生成的方案是安全的。
方案的安全與否 與 安全參數(shù) & 安全模型 均有關(guān)系逗堵，不能草率的 聲明一個(gè) 方案 是否安全秉氧。
4.1.8 Easy and Hard
數(shù)學(xué)難題的 難易程度 是一個(gè)模糊的相對(duì)概念。我們無(wú)法準(zhǔn)確的給出一個(gè)問(wèn)題的 困難程度蜒秤。
當(dāng)下 困難的問(wèn)題 以后可能會(huì) 變成 簡(jiǎn)單問(wèn)題
4.1.9 Algorithm Classification 2
假設(shè)存在一個(gè) 算法汁咏，它可以在 時(shí)間 t 內(nèi), 以 ε 的優(yōu)勢(shì) （in time t with advantage ε ）打破一個(gè)方案或解決一個(gè)難題（該方案或問(wèn)題是由 安全參數(shù) λ 生成的）
計(jì)算高效的算法也叫做 概率多項(xiàng)式時(shí)間算法(probabilistic polynomial-time (PPT) algorithm)
4.1.10 Algorithms in Cryptography
公鑰密碼學(xué)中的所有算法可以分為以下四種類(lèi)型亚斋，每種類(lèi)型 都有不同的定義 和 目的。
- 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).
在上述算法中攘滩，我們只要求 攻擊算法帅刊、求解算法和 歸約算法 的優(yōu)勢(shì)e 是不可忽略，而方案算法 中的 概率e 接近于1漂问。
如果敵手可以攻破方案或解決難題赖瞒，就表示：
敵手已知的 相應(yīng)的攻擊算法 或 相應(yīng)的求解算法 是計(jì)算高效的
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.
安全歸約： 是安全性證明的一部分， 重點(diǎn)是 如何將 攻破給定的方案 歸約到 解決潛在困難問(wèn)題 上级解。 安全歸約包括 模擬算法 和 求解算法 冒黑。
安全性證明： 要使我們確信方案是安全的。除了安全歸約之外勤哗， 安全性證明還應(yīng)該包括 對(duì) 安全歸約 的正確性分析。
致謝
本文主要內(nèi)容 基本出自 于新穎 師姐之手掩驱。非常感謝她的幫助芒划。
此處附上她的博客主頁(yè)：yxy517
