「Cryptography-ZKP」: Lec7 Poly-commit based on ECC

In this series, I will learn Zero Knowledge Proofs (ZKP) on this MOOC, lectured by Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler and Yupeng Zhang.
Any corrections and advice are welcome. ^ - ^

Topics:

  • Poly-commit based on Error-correcting Codes
  • Argument for Vector-Matrix Product
    • Proximity Test
    • Consistency Test
  • Linear-time encodable code based on expanders
    • Lossless Expander
    • Recursive Encoding with constant relative distance

「Cryptography-ZKP」: Lec6 Poly-commit based on Pairing and Discret-log

In this series, I will learn Zero Knowledge Proofs (ZKP) on this MOOC, lectured by Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler and Yupeng Zhang.
Any corrections and advice are welcome. ^ - ^

Topics:

  • KZG poly-commit based on bilinear pairing
    • KZG scheme
    • Powers-of-tau Ceremony
    • Security Analysis
    • Knowledge of exponent assumption
    • Variants: multivariate; ZK; batch openings
  • Bulletproofs poly-commit based on discrete logarithm

「Cryptography-ZKP」: Lec5-The Plonk SNARK

In this series, I will learn Zero Knowledge Proofs (ZKP) on this MOOC, lectured by Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler and Yupeng Zhang.
Any corrections and advice are welcome. ^ - ^

Topics:

  • Preprocessing SNARK
  • KZG Poly-Commit Scheme
  • Proving Properties of committed polys
    • ZeroTest
    • Product Check
    • Permutation Check
    • Prescribed Permutation Check
  • Plonk IOP for General Circuits

「Cryptography-ZKP」: Lec4-SNARKs via IP

In this series, I will learn Zero Knowledge Proofs (ZKP) on this MOOC, lectured by Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler and Yupeng Zhang.
Any corrections and advice are welcome. ^ - ^

Topics:

  • Differences between Interactive Proofs and SNARKs
  • Outline of SNARKs from IP
  • Brief intro to Functional Commitments
  • SZDL Lemma
  • Multilinear Extensions
  • Sum-check Protocol and its application.
    • Counting Triangles
    • SNARK for Circuit-satisfiability

「Cryptography-MIT6875」: Lecture 5
「Cryptography-MIT6875」: Lecture 4
「Cryptography-MIT6875」: Lecture 3

「Cryptography-MIT6875」: Lecture 3

In this series, I will learn MIT 6.875, Foundations of Cryptography, lectured by Vinod Vaikuntanathan.
Any corrections and advice are welcome. ^ - ^

Topics:

  • The Hybrid Argument.
  • An application: PRG length extension.
  • The notion of pseudorandom functions: Definition, motivation, discussion and comparison with PRGs.
  • PRG implies (stateful) secret-key encryption.
  • PRFs imply (stateless) secret-key encryption.

「Cryptography-MIT6875」: Lecture 2

In this series, I will learn MIT 6.875, Foundations of Cryptography, lectured by Vinod Vaikuntanathan.
Any corrections and advice are welcome. ^ - ^

Science wins either way.

Topics:

  • How to circumvent Shannon’s lower bound: the computational adversary
  • Definition of computational security
  • The definition of pseudorandom generators(PRG)

「Cryptography-MIT6875」: Lecture 1

In this series, I will learn MIT 6.875, Foundations of Cryptography, lectured by Vinod Vaikuntanathan.
Any corrections and advice are welcome. ^ - ^

Everything you’ve ever wanted is on the other side of fear.

Topics:

  • Introduction to cryptography
  • Secure Communication and Shannon’s definitions of perfect secrecy
  • Perfect Indistinguishability definitions.
  • The One-time pad construction
  • Shannon’s lower bound.

「Cryptography-Boneh」:Collision Resistance

上一节介绍了基于PRFs的MAC构造和基于随机的MAC:

previous MAC constructions

本节我们将介绍抗碰撞的MAC(MACs from collision resistance)。

第一部分介绍了什么是抗碰撞 (Collision Resistance),以及基于C.R.的MAC的安全性。

第二部分介绍了生日悖论,如何用生日攻击寻找2-way collision 和3-way collision.

第三部分介绍了Merkle-Damgarg范式(如果压缩函数h是C.R.,那么构造出的哈希函数H就是C.R.)以及如何构建C.R.的压缩函数(Davies-Meyer压缩函数).

最后一部分介绍了HMAC (Hash MAC)和一种针对MAC验证的timing attack and defense.


「Cryptography-Boneh」:Integrity

这篇文章主要介绍消息验证码,即MAC (Message Auth. Code)。

文章首先介绍了secure MAC的模型和安全定义,当攻击者能伪造出新的msg/tag对时,MAC就不再安全。

文章的第二部分介绍了基于PRF的MAC构造,根据相关定理,只要PRF的输出空间足够大,且这是一个安全的PRF,则基于PRF的MAC就是安全的。

但基于PRF的MAC只能计算固定消息大小的MAC,如何利用这个工具构造出更大消息空间的MAC?

文章后半部分给出了一些主流的MAC构造:

  • 串行构造:CBC-MAC、NMAC、CMAC
  • 并行构造:PMAC、HMAC(下一篇文章)
  • 基于one-time MAC: CW MAC

此外,文章还介绍了MAC Padding技术。


「Cryptography-Boneh」:Block Cipher 2

作为BlockCipher的第二篇文章。
第一部分介绍了块密码中的抽象概念PRF和PRP的安全定义。
第二部分介绍了两个概念,一个是抵抗one-time key的语义安全,另一个是抵抗many-time key(CPA)的语义安全。

在one-time key中,每条消息都使用新的密钥,类似于流密码中的OTP。介绍了不能抵抗CPA的ECB模式,还阐述了能抵抗CPA的det. CTR模式。

在many-time key中,同一条密钥可以用于加密多条消息,攻击者可以轻易具备CPA能力,文中说明了如果确定性的加密算法,则不能抵抗CPA,而random IV或者unique nonce的方式则可以抵抗CPA。


「Cryptography-Boneh」:Block Cipher 1

这篇文章介绍了块密码。

文中主要分为四个部分。

第一个部分解释了块密码的基础概念,包括抽象概念PRF(伪随机函数)和PRP(伪随机置换)的定义及其安全定义。

第二个部分介绍了经典块密码DES,包括DES的Feistel网络,支撑Feistel网络的Luby-Rackoff定理,triple-DES和对DES的一些攻击方法。特别是有效的中间相遇攻击。

第三个部分介绍了目前流行的块密码AES,包括AES的结构和一些攻击方法等。

最后一小部分介绍了用PRG构造PRF,再利用Feistel网络变成块密码。


「Cryptography-Boneh」:Stream Cipher 3

Stream Cipher的第三篇文章。

文章主要分为两部分,前部分逐步定义Secure PRG的定义,通过引入statistical test(统计测试)和Advantage(优势)得出当且仅当PRG is unpredictable,PRG is secure的结论。

后部分介绍了密码学中的一个重要概念Semantic Security的定义,通过引入 computationally indistinguishable(计算上不可区分)的概念给出定义,并证明了OTP的语意安全和在安全PRG条件下的流密码的语意安全,得出如果流密码中使用的PRG is secure,那么流密码就具备semantic security。

文章开头,也简单介绍了密码学中negligible和non-negligible的含义。


「Cryptography-Boneh」:Stream Cipher 2

作为Stream Cipher的第二篇文章。
第一部分分析了基于Stream Cipher的两种攻击:第一种是Two time pad,第二种是对与其完整性的攻击,即流密码是可被篡改的。
第二部分具体说明了一些使用流密码加密的例子。包括分析基于软件的RC4流密码、基于硬件的CSS流密码和现代的安全流密码:eStream中的Salsa20。


「Cryptography-Boneh」:Stream Cipher 1

Stream Cipher的第一部分:介绍了One Time Pad和Stream Cipher中的PRG。
其中OTP部分叙述了什么是Perfect Secrecy?为什么OTP很难在实践中应用?
Stream Cipher部分中,本文主要阐述了什么是PRG?Stream Cipher的另一种安全的定义(依靠PRG的unpredictable)。
本文后半部分,详细阐述了一种weak PRG——线性同余生成器,它是如何工作的?它为什么不安全?如何攻击它?