# Non-Interactive Zero-Knowledge and Its Applications

[:Brain: 論文連結_ Non-Interactive Zero-Knowledge and Its Applications](https://dl.acm.org/doi/10.1145/62212.62222)
> **Abstract** We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.

## 前情提要
在CPA出來之後，Yang等人透過CPA+Non-Interactive ZK的方式證明這種機制的安全性跟IND-CCA1是等價的。這裡的Non-interactive ZK是用於證明兩篇使用同一篇明文加密出來的密文，其來源真的都是同一篇明文。

任何一個proof system都要滿足以下兩項特性:
1. **Completeness**: Prover證明的事情是對的時候, Verifier要可以接受
2. **Soundness**: 如果要證明的東西是false的話，根據Protocal證明下來之後，Verifier一定會拒絕接受。白話來說，Prover無法欺騙Verifier。

**Zero knowledge**: Peggy leaks no knowledge in the protocol to Victor so that Victor can simulate himself all conversations in the interactive proof.==是在防止Verifier欺騙Prover。==

----
一些補充
:::info
* IP: Interactive proof，是計算理論裡的東西。NP是一種IP，是一種special case。
* [GMR] 是第一篇寫出zero-knowledge proof的論文
* language是一種問題
:::
## 1. Introduction
三項zero-knowledge proof與traditional proof的差異有三項:
* **Interaction**
* **Hidden Randomization**
* **Computational Difficulty**

這篇論文想做的事情是透過computational difficulty來取代interaction & hidden randomness。

### Conceptual Senario

有兩個數學家P和V。他們在玩了擲硬幣猜正反面的遊戲一段時間後，P就離開去旅行一陣子了。在旅行期間，他還是一直在做他的數學研究。每當P有發現一個新的理論的時候，他都會寫一張明信片給V，上面的內容是用zero-knowledge去做的證明以證明P發明的新理論的合理性。注意這裡必定是一個non-interactive process。更精確的說是一個mono-directional interaction: 只能從P到V。即便V想要跟P通訊，他也做不到。因為P一直在旅行、不斷在移動，所以沒有一個固定的收件地址。

### 1.1 Our Model Versus the Old One

:::success
### Information和knowledge是什麼?
[:Brain: 參考論文_The Knowledge Complexity of Interactive Proof Systems](https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf)
| Information |Knowledge |
| ----------- | -------- |
| 敘述一段訊息中有多少不確定情況| 敘述有沒有解決一個問題的computation power |
|有機率的成分在|沒有機率的成分在|
|可用==entropy==來度量一段訊息有多少Information|無法度量，只能說有或沒有knowledge
|在知道資訊後，entropy會變化|受public known (解相關問題的oracle，你不見得知道這些東西實際上是怎麼做的) 影響。有能力的人可以算得出來，沒有的就算不出來。|
* zero-knowledge的定義:在沒有prover(knowledge，secret $x$)的狀況下，如果我可以模擬出所有protocol訊息，並且無法跟真正protocol的訊息分辨開來。(重點在找一個simulator)

舉例一:
如果給了分解因數的oracle，知道$n=p \cdot q$的$p$跟$q$，就可以去解跟這個$p$、$q$相關的開根號問題，但是還是不會解其他$n'=p' \cdot q'$，$n$ 是 public known，$p$、$q$ 是 knowledge

discrete log 中，公開 $y=g^x$ (mod p)，$y$ 是 public known，$x$ 是 knowledge

舉例二:
丁老師的回家時間有information，因為我們不太確定每個周五會發生什麼事。但這件事裡有knowledge，我們可以透過一些public known、public objects來幫助我們判斷丁老師到底幾點下班。例如:打電話問師母(Oracle)、觀察老師辦公室前的腳踏車、那天報告的seminar有不有趣...等等。

:::
### 1.2 The Robustness of Our Result
作者提到，在他們提出的proof system中，只要字串 $\sigma$ 是 truely random的話就可以具備correct和zero-knowledge這兩種特性。這樣的proof system中，萬一使用的 $\sigma$ 不是truely random的話，至少也可以做到correct。

能做到這樣的程度有什麼厲害之處呢?這裡的貢獻在於，因為我們通常random source都是從自然界中取得。但我們不能每次都保證這些取得的random source的randomness是夠好的。

:::success
### 對於密碼學來說的貢獻
這邊需要再提到一件事。在沒有使用random string這個做法被提出前，密碼學在做zero-knowledge proof時往往是使用oracle的假設來幫助我們完成整個證明。但我們知道oracle是錯的，我們總不能一直建立這樣的假設來自欺欺人說這樣的證明很完整。於是這篇論文提出了使用random string來取代oracle的這個做法來完善zero-knowledge proof。這就像是我們在加解密的論文中有分成使用到oracle的機制跟standard的機制是類似的概念。
:::

### 1.3 Applications of our Result
這樣的zero-knowledge proof system被用於建構可抵禦choosen ciphertext attacks的加密機制。

## 2. Preliminaries
### Notations and Conventions

---
## 倒楣蛋的倒楣蛋
> [name=丁哥][time=2023, Dec 13th, 20:55] [color=#02C874]Computational Difficulty不知道他在做什麼?他怎麼取代掉interaction, hidden randomization跟使用hash。

> [name=育靜][time=2023, Dec 13th, 20:59][color=#9999CC] 有沒有IP的證明範例?
:heavy_check_mark: GNI (graphic on isomorphic)


> [name=煒甯][time=2023, Dec 13th, 21:00][color=#949449]
對於這一段不太理解
🦉 是在舉例有效率的證明，後面應該會有更多的解釋。重點在於$k$

>[name=煒甯][time=2023, Dec 15th, 16:13][color=#949449]
>不太理解 "sharing a random string $\sigma$ is weaker requirement than being able to interact" 這句話在講什麼?以我們前面的理解，random string 應該是一個替代interaction 這兩特性的東西。這裡的weaker requirment想說的事情是什麼?

>[name=煒甯][time=2023, Dec 27th, 21:11][color=#949449]
>* 在數學家的故事中，為什麼要拋coin?
>
>* 1.2中提到的correct的定義是什麼?
>:heavy_check_mark: 指對於verifier來說可以接受的敘述都不會是錯誤的。這一篇論文使用correct這個詞，應該是跟前情提要中寫到的Completeness是一樣的意思。