【课程知识点总结】安全性归约证明 与 理论密码学

2 minute read

Published:

持续更新至课程结束。最后更新于 2021-10-06

2021 年秋季研一课程笔记,开课地点为雁栖湖。安全性归约证明与理论密码学两门课的课程笔记,因两门课非常类似,故写在一起。本科期间打 CTF 比赛,对应用密码学和密码分析关注较多,对于证明和构造没什么了解,以致本科时很多论文看的半懂不懂,似懂非懂,只会写代码复现,而不知其所以然。这门课补充了我知识体系中的缺漏,因此开文记录。

0. 参考书目与课程大纲

安全性归约证明更侧重于证明技巧与过程,理论密码学主要关注各种密码学原语和组件的性质、构造、应用等,两节课的内容大部分重合。

参考书目

理论密码学课程大纲

教学目标
本课程的目的是为学生打下坚实的密码学理论基础, 开拓学科视野。通过教学,力图使学生能够深刻理解基于计算复杂性的现代密码学思想、熟练掌握安全归约证明的方法与关键技术、精通核心密码原语(包括单向函数、抗碰撞哈希函数、伪随机函数等)以及彼此之间的归约与分离、了解重要密码方案/协议的构造及应用; 思维上能够从抽象的角度和较高的观点理解现代密码学,为进一步学习和研究密码学的高级内容做准备。
章节目录
    第一章 导论 3学时 薛锐
    第1节 基于计算复杂性的现代密码学-预备知识
    第二章 单向函数 4学时 薛锐
    第1节 单向函数的概念
    第2节 弱单向函数隐含强单向函数
    第3节 单向性 vs. 伪随机性范式—Goldreich-Levin定理
    第3节 基于各类具体假设的单向函数构造
    第三章 不可区分性与困难假设 3学时
    第1节 单向性 vs. 伪随机性范式—Goldreich-Levin定理
    第四章 伪随机性与伪随机数发生器 3学时 李红达
    第1节 伪随机数发生器的构造
    第2节 伪随机生成器的应用
    第五章 伪随机函数 3学时 李红达
    第1节 伪随机函数的定义
    第2节 伪随机函数的构造
    第3节 伪随机函数各种变体
    第六章 哈希函数 3学时 李红达
    第1节 哈希函数及各类安全性质
    第2节 哈希函数的通用构造以及具体构造
    第3节 哈希函数的典型应用
    第七章 消息验证码 3学时 李红达
    第1节 消息验证密码的定义
    第2节 信息论和计算意义下的构造
    第八章 私钥加密 3学时 李红达
    第1节 私钥加密的定义
    第2节 私钥加密的通用构造
    第3节 认证加密的定义、构造及应用
    第九章 数字签名 3学时 李红达
    第1节 数字签名的定义及安全性
    第2节 基于单向函数的通用构造
    第十章 随机预言机模型 3学时 李红达
    第1节 随机预言机模型
    第2节 随机预言机模型中的归约
    第3节 随机预言机的实例化方法
    第一十一章 公钥加密 3学时 李红达
    第1节 公钥加密的定义
    第2节 选择明文安全的构造
    第3节 选择密文安全及构造
    第一十二章 不可延展性 3学时 李红达
    第1节 公钥加密的不可延展性
    第2节 私钥加密的不可延展性
    第一十三章 零知识证明 3学时 李红达
    第1节 交互式证明系统
    第2节 (非交互式)零知识证明系统
    第3节 零知识证明系统的应用
    

安全性归约证明课程大纲

教学目标
    该课程内容主要包含安全密码方案(协议)设计的基础知识和安全性归约证明基本方法,目的是使学生在系统学习密码学基本知识的基础上,了解一些前沿问题,理解密码体制与协议的安全模型,基本掌握安全性归约证明的基本思想和方法,为后续相关课的深入学习并从事相关研究奠定基础。
    
章节目录
    第一章 概述 0.1学时 李红达
    第1节 安全性证明简介
    第2节 安全性归约证明
    第二章 数学与计算复杂性基础 0.9学时 李红达
    第1节 数论与代数基础知识
    第2节 信息熵
    第3节 计算复杂性基础
    第4节 计算复杂性
    第三章 密码学基础 12学时 李红达
    第1节 随机分布的不可区分性
    第2节 困难问题与单向函数
    第3节 Hard-Core谓词
    第4节 伪随机性
    第四章 安全性归约证明基础 1学时 李红达
    第1节 基本思想
    第2节 密码假设
    第3节 基本安全模型
    第4节 RO模型
    第5节 关于可证明安全
    第五章 无密钥算法 2学时 李红达
    第1节 Hash函数
    第2节 随机性抽取器
    第六章 安全加密方案 6学时 李红达
    第1节 语义安全性
    第2节 不可区分安全性
    第3节 更多的安全性
    第4节 RO模型下的安全性
    第5节 可否认加密
    第七章 数字签名和消息认证码 6学时 李红达
    第1节 概述
    第2节 基本安全模型
    第3节 签名方案
    第4节 消息认证码
    第八章 基于身份密码体制 2学时 李红达
    第1节 基于身份的加密
    第2节 基于身份的数字签名
    第九章 安全协议简介 3学时 徐海霞
    第1节 概述
    第2节 基本密码协议
    第3节 应用协议
    第十章 高级安全性 3学时 李红达
    第1节 不可区分延展性
    第2节 并发安全性
    第3节 泄漏容忍安全
    第4节 白盒安全性
    第一十一章 代码混淆 2学时 李红达
    第1节 引言
    第2节 虚拟黑盒混淆
    第3节 较弱的混淆
    第4节 混淆在密码学中的应用
    第一十二章 新型密码体制 2学时 李红达
    第1节 基于属性密码体制
    第2节 证据加密
    第3节 函数加密
    

1. 密码学基础

  • 历史与起源

  • 代数知识

    整除与 GCD、同余与剩余类、CRTQR、素性检测、群环域模格

  • 概率论知识

    样本空间与随机变量、条件概率、贝叶斯、Markov 不等式、Chebyshev 不等式、Chernoff 不等式

  • 信息论

    熵、联合熵与条件熵、伪随机熵

  • 计算复杂性理论

    • 图灵机、可计算性

    • 归约(CookKarpLevin、自归约)

    • P 类与 NP 类(满足性问题 SATHAMPATH、三着色问题、子集和问题、图同构问题、整数分解、二次剩余、素数)、NP-complete 问题、CoNP 类、P/poly

    • 随机计算(BPP 类、RP 类、ZPP 类)

  • 常用名词与符号

    可忽略函数 negl(n)、不可忽略函数、显著函数、统计距离 $\Delta(X,Y)$、有限长度比特串集合 ${\lbrace 0,1 \rbrace}^{\ast}$、概率多项式时间 $PPT$、均匀分布 $U_n$、$\text{o}-\text{O}$ 记法

1.1 随机分布的不可区分性

  • 计算不可区分性

    区分器、随机投币、安全参数、计算不可区分、多项式时间不可区分、一致算法、非一致算法、一致计算不可区分性、非一致计算不可区分性、Hybrid technique

  • 多重抽样的不可区分性、重复抽样非一致计算不可区分性

  • 统计不可区分、计算不可区分但统计距离不可忽略

1.2 困难问题与单向函数

  • 给出单向函数严格定义的五次尝试、单向函数的定义

  • 弱单向函数、非全域单向函数

  • 长度正则与保长单向函数

  • 单向函数簇

  • 候选单向函数(整数分解、离散对数、RSA

  • 弱单向函数与强单向函数的关系

  • 非一致单向函数

  • 通用单向函数

  • 单向函数与 $P \overset{?}{=} NP$ 的关系

  • 单向陷门函数

1.3 Hard-core predicates

  • 定义、离散对数下的 Hard-core predicates

  • 单向函数与 Hard-core predicates 的关系

  • Goldreich-Levin 定理(四种特殊情形推导到一种一般情形)

1.4 伪随机性

  • 伪随机、伪随机生成器、扩张因子

  • 伪随机生成器存在则单向函数存在

  • 不可预测性、伪随机当且仅当多项式时间不可预测

  • 基于单向置换的伪随机生成器

    • 单项置换存在,则伪随机生成器存在。

    • 根据 Goldreich-Levin 定理构造伪随机生成器

  • 单向函数与伪随机生成器

    • 伪随机生成器存在,当且仅当单向函数存在。

    • 伪熵生成器、假熵生成器

  • 伪随机函数


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.