语义安全性

语义安全性(Semantic Security), 源于对流密码的安全性探索.

首先回顾一下Shannon的完美安全性概念.

完美安全性(Perfect Security): 令\(\mathbb{E}=(Enc,Dec)\)是\((\mathcal{K,M,C})\)上的一个加密体制, 称\(\mathbb{E}=(Enc,Dec)\)具备完美安全性, 是指如果对任意等长的明文\(m_0,m_1\in\mathcal{M}\), 都有\(\{Enc(k,m_0)\}=\{Enc(k,m_1)\}\), 其中\(k\leftarrow\mathcal{K}\).

即敌手无法分辨密文是由\(m_0\)还是\(m_1\)加密得来的. 但是上述定义太强, 不实用, 由于流密码使用的密钥长度比明文长度要短, 因而不满足上述定义.

考虑如下弱化形式:

令\(\mathbb E=(Enc,Dec)\)是\((\mathcal{K,M,C})\)上的一个加密体制, 称\(\mathbb E=(Enc,Dec)\)具备完美安全性, 是指如果对任意等长的明文\(m_0,m_1\in\mathcal{M}\), 都有\(\{Enc(k,m_0)\}\approx_p\{Enc(k,m_1)\}\), 其中\(k\leftarrow\mathcal{K}\).

即敌手无法在多项式时间内分辨密文是由\(m_0\)还是\(m_1\)加密得来的. 但此定义要求对所有明文都满足, 因而仍然很强.

不妨考虑只对敌手期望的明文成立, 这样就得到了语义安全性的概念, 这与选择明文攻击下的不可区分性(IND-CPA)等价, 主要通过一个仿真游戏来验证安全性, 游戏过程如下:

算法拥有者称为挑战者, 算法攻击者称为敌手\(\mathcal A\).

1. 挑战者拥有加密算法的公钥\(pk\)和私钥\(sk\), 将\(pk\)发给敌手;
2. 敌手选取两个等长的明文\(m_0,m_1\), 发给挑战者;
3. 挑战者获得明文后, 随机决定\(b\)的取值\(b=\{0,1\}\), 然后对\(m_b\)加密, 计算密文\(c=Enc(pk, m_b)\), 然后将密文\(c\)发给敌手;
4. 敌手获得密文后, 给出\(b'\)的值, 猜测密文是对明文\(m_0\)还是\(m_1\)的加密. 若\(b'= b\), 则敌手挑战成功, 否则失败.

敌手攻破加密算法的优势定义为 \( Adv_{SS}[\mathcal A,\mathbb E]=|\mathrm{Pr}[b'=1]-\mathrm{Pr}[b'=0]|.\)

敌手准确猜中\(b\)的优势定义为

\(\mathrm{Pr}[b'=b]=\dfrac{1}{2}+\varepsilon.\)

于是有 \(Adv_{SS}[\mathcal A,\mathbb E]=|\mathrm{Pr}[b'=1]-\mathrm{Pr}[b'=0]| = \varepsilon.\)

如果\(\varepsilon\)可以忽略, 则说明该加密算法是安全的, 反之则不安全.

本文标题: 语义安全性
本文作者: 云中雨雾
本文链接: https://weiviming.github.io/16208088340765.html
本站文章采用 知识共享署名4.0 国际许可协议进行许可
除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间: 2021-05-12T16:40:34+08:00