问在密码学中，硬实例意味着什么？

EN

“艰难的例子”是否意味着难以解决的问题，如DDH (决断的Diffie Hellman)假设？

基本上是的，它意味着一个困难问题的具体实例-例如，在DDH情况下，它意味着一个特定的挑战(g^a, g^b, g^c)。

约简的工作原理是，如果您有解决一个问题的方法/算法(通常是破坏协议)，那么您可以使用相同的算法来解决像DDH这样的难题。这证明，违反协议至少和破坏DDH一样困难。相反，如果DDH是硬的，那么协议是安全的。

减少通常从获取硬问题的实例开始，例如DDH问题。然后，您会这样说：“假设\mathcal{A}是一个对手/算法，它可以利用\epsilon优势破坏XXX协议”。接下来，您将展示如何将DDH问题g^a, g^b, g^c的实例转换为您可以给予\mathcal{A}的值，这样无论\mathcal{A}返回什么，您都将了解DDH实例的答案(可能比\epsilon的概率要低一些，后者被称为“紧密性损失”)。正是这种将DDH实例转换为您可以提供给\mathcal{A}的方法被称为将DDH问题的一个实例嵌入到您的协议中。

但是你会计算出概率，如果你能证明你在使用\mathcal{A}解决DDH问题上的优势是不可忽略的，如果\epsilon是的话，那么您已经成功地展示了从DDH降低您的协议的安全性。