Fiat-Shamir heuristic and Non-interactive Proof

what is heuristic

heuristic (from Greek εὑρίσκω "I find, discover"): The use of experience and practical efforts to find answers to questions or to improve performance -- Longman dictionary about "heuristic"

In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut. Nevertheless, heuristics is a widely used technique for a variety of reasons:

Problems that do not have an exact solution or for which the formulation is unknown

The computation of a problem is computationally intensive

Calculation of bounds on the optimal solution in branch and bound solution processes

Examples that employ heuristics include using trial and error, a rule of thumb or an educated guess.

Heuristics are the strategies derived from previous experiences with similar problems. These strategies depend on using readily accessible, though loosely applicable, information to control problem solving in human beings, machines and abstract issues. When an individual applies a heuristic in practice, it generally performs as expected. However it can alternatively create systematic errors.

人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内,可接受的计算成本内，大大减少尝试的数量，能迅速地达到问题的解决。但由于这种方法具有尝试错误的特点，所以不一定能保证所得的可行解和最优解,也就是说有失败的可能性, 甚至在多数情况下，无法阐述所得解同最优解的近似程度。因为启发式算法现在还没有完备的理论体系，只能视作一种技术。科学家的许多重大发现，常常是利用极为简单的启发式规则。

利用启发式算法进行目标优化的一些优缺点如下：

优点	缺点
1. 算法简单直观，易于修改 2. 算法能够在可接受的时间内给出一个较优解	1. 不能保证为全局最优解 2. 算法不稳定，性能取决于具体问题和设计者经验

Fiat-Shamir heuristic

The initial idea of Fiat and Shamir was to eliminate the interaction in public coin protocols (note that public coin means that the random choices of the verifier are made public) and was used to convert three steps public coin identification scheme into conceptually simple signature schemes (it has later been proven by Pointcheval and Stern that under the random oracle model such signature schemes provide existential unforgeability under chosen message attacks).

If you apply the Fiat-Shamir heuristic to interactive zero-knowledge proofs you

firstly collapse the protocol rounds which all the small challenge space of \(\{0,1\}\) into one round using a larger challenge space (e.g., \(ℤ𝕡\), where the size of the message space controls the soundness error) at the cost of only being honest-verifier zero-knowledge, and
secondly you do not longer let the verifier sample the challenge (public coins), but compute the challenge as output of a hash function with input the previous protocol messages. The hash function is modelled as a random oracle (outputs random strings that are not distinguishable from truly random strings), which models the unpredictability of the verifier.

Non-interactive Proof

In very simplified terms, a NI-ZK proof works in 2 stages: First, you run the protocol with a simulator (who is just a verifier, but the random choices are done differently), and then you can give the transcript of the protocol to anyone and convince them that the proof is real.

Two important ways to convert an interactive protocol to a non-interactive proof:

In the random oracle model (assuming that you have access to ideal hash functions), you can use the Fiat Shamir heuristic: You replace the verifier with a simulator, and whenever the verifier would have to choose randomly, you use the hash function over the entire protocol so far (most importantly, the commitments of the prover) to emulate a random unpredictable choice. Since the hash function is deterministic, you can't change the value without changing the previous interactions. When you're done with the protocol, you can just take the transcript and give it to someone. However, there is a tradeoff in the security level: If the prover is able to cheat with a certain probability, then he could just try different commitments if he doesn't like the result of the hash function. So in order to get e.g. an error of less than 1/280, you would need an error probability of less than 1/2160 with the hash function replacing true random choices. (And this is why it's called a heuristic, there is no proof for this)
With a common reference string you can achieve NI-ZK. The common reference string is a random string of symbols, which is drawn from some probability distribution. The assumption is, that these random values are available to all parties, but no party has any influence on their actual choice. And if you simulate the ZK proof with the random choices according to the common reference string, you should get the same result as anyone else validating the protocol transcript. I believe you don't have to double the security parameter in this case (like for Fiat Shamir), but on the other hand a common reference string is harder to realize than a hash function.

CRS model vs ROM model

The main difference between the ROM and CRS model is that proofs in the ROM are heuristic, since the actual protocol instantiation uses a hash function that is blatantly NOT a random oracle. In contrast, proofs in the CRS model have a standard reduction-based proof of security, and so are not heuristic.

The main advantage of the CRS model over the random oracle model is that security is standard, and doesn't rely on a heuristic belief system that the real protocol that uses a standard hash function is secure. The main disadvantage is that you need to somehow generate this CRS, and this isn't trivial if there's no trust. Zcash uses a CRS and ran a large MPC protocol between many parties to generate the CRS. As long as you believe that not all the participants colluded, then you can trust the system from that point on. This is a good example of where a CRS can be deployed in reality.

The CRS model achieves its function by incorporating hidden secrets. The reference string must have some structure based on secret random coins (e.g., be of the form Gs, Gs2, Gs3, . . .) and the secret (e.g.,the value s) must be discarded after generation. This makes CRS generation an inherently trusted process.

Fiat-Shamir heuristic and Non-interactive Proof

Fiat-Shamir heuristic and Non-interactive Proof

Fiat-Shamir heuristic and Non-interactive Proof

what is heuristic

Fiat-Shamir heuristic

Non-interactive Proof

CRS model vs ROM model

参考