# Computer Security
###### tags: `CS-course`, `booknote` , `security`
> Textbook: [Foundations of cryptography](http://xn--webducation-dbb.com/wp-content/uploads/2019/11/Oded-Goldreich-Foundations-of-cryptography.-Basic-tools.-Volume-1-Cambridge-University-Press-2001.pdf)
---

## Random Oracle Model

假設 random function 是隨機的(得出得結果沒辦法用函數式的方式得出)。一般以建 table 得出。

1. 假設 hash table 是 random function 。
2. 假設 random function 的 table 是不能被單一人紀錄。
以 $2^{512}$ 得數值大小為例，此數是宇宙所有原子數總和。因此，沒辦法紀錄此 table 。
3. 此 hash table 還要是 full domain hash (FDH) 。

## [IND-CPA](https://en.wikipedia.org/wiki/Ciphertext_indistinguishability)

IND ： 訊息不可分辨。例如給一個密文與兩個明文，經過多次猜測後，猜對的機率仍是二分之一。

A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.

定義什麼是安全性，要准許攻擊者有哪些資源。
- Ciphertext Only Attack
- Plaintext Only Attack
- Chosen Plaintext Attack
- Non-adaptive Chosen Ciphertext Attack (CCA1, Lunch-time Attack)
- Adaptive Chosen Ciphertext Attack (CCA2)

CCA: 攻擊者給密文，得到明文。挑戰：當得到密文，要能夠分辨明文。

:::info
**EUF-CMA (Choosen Message Attack)**

unforgeable: 對一個簽章，沒辦法在任何訊息下找到一個配對可以通過驗證。

---

**Reduction**

證明若 Q 則 P ，以若非 Q ，則非 P 反證。

**Seq. of Game**

利用多個 Game (假設)，其中一個為隨機另一個是要證明的。並驗證要證明的機率減去隨機的機率是小於一定程度(可忽略的)。
:::

## Goldwasser-Micali is IND-CPA

:::warning
作業：用文字描述證明。
在 Introduction to Provable Security 投影片的第 29 頁有 Goldwasser-Micali 的機率式加密系統的簡化描述，請參考前一頁的 ElGamal 加密機制的 IND-CPA 安全性證明，描述一下 Goldwasser-Micali 加密系統滿足 IND-CPA 安全性的證明。
:::

首先，定義 Quadratic Residuosity 為何：
一個整數 X 對另一個整數 p 的二次剩餘（指 X 的平方 $X^{2}$ 除以 p 得到的餘數。當存在某 $X$ ，使 $X^2 \equiv d (mod$ $p)$ 成立時，稱 d 為 $mod$ $p$ 的 QR 。而對任意 $X$ ，使 $X^2 \equiv d (mod$ $p)$ 不成立時，則否。

已知 $B$ 有隨機數 a 使 $t = -a^2 (mod$ $n)$，當輸入 y 至 $B$ 時， $B$ 當中有個 $A$ 可利用 n, t, y 得到 $b'$ ，若 $b'$ 為 0 則 y 為 $QR_n$ ； $b'$ 為 1 則為 $QNR_n$ 。

若要符合 IND-CPA ，則必須使 $B(QRA)$ 和 $B(RAND)$ 差距的絕對值小於 $1/2 + 1/p(n)$ 。亦即，無法分辨 QRA 與隨機數。因此，可得：

$Adv_B$
$= |Pr[B(QRA)=0] - Pr[B(RAND)=0]|$
$= |Pr[A(n,t,y)=0|QRA] - Pr[A(n,t,RAND)=0|RAND]|$
$=|Pr[A(n,t,y)=0] - 1/2| \geq |(1/2 + 1/p(n))-1/2|$

:::success
**Others**
* [MTAT.07.003 Cryptology II](https://courses.cs.ut.ee/MTAT.07.003/2017_fall/uploads/Main/0503-security-of-goldwasser-micali.pdf)
* [List of LaTeX mathematical symbols](https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols)
:::

---

## Perfect secrecy
> Perfect security is for signature
> #Keys >= |MsgSp|

:::info
* for all: $\froall$
* from: $\from$
:::

For all m1, m2 from MsgSp, for all c from C
Pr{f(m1) = c} = PR{f(m2) = c}

The adversary sees the same distribution of ciphertext, regardless of the message send, i,e, perfect. message indistinguishability (implies computaionally IND)

#### Deterministic encryption system

Perfect secrecy 的話， Key 的個數大小至少 messages 的大小**大於或等於**。

   # of distinct ciphertexts for each key k_i
<= # of distinct ciphertexts for each message m_j
<= # of keys

#### Perfect Secrecy vs. Computational Secrecy

One-time pad is great, perfect secrecy but is ineffiecent.
Efficiency is important in modern system.

### Shannon Secrecy

Pr{M = m|Ek(M) = c} = Pr{M = m}

M is a distribution on MsgSp.
An encryption scheme satisfies Shannon Secrecy with respect to M if for all m from MsgSp, for all c from C.

從看到 ciphtext 得到的明文的機率分佈，跟沒有看到 ciphtext 的明文幾率分佈是一樣。
=> shannon Secrecy == Perfect Secrecy

:::info
Perfect Secrecy 是很沒有效率。
key 的大小要大於等於 message.
:::

---

## Probability Inequallities

### Markov Inequality

X: nonnegative random variable,
v: real number

Pr{x >= v} <= E(x)/v

:::info
**NOTE**
1. equality holds when x' = 0 for some ases and x' = v for the other cases, such that Pr{x' = 0} * 0 + Pr{x' = v} * v = E(x')
2. Pr{x >= v} ∝ 1/v
:::

#### Applications - Graph Connectivity Problem

### Chebyshev Inequality

在 t 倍的標準差以外的機率會是 $\frac{1}{t^2}$ 的縮小 。會隨 $\delta^2$ 縮小。
所以，如果是兩個標準差以外，會是 $<\frac{1}{4}$。

X: random variable, delta > 0
Pr{|X - E(X)| >= delta} <= Var(X)/(delta)^2

#### Pairwis-Independent Sampling
> Chebyshev Inequality 的公式延伸。

做越多次 sampling ，他在尾巴的副份的分布機率會越來越小。


#### Chernoff Bound
> Chebyshev Inequality 的公式延伸。

用於 binary distribution 。

---

## 計算理論

Three different theory:
1. Complexity
2. Computability
* Talk about: "What is computable?"
* Major achievements: Theoretical models of computers, Classify problems as solvable or non-solvable.
3. Automata
* (Deterministic and Non-deterministic) Finite Automata (DFA, NFA)

### Turing Machine (TM)
* Complexity / Computablility is defined w.r.t. a certain model of computation
* Turing Machine
* Alan Turing, 1936
* Similar to finite automaton but with an unlimited and unrestricted
> Q is the set of states
> $\sum$ is the input alphabet not containing the special blank symbol $\lhd$
> $\Gamma$ is the tape alphabet, where $\lhd \in \Gamma$ and $\sum \subseteq \Gamma$

只要有個 NTM 他執行結果是 accepted state 的機率不是零，則可為 NP 。
如果機率不是一半 (1/2) ，則會指其為 NP 當中的子集合 BPP 。

NTM 可以在 O(P(n)) 時間轉換成 DTM 。但轉換後時間花費會變成 $O(k^{p(n)})$ exponential time。

### Complexity Classes (Polynomial and Non-deterministic Polynomial)
> NP and NP-hard
> strong/weak assumption

判斷一個問題是不是 NP ，從理論上來說建立起一個 Non-deterministic Turing Machine (NTM) 並且在 P 時間內走到 accept 就是 NP。
但通常這會很難去建立，因此會以在有解法的情況下，是否可以在 parallel 的驗證情況下，以 P 的時間內做完驗證。

任何一個在 NP-complete set 中，可以找到 Poly 的解。則可拓展到其他問題。

NP-complete: 所有 NP 的問題，例如 searching shortest path，都可轉成 (reduced) 此 set 中的問題 ，而此子集合中問題看起來都是 exponentail time (以驗證 P 時間花費來歸類為 NP)，因此要證明此子集合是否為 Polynomial time 。
NP-hard 的問題，不一定是 NP ，但至少跟 NP-complete 一樣難。

:::info
**Strong/Weak Assumption**
* [Lecture 24: Hardness Assumptions](https://www.cs.cmu.edu/~odonnell/toolkit13/lecture24.pdf)
:::

## Adversary Models
> 只有 perfect securcy (length of key >= length of message) 是不需要 adversary model ，就算 adverser 擁有無權大的計算能力，他依然是 $\frac{1}{2}$ 的機率。

在有效率、非 perfect securcy 的安全機制下，需要利用 adversary model 證明安全性。並且敵人的模型不能是擁有無窮大的算力，因為安全機制證明會沒有意義。

Algorithm:
* Decidable Turing Machine (a TM always halt)。此指不會永不停滯的，未停止的。
Randomized Algorithm:
* Powerful than DTM (ex. Fermat Test, Miller-Rabin Test, Random walk...). A DTM is only a special case of it.
* Use it to model the adversary
* Probabilistic Turing Machine

### Bounded Probabilistic Polynomial (BPP)


利用機率式的 Turing Machine 定義出來，並且 accept 的機率不能是 1/2 。

$RP \subset BPP$
* RP: Randomize Polynomial

目前還不能確定 BPP 在 NP 裡頭，還是只有部分重疊。
我們的加密機制會希望位於 NP 裡頭，但不在 BPP 之中。因 BPP 會是敵人的模型。

---

### Negligible Probability
> $1/p(n)$

> 在 $(1-u(n))^{p(n)} > 1 - p(n)u(n)$ 的右式已經是最小得值了。

Notion of rareness: a rare event should occur rarely even if we repeat the experiment for a feasible number of times p(n). 機率小到重複執行 p(n) 次都還是很小，因此可以忽略。

> $u(n) < n^{-c}$ 為 80 年代所常用的表示方法。

> |x| 指的是 x 的長度。

$D_1$ 的機率要求是 2/3 因此的比較嚴謹，$D_2$ 比較自由。 $D_3$ 則最嚴謹。這三種都會有不同用途。

### Homework2

#### 1. (Perfect Security) Please give a simple proof that a perfect secure encryption scheme is also IND-CPA secure.

The definition of perfect security:

For all m1, m2 from MsgSp, for all c from C
Pr{f(m1) = c} = PR{f(m2) = c}

The adversary sees the same distribution of cipher text, regardless of the message send, i.e, perfect. message indistinguishability (implies computationally IND)

The definition of IND-CPA:

The messages are unrecognizable. e.g., give one cipher text and plain text, the probability of successfully guessing always is 1/2.

Assume that there are the two string of bytes, which one is cipher text and the other is plain text.
Under the perfect security, the adversary sees the same distribution of cipher text, regardless of the plain text.
So, the success guessing probability for each bit is 1/2 (which from the 0/1 bit).
As a result, this kind of distribution is satisfying the IND-CPA secure.

#### 2. (Strong vs. Weak Assumptions) We talked about search and decision problems in the lecture this week and took the Decision Traveling Salesman Problem and the Search Traveling Salesman Problem as examples to illustrate the idea of whether or not a problem is an NP problem. Now that both versions of TSP problems are believed to be NP-Hard, please give an argument that the truth of which of the following two statements guarantees the security of the system S more.

> (a) If no one can solve the Decision TSP problem, then system S is secure.

Is NP-Complete.
This assumption is weak.

> (b) If no one can solve the Search TSP problem, then system S is secure.

Since this assumption is not NP, but it's difficult level is at least as hard as the hardest problems in NP (so it called NP-hard). Moreover, it assumes that the level they have is at least as same as hardest in NP, it has more assumption that former one. Therefore, this assumption is stronger than (a) statement.

#### (Negligible functions) Please answer whether each of the following functions is negligible, noticeable, or non-negligible, and give a brief justification. In the following, $negl(n)$ denotes somearbitrary negligible function, and $poly(n)$ denotes some arbitrary polynomial in $n$

> (a) $v(n) = n^{-5}$

negligible, Proof:
$n^{-5} < n^{-2}, \mbox{when n > 1}$

<iframe src="https://www.desmos.com/calculator/tdrxbmkeeu?embed" width="500" height="500" style="border: 1px solid #ccc" frameborder=0></iframe>

> (b) $v(n) = \frac{1}{2^{10\log{n}}}$

negligible: proof:
$\frac{1}{2^{10\log{n}}} = 2^{-10\log{n}}$
$10\log{n} > log{2} = c$
$2^{-10\log{n}} < n^{-\log{2}}, \mbox{when n > 1}$

<iframe src="https://www.desmos.com/calculator/wtxjbx2bol?embed" width="500" height="500" style="border: 1px solid #ccc" frameborder=0></iframe>

> (c\) $v(n) = n^{-\log{\log{n}}}$

negligible, proof:
$n^{-\log{\log{n}}} < n^{-\log{1}}, \mbox{when n > 10}$

<iframe src="https://www.desmos.com/calculator/cws0f3gwe2?embed" width="500" height="500" style="border: 1px solid #ccc" frameborder=0></iframe>

> (d) $v(n) = ploy(n) \cdot negl(n)$

noticeable, proof:
Assume that $ploy(n) = n^7$, so the equation will be $negl(n) \cdot n^7$, which can indicate to $negl(n) < n^c \mbox{ and } negl(n) \cdot n^7 < n^c \cdot n^7$.
Afterwards, we need to prove that $n^c < negl(n) \cdot n^7$ is correct.
Now, replace the $negl(n)$ by $n^{-5}$ which is from (a). So, the equation will be: $n^c < n^{-5} \cdot n^7 = n^2$. Therefore, the equation holds.

> (e) $v(n) = (negl(n))^{\frac{1}{poly(n)}}$

noticeable, proof:
This equation indicate that when n increased, the$\frac{1}{poly(n)}$ will close to 0. which means the $v(n)$ will close to 1. This means that $n^{-c}$ which c is positive value will not be higher than the equation $v(n)$. As a result, this equation is noticeable, since it satisfies the $u(n) > \frac{1}{p(n)}$.

> (f) $v(n) = 2^{-\sqrt{n}}$
noticeable, proof:

$2^{-\sqrt{n}}=2^{-n^{\frac{1}{2}}} < n^{-c}$ when $n$ is big and $c$ is small enough to satisfy the $n^{\frac{1}{2}} > c$. However, you can see the following graph. The graph shows that when the $n>4$ the $v(n)$ is higher than $n^{-c}, \mbox{c > 0}$. Which means that $v(n) \geq n^{-c}$.

<iframe src="https://www.desmos.com/calculator/dge9d2wmci?embed" width="500" height="500" style="border: 1px solid #ccc" frameborder=0></iframe>

> (g) $\frac{1}{n^2\log{n}}$

negligible, proof:
From the following graph, it indicates that the $\frac{1}{n^2\log{n}}$ is always lower than $n^{-c}$ when $n\geq3$ and $c=1$.

<iframe src="https://www.desmos.com/calculator/v8y5nimyqo?embed" width="500" height="500" style="border: 1px solid #ccc" frameborder=0></iframe>

> (h) $v(n) = \left\{ \begin{array} 2^{-n} \mbox{ if n is composite} \\ 10^{-100} \mbox{ if n is prime} \end{array} \right.$

non-negligible, proof:
The second statement will let the $v(n)$ suddenly higher than $n^{-c}$ when the n is prime, while after that n is enough larger.
So, it is non-negligible.

### Noticeable Function

* Noticeable function: strong negation of negligible func:
* A function u:N -> R is nticeable
* If there exists a positive polynomial p(.) and there eists an $n_0$ **such that for all n** > $n_0$, u(n) >= 1/p(n)
* Non-negligiable function
* A function u: N -> R is non-negligible
* If there exists a positive polynomial p (.) for all $n_0$ such that **there exists an n** > $n_0$, u(n) >= 1/p(n)
> for "there exists an n > $n_0$" i.e. infinitely man n

> The symbol ∃ means “there exists”. Finally we abbreviate the phrases “such that” and “so that” by the symbol or simply “s.t.”. When mathematics is formally written (as in our text), the use of these symbols is often suppressed.

所有函數不是 negligible 就是 non-negligible 。
如果是有限數的超越 1/p(n) ，則可視為 negligible 。因為可以定義在那之後都是。
但如果是無限數量的大於 1/p(n) ，則為 non-negligible 。
而 noticeable 則是在某個數後，全部都大於 1/p(n) 。

> 中右，第二項會求斜率。這邊是要找，在某一點大於某函數且之後斜率大於 0 ，因此可以判斷這之後都會在那函數之上。
> $\log_3{n} < log_2{n} \leq \sqrt{n}$
> [Derivative of log](https://brilliant.org/wiki/derivative-of-logarithmic-functions/)

> Three different type of BBP

### P/poly: Non-Uniform Polynomial Time


:::success
**Addiational**
Circuit (or Tree) Representation of TM
:::

---

## One-way function
> Porbabilistic Poly time (PPT)

digraph main {
    rankdir = LR
    x [label = "x"]
    fx [label = "f(x)"]
    x -> fx [label="easy\nf is a polynomial time comutable function"]
    fx -> x [label="hard\nfor all poly-time probabilistic TM,\nprobability to successfully invert the function is small"]

} 

Ex. Possible candidate: multiplication n=p * q is easy, factoring n when n is huge is an NP problem.

:::warning
**NOTE**
沒辦法證明一個函數是 one-way 。因為要把 f(x) 得到 x 的所有可能都驗證，很難。

---

會希望假設越少越簡單越好。
:::

* Finding fundamental intractability assumption: existence of OWF
* Minimize the number of assumptions
* Finding some equivalent relations

### Hard to invert

用機率的形式表示 one-way 的 hard to invert 。

For every probabilistic poly-time TM A' :
* every positive polynomial p(.) and all sufficient large n:
* $Pr\{A'(f(U_n),1^n) \in f^{-1}f(U_n)\} < 1/p(n)$
> 會如此表示 $A'(f(\_\_), ...) \in f^{-1}(\_\_)$，是也想表達除了一對一以外，多對一時也是成立。
> $1^n$ 為 n 個 1 的字串。
* $U_n$ us a uniformly distributed r.v. in $\{0,1\}^n$
* Given TM A', and p(.), finding $n_0$ such that for all n > $n_0$
* Useless to apply A' for. polynomial q(n) times to guess the inverse
* For $1^n$, exclude those function f(.) which can not be inverted by a poly-time A' because output of f(.) is too short such that the length of input of f(.) is exponential with respect to the length its output

But, for example, A(x) = $2^x$ is not PPT, and f(x)=log(x) is not one-way.

如果上述公式不含 $1^n$ (為了要讓輸入輸出長度一致)，f(x)=log(x) 會是 one-way，因為 f(x) 會是 1024 而 log(x) 會是 10 bit ，長度差距太大(例如，在只有 n 步驟 (poly-time) 的 TM ，輸出不會有 2^n (exponential-time)的長度)。然而 f(x)=log(x) 一般來說不是。所以輸入輸出不同長度(exponential 差異)的函數，需要個別去判斷。


:::info
every positive polynomial p(.) and all sufficient large n:
* For every probabilistic poly-time TM A' :
* $Pr\{A'(f(U_n),1^n) \in f^{-1}f(U_n)\} < 1/p(n)$

這種形式比之前的公式描述還嚴格困難。
:::

### Strong one-way function

f(.) is a strong one-way function if:
1. f is polytime computable
2. f is hard to invert

> non-negligible

### Weak one-way function

給予一個 f(x) ，只有一部分（不可忽略的 ; noticeable）x 集合沒辦法 invert ，則稱此為 weak one-way 。

> noticeable

weak one-way：至少有 noticeable 的機率不可 invert 。
Strong one-way：可 invert 的機率是可忽略的。

### Weak OWF exist => Strong OWF exists
> OWF (One-Way Function)

* Because we are still searching for REAL one-way functions, this theorem tells us that we only need to look for a weak one-way function.
* Intuition:
* $g(x_1x_2...X_{t(n)}) = f(x_1)f(x_2)...f(x_{t(n)})$
* 把多個 weak one-way function 串接起來組合成一個更大函數。
* 以機率來看，如果每個 Weak OWF invert 失敗的機率是 independent ，則可以相乘。
* Weak OWF 的成功的機率是 $1-\frac{1}{p(n)}$ 是小於 1 ，因此相乘越多會變越小。機率最後會變成 $e^{-n}$ ， where $\lim_{n\to x}{(1-\frac{1}{n})^n}=e^{-1}$ 。
* 但上述假設，在計算理論當中是不太能接受的東西。
* 很難證明每個 $f(x_{n_i})$ 的 invert 的過程與結果跟下一個 $f(x_{n_{i+1}})$ 是沒有幫助的。
* 並且，如果 f(x) 超過一定的數量，很難證明所有函數是 independent 。


:::info
**Additional**
One Way Function Exists => $P \neq NP$

Some more implications about the “OWF exists” intractability assumption
* This implies that an OWF can form a language that is in NP but not in P.
:::

### One-Way Function - More Implications

* If one-way function exists, hardcore predicate exists
* If one-way function exists, pseudo-random number generator (PRNG) exists
* ploy time adversary cannot detemine the ramdom number is from PRNG or truly RNG.
* If one-way function exists, pseudo-random function (PRF) exist
* If one-way function exists, secure bit commitment exists
* If one-way function exists, every NP problem has a ZKA (Zero-Knowledge proof).

### Claw-Free Function

> $D^i$ = Domain


### Hardcore Predicate

digraph main {
    node [shape=circle]
    rankdir = LR
    f_x [label = "f(x)"]
    f_x -> x [label = "hard"]
    x -> f_x [label = "easy"]
    label = "One Way Function"
}

Hardcore Predicate 定義了給予 x 後，到底是什麼東西算不出來？

> 如果機率等於 1 ，說明 f(x) 不會隱藏 b(x) 。
> 因為現在數值是以二元方式表示，因此機率最低會是 1/2 。
> b(x) 是 f(x) 相關，把 x 藏的最好的部分，並且 polynomial 的敵人在說 1 或 0 時，對或錯的機率都是 1/2 ，稱為 hardcore 。

:::success
任意 OWF 都存在 hardcore predicate 。
:::

### OWF exists => Hardcore Predicate exists

> $U(x,r)=x \cdot r \mod 2$ is important, it means that it is the XOR of a random subset of x's bits.
> 此說明，在 XOR 後的子集合，要判斷原先子集合有多少個 0 或 1 是很困難的。

此說明了，如果敵人可以在得知 f(x) 以及 random r 計算出 U(x, r) ，表示他的模型上有從 f(x) 得到 x 並在帶進 U(...) 的能力。也就是說，他可以從此模型當中，建立一個 a(...) 函式，得到 f(x) 的 invert (x 得值)。如果在一開始假設從 f(x) 得到 U(x, r) 的值是很困難的，則可稱有 one-way function 。

> [Lecture 9 - One Way Permutations and Hardcore bits.](https://www.cs.princeton.edu/courses/archive/fall05/cos433/lec10.pdf)

### Homework3

> **Q1. Show that the addition function $f(x, y) = x+y$ (where $|x|=|y|$ and $x$ and $y$ are interpreted as natural numbers) is not one-way. Likewise, show that $f(x) =x^2$ when computed over the integers is not one-way.**

For $f(x, y) = x+y$ (where $|x|=|y|$ and $x$ and $y$ are interpreted as natural numbers), this means that $f(x, y)$ will have one type which is $2z$ (where $z = |x| = |y|$ and $z$ is natural numbers). Therefore, even if the x and y are very large, the function $f$ is still easy to invert.

For $f(x) =x^2$, since x is natural number we can get the x from $\sqrt{f(x)} = \sqrt{x^2}$ to get the x. So, this statement is not the one-way function.

> **Q2. Prove that if there exist one-way functions, then there exists a one-way function $f$ such that for every $n$, $f(0^n) = 0^n$. Provide a full (formal) proof of your answer. This demonstrates that for infinitely many values $x$, the function $f$ is easy to invert. Why does this not contradict one-wayness?**

If $f$ is one-way function, this means that:

$Pr[A(f(U_n)) \notin f^{-1}(f(U_n))] \gt 1/p(n)$, Where A is PPT algorithm.

Then suppose that there have PPT algorithm A' can invert $f$ with probability at least $1/p(n)$, which:

$1/p(n) \le Pr[A'(f(U_n)) \in f^{-1}(f(U_n))]$ =
$Pr[A'(f(U_n)) \in f^{-1}(f(U_n)) | U_n \ne 0^n] \cdot Pr[U_n \ne0^n]$
$+ Pr[A'(f(U_n)) \in f^{-1}(f(U_n)) | U_n = 0^n] \cdot Pr[U_n = 0^n]$
$\ge Pr[A'(f(U_n)) \in f^{-1}(f(U_n)) | U_n \ne 0^n] \cdot Pr[U_n \ne 0^n]$

And, $Pr[U_n = 0^n] = \frac{1}{2^n}$; $Pr[A'(f(U_n)) \in f^{-1}(f(U_n)) | U_n \ne 0^n] = \frac{1}{p(n)} - \frac{1}{2^n}$.
Therefore, we can get $Pr[A'(f(U_n)) \in f^{-1}(f(U_n))] \ge (\frac{1}{p(n)} - \frac{1}{2^n}) \cdot (1 - \frac{1}{2^n}) \gt \frac{1}{2p(n)}$.
This means $A'$ inverts $f$ with probability greater than $\frac{1}{2p(n)}$.

In addition, with infinitely many value $x$, the function is easy to invert, however, the set is $2^n$ (exponential) large. For the polynomial computing, it is hard to find the value x without knowing what the function $f$. Contradiction.

> **Q3. Prove that if $f$ is a one-way function, then $g(x_1, x_2) = (f(x_1), x_2)$ where $|x_1|=|x_2|$ is also a one-way function. Note that $g$ fully reveals half of its input bits, but is nevertheless still one-way.**

Assume that there is an adversary A that, given $f(x_1)$ and $x_2$, finds $x_1$ and $x_2$ from $g(x_1, x_2)$ with non-negligible probability. Then, we can contruct an adversary B that, given $y$, finds $x_1$ from $y=f(x_1)$. However, the existence of such a B contradicts the one-way function $f$.

> **Q4. Let $x∈\{0,1\}^n$ and denote $x=x_1···x_n$. Prove that if there exist one-way functions, then there exists a one-way function $f$ such that for every $i$ there exists an algorithm $A_i$ such that for $x$ chosen uniformly over $\{0,1\}^n$,**
>
> **$Pr[A_i(f(x)) =x_i]≥\frac{1}{2}+\frac{1}{2n}$**
>
> **(This exercise demonstrates that it is not possible to claim that everyone-way function hides at least one specific bit of the input.)**

For $x_i$ chosen uniformly over $\{0,1\}^n$ means that it has half (1/2) probability is 0 (and 1). And, for 0, it has $\frac{1}{n}$ probability for A chosing $i$ location (which is $A(x) = x_i$). vice versa. Therefore, $Pr[A_if(x) = x_i] \ge \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{n} = \mbox{0 or 1} + \mbox{the location of 0 or 1}$.

:::info
* [Lecture 4: One Way Functions - II - CMU](https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture4.pdf)
* [CS276: Graduate Cryptography1 - University of California, Berkeley](https://people.eecs.berkeley.edu/~sanjamg/classes/cs276-fall16/collection.pdf)
:::

---

## Additional: Lattice Based Crypotography
> Related to Quantum Algorithm

### Point Lattice

### History of Lattice

> SVP shortest Vector Problem: Given a basis of L, find the shortest non-zero lattice vector
> CVP Closest Vector Problem

### SVP and CVP

SVP is NP-hard, best poly-time algorithm can do sub-exponential approximations: part of the difficulty of SVP comes from the fact that the given basis contains long vectors (much longer than the shortest non0zero vector)

> If point t is on the lattice (or is origin point?), it is SVP.

### Fully Homomorphic Encryption (FHE) Challenges
> Homomorphic encryption

兩個密文作互相運算後（例如相乘），相對應的明文還是跟計算後的密文有關係，則稱 Homomorphic encryption 。

---

## PRNG


(開根號 or 分解因式 mod m)，是等效的。
能夠開根號就可以分解因式。通常在傳統計算機系統，會是為 one-way function 。

(PRNG) The output sequence is indistinguishable from a true random sequence by any efficient algorithm.


Traditional/statistical PRNG 只能滿足部分 statistical tests ，而 Cryptographic PRNGS 要滿足所有。


1024 bit entropy 等級的 1 Gb 資訊有沒有機率會等效於 1 Gb entropy 的 1 Gb ？
> 有。
> 1024 bit entropy 等級的 1 Gb 資訊有 $2^{1024}$ 種排序，只要能分辨就可以。但 $2^{1024}$ 是遠比天文數字還大，沒辦法分辨是哪種。($2^{256}$ 約等於全宇宙原子總數)

### Handling Entropy

* entropy is not additive.

LFSR (Linear Feed back Shift Register)

### Randomness

Heuristic approaches of PRNG: programs that produce bit sequences that look like irregular and can pass some specific statistical tests, ex. FIPS 140-2 (monobit test, poker test, runs test, and long run test).
* Explicit behaviors of a PRNG:
* Efficient and deterministic programs
* Expand short random seeds into much longer PR bit sequences
* Pseudo random sequence:
* “computationally indistinguishable” from “true random” sequences by any efficient algorithm
* efficient: poly-time
* true random sequence
* e.g., Coin flipping
* r.v. $U_n, U_n \in_R{0,1}^n, Pr\{U_n=x\}=2^{-n}$
* 把所有序列列出並雖機選取，也是 random 。

### Kolmogorov Complexity of a String

是指描述 sequence 的困難度。
或指可以產生 sequence 的 program 的最短長度。

* **Kolmogorov radom**
* A string x is Kolmogorov-random if its length |x|=K(x).
* i.e. x is incompressible

### Models for Various Cryptosystem


### Pseudorandom Generators (PRNG)


Poly-time indistinguishable proof.

:::info
`\` means excluding.
:::


統計上不可分辨 => 計算上不可分辨。但不能反證。

### Existence of Pseudorandom Ensemble

> 1 為可以分辨。此指 $X_s$ 可與 $U_n$ 分辨與否。


### Indistinguishility by Repeated Sampling
> 1-indistinguishable <=> m(n)-indistinguishable


如果給你兩個 X, Y 序列，如果給多個 X, Y 序列跟只給一次，兩者的不分辨的機率相同。

此定理從如果不能從看多個序列分辨得出來，那麼只看一次也分辨出來的邏輯，說明如果反過來，從看一次也分辨不出來，那麼看多次會不會也分不出來？(結論，對也分辨不出來)


D 為給予多次序列，全部都是 X 或全部都是 Y 的輸入，D 的行為會有所不同。因此可以分辨。


理論， m 個可以不分辨的，可得 1 個也不分辨。
反推，當 1 個是不能分辨的，可得 m 個也不能分辨。

### Pseudorandom Ensemble


在 Ploy time 的 algorithm 下，符合 pseudorandom 定義的 pseudorandom generator 可以取代 random 。

Pseudorandom generator 拉長 random ，多一個 bit 他的 statistically not close to uniform U 。
> FC07, Page 44

### Unpredictability vs. Pseudorandomness
> PR (PseudoRandomness)

> $Pr{D(U_n)=1} = \frac{1}{2}$

:::warning
But how about X is PR <= X is Unpredictable?
> 證明：Start at FC-ch7, page 56.
:::

**結論：計算上來說，Unpredictability 和 Pseudorandomness 相等。**

### PRNG exist <=> OWF exists
> OWF (ony-way function)

* G 為 pseudorandom 。
* 如果 parameter 在進行函式時被丟掉（此為 y），而可以用 G(x) invert 得 x ，也是可以的（亦即，只要用 G(x) 得到其他不是在運算時丟掉的 parameter 則可稱可 invert）。
* D 輸出 1 表可 invert ，為 0 則為 uniform (invert 不了)。

* $\frac{2^n}{2^{2n}}$ 為 $U_n$ 是 $G(x)$ 的合法輸出機率。
* 而不只有等於的原因是因為 A 得到的機率是指不可忽略 ($\ge$ \frac{1}{p(n)})。

:::success
Other proof ： FC-ch7, page 66
:::

### Deniable Encryption

一般來說， public key 的加密的秘文相當於發票。當有脅迫者拿著密文要求加密者給出明文，加密者沒辦法說謊。即使有 random 參數也是，因為脅迫者也可以要求交出 random number 。

> 註：加密者，通常不會解密。

因此 Deniable encryption 就是為了解決此問題。

> 如果加密可以挑到右上圖的 x 點也可以是之外的(x 點為 pseudo number generater 的輸出)。

要考量到，解密出來的文跟原先明文不同的機率是多少。 機率為 $2^{-n}$ ，此數值足夠小。

:::success
一般來說，$2^{-n}$ 相當於直接猜秘文的機率。已經足夠小了。例如當 n > 256 ，就相當於全宇宙原子數。
:::

如果加密是一，可以說我有 $r_1$ 並且在加密在 x 點上。若加密是零，因為是 random ，可以說加密在 x 點也可以不是。


可以拿 $r_1'$ 跟 RSA key 反向算出 sigma 並跟 G($r_1$) 比對是否是 x 點。

### Hardcore Function

有人證明，例如 RSA 不只有 LSB 是 hardcore predicate (很難預測)，他至少有一段都是 hardcore predicate 。

### PRNG exists <= OWF exists

> FC07, page 66 ~ 69, 1 - 4 slide pages are first prove.


### Pseudorandom Functions


如果說想要 random access PRNG 生成的 random sequence ，例如第一百位的數值，就必須要讓 PRNG 從零開始生成到第一百位才可以得知。


$f_k(x)$ 會有 exponentially many pseudo random bits.
例如， x 為 n 的 bit ，就會有 $2^n$ 的 entry ，每個 entry 有 n 個 bit 。然而 PRNG 有 n 個 bit 的輸出會遠小於 $f_k()$ 。實務上，因此 PRNG 沒辦法建構 $f_k()$ 。



Random function n bit generate n bit need $2^n$ bits. Therefore, n bit of PRNG cannot use on random function.

#### The Definition of Pseudorandom function

> 任意有效率的方式都沒辦法分辨 deterministic function F 和 truly random function H ，則可稱 F 為 Pseudorandom function.

如，就算給予 ploy(n) 的 D $2^n$ 的表格， D 沒辦法在 ploy 的時間內完全分辨 $2^n$ 。


### Construction of a PRF from a PRNG



:::warning
PRF from PRNG proof, FC07, Page 119
:::


> $U_{2n}$ 在第 k 層的 $2^{k+1}$ 之後都是 random 。
> $G(U_n)$ 則是在第 k 層 $2^k$ 之後都是 random 。

---

## Zero-Knowledge Proof (ZKP)

verifier and proofer.

Three types of zero-lnowledge: perfect （完全不可分辨）, statistical (統計上不可分辨), computational.

> 右手邊的像天使的人，是公正的第三者。

此左右相等的意思是指左偏在證明時，是等效於右圖直接告訴此為正確的證明。並且，左圖在證明過程中是沒有洩漏重要訊息。

:::warning
非交談式（沒有溝通）ZKP 不是 ZKP ，那已經算是數位簽章。

---

* Fiat-Shamir, How to prove yourself, Crypto’86, Secure under the random oracle (RO) model, also the first paper related to RO mode
* FS’86 - QRA, GQ’88 - RSA, Schnorr’91 - DL, KW’03 - EQDL
:::

### Common Tricks for Proving ZK


### Information versus Knowledge

**Zero information proof is not zero knowledge proof.**


### Interactive Proof System


### Auxulary-Input ZK


### ZKP for NP-Assertion

所有 NP-Assertion 都是 ZKP 。
> 有條件的：If one-way functions exist.

> PPT (Probabilistic Polynomial-Time)


每一次 V 做驗證時，因為 P 會有 $\pi$ （random permutation） 所以 V 不會知道實際的 color 。

### Bit Commitment Using One-Way Function

One-way permutation 有 1-to-1 的特性，而 one-way function 事 many-to-1 特性。因此，若用 one-way function 會比 one-way permutation 還要來得複雜。

> Binding: 間單說，P 傳給 V 的訊息不會被竄改。
> Binding: Perfect / Hidding: Computational
> Binding 和 Hidding 通常是一個 trade off.

:::warning
isomorphic
:::