Zero-Knowledge-Proofs
什麼是零知識證明中的“見證人”？
我在談論知識提取器時看到過“見證”一詞，但我不知道它是什麼意思。我找不到定義。
什麼是零知識證明中的“見證人”？
NP 陳述的證人是一條資訊，可讓您有效地驗證陳述的真實性。例如，如果陳述是在某個圖中存在哈密頓循環，那麼見證就是這樣的循環。給定一個循環，可以有效地檢查它是否是有效的哈密頓循環，但很難找到這樣的循環。
知識提取器用於知識證明的定義。在那裡，您不僅要證明某些陳述是真實的，而且您知道該陳述的證人。了解某事的機器是通過知識提取器的存在來定義的，該知識提取器粗略地說，與機器互動，然後輸出（提取的）見證。
非正式地，假設你有一些更大的集合的一些子集。一般來說，用數學方法定義子集很容易，但在實踐中，可能很難說較大集合的元素是否在子集中。子集元素的見證可以讓您輕鬆驗證該元素是否確實在子集中。
一個範例可能如下。讓 $ n $ 是一個 RSA 模數。一些數字來自 $ 1 $ 至 $ n-1 $ 是平方，因為它們與某個整數模的平方一致 $ n $ . 但是，似乎很難確定一個數字是否為正方形。（雅可比符號允許您辨識一些非正方形，但不是全部。）
但是如果你有一個正方形 $ x $ , 該正方形的見證是任何整數 $ w $ 這樣 $ x \equiv w^2 \pmod{n} $ ，因為您可以輕鬆地檢查該等式是否成立。
當然，有時確定成員資格很容易，但我們仍然關心見證人，但現在只關心“有用”的見證人。例如，假設 $ G $ 是一個有生成器的循環群 $ g $ . 通常，很容易檢查某物是否是組的成員（但並非總是如此！），因此可以說，組元素可以是它自己的見證人。然而，一個元素的更有用的見證 $ x $ 在組中可以是整數 $ w $ 這樣 $ x = g^w $ , 的離散對數 $ x $ .