加密的纠错功能？
这是这个问题关于恢复(损坏的)加密文件的动机，特别是语句(在答案中)：
但是如果我知道算法和密钥，并且我做了一个定制的软件来解密文件的内容，无论如何，我可能会得到一个解密的JPEG，可能会在某些地方被部分查看/混淆。
一般来说，像全磁盘加密这样的东西是如何与随机翻转的比特交互的，这一点我还没有想过。有两个明显的解决方案：
- 将全磁盘加密封装在纠错代码中。
- 最小化每个加密的数据块的大小，如果有错误(虽然这不是完全的磁盘加密)，则接受数据的完全丢失(对于单个小块)。
这个问题是在问其他可能的解决办法。
对于固定密钥k\in\mathcal{K}和加密随机性r\in\mathcal{R}，可以将加密方案m\mapsto \mathsf{Enc}_k(m;r)看作域\mathcal{M}和协域\mathcal{C}_{k, r}\subseteq \mathcal{X}的编码(在编码理论意义上)。加密方案的正确性表明，代码是唯一可解码的，可以将其作为条件：\forall k\in\mathcal{K} : \mathsf{Dec}_k(\mathsf{Enc}_k(m; \mathcal{R})) = m可以通过映射\mathsf{encode}和\mathsf{decode}抽象地在\mathcal{M}和\mathcal{X}之间定义代码。然后，可以通过上述条件来捕获几个编码理论性质，比如唯一的可解码性：\forall m\in\mathcal{M} : \mathsf{decode}(\mathsf{encode}(m)) = m更有趣的能力是能够纠正某些有界集\mathcal{E}中的错误。这通常会有“几何”的味道(\mathcal{E}在某种规范中是一个球，所以错误是“小的”)，但是我不会强加这个要求。代码(\mathsf{encode}, \mathsf{decode})可以更正\mathcal{E} if：\forall m\in\mathcal{M} : \mathsf{decode}(\mathsf{encode}(m) + \mathcal{E}) = m
我很好奇关于IND加密方案的纠错能力能说些什么。它们显然可以有一些，原因很简单，如果(\mathsf{Enc}_k, \mathsf{Dec}_k)是IND，而(\mathsf{encode}, \mathsf{decode})可以纠正\mathcal{E}错误，那么(\mathsf{encode}\circ \mathsf{Enc}_k, \mathsf{Dec}_k\circ\mathsf{decode})仍然是IND(它的密文可以从初始方案的密文中公开计算)，但现在可以纠正\mathcal{E}错误。
因此，问题是，是否有任何共同的方案有任何纠错属性。具体来说，如果我取了一些密文c并在其中“翻转”一点(或者添加任何其他潜在的微小错误)，那么关于明文与“真实明文”的关系，还能说些什么吗？是否有任何IND安全方案与错误更正“烘干”，或必须明确地与纠错代码，如我在上面提到的建设？
请注意，即使这些方案不再正确，但在某种意义上“接近纠正”，我也会感兴趣。特别是，如果\forall k\in\mathcal{K}：\mathsf{Dec}_k(\mathsf{Enc}_k(m;\mathcal{R}) + \mathcal{E}) \in m + \mathcal{E}'，其中\mathcal{E}'是一些允许的错误，并且有希望与\mathcal{E}相关(也就是说，如果保证噪声很小，那么产生的错误也是很小的)。
请注意，对上述问题的一个明显的答案(LWE加密，它已经具有自然的编码理论解释)似乎只是部分工作-表单(a, b)的密文自然是“在b插槽中”纠错，而不是“在a插槽中”。然后可以定义错误集\mathcal{E} = \{0\}^n\times \overline{\mathcal{E}} ( a是n-dimensional)，而\overline{\mathcal{E}}在精确意义上是“足够小”的。我发现，由于错误\mathcal{E}的“人为”形状(基于LWE的加密可以说已经需要选择纠错代码，因此它具有“出炉”的纠错特性就不足为奇了)，这让我感到有些不满意。
回答 2
Cryptography用户
发布于 2020-04-05 05:50:51
要实现你想要的，没有简单的方法。
让{\cal M}=\{0,1\}^n,和{\cal K}=\{0,1\}^k.让集合\cal E,具有简单的基数2^{f}, (如果您只对停止低重量错误感兴趣，则没有Hamming球体)。对于每个消息m\in {\cal M}和我们拥有的每个e\in {\cal E}，您都需要这样做：E^{-1}_k(E_k(m)+e)=m ,\quad \forall k\in {\cal K} 让正在使用的分组密码遵守雪崩准则。这可以是统计的或确定性的[一个比特翻转改变至少\theta n位，与\theta=1/2进行具体的比较。
在任何情况下，高概率的情况下，在你的比特翻转后，修改后的密文将大致在汉明距离n/2真正的密文。这有两个含义：
- 要纠正
n/2错误，需要传统的渐近零速率纠错码。由于半径的两个汉明球，\lfloor n/2 \rfloor只能在一个很小的中心(码字的对数数)上不相交。例如，您可以使用具有距离n/2,的Hadamard (相当于1阶里德穆勒)代码，但这只能检测(n/2)-1或纠正(n/4)-1错误。对于n=256，您可以更正63错误，并具有9信息位，这是代码的维度。半径n/2的Hamming球体具有大致的2^{n-1}/\sqrt{n}体积(矢量数)。有关详细信息，请参见这里问题的答案。 - 有一些代码可以纠正指定的错误模式，而这些错误模式并不是Hamming球体(即，距离内与码字最近的向量)。参见Tan，Welch和Scholtz 这里的这篇文章，这些码的效率甚至更低，并且在码字数方面的渐近性会更差。
这会带来效率方面的影响，因为您不再真正对消息进行一对一加密，而是加密消息的等价类(特别是消息m的等效类为[m]=\{m+e: e \in {\cal E}\}. )，您的有效消息空间现在是{\cal M}^\ast=\{[m]: m \in {\cal E}\}，它的大小为2^{n-f}.。事实上，这个设置让人想起Gilbert为(键控的)身份验证代码(MACs)设置的方法，而不需要保密。
在安全性参数方面，我冒昧地说，如果您想要N位安全性，您可能希望选择n=N+f,和k=N,，以防您喜欢keylength=blocklength机制、平衡字典和暴力攻击。推测AES-256可能就是这样使用的。
然而，一个经过适当设计的分组密码，在设计了雪崩特性之后，不太可能有一个集\cal E，它与以零为中心的汉明球体重叠，或以任何重要的方式出现任何其他指定的错误集。
Cryptography用户
发布于 2022-04-29 21:40:12
可能有一些特定的用例，希望将这些操作组合在一起，但总的来说，我不认为加密和编码有什么好处。
主要的缺点是，如果这个方案不等同于加密，然后是编码--也就是说，编码实际上是加密的一个基本部分--那么就不可能在不使用密钥执行解密的情况下纠正错误。也就是说，如果这种组合加密和编码不能分离为独立的步骤E_k(m) = Encode(Encrypt(m, k))，那么就必须没有一个与密钥无关的纠错或检测算法。对于长期存储来说，这将是一个重大的问题，因为在这种情况下，设备可以在持续的基础上监视和纠正“比特腐烂”。
通常，应根据存储介质或传输信道的特性选择编码参数(即纠错能力)。一段加密的数据可能在多个不同的通道上移动或通过几个不同的通道，最好是
- 纠正每一步的错误(不解密)和
- 对每个数据进行最佳编码。
像这样的方案需要在内置的基础上增加额外的冗余，这只是效率低下。加密和编码是两个独立的问题，因此算法和参数应该独立选择。
https://crypto.stackexchange.com/questions/79589
复制相似问题
腾讯云开发者
