原文出自：https://blog.z.cash/snark-explain3/
作者：Ariel Gabizon
譯者：Matter實(shí)驗(yàn)室
In Part II, we saw how Alice can blindly evaluate the hiding E(P(s)) of her polynomial P of degree d, at a point s belonging to Bob. We called this “blind” evaluation, because Alice did not learn s in the process.
在第二部分柒爸，我們知道了Alice如何在屬于Bob的 s 點(diǎn)数初，去盲評(píng)她d階多項(xiàng)式P的匿數(shù)E(P(s))声登。我們將其稱為 “盲” 評(píng)估稍刀，因?yàn)?Alice 在這個(gè)過(guò)程中并不知道 s掌逛。
However, there was something missing in that protocol – the fact that Alice is able to compute E(P(s)) does not guarantee she will indeed send E(P(s)) to Bob, rather than some completely unrelated value.
然而宠互，在那項(xiàng)協(xié)議中有瑕疵 – 雖然Alice 能夠計(jì)算出 E(P(s)) ，但并不能確保她將正確 E(P(s)) 發(fā)送給 Bob朵夏，而非一些完全不相關(guān)的值。
Thus, we need a way to “force” Alice to follow the protocol correctly. We will explain in part IV precisely how we achieve this. In this post, we focus on explaining the basic tool needed for that – which we call here the Knowledge of Coefficient (KC) Test.
因此榆纽，我們需要一種 “強(qiáng)制” Alice 正確地遵從協(xié)議的方式仰猖。我們將在第四部分詳細(xì)解釋我們?nèi)绾螌?shí)現(xiàn)這一點(diǎn)。在本文中掠河，我們專注在解釋實(shí)現(xiàn)這一功能需要用到的基礎(chǔ)工具 – 我們將其稱為 “知識(shí)系數(shù)(KC)測(cè)試”亮元。
As before, we denote by g a generator of a group G of order |G|=p where the discrete log is hard. It will be convenient from this post onwards to write our group additively rather than multiplicatively. That is, for α ∈ Fp, α?g denotes the result of summing α copies of g.
正如之前一樣，我們使用 g 表示一個(gè)階為|G|=p的群G的生成器唠摹，對(duì)于該群爆捞，離散對(duì)數(shù)是困難的。在文章開(kāi)始時(shí)使用加法而不是乘法解釋起來(lái)更加方便勾拉。 那就是煮甥，對(duì)于 α∈Fp ，α?g 表示 α 個(gè) g 的求和結(jié)果藕赞。
THE KC TEST
知識(shí)系數(shù)(KC)測(cè)試
For α ∈ F(?,p) [1], let us call a pair of elements (a,b) in G an α-pair if a,b≠0 and b=α?a.
[1] F(?,p) denotes the non-zero elements of Fp. It is the same as Z(?,p) described in Part I.
The KC Test proceeds as follows.
Bob chooses random α ∈ F(?,p) and a ∈ G. He computes b=α?a.
He sends to Alice the “challenge” pair (a,b). Note that (a,b) is an α-pair.
Alice must now respond with a different pair (a′,b′) that is also an α-pair.
Bob accepts Alice’s response only if (a′,b′) is indeed an α-pair. (As he knows α he can check if b′=α?a′.)
對(duì)于 α∈F(?,p)[1], 如果 a,b≠0 和 b=α?a 同時(shí)成立成肘，則我們稱 G 中的一組元素 (a,b) 為 α-pair。
- F(?,p) 表示 Fp 中的非零元素組成的集合斧蜕，它與第一部分描述的 Z(?,p) 相類似双霍。
知識(shí)系數(shù)(KC)測(cè)試按照如下的步驟進(jìn)行:
- Bob 隨機(jī)選擇一個(gè) α∈F(?,p) 和 a∈G 。他計(jì)算出 b=α?a 批销。
- 他發(fā)送 “挑戰(zhàn)” 數(shù)對(duì) (a,b) 給 Alice洒闸。注意，(a,b) 是一個(gè) α-pair 均芽。
- Alice 現(xiàn)在必須回復(fù)一個(gè)不同的數(shù)對(duì) (a′,b′) 同時(shí)也必須是 α-pair 丘逸。
- 如果 (a′,b′) 確實(shí)是一個(gè) α-pair ，則 Bob 接受 Alice 的回復(fù)掀宋。(由于他知道 α 深纲，他可以檢查 b′=α?a′是否成立。)
Now, let’s think how Alice could successfully respond to the challenge. Let’s assume for a second that she knew α. In that case, she could simply choose any a′ in G, and compute b′=α?a′; and return (a′,b′) as her new α-pair.
現(xiàn)在劲妙，讓我們思考 Alice 如何成功地回復(fù)挑戰(zhàn)湃鹊。 讓我們假設(shè)一下，她知道 α 是趴。 在這種情況下涛舍，她便可以在 G 中簡(jiǎn)單地挑選出 a′，并計(jì)算出 b′=α?a′; 同時(shí)返回 (a′,b′) 作為她得到的新 α-pair 唆途。
However, as the only information about α she has is α?a and G has a hard discrete log problem, we expect that Alice cannot find α.
然而富雅，由于 Alice 唯一擁有關(guān)于α的信息的載體是α?a 掸驱，并且 G 具有難離散對(duì)數(shù)問(wèn)題，我們可以預(yù)計(jì) Alice 并不能得到 α没佑。
So how can she successfully respond to the challenge without knowing α?
因此毕贼，如何讓 Alice 在不知道 α 的前提下成功回復(fù)挑戰(zhàn)呢？
Here’s the natural way to do it: Alice simply chooses some γ∈F?p,γ∈Fp?, and responds with (a′,b′)=(γ?a,γ?b).(a′,b′)=(γ?a,γ?b).
In this case, we have:
b′=γ?b=γα?a=α(γ?a)=α?a′,b′=γ?b=γα?a=α(γ?a)=α?a′,
so indeed (a′,b′)(a′,b′) is an αα-pair as required.
以下是實(shí)現(xiàn)這一目標(biāo)的自然做法： Alice 簡(jiǎn)單地選擇一些 γ∈F(?,p)蛤奢，并且回復(fù) (a′,b′)=(γ?a,γ?b) 鬼癣。
在這種情況下，我們有：
b′=γ?b=γα?a=α(γ?a)=α?a′,
因此(a′,b′)確實(shí)是這里需要的 α-pair 啤贩。
Note that if Alice responds using this strategy, she knows the ratio between a and a′. That is, she knows the coefficient γ such that a′=γ?a.
注意到待秃，如果 Alice 使用這種策略進(jìn)行回復(fù)，她就知道 a 和 a′ 之間的比率痹屹。 也就是說(shuō)章郁，她知道系數(shù) γ 滿足 a′=γ?a 。
The Knowledge of Coefficient Assumption [2] (KCA) states that this is always the case, namely:
This is typically called the Knowledge of Exponent Assumption in the literature, as traditionally it was used for groups written multiplicatively.
KCA: If Alice returns a valid response (a′,b′) to Bob’s challenge (a,b) with non-negligible probability over Bob’s choices of a,α, then she knows γ such that a′=γ?a.
The KC Test and Assumption will be important tools in Part IV.
知識(shí)系數(shù)假設(shè) [2] (KCA) 指出志衍，情況總是像這樣：
- 它的書(shū)面名稱通常為知識(shí)系數(shù)假設(shè)暖庄，傳統(tǒng)上被用在字面乘法性質(zhì)的群上。
KCA: 如果 Alice 對(duì)于Bob選擇的a,α楼肪，以不可忽略的可能性培廓，對(duì)Bob的挑戰(zhàn)(a,b)**給出一個(gè)有效的回復(fù) (a′,b′),此時(shí)，她所知道的 γ 春叫，可以滿足 a′=γ?a 肩钠。
知識(shí)系數(shù)(KC)測(cè)試和假設(shè)將是第四部分的重要工具。
WHAT DOES “ALICE KNOWS” MEAN EXACTLY
“ALICE知道”的確切意義是什么
You may wonder how we can phrase the KCA in precise mathematical terms; specifically, how do we formalize the notion that “Alice knows γ” in a mathematical definition?
你也許會(huì)好奇我們?nèi)绾螌?KCA 用準(zhǔn)確地?cái)?shù)學(xué)形式表達(dá)出來(lái)暂殖；具體來(lái)說(shuō)蔬将，我們?nèi)绾斡脭?shù)學(xué)定義將 “Alice 知道 γ” 的意義形式化出來(lái)?
This is done roughly as follows: We say that, in addition to Alice, we have another party which we call Alice’s Extractor. Alice’s Extractor has access to Alice’s inner state.
我們通過(guò)下面這樣粗略的方式說(shuō)明： 我們說(shuō)，除了 Alice 之外央星，我們有一個(gè)被稱為 Alice的提取器 的角色。 Alice的提取器可以訪問(wèn) Alice 的內(nèi)部狀態(tài)惫东。
We then formulate the KCA as saying that: whenever Alice successfully responds with an α-pair (a′,b′), Alice’s Extractor outputs γ such that a′=γ?a. [3]
[3]The fully formal definition needs to give the Extractor “a little slack” and states instead that the probability that Alice responds successfully but the Extractor does not output such γ is negligible.
我們這時(shí)便可以這樣形式化 KCA: 當(dāng) Alice 使用一個(gè) α-pair (a′,b′) 成功回復(fù)時(shí)莉给，Alice的提取器 輸出的 γ 滿足 a′=γ?a. [3]
- 完整正式定義需要讓提取器 “稍微松懈一下”，并反過(guò)來(lái)聲明廉沮，Alice 成功回復(fù)但是提取器無(wú)法正常輸出這樣的 γ 的可能性可以忽略不計(jì)颓遏。
譯者總結(jié)
