数据安全与密码学基础

密码学基础模型

• Alice与Bob在加密通信的过程中，由Eve对两人进行攻击（解密）。此时Alice与Bob拥有secret key，而Eve不知道这个key

$Gen(\cdot)\rightarrow sk(secret\ key)$, the process of generate secret key contains randomness.

$Enc(sk,M)\rightarrow C$, at most of time encryption and decryption are not random

$Dec(sk,C)\rightarrow M$

• How to define “Correctness”
  • M is message space, K is secret key space
  • $\forall m\in M,P[Dec(Enc(sk,m))=m]=1$

Power of adversary

• Can the adversary know (Gen, Enc, Dec)
  Assumption: if the security of the Cryptosystem highly relies on the fact that “Adv does not know (Gen, Enc, Dec)”
  Eventually leaks, costs much

Provable Security

In traditional age, people use

• shift encryption
  Too easy, the sk space is only 25
• substantial encryption
  not that easy, but can be attack by frequency attack
• …

$$proof\rightarrow evidence\rightarrow\begin{cases}Security\ Definition\\Mathematic\ Assumption\\Reduction\end{cases}$$

If $\exist$ Attacker A that breaks the Security of $\Pi$, then there is $B=R^A$ that solve the Math Problem

也就是如果一个数学问题目前没有很好的解决方案，那么相对应的加密算法就也不会有很好的破解方法，而该加密算法如果被解决，那么也就能基本解决相应的数学问题。

Definition （Shannon Privacy）

Given $\Pi = (Gen, Enc, Dec, M, K)$, we say $\Pi$ is Shannon Privacy, with respect to Distribution D if $\forall t\in M, c\in C, P_{m\leftarrow D}[m=t]=P_{m\leftarrow D,sk\leftarrow Gen}[m=t|Enc(sk,m)=c]$

即攻击者即使知道了密文也无法获取任何额外信息，我们称$\Pi$是香农安全的。

数学表达上即先验概率（知道密文前）与后验概率（知道密文后）相等

Perfect Privacy

The Distribution of the Ciphertext is always identical

$\forall m_1,m_2\in M, c,P[Enc(sk,m_1)=c]=P[Enc(sk,m_2),c]$

任意明文加密后，等于特定密文的概率都是相等的。