软问题:密码学中漂亮证据的例子是什么？

Question

这些可能包括任何证明，缩减，结构等。例如，简单的解决问题，似乎似乎很难。优雅的构造隐藏了深刻的数学概念，但一旦提出，是容易使用的。

任何你认为优雅和聪明的东西。

特别欢迎有精美图形的校对。

(最好是能够合理地融入StackExchange答案的那些)。

Answer 1

定理。在选择明文攻击下，分组密码的欧洲央行模式具有可笑的高优势。

证据。

Answer 2

我最喜欢的密码证明，是如何证明图着色存在于零知识。我喜欢它，因为它不需要任何密码学。

假设我们有一个图，我知道有一个k色的着色，Bob想要向Alice证明这样一个着色的存在，他知道它，却没有透露任何关于它的信息。

他们把图画在地板上，让爱丽丝离开房间。鲍勃随意地消磨颜色。所以哪种颜色是随机的。Bob在每个vertix上都放置了一个颜色标记，以匹配他的颜色，并用帽子覆盖它们。然后爱丽丝走进房间，挑出两个相邻的顶点，露出它们的颜色。Alice验证它们都来自商定的颜色集，并且是不同的。

然后重复这一过程，直到达到所需的信任为止。每次鲍勃改变颜色(例如用绿色代替蓝色，用蓝色代替红色，.)再次覆盖和爱丽丝选择一个新的边缘显示随机。

如果Bob确实有一个有效的着色，它就会成功，这是微不足道的。这也是微不足道的零知识，因为你在揭示中学到的唯一的东西是，在当前的隐藏着色中，这两个顶点有一个不同的颜色，如果真的有有效的着色，这是可能的。

如果Bob不知道有效的着色，那么每个显示阶段都有失败的非零机会。Bob不能设置颜色以便任何显示都能工作。因此，至少有一个1/|E|失败的机会，由爱丽丝的随机选择控制。因此，如果反复多次，爱丽丝就能获得武断的自信。

我喜欢这个，因为它是一个简单的零知识证明，在这里我们证明一个事实(不像圆形洞穴的例子，我们在物理世界中证明能力)。然而，我们使用的是身体上的承诺(戴上帽子)，而且很容易遵循这个证据。

我还喜欢使用物理的不经意传输(两个信封)的多方计算，以及使用信封和没有密码原语的承诺。

Answer 3

基于AES-CTR的非SIV模式密码在重用nonce时泄漏明文安全故障.

证明