52 Things: Number 47: What is the Fiat-Shamir transform?

52件事：47号：菲亚特沙米尔的转型是什么？

What is the Fiat-Shamir transform?
什么是菲亚特沙米尔的转变？

Sigma protocols, which we saw last week, are fast and useful protocols for Alice to prove something to Bob - as long as they're both online at the same time. Alice sends Bob a commitment, Bob replies with a challenge and Alice sends a response. Unfortunately bar further modifications, Sigma protocols are not actually known to be zero-knowledge: they are only honest-verifier zero- knowledge.
我们上周看到的Sigma协议是快速而有用的协议，Alice可以向Bob证明一些事情——只要它们同时在线。Alice向Bob发送承诺，Bob回复挑战，Alice发送响应。不幸的是，除了进一步的修改，西格玛协议实际上并不是零知识：它们只是诚实的验证器零知识。

The Fiat-Shamir transform is a technique to turn a Sigma protocol into a non- interactive proof. This not only lets Alice send a proof to Bob by e-mail, which he can read later without having to send her a challenge back, it also lets her turn any Sigma protocol into a digital signature scheme with which she can assert "someone who knows the secret for this Sigma protocol has signed that message". Alice can create a signature once and post it to a usenet bulletin board and everyone who sees the signed message can check the signature without having to contact Alice. And zero-knowledge comes for free, since Bob or any other reader no longer has to do anything.
Fiat-Shamir变换是一种将西格玛协议转化为非交互式证明的技术。这不仅可以让Alice通过电子邮件向Bob发送证据，Bob稍后可以阅读该证据，而无需向她发回质疑，还可以让她将任何Sigma协议转化为数字签名方案，她可以断言“知道该Sigma协议秘密的人已经签署了该消息”。Alice可以创建一次签名并将其发布到usenet公告板上，所有看到签名消息的人都可以检查签名，而无需联系Alice。零知识是免费的，因为Bob或任何其他读者不再需要做任何事情。

Although this technique is explained in Fiat and Shamir's 1986 paper, several eminent cryptographers have pointed out in the past that it was actually given by Blum in an even earlier work, though we have not been able to trace this.
尽管Fiat和Shamir在1986年的论文中解释了这一技术，但几位著名的密码学家过去曾指出，这实际上是Blum在更早的工作中提出的，尽管我们无法追踪到这一点。

A Sigma protocol can be implemented as four algorithms *Commit*, *Challenge*, *Respond* and *Check*, to be executed as follows:
西格玛协议可以实现为四种算法*提交*、*挑战*、*响应*和*检查*，执行如下：

Alice                                Bob
-----                                -----
    
co,st = Commit(secret,public)
         ---------- co --------->
                                     c = Challenge()
         <--------- c  ----------
r = Respond(st,c)
         ---------- r  --------->
                                         Check(co,c,r)

For the Fiat-Shamir transformation, Alice picks a hash function H and uses it to create the challenge herself:
对于Fiat Shamir转换，Alice选择一个散列函数 H ，并使用它自己创建挑战：

Alice                                World
-----                                -----

co, st = Commit(secret,public)
c = H(public,co)
r = Respond(st,c)
         ------ co,r ----------->
                                     c = H(public,co)
                                     Check(co,c,r)

If Alice wants to sign a message m, she includes that in the hash: c = H(public, co,m) and posts (m,co,r) as her signed message.
如果Alice想对消息m进行签名，她将其包括在散列中：c=H（public，co，m），并将（m，co，r）作为她的签名消息发布。

Why does this work? If H were a random function, then the challenge is clearly uniformly random and independent of Alice's public information and commitment. The security analysis considers an Alice who does not have access to the code of H directly, only to an oracle for H. In this case, the probability of Alice making a correct response without following the protocol (especially if she does not know the necessary secret) is proportional to the inverse of the size of the range of H, that is if H has domain X and range Y then someone without the the secret who makes up to q H -calls has at most a q/|Y| probability of making a r-value that *Check* accepts. Typically |Y| = 2^n for a decently large value of n, so this probability is negligible.
为什么这样做？如果 H 是一个随机函数，那么挑战显然是一致随机的，并且与Alice的公开信息和承诺无关。安全性分析考虑了一个Alice，他不能直接访问 H 的代码，只能访问 H 的预言机。在这种情况下，Alice在不遵循协议的情况下做出正确响应的概率（尤其是当她不知道必要的秘密时）与#3的范围大小成反比，也就是说，如果#4具有域X和范围Y，那么没有秘密的人组成q H 调用最多有q/|Y|做出*Check*接受的r值的概率。对于一个相当大的n值，通常|Y|=2^n，所以这个概率可以忽略不计。

Some people will tell you that this style of analysis, known as the Random Oracle Model (ROM), is deeply flawed because there's an artificial counter- example of a scheme that is secure in the ROM but is insecure for any actual hash function H. What this counter-example shows is that if you go to enough effort to make a stupid scheme, you can end up with a stupid scheme. In practice, Fiat-Shamir has been known since at least 1986, used in several practical applications and stands unbroken to this day (if done properly). No- one has to date proposed a workable attack on a Fiat-Shamir transformed Sigma protocol that was not deliberately designed to be stupid, which is more than can be said for quite a few other cryptographic schemes.
有些人会告诉你，这种被称为随机Oracle模型（ROM）的分析风格存在严重缺陷，因为有一个人为的反例，该方案在ROM中是安全的，但对于任何实际的哈希函数 H 来说都是不安全的。这个反例表明，如果你付出足够的努力来制定一个愚蠢的计划，你最终可能会制定一个糟糕的计划。在实践中，菲亚特Shamir至少从1986年起就为人所知，并在多个实际应用中使用，直到今天（如果操作得当）都完好无损。迄今为止，没有人提出对Fiat Shamir转换的Sigma协议的可行攻击，该协议并非故意设计为愚蠢的，这比相当多的其他加密方案更能说明问题。