McEliece后量子密码学

Question

如果可能的话，有人能用简单的英语解释我，McEliece非对称加密是如何工作的，为什么它的量子安全？提前谢谢。

Answer 1

也许不像@SEJPM描述的那样简单、基本，但是这里是这样的。

密文c是通过使用公钥矩阵\hat{G}编码消息并在其中添加一些随机的人工噪声来获得的，基本上模拟一个有噪声的信道(就像在无线电传输中一样，你总是捕捉到一些宇宙噪声)：

c = \overbrace{m\hat{G} + e}^{\text{hard}} = m(SGP) + e = mS(GP)+e

由于不知道秘密逆变换(秘密密钥)，攻击者将面临一个(大概)困难的问题，因为\hat{G}看起来像一个随机代码(如果它确实是随机的，那么问题就是NP --难--这意味着它非常困难，可能需要指数时间来解决)。您可以将其看作是最小二乘问题的离散版本。知道陷阱门，即秘密可逆矩阵S和秘密置换P，可以将实例转换为一个简单的实例：

cP^{-1} = ((mS)GP+e)P^{-1} = (mS)G + eP^{-1} = \underbrace{\hat{m}G + \hat{e}}_{\text{easy}}

在G定义可有效解码的代码的情况下，这很容易，这意味着有一段代码可以在合理的时间内纠正错误。注意，置换P仅通过交换周围的元素来处理错误e。例如，P:(0,1,0)\mapsto (1,0,0)。它不会改变错误的数量。因此，可以在加密中添加与代码能够更正的相同数量的错误。