Public Key Crypto

Notice, for $p, q \in \mathbb{Z}$, where $(p, q) = 1$, $\phi(pq) = \phi(p)\phi(q)$
- Proof -> $(a, m) = 1 \rightarrow \exists b \in \mathbb{Z}_m ab \equiv 1 (m)$
  - Notice, $\exists s, t \in \mathbb{Z}, sa + tm = 1 (m) \rightarrow sa \equiv 1 (m)$
- $(a, m) = 1 \rightarrow a^k \equiv 1 (m)$, notice, for all $k, (a^k, m) = 1$
  - For $k = 1$ the theorem holds, suppose it holds for $n$, then, consider $sa^{n+1} + tm = a$, then $(a^{n+1}, am) = a$, and $(a^{n + 1}, m) = d \rightarrow d | a$, thus $d = 1$
- If $(a, m) = 1$, and $(a, n) = 1$, then $(a, mn) = 1$
- $(k, mn) = 1$, iff $(k, m) = 1$, and $(k, n) = 1$
  - Reverse - above
  - Forward - triv
  - Fix $k \leq mn, k = rm + b$, where $r \leq n - 1$, and $b < m$
    - If $(b, m) = 1$, then $(k, m) = 1$ -> otherwise contra using $(k, m) | rm \land (k, m) | b$
    - Notice if $(r, n) = 1$, then $(k, n) = 1$ (similar argument as above), i.e $l | rm \rightarrow l | n \lor l | m$
    - As such there are $\phi(n)$ choices for $r$, and $\phi(m)$ choices for $b$
RSA
- Features
  - $D: \mathcal{C} \rightarrow \mathcal{M}$, $E: \mathcal{M} \rightarrow \mathcal{C}$, where $\forall M \in \mathcal{M}, D(E(M)) = M$
  - $E, D$ are easy to compute
  - Publicity of $E$ does not comprimise $D$
- Let $N = pq$, then $(m^{ed}) \equiv m (pq)$, where $N, e$ are the public-key, $N, d$ are the private-key
  - Notice $m^{\phi(N) + 1 = k\phi(p)\phi(q) + 1= (p - 1)(q - 1) + 1} \equiv m (N = pq)$, if $(m, n) = 1$
- Then $ed = k\phi(N) + 1$, in other-words $ed \equiv 1 (\phi(N))$

Algorithms

Multi-precision numeric package
- I.e store arbitrarily long numbers using (base as 2^64)
- Addition / subtraction $O(n)$ where $len(int) = n$
- Multiplication $O(n^2)$

Powering Algorithms

Given some $g \in G$, we wish to compute $g^n$

Naive: requires $n - 1$ multiplications, i.e $g * g \cdots * g$
Faster: $n = \Sigma_i \epsilon_i 2^i$ (where $0 \leq i < log_2(n)$), store $1, g^2, g^4, \cdots$ in memory, then $g^n = \Pi_i \epsilon_i g^{2^i}$
- This requires only $log_2(n)$ operations

  func Exp(base, exp int) int {
      return exp_(base, exp, 1)
  }

  func exp_(base, exp, accum int) int {
      if exp == 0 {
          return accum
      }
      if exp % 2 == 0 {
          return exp_(base, exp >> 1, accum * accum)
      }
      return exp_(base, exp - 1, accum * base)
  }

Euclidean Algorithms

Typical Algorithm

    func GCD(a, b int) {
        if a < b {
            a, b = b, a
        }
        if b == 0 {
            return a
        }
        return GCD(b, a % b)
    }

Lehmer
- ...
Binary

Euclid Extended Algorithm

Let $n, m \in \mathbb{Z}, d = (n, m) \rightarrow \exists s, t, sm + tn = d$
- EEA - gives the parameters $s, t$ for the bezout's equality above

    func ExtendedEuclidean(a, b int) (u, v, d int) {
        // initialize aux variables
        var (
            v_1 = 0
            v_3 = b
            t_1 = 0
            t_3 = 0
        )
        // switch if necessary
        if a < b {
            a, b = b, a
        }
        u = 1
        d = a
        // short circuit if possible
        if b == 0 {
            return u, 0, a
        }
        for v_3 != 0 {
            t_3 = d % v_3
            t_1 = u - (d / v_3) * v_1
            u = v_1
            d = v_3
            v_1 = t_1
            v_3 = t_3
        }
        return u, (d - a * u) / b, d
    }

Basic Defn.
- Shannon Cipher + Perfect Security
  - Shannon Cipher
    - $\Epsilon = (E, D)$ is a pair of functions, where $E : \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{C}$, and $D : \mathcal{C} \times \mathcal{K} \rightarrow \mathcal{M}$
    - Where the following correctness property is satisfied, i.e $\forall k \in \mathcal{K}, \forall m \in \mathcal{M}, D(k, E(k, m)) = m$
    - In this case $\Epsilon$ is defined over $\mathcal{K}, \mathcal{M}, \mathcal{C}$ -> these define the concrete spaces of objects that the protocol takes as inputs, i.e $\mathbb{Z}_{p}, 2^{256},\cdots$
  - Using the above SC, $\Epsilon$ Alice + Bob communicate securely by secretly sharing $k \in \mathcal{K}$ (their shared key), and communicating $c = E(k, m) \in \mathcal{C}$ in plain-text
    - Concerns
      - Can Eve intercepting $c$ learn anything abt. $m$ without knowing $k \in \mathcal{K}$?
      - Can Eve tamper with $c$, and make the message to Bob un-intelligible?
  - one-time pad
    - Let $\mathcal{M} = \mathcal{K} = \mathcal{C} = 2^L$ (i.e bit-strings of length $L$), and for $m \in \mathcal{M}, k \in \mathcal{K}, c = E(k,m) = m \oplus k$, and $D(k,c) = c \oplus k$
      - Naturally correctness is satisfied, i.e $\forall k \in \mathcal{K}, m \in \mathcal{M}, D(k, E(k, m)) = D(k, m \oplus k) = m \oplus k \oplus k = m \oplus 0^L = m$
  - substitution cipher
    - $\mathcal{M} = \mathcal{C} = \Sigma$, $\mathcal{K} = {f : \Sigma \rightarrow \Sigma: \forall a \in \Sigma, f(f(a)) = a}$, and $c = E(k, m), c[i] = k(m[i])$, and $D(c, k) = m', m'[i] = k(c[i])$
      - Thus $m' = D(k, E(k, m)), m'[i] = k(k(m[i])) = m[i]$ -> correctness satisfied
  - Perfect Security
    - i.e for $c = E(k, m)$ -> how much abt. $m$ can Eve know if she intercepts $c$?
    - Assume that $k \in \mathcal{K}$ is drawn uniformly at random from $\mathcal{K}$, i.e $Pr[X = k] = \frac{1}{|\mathcal{K}}$
    - Want to make it so that attacker's choice of $m$ is independent from $c$
    - Definition
      - Let $\Epsilon = (E, D)$ be a SC. Suppose $k \in \mathcal{K}$ is a uniformly random variable sampled from $\mathcal{K}$, then $\Epsilon$ is perfectly secure if
        
        $\forall m_0, m_1 \in \mathcal{M}$, and $\forall c \in \mathcal{C}$, $Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]$
    - Let $\Epsilon$ be a PS SC, then the following are equivalent
      - $\Epsilon$ is perfectly secure
      - For every $c \in \mathcal{C}$, $\exists N_c$, such that $\forall m \in \mathcal{M}$, $|{k \in \mathcal{K}: E(k, m) = c}| = N_c$
      - For each $m \in \mathcal{M}$, $E(k, m)$ has the same distribution as $\mathcal{K}$
      - Proofs
        
        Forward - Suppose $\Epsilon$ is a PS SC, fix $c \in \mathcal{C}$, fix $P_m = Pr[E(k, m) = c]$ notice $\forall m_0, m_1 \in \mathcal{M}, P_{m_0} = P_{m_1}$, and $N_c = P_m |\mathcal{K}|$
        
        Reverse - Fix $c \in \mathcal{C}$, and $m_0, m_1 \in \mathcal{M}$, then $Pr[E(k, m_0) = c] = \frac{N_c}{|\mathcal{K}|} = Pr[E(k, m_1) = c]$
        
        Fix $k \in \mathcal{K}$, and $c \in \mathcal{C}$, then $\forall m \in \mathcal{M}, Pr[E(k, m) = c] = P_c = N_c / |\mathcal{K}|$
    - One time pad is PS SC
      - Fix $c \in \mathcal{C}$, and $m_0, m_1 \in \mathcal{M}$, then if $k \in \mathcal{K}$ is sampled randomly the probability that $Pr[E(k, m_0) = c] = Pr[m_0 \oplus k = c] = Pr[k = m \oplus c]$, thus fix $N_c = 1$
  - Negligible, super-poly, poly-bounded
    - negligible - $f : \mathbb{Z}_{\geq 1 } \rightarrow \mathbb{R}$, if for all $c \in \mathbb{R}$, $\exists N$, where $n \geq N \rightarrow |f(n)| < 1/n^c$, i.e $f$ decreases faster than any polynomial in $n$
    - $f : \mathbb{Z} \rightarrow \mathbb{R}$ is negligible iff $lim_n f(n)n^c = lim_n f(n) lim_n n^c = lim_n 1/n^c lim_n n^c = 0 * lim_n n^c = 0$
      - Reverse - Suppose $lim_n f(n)n^c = 0$,
  - Is $\frac{1}{n^{log(n)}}$ negligible?
    - Fix $c \in \mathbb{R}$, and choose $N > 2^c, log(N) > c$, then $n \geq n \rightarrow \frac{1}{n^{log(n)}} < \frac{1}{N^{log(N)}} < \frac{1}{n^c}$, thus it is negligible
  - Let $\Epsilon = (E, D)$ be SC defined over $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, then $\Epsilon$ is PS iff for any $\phi : \mathcal{C} \rightarrow {0,1}$, $\forall m_0, m_1 Pr[\phi(E(k, m_0))] = Pr[\phi(E(k, m_1))]$
    - Forward - Suppose $\Epsilon$ is PS, fix $C \subset \mathcal{C}$, where $c \in C \rightarrow \phi(C)$, then $Pr[\phi(E(k, m_0))] = \Sigma_{c \in C} Pr[E(k, m_0) = c] = \Sigma_{c \in C} Pr[E(k, m_0) =c] = Pr[\phi(E(k, m_1))]$
    - Reverse -
      - Suppose $\forall m_0, m_1, Pr[\phi(E(k, m_0))] = Pr[\phi(E(k, m_1))]$, suppose $\Epsilon$ is not PS, then $\exists c \in \mathcal{C}$ where $Pr[E(k, m_0) = c] \not= Pr[E(k, m_1)]$, and define $\phi(c') = 1 \iff c' = c$ (contradiction)
  - Also equivalent $Pr[M = m | E(K, M) = c] = Pr[M = m]$
    - Apply bayes and that each value is uniformly distributed
  - Shannon's Theorem
    - Let $\Epsilon = (E, D)$ be shannon-cipher, $\Epsilon$ is PS iff $|\mathcal{K}| \geq |\mathcal{M}|$
      - Suppose $|\mathcal{K}| < |\mathcal{M}|$, WTS, fix $k \in \mathcal{K}$, then $\exists m_0, m_1$, where $Pr[c = E(k, m_0)] \not= Pr[c = E(k, m_1)]$ (i.e $m_0, m_1$ under $k$ are distinguishable)
      - Let $S = {D(k, E(k, m)), m \in \mathcal{M}}$, thus, there exists $m_0, m_1$ where $E(k, m_0) = E(k, m_1)$, then consider $Pr[M = m | E(K, M) = c] = Pr[M = m]$
      - Alternatively, fix $k \in \mathcal{K}, m \in \mathcal{M}$, then consider $S = {D(k', c = E(k, m)), k' \in \mathcal{K}}, |S| = |\mathcal{K}| \leq |\mathcal{M}|$
        
        Since $(E, D)$ is Shannon-Cipher, $D(k, E(k, m)) = m$, if $m' \in \mathcal{M}\backslash S$, then $D(k, E(k, m')) \in S$ (contradiction), and $c \not= E(k, m')$ (thus $(E, D)$ is not perfectly secure)
- Computational Ciphers + Sematic Security
  - Shannon's Thm -> $|\mathcal{K}| \geq |\mathcal{M}|$ (space of bit-sequences length of keys > length of messages)
    - semantic security - Force indistinguishability under computationally bounded adversaries (lessen requirement from perfect-security) (also lessen requirement of shannon-cipher? Equality of message probablistic, concurrrently send multiple messages?)
  - computational cipher - Let $\Epsilon = (E, D)$ (definition is analogous to shannon-cipher), $E$ is a probablistic algo.
    - correctness, let $c \leftarrow^{R} E(k, m) \rightarrow m = D(k, c)$
      - Thus CC -> SC, but not vice-versa
  - semantic security
    - For all predicates $\phi : \mathcal{C} \rightarrow {0,1}$, $|Pr[\phi(E(k, m)) = 1] - Pr[\phi(E(k, m')) = 1] \leq \epsilon|$ (where $\epsilon$ is negligible)
  - attack games - Consider a game between $\mathcal{P}$ (adversary), and $\mathcal{V}$ (challenger) multiple rounds of interaction, advantage is probability space that $\mathcal{V}$ incorrectly accepts the final value output from $\mathcal{P}$
  - Semantic Security Attack Game
    - Define two experiments $b \in {0,1}$
    - Experiment $b$
      - $\mathcal{P}$ sends $m_0, m_1 \in \mathcal{M}$ to $\mathcal{V}$
      - $\mathcal{V}$ computes $k \leftarrow^R \mathcal{K}, c \leftarrow^R E(k, m_b)$, and sends $c$ to $\mathcal{P}$
      - $\mathcal{P}$ outputs $\hat{b} \in {0,1}$
  - semantic security advantage - Let $W_b$ be $\hat{b}$ in experiment $b$, then $|Pr[W_b = 1] - Pr[W_0 = 1]|$
    - $(E, D)$ is semantically secure iff $SSadv[\mathcal{P}, \mathcal{E}] \leq \epsilon$ (where $\epsilon$ is negl.)
    - Can consider $\mathcal{P}$ as evaluating any $\phi$ (predicate on $c$)
Computational Security
New Directions in Crypto.
- Initially - Key must be known between each user
  - Attacks
  - cipher-text only - Attacker only has cipher text of a message
  - known plaintext attack - attacker has cipher-text + plain-text mappings -> want to determine $S_k$ -> encryption function
  - chosen plaintext attack - Attacker can send own plain-text, and receive cipher-text of that plain-text (hardest to over-come) $Alt text$
    - Above diagram details conventional (shared-key) crypto. i.e transmitter and receiver have secure channel to communicate key, and open channel to communicate message
- public-key
  
  $Alt text$
  - pk distribution -> signatures, i.e receivers know who the transmitter was that sent message (using only public info)
  - pk cryptosystem -> More complex - Secure channel using only public information -> only transmitter / receiver can verify
  - Definitons
problems
- Suppose Alice / Bob send messages over a channel, where Eve intercepting each bit observes $b$ with prob. $p$, and $1 - b$ with prob. $1 - p$
One Way Functions
PRGs
Computational Security

Proofs, Arguments, and Knowledge

Suppose Alice / Bob, have files $a_i \in {0,1}$, $b_i$ and wish to know whether the files are equal
- Simplest protocol: send all bits, $O(n)$ complexity (arbitrarily large)
Simpler protocol, choose $\mathcal{H}$ a set of hash functions, where
- $\forall x, y, Pr_{h \in \mathcal{H}}[h(x) = h(y) | x \not= y] \leq negl(x)$
For example, take $h_r(a) = \Sigma_i a_i r^i \in \mathbb{F}_p$
- then if $a_i \not= b_i$, $Pr[h_r(a) \not= h_r(b)] = 1 - \frac{n}{p} \leq 1 - 1/n$ (notice, this hash function is not actually secure)
If $p_a, p_b \in \mathbb{F}_p[X]$, then $p_a(x) = p_b(x)$ for at most $n$ distinct $x$
- Notice $deg(p_a - p_b) \leq n$

Definitions + Technical Prelims

Interactive Proof
- Let $f: {0,1}^n \rightarrow \mathcal{R}$, a k-message interactive proof system for $f$, is a probablistic alg. of runtime $poly(n)$, $\mathcal{V}$, and a deterministic prover $\mathcal{P}$, where both $\mathcal{V}, \mathcal{P}$ are given input $x \in {0,1}^n$, and $\mathcal{P}$ computes $f(x)$, each party then alternates sending $m_i$ (the output of some internal state-machine (non-deterministic for $\mathcal{V}$)), then at the end of the protocol $\mathcal{V}$ outputs $0,1$ depending on whether $\mathcal{V}$ agrees that $f(x) = y$
  - Denote $out(\mathcal{V}, r, x, \mathcal{P})$ the outcome of the protocol, according to some random input $r$, notice, we may then determine $\mathcal{V}_r$ as a deterministic algorithm
- Definition
  - Let $(\mathcal{V}, \mathcal{P})$ be a pair of verifier / prover alg., then
    - completeness - For $x \in {0,1}^n$, $Pr_r[out(\mathcal{V}, x, r, \mathcal{P}) = 1] \geq 1 - \delta_c$
      - Intuitively, given a deterministic prover, this determines the rate of false negatives for any $r$
    - soundness - For any $x \in {0,1}^n$ and any deterministic prover strategy $\mathcal{P}'$, if $\mathcal{P}'$ sends $y \not= f(x)$ at the start of the protocol, then $Pr_r[out(\mathcal{V}, x, r, \mathcal{P}') = 1] \leq \delta_s$
  - and IP is valid if $\delta_s, \delta_c \leq 1/3$
Argument System
- IP where soundness only desired to hold against polynomially bounded prover - computational soundness
Intuition
- Why error tolerance $1/3$?
  - Valid IP can be transformed into IP with perfect Verifier, i.e $\delta_c = 0$
- Why restrict $\mathcal{P}$ to be deterministic? Suppose $\mathcal{P}'$ exists, where with $p < 1$ prob. $out(\mathcal{V}, x, r, \mathcal{P}') = 1$, then set $\mathcal{P}_r$ (deterministic) as $\mathcal{P}$
Schwartz-Zippel
- Let $\mathbb{F}$ be a field, and $g : \mathbb{F}^m \rightarrow \mathbb{F}$, be a non-constant $m$-variate poly. of total deg $d$, then $Pr_{x \leftarrow S^m}[g(x) = 0] \leq d/|S|$
  - Take $S = \mathbb{F}$, then $Pr[p(X) = g(X)] = d/|\mathbb{F}|$, i.e $g - f \in \mathbb{F}^m[X]$, and $deg(g - f) \leq d$
Low degree and Multi-linear extensions
- Notice, given an input set $I = {0, 1, \cdots, n-1}$, and a function $g : I \rightarrow \mathbb{F}_p$, one can construct the lagrange interpolation poly. $f$ over $\mathbb{F}_p$, of degree $n - 1$, where $g(x) = f(x)$
- One can also construct the low-degree extension, $\tilde{g} : {0,1}^v$, where $v = log(n)$
  - $g$ is multi-linear poly. - that is $deg(\tilde{g}) = v$ (product of $g_x : {0,1} \rightarrow \mathbb{F}_p, deg(g_x) = 1$)
    - Lower degree = fewer field mult. = faster evaluation
- Univariate extension looks like this $P_x = \Pi_{y \in \mathbb{Z}n \backslash x} \frac{X - y}{x - y}$, then $P_x(z) = 0 \iff z \not= x, P_x(z) = 1 \iff z = x$, then $f_g(X) = \Sigma{x \in \mathbb{Z}_n} g(x)P_x(X)$
  - Notice, $deg(f_g) = n - 1$
multilinear poly - Let $g(x_1, \cdots, x_n) = \Sigma_i a_i \Pi_i x^{j_i}, j_i = 1$, i.e $g(x_1, x_2) = x_1 + x_2 + x_1x_2$ is multi-linear, $g(x_1, x_2) = x_2^2$ is not
extension
- Let $f : {0,1}^n \rightarrow \mathbb{F}$ be a function, then the multi-linear extension, $g : \mathbb{F}^n \rightarrow \mathbb{F}$ is an extension, if $g(x) = f(x)$, i.e for $g$, take $x$ as $0_{\mathbb{F}}, 1_{\mathbb{F}}$
  - Extension is distance-amplifying - according to schwartz-zippel, if $f, f' : {0,1}^n \rightarrow \mathbb{F}$ dis-agree anywhere, then $g, g' : \mathbb{F}^n \rightarrow \mathbb{F}$ dis-agree w/ prob $1 - d/|\mathbb{F}|$ (make size of $\mathbb{F}$ extremely large, and randomly sample evaluations)
  - Utility, if $f, f'$ are the same, then expect $g, g'$ to be the same, otherwise, expect them to differ in $|\mathbb{F}| - d$ points
Let $f : {0,1}^v \rightarrow \mathbb{F}$ has a unique multi-linear extension over $\mathbb{F}$
- existence - Let $f : {0,1}^v \rightarrow \mathbb{F}$, then $\tilde{f}(x_1, \cdots, x_v) = \Sigma_{w \in {0,1}^v}f(w) \chi_w(x_1, \cdots, x_v)$, where for $w = (w_1, \cdots, w_v), \chi_w(x_1, \cdots, x_v) = \Pi_{1 \leq i \leq v} (x_iw_i + (1 - x_i)(1 - w_i))$
  - $\tilde{f}$ extends $f$
  - $\chi(w)$ is defined as the multi-linear lagrange basis poly.
  - Notice for $\chi_w(w) = 1$, and $\chi(y) = 0$, $w \not = y$
  - Furthermore $\chi_w$ is multi-linear, sum of multi-linear is also multi-linear
- uniqueness
problems
Interactive Proofs
- Sum-check Protocol
  - Given $v$-variate poly. $g : {0,1}^v \rightarrow \mathbb{F}$, prover / verifier want to agree on $\Sigma_{0 \leq i \leq v} \Sigma_{b_i \in {0,1}} g(b_1, \cdots, b_v)$ (sum of evaluations of $g$ across all possible inputs)
    - Given $g$, verifier can evaluate $g$, $2^v$ times (worst-case), prover = verifier
  - protocol
    - Round 0. $\mathcal{P}$ sends $C = H_g$ to $\mathcal{V}$
    - Round 1. $\mathcal{P}$ sends $g_1(X_1) = \Sigma_{x_2, \cdots, x_v \in {0,1}} g(X_1, x_2, \cdots, x_v)$ (univariate)
      - $\mathcal{V}$, checks that $C = g_1(0) + g_1(1)$, and that $deg(g_1) = deg_1(g)$, where $deg_i(g) = deg(g(X_1, \cdots, X_v))$ (in variable $X_1$, i.e fix all other variables to be fixed values in ${0,1}$)
      - $\mathcal{V}$ sends $\mathcal{P}$, $r_1$
    - Round $j$. where $1 < j < v$
      - $\mathcal{P}$ send $g_j = \Sigma_{v_{j+1}, \cdots, x_v \in {0,1}} g(r_1, \cdots, r_{j-1}, X_j, x_{j+1}, \cdots, x_v)$
      - $\mathcal{V}$ checks that $g_{j - 1}(r_j) = g_j(0) + g_j(1)$, and that $deg(g_j) \leq deg_j(g)$
      - $\mathcal{V}$ sends random $r_j$ to $\mathcal{P}$
    - Round $v$
      - Same as $j$, except that $g_v(r) = g(r_1, \cdots, r_v)$
  - intuition
    - Notice, both $\mathcal{P}, \mathcal{V}$ agree on value of $g$, thus given $g_1$ from $\mathcal{P}$, and that $g_1(0) + g_1(1) = C$, how to prove that $g_1$ actually is evaluated correctly? $\mathcal{V}$ if doing brute-force, would have to evaluate $2^{v - 1}$ variables in $g$?
      - Instead re-cursively apply sum check, i.e start again with $g_1 = g$, and continue
  - correctness
    - completeness - If $\mathcal{P}$ evaluates $g$ correctly, and sends $C$, the protocol is always correct
    - soundness - Protocol gives false positive with error $dv/|\mathcal{F}|$
      - Notice, if in any of the rounds, $\mathcal{V}$ accepts an incorrect evaluation, then $\mathcal{P}$ can extrapolate the incorrect evaluations to later, rounds (sum-check with $g$ controlled by $\mathcal{P}$), prob that $Pr[g_i(x) = s_i(x)] = deg_i(g)/\mathcal{F}$, thus take union over all rounds to get $dv/|\mathcal{F}|$
- Application of sum-check: $#SAT \in IP$
  - boolean formula - Formula over $n$ variables, with $2^n$ nodes, and $log(n)$ height. Represented with input in leaves, each parent is product of $\land, \lor$ over children
  - $#SAT$ - Given boolean formul $\phi : {0,1}^N \rightarrow {0,1}$, determine number of satisfying values, in other words, $\Sigma_{x \in {0,1}^n} \phi(x)$
  - Determine extension of $\phi$ and apply sum-check, then $\tilde{\phi} : \mathbb{F} \rightarrow \mathbb{F}$, $\mathbb{F}$ must be chosen so that the error prob -> $deg(\phi)n /|\mathbb{F}|$ is negligible
  - Determining extension from $\phi$ is arithmetization
    - $x \land y := xy$, $x \lor y := x + y - xy$
- GKR
  - Notice for $#-SAT$ although the verifier runs in poly. time, the $\mathcal{P}$ prover must still evaluate the sum in time-exponential in the inputs (likely impossible for reasonable size)
  - $\mathcal{P}$ and $\mathcal{V}$ agree on a log-space uniform arithmetic circuit of fan-in two (i.e the underlying boolean formula, leaf-nodes can have more than one parent (can be inputs to more than one parent ))
    - Log-space uniform -> implies that $\mathcal{V}$ can gain accurate under standaing w/o looking at all of $\mathcal{C}$, thus complexity can be logarithmic in $gates(\mathcal{C})$, and logarithmic in $inputs(\mathcal{C})$
    - $\mathcal{P}$ prover complexity linear in $gates(\mathcal{C})$ (significant improvement to $#-SAT$)
  - protocol
    - intuition - Circuit represented as a binary tree, with each top-level being an arithmetic (multi-variate poly.) in the gate-outputs from the level-beneath, goal, prover sends all evaluations, then iteratively applies sum-check at each depth (correctly verify that gate values at each level are evaluated), until the inputs are checked ($O(1)$ check per input by $\mathcal{C}$)
    - $\mathcal{P}$, $\mathcal{V}$ agree on LSU circuit $\mathcal{C}$ -> arithmetic circuit represented as $g : \mathbb{F}^n \rightarrow \mathbb{F}$, where $size(\mathcal{C}) = S$, and $d = depth(\mathcal{C})$ (layers), $S \leq 2^d$?
      - $0$ is output, $d$ is input layer, let $S_i$ be the number of gates at layer $i$, where $S_i = 2^{k_i}$
      - $W_i : S_i \rightarrow \mathbb{F}$ - I.e a function mapping a gate at layer $i$ to its output
        
        Dependent upon the inputs to circuit? I.e actually a ML poly. in inputs $x_i$?
      - Let $in_{i, 1}, in_{i, 2} : S_i \rightarrow S_{i + 1}$, where $in_{i, 1}$ returns the left child of $a$, and $in_{i, 2}$ returns right child of $a$, notice, inputs to gates at $i$ will be at layer $i + 1$
  - Algorithm
    - Protocol has $d$ iterations (one for each layer of circuit)
    - Let $\tilde{W_i} : \mathbb{F}^{k_i} \rightarrow \mathbb{F}$ -> MLE (multi-linear lagrangian extension of $W_i$), means that it is distance encoding, so $\mathcal{P}$ sends $\mathcal{V}$, $\tilde{W_i}(r)$ for some random $r \in \mathbb{F}$
      - Then $\mathcal{V}$ chooses $r_i \in F^{k_i}$ to be evaluated, and $\mathcal{P}$ sends $\tilde{D_i}(r)$, verifier checks that $\tilde{W_i}(r) = \tilde{D_i}(r)$
      - However, does $\mathcal{V}$ evaluate $\tilde{W_i}(r)$ itself? Requires evaluation at all layers $1 \leq j \leq i$ exponential run-time? No, recursively checks that $\tilde{W_i}$ by reducing to claim abt $\tilde{W_{i + 1}}(r)$ until reduced to claim abt. inputs
    - How to reduce evaluation of $\tilde{W_i}(r)$ to $\tilde{W}_{i + 1}(r)$?
      - $\tilde{W}i(z) = \Sigma{b,c \in {0,1}^{k+1}} \tilde{add}i(z,b,c)(\tilde{W}{i + 1}(b) + \tilde{W}{i + 1}(c)) + \tilde{mult}i(z, b, c)(\tilde{W}{i + 1}(b)\tilde{W}{i + 1}(c))$
      - Notice, above is still a MLE, (composition of addition / multiplication of MLEs from lower layer)
    - Thus apply sum-check to $\tilde{W}_i$
      - i.e start with $f_{r_i}(b,c) = \Sigma_{b,c \in {0,1}^{k + 1}} \tilde{add}i(r_i, b, c)(\tilde{W}{i + 1}(b) + \tilde{W}{i+1}(c)) + \tilde{mult}i(r_i, b,c)(\tilde{W}{i + 1}(b)\tilde{W}{i+1}(c))$
        
        i.e at each round sum is over $2^{k + 1}$ values, and takes $2$ rounds (fix $b$, then $c$), then have to evaluate $\tilde{W}{i + 1}(b), \tilde{W}{i + 1}(c)$ (rely on next round, but how to take $b^, c^$ into accout for random value?)
    - Reduce verification to single point, let $l : \mathbb{F} \rightarrow \rightarrow F^{k + 1}$, where $l(0) = b^$, and $l(1) = c^$ (unique), then evaluate $q : \mathbb{F} \rightarrow \mathbb{F} = \tilde{W}{i + 1} \circ l$, $\mathcal{P}$ sends $q$ to $\mathcal{V}$, and checks that for random $r^* \in \mathbb{F}^{k + 1}$, $q(r^*) = \tilde{W}{i + 1} \circ l (r^*)$
    - Next iteration starts with $r_{i + 1} = l(r^*)$
    - GKR -> see gkr.png
      - Round 0: $\mathcal{P}$ sends $D : {0,1}^{k_0} \rightarrow \mathbb{F}$ (outputs of circuit), $\mathcal{V}$ computes $\tilde{D}(r_0) = m_0$, where $r_0$ is randomly sampled from $\mathbb{F}^{k_0}$
      - Round $0 < i \leq d - 1$
        
        Let $f_{r_i}(b, c) = \tilde{add}i(r_i, b, c)(\tilde{W}{i + 1}(b) + \tilde{W}{i + 1}(c)) + \tilde{mult}i(r_i, b, c)(\tilde{W}{i + 1}(b)\tilde{W}{i + 1}(c))$
        
        $\mathcal{P}$ claims that $m_i = \Sigma_{b,c \in {0,1}^{k_{i + 1}}} f_{r_i}(b, c) = \tilde{W}_i(r_i)$
        
        $\mathcal{V}$ / $\mathcal{P}$ perform sum-check to verify $m_i$, and $\mathcal{V}$ is forced to evaluate $b^, c^ \in \mathbb{F}^{k_{i + 1}}, \tilde{W}{i + 1}(b^*), \tilde{W}{i + 1}(c^*)$
        
        then $\mathcal{V}$ determines $l : \mathbb{F} \rightarrow \mathbb{F}^{k_{i + 1}}$, $l(0) = b^, l(1) = c^$, and expect $\mathcal{P}$ to send $q = \tilde{W}_{i + 1} \circ l$
        
        $\mathcal{V}$ verifies $q$, by evaluating $q(0) = \tilde{W}_{i + 1}(b^)$ (similarly for $c^$)
        
        then round $i + 1$ starts, where $m_{i + 1} = q(r_{i + 1} = l(r^))$, $r^$ is randomly sampled
How to transform IP to PVPQ
- Given an $IP$, $\mathcal{P}, \mathcal{V}$, how to construct a publicly verifiable protocol (that is non-interactive)?
- IP
  - $\mathcal{P}$ sends $m_0$ to $\mathcal{V}$, $\mathcal{V}$ sends $(m_1 \leftarrow M_i(m_i))$ to $\mathcal{P}$ i.e $\mathcal{V}$'s response is application of non-deterministic algorithm (random in variable $M$)
  - What if $\mathcal{P}$ posted trace w/ random evaluations? How to determine that each random value is not dependent upon previous ones chosen by $\mathcal{P}$, if $\mathcal{P}$ knows set of random values.. they can construct solutions before-hand and post incorrect traces
- example
  - Let $\mathcal{P}$ be a dis-honest prover, and $s$ be the correct poly. that should be agreed on. If $\mathcal{P}$ knows what $r_1$ should be, then $\mathcal{P}$ can send, $g$, where $C = g_1(0) + g_1(1)$, where $g_1(r_1) = s_1(r_1)$
- Fiat-Shamir Transform
  - hash-chaining - Every random-oracle output is derived from the $\mathcal{P}$ input from prev. round (which is determined from randomness from prev. round recursively)
    - i.e $r_1 = R(i, x, r_{i - 1}, g_{i - 1})$ -> value at $r_i$ uniquely determined by input, prev. randomness, and response from $\mathcal{P}$ to randomness from prev. round
      - I.e prevents $\mathcal{P}$ from guessing forward, and back-propagate to acct. for randomness
- adaptive-soundness - Security against $\mathcal{P}$ that can choose input to first round (GKR (out-puts of circuit))
Computer Programs -> Circuits
- Given computer program -> turn into arithmetic circuit -> delegate execution via NIP (GKR w/ hash-chaining)
- Machine Code
  - Random Access Machine -
    - $s$ cells of memory, where each cell stores $64$-bits of memory
      - Can only store data
    - $r$ number of registers, i.e instructions can perform operations on these
    - $l$ instructions, the set of operations that can be performed on registers
- Circuit Satisfiability Problem
  - circuit evaluation - Given $\mathcal{C}$ (circuit), and $x$ (input), and $y$ (output), prove that $\mathcal{C}(x) = y$
  - circuit satisfaction - $\mathcal{C}$ takes two inputs, $x$ (input), $w$ (witness). Given $\mathcal{C}$, $x$ (input), $y$ (output), prove whether $\exists w, \mathcal{C}(x, w) = y$
    - Sometimes proof that $w$ exists is not enough
    - knowledge soundness - Prover also proves that it knows a $w$
  - Given $\mathcal{C}$, takes two inputs, $x$ (input) $w$ (witness), determine whether $\mathcal{C}(x, w) = y$ (outputs)
    - problem - Given $\mathcal{C}$, $x, y$, determine whether or not there exists a witness $w$, such that $\mathcal{C}(x, w) = y$
  - More expressive than circuit evaluation
  - intuition
    - CE - Given some machine $M$ find a proof that $M(x) = y$
    - CS - Prove that some proof $w$ exists that $M(x) = y$, and show that $M'(x, w) = y$ (show that proof exists, and is correct)
      - Intuitively, knowing that a proof exists, and checking the proof is easier than finding it
  - example
    - Suppose $\mathcal{C}$ is a circuit that evaluates an arithmetic expression over $\mathbb{F}_q$, including $*, +, /$, notice $a / b$ is represented as $ab^{-1}$
      - In arithmetic circuit for $\mathcal{C}$, gates are only +, *, this $\mathcal{C}$ for each divison $a / b$, has to be replaced w/ circuit finding $b^{-1}$ (complex)
    - Instead treat $\mathcal{C}'$ (CSAT) circuit, where witness $w = (e_1, \cdots, e_n)$, where $e_1$ corresponds to the $b^{-1}$ for each $b$ involved in a division $a / b$
    - Now circuit is j multiplication + addition (much less deep), but wider by $len(w)$, for each $e_i$, have a check that $e_i * b_i = 1$
  - Succint Arguments
    - $\mathcal{P}$ sends $w$ to $\mathcal{V}$, then $\mathcal{P}, \mathcal{V}$, evaluate GKR on $\mathcal{C}(x, w)$
      - Instead of sending $w$ in full, send $commit(w)$ to $\mathcal{V}$, and have $\mathcal{P}$ open commitment at random points
      - Final step of GKR requires evaluation of $\tilde{u}$ (MLE of $(x, w)$)
- Transformation (Circuit -> CSAT)
  - Able to transform program in RAM that runs in $T$ time-steps, and uses $s$ memory cells into $log(T)$ depth, and width $T$
  - high-level
    - Specify trace of RAM $M$, i.e $T$ steps, where each step has values of each register in computation ($O(1)$) registers
  - details
    - $\mathcal{C}$ takes transcript of execution of $M$ on $x$ as input, transcript represented as follows
      - list of tuples $(t, m_1, \cdots, m_r, a_t)$
        
        $t$ is the current time-step of the machine
        
        $m_i$ are the values of the registers of the machine
        
        $a_t = (loc, val)$ - $a_t$ is meta-data abt the memory operation perfomed at $t$ (if any)
        
        $loc$ is memory location read / written to
        
        $val$ - is value read / value written
    - Checks
      - Must check that values in memory are read / written to correctly (memory-consistency)
        
        I.e value read is the latest value written
      - (Assuming memory-consistency) Must check that $(t, m_1, \cdots, m_r, a_t) \rightarrow (t + 1, m'_1, \cdots, m'r, a{t + 1})$ follow correctly from state-transition defined by $\mathcal{C}$ (time-consistency)
        
        What is instruction is LDUR? BC of memory-operation we can check that this value resulted from last write
    - Circuit construction
      - Represent transition function, as a small circuit that takes $l(i)$ (i.e $i$-th element of list), and checks that $l(i + 1)$ follows correctly (time-consistency)
      - memory-consistency - Order $l(i)$ according to $a_i.loc$, and time, check that for each read $a_t.val = a_{t'}.val$ where $t'$ is the latest time-step at which a write occurred to $a_t.loc$
  - Representing Transition Function
    - For each time-step, have a selector (which instruction $l(t)$) is being executed
    - From there represent configuration at $t$, $C(t)$, as inputs to sub-circuit, and apply instruction sub-circuit on relevant inputs
      - Notice, application of sub-circuit for instruction has size $poly(W)$
  - Representing Memory Consistency
    - Sorting?
      - Revisit
Succint Arguments
- Arguments of Knowledge + SNARKs
  - knowledge-soundness
    - $\mathcal{P}$ establishes that $\exists w, \mathcal{C}(x, w) = y$ exists, and that $\mathcal{P}$ knows such a $w$
  - SNARK - Succint, non-interactive, argument of knowledge
    - I.e knowledge-sound argument for arithmetic circuit-satisifiability
- First Argument
  - polynomial commitment - Prover commits to a poly. $\tilde{w}$, and later can open to any evaluation of the poly. $\tilde{w}$
  - High-level
    - $\mathcal{P}$ sends commitment $\tilde{w}$ to $\mathcal{V}$ at beginning of the protocol, and executes GKR on $\mathcal{C}(x, w)$
  - What does GKR need to know abt $w$
    - Let $w, x \in {0,1}^n$, can reprsent input $z = x | w$, can construct $\tilde{z}(r_0, \cdots, r_{log(n)}) = (1 - r_0)\tilde{x}(r_1, \cdots, r_{logn}) + r_0 \tilde{w}(r_1, \cdots, r_{logn})$
    - $\mathcal{P}$ only has to open commitment to $\tilde{w}$ at $r_1, \cdots, r_{logn}$
- What does $\mathcal{V}$ need to know about $\tilde{w}$
  - Notice, final round of $\mathcal{V}$ evaluating GKR on $\mathcal{C}(x, w) = y$
  - Let $z = w | x$, where $len(x) = len(w) = n$, then $degree(\tilde{z}) = 2^{1 + log(n)}$
    - Where $\tilde{z}(r_0, \cdots, r_{log(n)}) = (1 - r_0)\tilde{x}(r_1, \cdots, r_{log(n)}) + r_0 \tilde{w}(r_1, \cdots, r_{log(n)})$
- Knowledge Soundness
  - witness extraction If $\mathcal{P}$ convinces $\mathcal{V}$ of $\exists w, \mathcal{C}(x, w) = y$, then there exists an efficient $\mathcal{E}$, w/ rewinding access to $\mathcal{P}$ can extract a $w$ satisfying CS
  - extractability of poly. commits
    - commitment scheme, where if $\mathcal{V}$ is able to rewind $\mathcal{P}$'s poly. commit, then it can extract $p$ (i.e $\mathcal{P}$ certainly knows a $p$ from the commitment)
Low Degree Tests
- Form of poly. commitment
  - Not exactly, only works for low-degree MV poly.
- Given $\mathcal{O}$ (oracle), which gives evaluation of poly. at specified point
- The LDT guarantees that the commitment has low Hamming-Degree distance from specified poly. $p$
  - i.e $s, p$ agree on $\lambda$ (fraction) of all points
- Example given $s$, commitment to some $p : \mathbb{F}^k \rightarrow \mathbb{F}$, take $l : \mathbb{F}^k \rightarrow \mathbb{F}$ (line), and check that $s(l) = p(l)$
MIPs / Succint Arguments
- protocol - Involves $k$-provers, $\mathcal{P}_i$, and $\mathcal{V}$ (PPT-verifier)
  - Transcript defined analogously $t = (\mathcal{V}(r), \mathcal{P}_1, \cdots, \mathcal{P}_k)$
    - $\mathcal{P}_i$ have no interaction w/ each other -> otherwise $MIP = IP$
- Second Prover?
  - non-adaptivity - $\mathcal{P}_1$'s response to $\mathcal{V}(r)_i$ (message from $\mathcal{V}$ at $i$), cannot depend on $\mathcal{P}_i$'s prev. answers, as $\mathcal{V}$ could have also sent diff. messages to $\mathcal{P}_2$
  - analog is prisoners being interrogated
    - prisoner's dilemma if any of the other provers are truthful, the other lying provers can be detected
  - Let $\mathcal{L}$ be language, $M$ PPT oracle TM for $\mathcal{L}$. Let $M^{\mathcal{O}}$ be the $M$ when given access to $\mathcal{O}$. Suppose if $x \in \mathcal{L}$, $\exists \mathcal{O}, where Pr[M^{\mathcal{O}}(x) = 1] = 1$, and for $x \not \in \mathcal{L}$, $\forall \mathcal{O}, Pr[M^{\mathcal{O}}(x) = 1] < 1/3$. Then there is 2-prover MIP for $M$
    - proof
      - idea - Construct 2-prover MIP w/ perfect completeness, and high-soundness, then repeat protocol
      - 2-prover MIP
        
        $\mathcal{V}$ executes $M^{\mathcal{O}}(x)$, and for each $\mathcal{O}(q)$, $\mathcal{V}$ posits query to $\mathcal{P}_1$, for value
        
        Final round, $\mathcal{V}$ poses random query to $\mathcal{P}_2$, and cross-verifies w/ $\mathcal{P}_1$'s answer
        
        perfect completeness
        
        Triv, $\mathcal{P}$, $\mathcal{P}_2$ j respond w/ $\mathcal{O}$
        
        soundness
        
        If $x \not \in \mathcal{L}$, and $\mathcal{P}$ responds w/ any $\mathcal{O}$, then $Pr[\mathcal{V} reject] \geq 2/3$, otherwise, if $\mathcal{P}_1$ responds w/ diff $\mathcal{O}'(q)$, prob of $\mathcal{V}$ asking
    - intuition
      - $\mathcal{P}_2$ is treated as oracle
        
        Only asked 1 query, w/ no-communication elsewhere, thus must return some random value $\mathcal{O}$
      - If $\mathcal{P}_1$ acts adaptively (i.e not as an oracle / circuit), then $\mathcal{P}_2$ will disagree
  - Why non-adaptivity
    - Buys succinctness for NP statements
      - Analogous to protocol for evaluating $\mathcal{C}(x, w) = y$, where $\mathcal{P}$ commits to $\tilde{w}$, and $\mathcal{V}$ executes GKR on $\mathcal{C}$
  - MIP for C-SAT
    - warmup
      - intuition - Use $\mathcal{P}_2$ to function as poly. commit, i.e $\mathcal{P}_2$ functions to make $\mathcal{P}_1$'s response non-adaptive
      - I.e use $\mathcal{P}_2$ to perform a low-degree test of $\tilde{w}$ to ensure that $\mathcal{P}_1$'s response of $\tilde{w}(r)$ was correct
    - protocol
      - summary
        
        Let $\mathcal{C}(x, w)$ be C-SAT over $\mathbb{F}$, let $S = 2^k$ be the # of gates in $\mathcal{C}$
        
        Let $W : {0,1}^k \rightarrow \mathbb{F}$ be a transcript for $\mathcal{C}$ (i.e description of execuction) where $W(b)$, is the $b-th$ gate assignment
        
        Let $W$ be the witness for $\mathcal{C}(x) = y$
      - overview
        
        $\mathcal{P}_1$ claims to hold $Z = \tilde{W}$ for ${\mathcal{C}, x, y}$
        
        Identify $g_{x, y, Z}: \mathbb{F}^{3k} \rightarrow \mathbb{F}$, where $\Sigma_{a,b,c \in {0,1}^k} g_{x, y, Z}(a, b, c) = 0 \iff Z = \tilde{W}$
        
        i.e apply SC to $g_{x, y, Z}$
      - Comparison to GKR
        
        GKR executes sum-check for each layer of circuit
        
        Prover only making claim about input alone
        
        Verifier does not execute circuit, does not have access to information abt. intermediate gates (in single prover)
        
        Verifier does not a-priori know the gates of the circuit (CE)
        
        MIP executes GKR on all gates at once, how?
        
        Proof of CS, take witness as intermediate gates in execution of circuit
        
        $\mathcal{V}$ has access to multiple provers, can prod other provers for info abt the intermediate gates
        
        Can get the same benefit by having prover commit to transcript, and reveal evaluations later (non-adaptivity)
      - details
        
        $add, mult: {0,1}^{3k} \rightarrow {0,1}$ - functions where $add(a, b, c) = 1$, if $a$ adds $b, c$
        
        $io : {0,1}^{3k} \rightarrow{0,1}$, where $io(a, b, c) = 1$ if $a$ is input and $b = c = 0$, or $a$ is output, and $b, v$ are children of $a$
        
        $I_{x, y} : {0,1} \rightarrow \mathbb{F}$, where $I_{x,y}(a) = x_a$ or $I_{x, y}(a) = y_a$
      - Construction of $G_{x, y, W}(a, b, c) : {0,1}^{3k} \rightarrow \mathbb{F}$, where $\forall a,b,c, G_{x, y, W}(a, b, c) = 0 \iff W = \mathcal{C, x, y}$
        
        $G_{x, y, W}(a,b,c) = io(a, b, c)(I(x, y)(a) - W(a)) + add(a, b, c)(W(a) - (W(b) + W(c))) + mult(a, b, c)(W(a) - W(b)W(c))$
        
        Then for $Z$ (a proposed mLE of $W$), $g_{x, y, Z}(a, b, c) = \tilde{io}(a, b, c)(\tilde{I}(x, y)(a) - Z(a)) + \tilde{add}(a, b, c)(Z(a) - (Z(b) + Z(c))) + \tilde{mult}(a, b, c)(Z(a) - Z(b)Z(c))$
      - Construction of $h_{x, y, Z}$, where $\Sigma_{a, b, c \in {0,1}^k} h_{x, y, Z}(a, b, c) = 0 \iff \forall a, b, c g_{x, y, Z}(a, b, c) = 0$
  - Succint Argument For Deep Circuits
    - Polynomial commit schemes are bottleneck for prover + verifier
    - MIP argument, takes transcript as witness, and only requires evaluation of SC on witness based poly.
    - GKR linear in depth
  - Circuit-SAT -> R1CS-SAT
    - Arithmetic circuit satisfiability -> Form of intermediate representation
    - R1CS -> also form of intermediate representation
    - R1CS
      - Set of $A, B, C \in Mat(\mathbb{F}, n)$, is satisfiable if $\exists, z \in \mathbb{F}^n, (A\cdot z) \odot (B \cdot z) = C \cdot z$ ($z$ is witness)
        
        $\odot$ is pair-wise multiplication of entries in vector (Hadamard product)
        
        rank-1-constraint - Denote $A_i$ as the $i$-th row of $A$, then $\langle A_i, z \rangle \langle B_i, z\rangle = \langle C_i, z \rangle$
        
        rank-1 - Operation only involves single multiplications + additions
    - Any instance of ACS -> R1CS
    - relationship
      - #of rows / columns in $A/B/C$ is ~ #of gates in $\mathcal{C}$ (ACS for a circuit)
      - #of non-zero entries in $A/B/C$ bound-above by fan-in of circuit (matrices are sparse)
      - transformation
        
        Let ${\mathcal{C}, x, y}$ be ACS, and $\mathcal{P}$ wants to convice $\mathcal{V}$ $\exists w, \mathcal{C}(x, w) = y$
        
        Let $N$ be the #of gates of $\mathcal{C}$ (excluding at depth 0) + $len(w) + len(x)$, i.e $a \in \mathbb{F}^N$ (contains gates + x + w)
        
        constraints
        
        One for each non-input / output gate, 2 for each output gate, thus matrices are $M \times (N + 1)$ (witness length is $N + 1$), and $M = N + y - w$
        
        How to construct $z$, $A, B, C$ s.t $(A \cdot z) \odot (B \cdot z) = (C \cdot z)$, $z$ iff $\exists w, \mathcal{C}(x, w) = y$?
        
        Each entry in $z$ represents either $x_i, w_i$ or a gate in circuit, first entry $z_1 = 1$
        
        inputs - For $j$-th entry in $z$ ($z_j$), corresponding to $x_i$, constraint is that $z_j = x_i$, i.e j-th row of $A$ is $e_1$, j-th row of $B$ is $e_j$, and j-th row of $C$ is $x_i \cdot e_1$, thus $z_j - x_i = 0$
        
        outputs - Same is done for outputs, i.e for $z_j$ capturing $y_i$, capture $z_j - y_i = 0$
        
        addition gates
        
        For $z_j$ representing an addition gate between $z_{k}, z_m$ (either inputs or witness), capture $z_j - (z_k + z_m)$
        
        i.e $A_j = e_1$, $B_j = e_k + e_m$, $C_j = e_j$
        
        multiplication gates
        
        For $z_j$ representing multiplication gate between $z_k, z_m$ capture $z_j - z_k * z_m$
        
        $A_j = e_k$, $B_j = e_m$, $C_j = e_j$
    - MIP for R1CS-SAT
      - View matrices $A,B,C$, as $f_A, f_B, f_C : {0,1}^{log_2m}\times {0,1}^{log_2n} \rightarrow \mathbb{F}$, transcript viewed as $Z : \mathbb{F}^{log_2(n)} \rightarrow \mathbb{F}$, and, $\forall a \in {0,1}^{log_2m}$ (i.e for each constraint) $$g_{A, B, C, Z}(a) = (\Sigma_{b \in {0,1}^{log_2n}}\tilde{f_A}(a, b)Z(b)) \cdot (\Sigma_{b \in {0,1}^{log_2(n)}}\tilde{f_B}(a,b)Z(b)) - \Sigma_{b \in {0,1}^{log_2n}}\tilde{f_C}(a, b) Z(b) = 0$$
      - Polynomial above is $log_2(m)$ variate poly. , and sum over all inputs must be $0$
        
        Apply sum-check to the poly.?
        
        Slight modification - Must create $h_{A, B, C, Z}$ such that, $g_{A, B, C, Z}$ vanishes on ${0,1}^{log_2(m)}$ iff $\Sigma_{b \in {0,1}^{log_2(m)}} h_{A, B, C, Z} = 0$
PCPs and Succint Arguments
- IP - $\mathcal{P}$ asked questions by verifier, and $\mathcal{P}$ behaves adaptively
- PCP - proof is $\pi$, i.e static object, that has well-defined responses to each query $q_i$ asked by $\mathcal{V}$, answers are not dependent upon $q_j, j < i$
  - A PCP for $\mathcal{L}$, is $(\mathcal{V}, \pi, x)$, $\pi \in \Sigma^l$
    - completeness - For every $x \in \mathbb{L}$, there exists a $\pi \in \Sigma^l$, where $Pr[\mathcal{V}^{\pi} = 1] \geq 1 - \delta_c$
    - soundness - For every $x \not\in \mathcal{L}$ and each proof string $\pi \in \Sigma^l$, $Pr[\mathcal{V}^{\pi}(x) = 1] \leq \delta_s$
- MIP -> PCP
  - Suppose $\mathcal{L} \subset {0,1}^*$ has a $k$-prover MIP, where to each $\mathcal{P}_i$ $\mathcal{V}$ sends a single query of size $r_Q$, and response size of $r_A$, then the PCP has length $k * 2^{r_Q}$
    - I.e for each prover, PCP has to accomodate all possible queries that $\mathcal{V}$ could have sent. (NON-interactive?), i.e MIP $\mathcal{P}$ can act adaptively, and lessen problem space to set of questions that $\mathcal{V}$ has asked
    - Prover run-time increase significantly from MIP, verifier run-time is the same
- PCP -> succint argument?
  - I.e want to have a succint PCP for CS of ${\mathcal{C}, x, y}$
    - With GKR (IP), send PC of $\tilde{w}$, and evaluate GKR on $\mathcal{C}(x, w) = y$
  - Any PCP -> SA
    - Any PCP -> 4 message argument system for all of NP
    - Each communication step (Oracle samples), $O(log(n))$ hash values (merkle-proof?)
    - Applying FS, yields NIP in ROM
  - intuition
    - Prover makes $\pi$ (PCP), and forms merkle tree w/ leaves as evaluations of $\pi$ for all possible evaluations (i.e charaters of string) (COMMIT PHASE)
    - $\mathcal{V}$ simulates PCP-verifier, and requests evaluations from merkle tree at all specified evaluations from PCP-verification
    - completeness - Triv.
    - soundness - Rely on collision resistance, i.e intractable for prover to find collisions, thus if $\mathcal{P}$ sends $C(\pi)$ it is impossible to send $\pi'(q_i)$ for any $i$, unless $\pi'(q_i) = \pi(q_i)$
  - question
    - Commitment to $\pi$, $C(\pi)$ (if it is merkle VC), how to address LDT? For $\pi$
      - I.e $\mathcal{V}$ has no assurance that leaves are all / only evaluations of $\pi$? Choose random evaluation
  - Witness Extraction of PCP / Knowledge Soundness
    - As long as underlying PCP is KS, the FS + succinct PCP is also Knowledge sound, thus it is a SNARK
  - MIP -> PCP
    - Can transform MIP using SC over $h_{x, y, Z}$ (where $x, y$ is input/output, and $Z$ is MLE of transcript), into a PCP, where $\pi$ is set of all possible evaluations of $Z$ (restricted to line),
Interactive Oracle Proofs
- Messages sent from $\mathcal{P}$ are not read in full by $\mathcal{V}$
  - i.e leads to sub-linear time verifier strategies
- Polynomial IOPs
  - Let $m_i$ be a message from $\mathcal{P}$ that is not read in full by $\mathcal{V}$,
    - $m_i$ represented as string, and $\mathcal{O}$, oracle to give query access to symbols of $m_i$
  - In polynomial IOP, special messages (messages not fully processed by $\mathcal{V}$), represented as poly. $h_i$ over $\mathbb{F}$ w/ max degree $d_i$
    - Poly. usually uni-variate
    - Max degree generally large, For R1CS may be as large as $S$ (prefer to send commitment)
  - Steps for obtaining SNARK
    1. Design poly. IOP for circuit / R1CS-SAT
    2. Replace special messages w/ poly. commitment scheme
    3. Apply FS
  - IP / MIP as poly. IOP?
- Polynomial IOP for R1CS-SAT
  - Univariate Sum-Check
    - Results in constant rounds (as opposed to $O(log(n))$ rounds in MV-SC)
    - description
      - fact - Let $\mathbb{F}$ be finite field, and $H \subset \mathbb{F}$ a MG where $O(H) = n$, then $\Sigma_{a \in H} q(a) = q(0) * H$
        
        Notice, for $\Pi_{a \in H} (x - a) = X^n - 1$, coeff of $X^{n - 1}$ is $\Sigma_{a \in H} a = 0$
        
        Thus for $q(X) = X, \Sigma_{a \in H} q(a) = 0$
        
        Similarly, for $q(X) = X^m$ where $gcd(m, n) = 0$, let $\langle h \rangle = H \rightarrow \langle h^m \rangle = H$, then $\Sigma_{a \in H} q(a) = \Sigma_{a \in H} (h^m)^j = \Sigma_{a \in H} a = 0$
        
        For $q(X) = X^m$ where $gcd(m, n) =d$, $\langle h^m \rangle = H' \subset H$, i.e $h^m$ generates sub-grp of $H$, and $\Sigma_{a \in H}q(a) = (1 + h + h^2 + \cdots + h^d) \Sigma_{a \in H'}q(a) = 0$
        
        Thus for $q(a) = \Sigma_i q_i a^{i}$, $\Sigma_{a \in H} q(a) = \Sigma_i q_i\Sigma_{a \in H} a^i = \Sigma_{a \in H} q_0 = q(0)*H$
      - Let $\mathbb{Z}H(X) = \Pi{a \in H} (X - a)$ (poly vanishes on $H$)
      - $\Sigma_{a \in H} p(a) = 0 \iff p(X) = q(X)(X^n - 1) + X \cdot f(X)$
        
        Forward
        
        Triv
        
        Converse
        
        Triv
        
        Intuition, the same as proving that $p(0) = 0$, i.e $p(X)$ has no constant term
  - Problem
    - For USC, where $\Sigma_{a \in H} p(a) = 0$,
      - Problem of committing to $p(a) = 0$, is triv. prover j commits to some poly. where $q(0) = 0$, how to get around this?
    - Commit to $q(x), f(X)$ (above), and prove evaluations at some random point co-incide
  - Second Problem
    - Why not use MIP for R1CS? Requires $O(log(m)log(n))$ rounds, i.e for each constraint have to send $log(n)$-variate poly.
    - Instead, only send uni-variate poly. that results in constant rounds
  - description
    - Given $A, B, C$ R1CS instance, and $z$ (witness), let $\hat{z}$ be the uni-variate extension of $z$, $\hat{z_A}, \hat{z_B}, \hat{z_C}$ the analogous univariate extensions of $Az, Bz, Cz$
      - Thus $\forall h \in H, \hat{z_A}(h) \cdot \hat{Z_B}(h) = \hat{z_C}(h)$
        
        Then $\hat{z_A}\cdot \hat{z}_B - \hat{z}_C = h^*(X) \cdot \mathbb{Z}_H(X)$ ( apply schwartz-zippel and check eval at random)
      - $h \in H, M \in {A, B, C}, \hat{z_M}(h) = \Sigma_{j \in H}M_{h, j}\hat{z}(j)$
    - Checking $M \in {A, B, C}$, let $\hat{M}(X, Y)$ denote bi-variate MLE of $M$, thus $\hat{z}M(X) = \Sigma{j \in H}\hat{M}(X, j)\hat{z}(j)$
      - Then $q(Y) = \hat{M}(r', Y)\hat{z}(Y) - \hat{z}M(r')O(H)^{-1}$, $\Sigma{X \in H}q(X) = 0$
        
        Apply univariate sum-check (constant number of rounds)
    - $\mathcal{V}$ has to compute $\hat{M}(r', r'')$ (is this hard?)
- FRI poly commit
ZK via Commit And Prove
Zero-Knowledge Proofs and Arguments
- Verifier learns nothing from $\mathcal{P}$ apart from validity of statement being proven
  - Existence of simulator - Given inputs to be proved, produces distribution over transcripts indistinguishable from the distribution over transcripts produced when $\mathcal{V}$ interacts with honest prover
- Let $\mathcal{P}$, $\mathcal{V}$ be a PS, then it is zero-knowledge if $\forall, \hat{\mathcal{V}}$ (poly. time verifier), there exists a PPT $S$, where $\forall x \in \mathcal{L}$, the distribution of the output $S(x)$ is indistinguishable from $View(\mathcal{P}(x), \hat{\mathcal{V}}(x))$ (distribution of all transcripts from execution of $\mathcal{P}, \mathcal{V}$)
  - perfect zero-knowledge - $S(X), View_{\hat{\mathcal{V}}}(\mathcal{P}(x), \hat{\mathcal{V}}(x))$ are the same (transcripts determined by randomness from $\mathcal{V}$)
  - statistical zero-knowledge - the statistical distance is negligible, i.e $1/2 \Sigma_{m \in \mathcal{M}}|Pr[S(x) = m] - Pr[View_{\hat{\mathcal{V}}}(x) = m]|$
    - i.e given a poly. number of samples from $\mathcal{L}$, the verifier is unable to determine if the distributions are diff.
  - computational zero knowledge - statistical distance can also be defined as max. over all algorithms $\mathcal{A} : D\rightarrow {0,1}$ ($D$ is random variable), then $|Pr_{y \leftarrow D_1}[\mathcal{A}(y) = 1] - Pr_{y \leftarrow D_2}[\mathcal{A}(y) = 1]|$
- honest v. dishonest verifier zero-knowledge
  - Above definition, requires existence of simulator for all verifiers $\hat{\mathcal{V}}$ (even malicious verifiers)
  - Can also have honest verifier, i.e works for prescribed verifier strategy
- plain zero-knowledge v. auxiliary input zero-knowledge
  - If $\hat{\mathcal{V}}$ is dis-honest, and may return responses to $\mathcal{P}$ according to some auxiliary input $x$, and a simulator exists $S(x, z)$ (for auxiliary input $z$), then the protocol is satisfies auxiliary zero-knowledge
  - Distinction of plain v. auxiliary irrelevant after applying fiat-shamir transform
- Graph Non-Isomorphism Proof
  - graph isomorphism - Let $G_1, G_2$ be graphs, and $\pi : V_1 \rightarrow V_2$, then $G_1 \cong G_2 \iff (e_1 = (v_1, v_2) \in E_1 \iff e_1' = (\pi(v_1), \pi(v_2)) \in E_2)$
  - protocol
    - $\mathcal{P}, \mathcal{V}$ begin with $G_1, G_2$
    - Round 1: $\mathcal{V}$ randomly chooses permutation $\pi : {1, \cdots, n} \rightarrow {1, \cdots, n}$ and $b \in {1, 2}$, and sends $\pi(G_b)$ to $\mathcal{P}$
      - Notice $\pi(G_b) \cong G_b$, thus $\mathcal{P}$ if $G_1 \not \cong G_2$ can efficiently determine which of $G_1, G_2$, $G_b$ is isomorphic to
      - Otherwise, if $G_1 \cong G_2$, then $\mathcal{P}$ cannot determine what $G_b$ is, and has $1/2$ chance at guessing
    - Two cases
      - Fix $\hat{\mathcal{V}}$, and $S(x)$ which on graph non-isomprphism correctly sends $b$ to verifier
      - On iso-morphism, randomly sends $b'$ back to $\mathcal{V}$ (using same distribution as $\mathcal{P}$)
  - Not zero-knowledge against dis-honest verifiers
    - $\hat{\mathcal{V}}$ can know that $H \cong G_1 \lor H \cong G_2$, and can send $H$ to $\mathcal{P}$ + random $G_b$ depending on response from $\mathcal{P}$, can learn which $H$ is IM to.
- Additional Intuition
  - Given axioms + inference rules, and $x$ input, a proof is $\pi = (x, m_0, \cdots, m_n)$, where each $m_i$ is derived from $x \cup_{j < i} m_j$
  - soundness - Can't prove incorrect statements (i.e $x \not \in \mathcal{L}$, but $\mathcal{P}$ convinces $\mathcal{V}$ that $x \in \mathcal{L}$)
  - completeness - If $x \in \mathcal{L}$, $\mathcal{P}$ can prove this to any $\mathcal{V}$
- Quadratic Residue proof
  - $\mathcal{P}$ + $\mathcal{V}$ know $x \in \mathbb{Z}^_p$, $\mathcal{P}$ knows $s \in \mathbb{Z}^_p$ where $x \equiv s^2 (p)$ (quadratic residue)
  - Round 1. $\mathcal{P}$ sends $r \leftarrow \mathbb{Z}^*_p, r^2$ to $\mathcal{V}$, $\mathcal{V}$ sends $b \leftarrow {0,1}$
  - Round 2. if $b = 0$, $\mathcal{P}$ sends $r$, otherwise $rs$, then $\mathcal{V}$ performs the following check, $z = x^br^2 = p$, where $p$ is the value sent from $\mathcal{P}$
  - intuition
    - soundness - Less than $1/2$ (can be increased by repeating experiment)
      - The case where $\mathcal{P}$ is acting correctly naturally satisfies the above.
      - Suppose $x \not\in QR_n$, and $\hat{\mathcal{P}}$ is not acting according to the protocol
        
        If $u^2 = y \in QR_n$ (value sent to $\mathcal{V}$ in round 1.), then if $b = 1$ (prob 1/2), then then if $z^2 = xu^2$, then $(zu^{-1})^2 = x$ (contradiction), so the prover fails
        
        If $y \not \in QR_n$, then with prob. $1/2$, $b = 0$, and the prover obv. fails
    - completeness - Triv.
  - Is it zero-knowledge? How to properly define the simulator?
    - $S(x)$ defined as follows
      - Fix $b' \leftarrow {0,1}$, $r \leftarrow \mathbb{Z}_m^*$
      - if $b' = 0$, then $x' = r^2$
Schnorr's $\Sigma$-Protocol for knowledge of DLog
- Schnorr Identification Protocol
- Solve
  - Prover has knowledge of Dlog of grp. element
  - Prover commits to group element w/o revealing grp. element to verifier
- Consider set of relations $\mathcal{R}$, where $(h,w) \in \mathcal{R}$ specify set of instance-witness pairs
  - Example, given $\langle g \rangle = \mathbb{G}$, then $\mathcal{R}_{DL}(\mathbb{G}, g)$ is the set of $(h,w)$, where $h = g^w$
- $\Sigma$-protocol for $\mathcal{R}$ is a 3-message PC protocol, where $\mathcal{P}, \mathcal{V}$ know $h$ (public input), and $\mathcal{P}$ knows $w, (h,w) \in \mathcal{R}$
  - Protocol consists of 3-messages, $(a, e, z)$
  - Perfect completeness
- special soundness - There exists PPT $\mathcal{Q}$, where when given $(a, e, z)$, and $(a, e', z')$ (accepting transcripts), where $e \not= e'$, $\mathcal{Q}$ outputs, $(h,w) \in \mathcal{R}$
  - Useful for witness extraction (proving knowledge-soundness)
- attempt protocol
  - $\mathcal{R}_{DL} = {(h,w) : h = g^w}$
  - $\mathcal{P}, \mathcal{V}$ know $h, g$, $\mathcal{P}$ hold $(h,w)$
  - Attempt (not, specially sound)
    - $\mathcal{P}$, chooses $a \in \mathbb{G}, a = g^r, r \in {0, \cdots, n -1}$, and $z = (w + r)$
    - $\mathcal{V}$ checks that $ha = g^z$
    - Complete
    - Zero-knowledge
      - Take $S(h)$, where $z$ is randomly chosen, and $a = g^zh^{-1}$, i.e $S$ does not have to know $w$, but can still output $(a, z)$ which are randomly distributed ($z$ has same dist. as $a$)
    - For above reason not sound, take $P^* = S(h)$
- protocol
  - $\mathcal{P}$ sends $a = g^r, r \leftarrow^R {0, \cdots, n - 1}$ to $\mathcal{V}$
  - $\mathcal{V}$ sends $e \leftarrow^R {0, \cdots, n - 1}$ to $\mathcal{P}$
  - $\mathcal{P}$ sends $z =(ew + r)$ to $\mathcal{V}$ checks that $ah^e = g^{z}$
- Completeness - triv.
- Soundness
  - Let $(a, e, z), (a, e', z')$ be two accepting transcripts, then $w = \frac{z - z'}{e - e'}$
- Zero-knowledge -
  - Have to fix poly. time simulator $S$, where $e, z \leftarrow {0,\cdots, n - 1}$, and $a = g^z(h^e)^{-1}$
Fiat-Shamir in $\Sigma$-protocols
- If $(a, e, z)$ is the transcript from a $\Sigma$-P $\mathcal{I}$, and $\mathcal{Q}$ be the NI argument obtained from applying FS, where $e = R(h, a)$
  - Notice, by special-soundness, a witness $w$ can be obtained from $\mathcal{Q}$ by executing twice, contradicting intractibility of $\mathcal{R}$
- Creating argument of knowledge from $\Sigma$-Protocol via FS
Commitment Schemes
- Two parties, $\mathcal{P}$ (comitter), $\mathcal{V}$ (verifier)
- binding - Once $\mathcal{P}$ sends $\mathcal{C}(m)$, $\mathcal{P}$ cannot open the commitment to anything else, i.e $\mathcal{C}(m_1) \not= \mathcal{C}(m_2)$
- hiding - $\mathcal{C}(m)$ shld not reveal any information abt. $m$
- Composed of algs. KeyGen, Commit, Verify
  - KeyGen -> $(ck, vk)$, where $vk$ is the public verification key
  - $c = Commit(m, ck)$
  - $Verify(vk, Commit(m, ck), m') = 1 \iff m = m'$ (can also come in statistical / computational flavors), i.e $Pr[A|m \not= m'] \leq negl$
- Commitment Scheme From Sigma Protocol
  - hard relation - Let $\mathcal{R}$ be a relation, then it is hard if for $(h, w) \in \mathcal{R}$, is output by an efficient randomized algo., then no poly. algo. exists that when given $h$, can output $(h, w') \in \mathcal{R}$ (except w/ negl. prob.)
    - I.e no efficient algo. for identifying witness $w$ for instance $h$, wher $(h, w) \in \mathcal{R}$
    - Example, let $\mathbb{G}$ be a finitely generated group w/ order $p$ (prime), and $\mathcal{R}_g = {(h, r): h = g^r}, \langle g \rangle = \mathbb{G}$ (assume DLOG)
  - $\Sigma$-protocol for hard-relation can be used to obtain perfectly hiding, computationally binding commitment scheme
  - Damgard
    - Retrieve CS from schnorr $\Sigma$-protocol
    - $(h,w) \leftarrow Gen$, $ck = vk = h$, i,e $h = g^w$
      - $w$ is considered toxic-waste (i.e must be removed otherwise, binding is not satisfied)
      - Construction of SRS?
    - To commit to $m$
      - Committer runs simulator to obtain $S(h, m) = (a, m, z)$, send $a$ as commitment
        
        Notice $S$ (simulator) is specially-HVZK, i.e can also take $m$ (challenge) and generate indistinguishable challenges
    - Verification
      - Send $m, z$, verifier runs $\Sigma$ on $(a, m, z)$
        
        Notice, $S(h, m) = (a, m, z)$, where $z \leftarrow^{R} \mathbb{G}$, i.e $a = (h^m)^{-1}g^z$
    - pederson commitments
      - Apply Damgard trans. to Schnorr $\Sigma$ protocol (common params are $\langle g \rangle = \mathbb{G}, \langle h \rangle = \mathbb{G}$)
      - $\mathcal{P}$ wants to commit to $m$, $\mathcal{C} = g^m h^z$ (notice, $g^m$ is also a hiding / binding commitment, $z$ is essentially salt)
      - $\mathcal{P}$ opens via $(m,z)$
  - Properties
    - Perfectly hiding
      - Commitment $a$ is independent from $m$ (challenge)
    - Correctness
    - Computational Binding
      - Special soundness of $\Sigma$, implies that if $(a, m', z'), (a, m, z) \in \mathcal{R}$, then witness extraction is poly. time computable hardness of $\mathcal{R}$ is violated
  - $(h, _)$ (cvk, vrk) can be generated transparently, as long as generator $h$ is chosen, choose $h' \leftarrow^{R} \mathbb{G}$, and no toxic waste exists
- pederson commitments
  - Additively HM
    - I.e for $m_1, m_2$, where $c(m_1) = (a_1, m_1, z_1)$, and $a_1 = g^{z_1}h^{-m_1}$
      - $c(m_1 + m_2) = a_1a_2 = g^{z_1}h^{-m_1}g^{z_2}h^{-m_2}$
  - how to make PC hide the message? (HVZK)
    - In above protocol $m$ is revealed in opening info... how to open commitment $c$ without revealing $m$?
      - Even better, prove knowledge of opening (but don't open commitment)
    - Goal- $\mathcal{P}$ proves to $\mathcal{V}$, that it knows $m, z$, where $c = g^mh^{z} = Com(m, z)$
    - protocol (notice this is the opening procedure for $\mathcal{C} = PC(m, z) = g^m h^z$)
      - $\mathcal{P}$, $d, r \leftarrow^{R} \mathbb{Z}$, sends $a = g^dh^r = Com(d, r)$
      - $\mathcal{V}$ sends $e \leftarrow \mathbb{Z}$ to $\mathcal{P}$
      - $\mathcal{P}$ sends $(me + d, ze + r)$, and $g^{me + d}h^{ze + r} = (g^mh^z)^e a = c^ea$
Masking Polynomials
- commit and prove
  - $\mathcal{P}, \mathcal{V}$ want to agree on $\mathcal{C}(x, w) = 1$, then $\mathcal{P}$ can commit to $Com(w)$ to $\mathcal{V}$, execute $\mathcal{C}(x, w) = 1$
    - $\mathcal{P}$ sends PCs to all $w_i$, and for each multiplication gate in $\mathcal{C}_x$
      - Round 1. Use HVZK opening of $w_i$ to prove opening
      - Round 2. For height $h$, take comms from $h - 1$ if addition add comms, if mult. $\mathcal{P}$ sends comms
      - Final round, use schnorr for ZK knowledge of PC to $y$
- Adaptations (ZK via Masking Poly.)
  - How to reduce number of commitments to be sub-linear in witness size + multiplicative
    - Commit to $\tilde{w}$ using extractable poly. commitment (FRI, bulletproofs, KZG, etc.)
  - ZK sum-check
Poly Commitments from KZG
- Bilinear pairings
  - Not all curves (grps.) on which the DLP is hard have efficiently computable bilinear pairings defined over them
  - Grp. operations in pairing friendly grps. tend to be slower
- DDH (Decisional Diffie Helman) - Given $\langle g \rangle = \mathbb{G}$, and $g^a, g^b$ it is hard to determine $g^{ab}$
- KZG
  - Let $e : \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}^t$ be BP, $o(\mathbb{G}) = p$ (prime), and $g \in \mathbb{G}$
  - structured reference string - Let $\tau \in \mathbb{F}_p$ (toxic waste), srs is $g^{\tau}, g^{\tau^2}, \cdots, g^{\tau^D}$ ($D$ is max deg. of poly. committed to)
    - $\tau$ is toxic waste, i.e if $\tau$ is exposed, binding is broken
  - To commit to poly. $q = \Sigma_i a_i x^i$, send $g^{q(\tau)} = \Pi_i (g^{\tau^i})^{a_i}$ (computable via composition of SRS elements)
    - Suppose $q(v) = z$, then $q(x) - z$ has a root at $v$, then $(X - v) | q(X) - z$, and $w(X)(X - v) = q(X) - z$, and $w(\tau)(\tau - v) = q(\tau) - z$ (notice prob. of finding root is $n / \mathbb{F}$)
    - $\mathcal{P}$ sends $g^{w(\tau)}$, $\mathcal{V}$, checks that $e(cg^{-z}, g) = e(g^{q(\tau) - z}, g) = e(y, g^\tau g^{-v}) = e(g^{w(\tau)}, g^{\tau - v})$
  - binding
    - Suppose $q(v) \not= z$, then $w(X) = \frac{q(X) - z}{X - v}$ is not poly. rather rational fn. $w(X) = q'(X)/(X - v)$ (how to compute given only SRS?), i.e need to send $g^{(q(tau) - z) / \tau - v}$
    - Given $\tau$, it is easy to compute ${(\tau - z)^{-1}}$, and then send $c = g^{(q(\tau) - z)^{(\tau - z)^{-1}}}$
    - If $c$ is KZG commitment to $q$, that can be opened to $v, v', v \not = v'$, then SDH is violated
    - intuition
      - binding - If $\mathcal{P}$ can open $\mathcal{C}(q)$ to $v, v', v \not = v'$, SDH is violated
        
        that is, $\mathcal{P}$ sent $w(\tau)$, $w'(\tau), q(\tau) - v' = w(\tau)(\tau - z)$, and $q(\tau) - v = w'(\tau) (\tau - z)$, thus $\mathcal{P}$ can solve for $\tau - z$
- Knowledge Extraction
  - Polynomial Knowledge Extraction
    - Intuitive - For every $\mathcal{P}$ that succesfully answers challenges from $\mathcal{V}$, $\mathcal{P}$ must know a satisfactory poly.
    - formal - There exists $\mathcal{A}$ (efficient adversary) that can extract a $p$ from $c$, that satisfies all openings of $c$ (evaluations)
      - Have to show construction of $p$?
      - Rewinding access?
    - binding - Only shows that openings are unique for queries, how to show that openings are evaluations of poly?
  - first attempt
    - Modify SRS by $(g,g^{\alpha}, g^{\tau}, g^{\alpha \tau}, \cdots, g^{\tau^d}, g^{\alpha \tau^d})$, where $\tau, \alpha \leftarrow \mathbb{F}_p$
    - PKOE (Power Knowledge of Exponent)
      - Let $\mathcal{A}$ be a ppt alg. given access to SRS (modified SRS above), that outputs $g_1, g_2 \in \mathbb{G}$, where $g_1 = g_2^{\alpha}$
      - Then it must be the case that $\mathcal{A}$ constructed $g_1 = \Pi (g^{\tau_i})^{c_i}$, thus $g_2 = \Pi_i (g^{\tau_i})^{\alpha c_i}$
        
        Algo. must know $c_i$ to satisfy relation
        
        I.e no efficient prover can retrieve $\alpha$ from SRS (thus only way to construct elements w/ given relation is thru SRS)
    - protocol
      - KZG commitment is $(U = g^{q(\tau)}, V = g^{\alpha q(\tau)})$, same check as above for opening w/ $w(\tau), z$, and additional check that $e(U, g^{\alpha}) = e(g, V)$
    - How is it extractable?
      - Guarantees that $U$ is composition of SRS (which are exponents), must be linear, thus it is a poly. :)
    - Extractor
      - Given $U, V, U^{\alpha} = V$, there must be $c_i$, such that $U = \Pi_i (g^{\tau_i})^{c_i}$, thus extract $p(X) = \Sigma_i c_i X^i$
    - Non-falsifiable
      - Given $(g_1, g_2)$, how can challenger verify that $\mathcal{P}$ knows $c_i$? It cannot, no attack game exists to verify
      - All zk-SNARKS for ACS based on non-falsifiable assumptions
- Generic / Algebraic Group Model
  - AGM
    - Given $g' \in \mathbb{G}$, constructed as composition of known grp. elements $(L_1, \cdots, L_n)$ (thus unmodified KZG in AGM is extractable)
Linear PCPs And Succint Arguments
- Short PCPs for arguments of knowledge (length quasilinear in circuint (witness) size)
- Can transform to succint argument, by merkle hashing symbols of $\pi$
- problem
  - Prover still has compute $\pi$ (all symbols) and commit to it (any way for $\mathcal{P}$ to get around this?)
    - Yes, if proof has specific structure (linearity)
- Linear PCPs
  - $\pi$ represented as function evaluation table $\mathbb{F}^v \rightarrow \mathbb{F}$, where for queries $q_1, q_1$, $\pi(d_1 q_1 + d_2 q_2) = d_1 \pi(q_1) + d_2 \pi(q_2)$
  - Proof
    - $\mathcal{P}$ commits to $\pi$ (leverages linearity so that it doesn't have to evaluate all of $\pi$)
    - $\mathcal{V}$ interactively issues queries to $\pi$, and receives openings
    - Can't be rendered non-interactive (no public coin randomness)
  - GGPR (yields snark), w/ proof length of $|\mathbb{F}|^{O(S)}$ + can be turned interactive (SNARK)
  - characteristics
    - If $len(\pi) = L$, then choice of symbol from $\mathcal{V}$ is $log(L)$
      - Represent queries in terms of SRS (at least in commit phase)
      - Each SRS dependent upon circuit being proved (diff. circuits require diff trusted-setup)
- tools
  - Homo-morphic encryption, i.e $Enc(d_1m_1 + d_2m_2) = d_1Enc(m_1) + d_2Enc(m_2)$
- Commitment To Linear PCP
  - Let $\pi : \mathbb{F}^v \rightarrow \mathbb{F}$
    - Question: how to commit to $\pi$, and open commitment to queries $q_1, \cdots, q_k$
  - Commit Phase
    - $\mathcal{V}$ sends $(Enc(r_1), \cdots, Enc(r_v)) \in \mathbb{F}^v$ to $\mathcal{P}$
      - $\pi(r) = \Sigma_i d_i r_i = \langle d, r \rangle$, thus $Enc(\pi(r)) = \Sigma_i d_i Enc(r_i)$
    - $\mathcal{P}$ sends $Enc(\pi(r))$ (notice $\mathcal{P}$ does not know $r$ (Enc is Semantically Secure)) (analog of hiding for encryption schemes)
    - $\mathcal{V}$ decrypts $s = Enc(\pi(r))$ to get $\pi(r)$
    - notice
      - What if $\mathcal{V}$ sent $\mathcal{C}(r_i)$ (assume $\mathcal{C}$ is additively HM CS), then $\mathcal{P}$ can compute $\mathcal{C}(\pi(r))$ (how does $\mathcal{V}$ open $\mathcal{C}(\pi(r))$)?
  - Reveal Phase
    - Now $\mathcal{V}$ requests answers to queries $q^{(i)}$, and $q^* = r + \Sigma_i \alpha_i q_i$
    - $\mathcal{P}$ responds w/ $a_i = \pi(q_i)$, and $a^* = \pi(q^*)$
    - $\mathcal{V}$ checks that $a^* = \pi(r) + \Sigma \alpha_i a_i$
  - binding
    - $\mathcal{P}$ after sending commitment must answer all of $\mathcal{V}$'s queries using the same fn. $\pi$
      - Only way to violate, is to know $\alpha_i$, and prover can retrieve $r$ from $q^*$ (violates SS of Enc)?
    - When k = 1
      - Only one query $q$, and $q^* = r + \alpha q$
      - binding
        
        If $\mathcal{V}$ sends $q, q^* = r + \alpha q$, and $q, \hat{q} = r + \alpha ' q$, and $\mathcal{P}$ responds w/ $a, a'$ (answers to $q$), then $a = a'$ (otherwise SS of $Enc$ is broken, i.e $\mathcal{P}$ knows $r$)
      - What happens in prover knows $\alpha, \alpha'$
        
        Suppose $\mathcal{P}$ gets $q, q^* = r + \alpha q, \hat{q} = r + \alpha' q$, then all $\mathcal{P}$ has is that $\hat{q} - q^* = (\alpha - \alpha')q$, then if $r' = r - cq$, $\alpha + c, \alpha' + c$ satisfy above inequality
        
        Thus to identify $\alpha, \alpha'$ (with more than randomly guessing), $\mathcal{P}$ must know smth abt $r$ (i.e some bound on $c$) (violates semantic security of $Enc$)
      - What happens if $\mathcal{P}$ responds w/ $a, a', a \not = a'$
        
        Suppose prover responds w/ $a, a^$ from $q, q^ = r + \alpha q$, and $a', \hat{a}$ from $q, \hat{a} = r + \alpha' q$, then $a^* - \hat{a} = \alpha a - \alpha' a'$, and $\mathcal{P}$ has that $q^* - \hat{q} = (\alpha - \alpha')q$
        
        Two lin ind. equations in two unknowns, and solve for $\alpha, \alpha'$, thus $\mathcal{P}$ must have known smth abt $r$ SS broken...
  - Linear PCP for ACS
    - Let ${\mathcal{C}, x, y}$, let $W \in \mathbb{F}^S$ be assignment of values to gates in execution
    - constraints
      - Constraints placed on $W$, $W$ is correct execution iff $l = S + |y| - |w|$ constraints
        
        For in-gate $a$, $W_a - x_a = 0$
        
        Out gate $a$, $W_a - y_a = 0$
        
        Add-gate $a$, $W_a - (W_{in_{left}(a)} + W_{in_{right}(a)}) = 0$
        
        Mult-gate $a$, $W_a - W_{in_{left}(a)}W_{in_{right}(a)} = 0$
      - Constraints are of form $Q_a(W)$, (poly. in entries of $W$), i.e $deg(Q_a(W)) \leq 2$ (mult is non-linear?)
    - Not all constraints are non-linear :( (get around this via hadamard encoding)
      - I.e take $(W, W \otimes W)$), vector of length $S + S^2$, where $W \otimes W$ represents, $W_i W_j$ (set of all multiplication gates)
      - Defined $f_{(W, W \otimes W)} = \langle \cdot, (W, W \otimes W) \rangle$ (linear functional on $W, W \otimes W$)
    - $\pi$ represents all evaluations of $f_{(W, W \otimes W)}$ (of size $\mathbb{F}^{S + S^2}$)
    - Checks
      - Linearity (must check that $\pi$ is linear)
        
        Probe $\mathcal{P}$ with $q_1, q_2$, check that $\pi(q_1 + q_2) = \pi(q_1) + \pi(q_2)$
      - Must check that $\pi$ is of form $f_{W, W \otimes W}$ for transcript $W$
        
        $\mathcal{V}$ chooses $q_3, q_4$, and requests $\pi(q_3, \cdots), \pi(q_4, \cdots)$, and $\pi(\cdots, q_3 \otimes q_4)$
        
        $\mathcal{V}$ checks that $\pi(q_3, \cdots) \pi(q_4, \cdots) = \langle q_3, \cdots \rangle \langle q_4, cdots \rangle = \Sigma_i W_i q_i^{(3)} \Sigma_j W_j q_j^{(4)} = \pi(\cdots, q_3 \otimes q_4)$
      - Must check all $l = S+ |y| - |w|$ constraints
        
        Must check that $Q_i(W) = 0, \forall i$, avoid querying $l$ constraints? Instead make single query
        
        I.e choose $\alpha_i$, and expect $\Sigma_i \alpha_q Q_i(W) = 0$, deg 2 ML in $W$, thus Schwartz Zippel insinuates that only $2$ points where poly. can be zero (if not uniformly)
        
        Also is linear in $(W, W \otimes W)$, and can be evaluated in single query to $\pi$
    - All queries combined w/ Linear PCP commit / reveal scheme
  - GGPR
    - Above protocol w/ linear PCPs requires PCP len $\Theta(S^2)$, GGPR leads to $O(S)$ (also solves more general R1CS)
    - R1CS
      - Given matrices $A, B, C$ R1CS-sat iff, $\exists z, (A \cdot z) \odot (B \cdot z) = C \cdot z$
        
        $A, B, C \in Mat(m \times l)$ (l constraints, $M = S - |w| + |y|$ variables)
        
        Can reduce to equation, where $A_i$ ($i$-th row of $A$) $l$ constraints of form $\langle A_i, z \rangle \langle B_i, z \rangle = \langle C_i, z \rangle$
    - goal
      - define $g_z$ univariate poly. vanishing on $H \subset \mathbb{F}$ (multiplicative grp.) iff $z$ is witness to $A, B, C$
    - Protocol
      - $H = {\sigma_1, \cdots, \sigma_l} \subset \mathbb{F}$ arbitrary constants (one for each constraint)
      - Define $\mathcal{A_j}$ (interpolation of $j-th$ column of $A$), i.e $A_j(\sigma_i) = A_{i,j}$, (Sum of Lagrange bases for $A_{i}$)
      - Define poly vanishing over $H$, iff $z$ is witness to R1CS
        
        $g_z(t) = (\Sigma_{j \in 1, \cdots, S} z_j \mathcal{A}j(t))(\Sigma{j \in 1, \cdots S} z_j \mathcal{B}j(t)) - \Sigma{j \in 1, \cdots, S} z_j \mathcal{C}_j(t)$
        
        Thus for $\Sigma_i$, $g_z(\sigma_i) = (\Sigma_{1, \cdots S} z_j \mathcal{A}j(\sigma_i))(\Sigma{1, \cdots S} z_j \mathcal{B}j(\sigma_i)) - (\Sigma{1, \cdots S} z_j \mathcal{C}j(\sigma_i)) = (\Sigma{j \in S} z_j A_{i, j})(\Sigma_{j \in S} z_j B_{i, j}) - \Sigma_{j \in S} z_j C_{i, j} = \langle A_i, z \rangle \langle B_i, z \rangle - \langle C_i, z \rangle$
      - Proof
        
        Notice, $deg(g_z(t)) \leq 2(l - 1)$ (i.e $deg(\mathcal{A}_i) = deg(\mathcal{B}_i) = deg(\mathcal{C}_i) = l - 1$), thus if $g_z(t)$ vanishes on $H, |H| = 1$, $\mathbb{Z}H = \Pi{\alpha \in H} (t - \alpha)$, $g_z(t) = h^(t)\mathbb{Z}_H(t)$, where $deg(h^) \leq deg(g_z(t)) - deg(\mathbb{Z_H(t)}) = l - 2$, thus choose random evaluation and apply SZ
        
        $\pi$ consists of $f_{coeff(h^)}, f_{coeff(h^)}(1, r, \cdots, r^d) = h^*(r)$, and $f_z$ s.t $g_z$ can be evaluated as follows, $f_z(\mathcal{A}_1(r), \cdots, \mathcal{A}_S(r) f_z(\mathcal{B}_1(r), \cdots, \mathcal{B}_S(r)) - f_z(\mathcal{C}_1(r), \cdots, \mathcal{C}_S(r))$
    - Non-Interactivity
      - LIP - Linear interactive proof, (results from transformation of linear-PCP), guarantees that all queries answered by same linear fn.
        
        (2-message)
        
        Ask all queries
        
        Ask sum of queries (check equality)
      - Protocol (SNARK)
        
        Above LPCP protocol is not public coin
        
        Relies on priv. key known only to verifier (HM Enc fn.), if made public, then $\mathcal{P}$ is not bound to $\pi$ (how to fix?)
        
        SRS!!
        
        Make $\mathcal{V}$ public coin, then apply FS
        
        Use SRS to get around using additive HM w/ keys unique to verifiers (SRS essentially generates this + toxic waste)
        
        Trusted Setup
        
        SRS (prover)
        
        For each of queries $q^{(1)}, \cdots, q^{(5)}$, SRS contains $(g^{q^{(i)}_j}, g^{\alpha q^{(i)}_j})$ (i.e HM encoding of queries in basis representation ), i.e alternatively have SRS be $1, r, \cdots, r^{l - 1}$ (max degree of $\mathcal{A}, \mathcal{B}, \mathcal{C}$)
        
        SRS (for verifier)
        
        $g, g^{\alpha}, g^{\mathbb{Z}_H(r)}, g^{\beta_1}, g^{\beta_2}, g^{\beta_3}$
        
        Protocol
        
        $\mathcal{P}$ sends $(g^{f_z(q^{(1)})}, g^{\alpha f_z(q^{(1)})}), (g^{f_z(q^{(2)})}, g^{\alpha g^{q^{(2)}}}), (g^{f_z(q^{(3)})}, g^{\alpha \cdots}), (g^{f_{coeff(h^)(q^{(4)})}}, g^{\alpha f_{coeff(h^)}(q^{(4)})}), (g^{f_z(q^{(5)})}, g^{\alpha f_z(q^{(5)})})$
        
        Where $q_j^{(5)} = \beta_1 q_j^{(1)} + \beta_2 q_j^{(2)} + \beta_3 q_j^{(3)}$
        
        $\mathcal{V}$ checks $e(g_1, g_2) = e(g_4, g^{\mathbb{Z}_H(r)})e(g^{(3)}, g)$ (check that $g_z = \mathbb{Z}_H * h^*$)
        
        $\mathcal{V}$ checks that $\Pi_{1 \leq i \leq 3}e(g^{\beta_i}, g_i) = e(g_5, g)$ (linearity check PCP -> LIP transform)
        
        Notice $\beta_i$ is unknown to verifier, but $g^{\beta_i}$ is known (hence utilization of pairing checks)
        
        $e(g_i, g^{\alpha}) = e(g, g_i')$ (check that response is linear comb. of SRS)
        
        Assumptions
        
        Knowledge of Exponent
        
        Similar to PKoE, i.e given $g_i, g_i^{\alpha}$, if $\mathcal{P}$ sends $f, f^{\alpha}$, then $\mathcal{P}$ can explaing $f = \Pi g_i^{c_i}$
        
        Poly-power DL is hard
        
        Let $r \leftarrow \mathbb{F}_p$, then it is hard to determine $r$ from $g, g^r, \cdots, g^{r^t}$
        
        what abt inputs?
      - Zero Knowledge

NIZK

Components of ZK
- Interaction: $\mathcal{P}$ + $\mathcal{V}$ talk back + forth
- Hidden Randomization: $\mathcal{V}$ tosses coins that are hidden from $\mathcal{P}$, and embeds this randomness in responses
- Computational Difficulty: $\mathcal{P}$ embeds in proofs difficulty of some other problem
How to achieve non-interactivity
- Shared randomness?
notation
- efficient non-uniform algorithm: sequence ${T_n}$ of turing-machines, s.t on input $x, |x| \leq n$, $O(T_n(x)) \leq n^c$ (i.e diff. input lengths have diff. TM, and TMs are aware of input lengths)
- random selector: Random oracle, taking $(s, \mathcal{S})$, where $s$ is a seed, and $\mathcal{S}$ is a set, and outputs $r \in \mathcal{S}$ (i.e $r = RO(s, \mathcal{S})$)
- Random Selecting algorithm: Turing machine w/ access to $RS$
  - Note strictly more powerful than access to a public-coin / Random oracle, i.e $b_i = Select(x \circ b_{i -1}, \mathcal{S})$ (appears as random coin tosses to algorithm, each draw independent of prev.)
  - Think of hash-chain
- Quadratic Residuosity
  - $p \in \mathbb{Z}^_x$, iff $\exists q \in \mathbb{Z}^_x, p^2 \equiv q (x)$, let $\mathcal{Q}_x = \begin{cases} 1 & \text{y is QR (x)} \ 0 \end{cases}$
GGPR

Groth-16

Cryptograhic Pairings
- DLP - Suppose $G = \langle P \rangle$, then given $Q = aP$, it is intractable to determine $a$ from j $Q, P$
  - Multiplicative grp. of finite field
  - Grp. of points over elliptic curve
- $Alt text$
- DHP - Given $P, aP, bP$ it is intractable to determine $abP$
  - DHP key agreement - Alice generates $aP \in G$, Bob generates $bP \in G$, and each sends their grp. element, shared key is $abP$
    - I.e each is expected to know their own exponent
- What abt for three parties?
  - I.e $K = abcP$?
    
    $Alt text$
  - I.e effectively repeating DHP twice
- What about a 1 round protocol for DHP w/ > 2 ppl?
  - Bilinear pairings!!
- Bilinear Pairings
  - let $(G_1, G_T)$ be grps, $G_1$ is a cyclic grp. of prime order (additive), and $G_T$ is a multip. grp.
  - $e : G_1 \times G_1 \rightarrow G_T$ if
    - bilinearity - $r, s, t \in G_1, e(r + s, t) = e(r, t)e(s, t)$
    - non-degeneracy - $e(s, s) \not= 1_T$
  - DLP in $G_1$ -> DLP in $G_T$, fix $P, Q \in G_1, G_1 = \langle P \rangle, Q = aP$, then $e(P, Q) = e(P, xP) = e(P, P)^x$
- Bilinear DHP
  - Let $e : G_1 \times G_1 \rightarrow G_T$ be a bilinear pairing, then given $P, aP, bP, cP$ compute $e(P, P)^{abc}$
- Protocols
  - Three-Party one-round key agreement (generalizable to n-party) $Alt text$
    - Shared secret-key is $K = e(P, P)^{abc}$, Alice $a \leftarrow o(G)$ computes $e(bP, cP)^a$
    - Notice for $n-party$ there must exist pairing over $G_1^{n -1}$ (existence is open-question)
  - Short Signatures (BLS short-signatures)
    - Suppose the DLP is intractable over $G_1$, and $H : {0,1}^* \rightarrow G_1$ is hash fn.
    - Alice priv. key $a \leftarrow {1, \cdots, n -1}$, pubkey is $A = aP$, message $M = H(m)$, signature is $S = aM$, and $(P, A, M, S)$ is DDHP quad
      - i.e $e(P, S) = e(A, M)$
      - Pairings serve as check for DDHP
    - signature aggregation
      - Let $(m_i, s_i)$ signed messages generated by parties $(a_i, A_i)$, aggregate signature $S = \Sigma_i S_i$, $e(P, S) = e(P, \Sigma_i S_i) = \Pi_i e(A_i, H(m_i))$
  - Identity Based Encryption
    - Alice sends $ID_A$ and $TTP$ generates a pub-key for alice derived from $ID_A$
      - What are the criteria composing $ID_A$ that Bob uses to request the pK for Alice?
        
        Can be arbitrary, credit-score, etc. policy is up to Bob and TTP for generating the pK
    - Boneh / Franklin
      - Let $e : G_1 \times G_1 \rightarrow G_T$ be BP, $H_1 : {0,1}^* \rightarrow G_1$, $H_T : G_t \rightarrow {0,1}^l$
      - TTP priv-key is $t \in {1, \cdots, o(G_1)}$, $T = tp$ is pub-key
      - Given $ID_A$ (Alices ID string), TTP sends a BLS signature $d_A = tH_1(ID_A)$ to Alice (over secure channel presumably)
      - Bob wishes to transmit $m$, to Alice, Bob fixes $r \leftarrow {1, \cdots, o(G_1)}$, $c = m \oplus H_T(e(H_1(ID_A), T)^r)$
        
        Bob sends $(c, rP)$ to Alice
      - Alice verifies by $c \oplus H_T(e(d_A, R)) = c \oplus H_T(e(tH_1(ID_A), rP)) = c \oplus H_T(e(H_1(ID_A), tP)^r) = m$
Elliptic Curves
- Defined over field $K$
  - weierstrass - $y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$
- Hasse's - If $K = \mathbb{F}_q$, then $(\sqrt{q} - 1)^2 \leq |E(K)| \leq (\sqrt{q} + 1)^2$
KZG Commitments
- Merkle proofs form of VC (Vector Commitment), i.e given ordered sequence $(a_1, \cdots, a_n)$, send $c \leftarrow \mathcal{C}$ which serves as commitment to all ordered values, and any value / position can be opened later
- Polynomial Commitment - Prover commits to a poly. and at any point in the future, prover can open commitment to evaluation of poly. at any point chosen by verifier
  - Hiding - Does not tell what the poly. is
  - Binding - Prover cannot trick verifier into accepting poly. commit for a different poly.
- Commitment size is a grp. element
- Proof size is one grp. element (~48 bytes)
- Verification - 2 pairings + 2 grp. mult
- Computationally hiding
- $\langle H \rangle = \mathbb{G}_1, \langle G \rangle = \mathbb{G}_2$, order of grps. is $p$, $e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$, $[x]_1 = xG, [x]_2 = xH$
  - Pairing serves for multiplication of commitments
- trusted setup
  - Grps. generally group of points of EC
  - Choose random $s \in \mathbb{F}_q$, and make public $[s^i]_1, [s^i]_2$, $0 \leq i \leq deg(f)$
  - $[x]_i + [y]_i = [x + y]_i$ (additive), commitment also preserved across mult. by scalar (in $\mathbb{F}_q$)
- i.e $[p(X)]_j = [\Sigma_i a_i X^i]_j = \Sigma_i a_i [X^i]_j$
- Commitment
  - Commitment $C = [p(s)]_1$
  - Opening commitment?
    - Fix $z \in \mathbb{F}_q$, $p(z) = y$, $q(X)(X - z) = p(X) - p(z)$
    - Then $e([q(s)]_1, [(s - z)]_2) = e(C - [p(z)]_1, H)$
- Multi-proofs
  - Proving evaluation of poly. at multiple points $(x_0, p(x_0)), \cdots, (x_n, p(x_n))$, create $I(X)$ (lagrange interpolation poly.) for the points mentioned, then $q(s) = \frac{p(s) - I(s)}{Z(s)}$, where $Z(X) = (X - x_0)\cdots (X - x_n)$, $[q(s)]_1$ is opening to commitment
PCPs
- IP - $\mathcal{P}$ asked questions by verifier, and $\mathcal{P}$ behaves adaptively
- PCP - proof is $\pi$, i.e static object, that has well-defined responses to each query $q_i$ asked by $\mathcal{V}$, answers are not dependent upon $q_j, j < i$
  - A PCP for $\mathcal{L}$, is $(\mathcal{V}, \pi, x)$, $\pi \in \Sigma^l$
    - completeness - For every $x \in \mathbb{L}$, there exists a $\pi \in \Sigma^l$, where $Pr[\mathcal{V}^{\pi} = 1] \geq 1 - \delta_c$
    - soundness - For every $x \not\in \mathcal{L}$ and each proof string $\pi \in \Sigma^l$, $Pr[\mathcal{V}^{\pi}(x) = 1] \leq \delta_s$
PLONK
- General-purpose zkps
- trusted setup
  - Multiple people can participate, once completed once, any kind of poly. can be proven
- arithmetization
  - Algebraic Intermediate Representation
    - Execution Traces + Constraints
      - Evolution of some computation over time
      - Representation
        
        $E \in Mat(T, W)$, i.e a $W$-column, $T$-row matrix, where $W$ is the number of registers, and $T$ is the number of time-steps
        
        i.e each column $f_i : T \rightarrow \mathbb{F}$ (assignment of registers over time)
        
        Must prove that execution trace adheres to certain constraints, i,e for fibonacci ($f_1(t + 2) = f_1(t) + f_1(t + 1)$)
        
        boundary contraints
        
        assertion, that register $i$ at time $t$ had value $\alpha$, i,e $(t, i, \alpha), f_i(t) = \alpha$
        
        Can be used to verify input / output, etc.
        
        Transition constraints
        
        Poly, where $\forall j \in [T - 1], P(f_1(j), \cdots, f_w(j), f_1(j + 1), \cdots, f_w(j + 1))$
      - Recall that each column $i$, is a fn. $f_i : T \rightarrow \mathbb{F}$, this function has a specific structure
        
        Let $H \subset \mathbb{F}^*, O(H) = T, H = \langle \omega \rangle$, then $f_i[t] = f_i(\omega^t)$ (i.e each column's value is evaluation of polynomial at specific point in multiplicative subgrp. of $\mathbb{F}$)
      - Expressing constraints via polynomials
        
        Suppose that $f_i[t]^2 = f_i[t + 1]$, then $f(X)^2 = f(X * \omega)$, notice $X \in H, x = \omega^t$ (for some $t$)
        
        Suppose that constraint is satisfied at $X_1, \cdots, X_n = (\omega^{t_1}, \cdots, \omega^{t_n})$, then $(X - \omega^{t_1}) \cdots (X - \omega^{t_n})|f(X)^2 - f(X * \omega)$
        
        boundary
        
        $(X - \omega^t)|f_i(X) - \alpha$
        
        transition
        
        notice, $H = \langle \omega \rangle, O(H) = T$, thus $X^T - 1 = (\omega - X) \cdots (\omega^T - X)$
        
        $(X - \omega) \cdots (X - \omega) | P(f_1(X), \cdots, f_w(X), f_1(X * \omega), \cdots, f_w(X * \omega))$
Statements
- Let $\Sigma$ be alphabet, then $L \subset \Sigma^$ is language, $R : \Sigma^ \rightarrow {0,1}$ (i.e $R$ determines what words are in language $L_R$)
- Separate into two separate languages $\Sigma_I, \Sigma_W$ (one for instances, one for witnesses), where prover constructs instance, for a specific witness, i.e prover sends, $R_w : \Sigma_I \rightarrow {0,1}$, then the verifier evaluates $R_w(I)$
  - i.e in Schnorr, instance is $(a, e, z)$ witness is $w$
Presentation
- Intro to groups, rings, fields, pairings, poly., (elliptic curves?), sigma-protocols, FFT definitions of interactive, non-interactive, zk-proofs
- Commitment Schemes
  - Pederson
  - KZG
- Tying all together with PLONK
- Looking forward to applications (zk-evms)
Presentation 1
- Intro
  - Introduce basic direction of presentation $Alt text$
    - I.e - Computation -> Witness Generation -> polynomials -> single polynomial commitment -> verifiers read commitment, and can request evaluation at random points
- Introduce definitions of zk
  - Languages, relations,
  - Interactive Proofs
    - Definition
      - Introduce polynomials?
    - Graph Non-isomorphism
    - Sum-check
      - Example using poly.
      - MLEs
        
        Schwartz-Zippel
    - Example?
  - Non-interactive proofs
    - Apply Fiat-shamir transform to sum-check using random-oracle
  - Brief Intro to GKR
    - Intro to Arithmetic Circuits
      - Matrix multiplication example
  - Circuit Construction
  - SNARKs
    - $\Sigma$-protocols?
    - Commitment Schemes
      - Polynomial v. vector commitments
  - Zero-knowledge
    - Definition
      - Simulator Paradigm
    - Quadratic Non-Residue zk-proof
    - Schnorr
      - Brief intro to grp. theory

Pederson Secret Sharing

Distribute secret shares to $n$ ppl, where $k \leq n$ can recover the secret, but $< k$ shares retrieve no (shannon info) abt the secret

Ferveo

Tying consensus layer security assumptions w/ threshold cryptography to achieve strong mempool layer privacy guarantees
- Txs encrypted until block-finalization
- Txs decrypted in order at block finalization
ferveo - DKG + TPKE protocol for TM based PoS blockchains
- ~10ms compute per tx
DKG
- Generates pub-key and $n$ priv-key shares held by set of entities (validators)
TPKE
- For fixed threshold $t$, allows any subset of at least $t \subset n$ shares to decrypt messages encrypted with pub-key generated above
alternatives
- Timelock Encryption - Based on VDF, requires $T$ timesteps to decrypt txs
- TEE Encryption -
- Witness Encryption -
Techniques + Design Goals
- properties
  - Information safety: infeasible to decrypt contents of tx prior to finalization of block containing it
  - Execution Guarantee: Once a valid tx is committed to a block, it must be executed
  - Efficiency: Computationally + communication efficient to not limit thru-put + latency of network
- bottlenecks
  - Number of key-shares linearly increases time for decryption
    - I.e large-validator set = large distribution of tokens = requires larger number of shares to align w/ validator set distribution
- partitioning
  - Take $\lfloor\frac{power(val_i)}{total_power} * total_shares \rfloor$ (leads to some approximate error), i.e $n$ validators can be mis-allocated
    - Under-estimate stake?
- public fees
  - Fees are public, i.e don't execute tx before block is committed, so must exhaust all of gas_limit on submission (tx-reversion possible),
  - Simulate txs before submission for approx. gas consumption determination?
- consensus efficiency
  - Per tx, all priv-key shares must be broadcast for validator
- maliciously crafted txs?
- epoched staking
  - I.e must determine shares in advance for each epoch (one DKG round per epoch)
Crypto
- Uses scrape
  - $scrape.Deal(bp, ek_1, \cdots, ek_n) \rightarrow pvss$, where $ek_i = [dk_i]H$, where $ek_i$ are public, but only each $P_i$ knows $dk_i$
    - Randomly uniformly select $f(x) = a_0 + a_1x + \cdots + a_tx^t$
    - $(a_i, \cdots, a_t) \leftarrow \mathbb{F}^t$
    - $F_0, \cdots, F_t \leftarrow [a_0]G, \cdots, [a_t]G$, $\langle G \rangle = \mathbb{G_1}$
    - $A_1, \cdots, A_n \leftarrow [f(\omega_1)]G, \cdots, [f(\omega_n)]G$
    - $Y_1, \cdots, Y_n \leftarrow [f(\omega_1)]ek_1, \cdots, [f(\omega_n)]ek_n$
    - $pvss \leftarrow (F_0, \cdots, F_t, A_1, \cdots, A_n, Y_1, \cdots, Y_n)$
- verification
  - $scrape.Verify(bp, ek_1, \cdots, ek_n, pvss) \rightarrow {0,1}$
    - Choose uniformly random $\alpha \leftarrow \mathbb{F}$
    - Check $\Pi_{j = 1}^n A_j^{l_j(\alpha)} = \Pi_{j = 0}^t F_j^{\alpha_j}$
      - Poly evaluation at $\alpha$ hidden via pederson commitments
    - Check $\forall j, e(G, Y_j) = e(A_j, ek_j)$
- Scrape yields a HM additive transcript
DKG
- Requires no trusted party
  - Each validator acts as a PVSS dealer, add all shares together
- algorithm
  - Each validator $V_i \in ValSet$
    - $V_i$ generates $dk_i$
    - $V_i$ announces $ek_i = [dk_i]H$ on blockchain
  - Each validator $V_i$ runs PartitionDomain
    - Allocates shares to validators in set according to voting-power
  - Each validator $V_i$
    - $V_i$ computes $pvss_i \leftarrow Scrape.Deal$
    - $V_i$ post $pvss_i$
  - Each validator $V_i$
    - For each $V_j \in ValSet, j \not= i$
      - $V_i$ runs $Scrape.verify(pvss_j)$
      - $V_i$ computes $pvss \leftarrow pvss + pvss_j$
    - When $2/3$ by voting power of vals have posted $pvss_j$ exit
  - Liveness dependent upon $1/3$
- Final pub-key for DKG is $F_0$
Encryption
- Given $Y$ (public key, $Y \in \mathbb{G}_1$), $aad$ (authentication-data (nonce, etc.)) generate a shared secret $S$ (symmetric encryption / decryption key)
  - Generate $(U,W)$ (cipher-text (posted to block-chain)), and $S$ symmetric key used to encrypt tx (AEAD)
- Given $TPKE.Encrypt(Y, aad)$ to create $(U, W, aad)$ (public), $S$ (secret)
  - Where counter-party with priv-key for $Y$ can recover $S$ from $(U, W)$
  - Let $r \leftarrow \mathbb{F}$
  - Let $S = e([r]Y, H)$
  - Let $U = [r]G$
  - Let $W = [r]H_{\mathbb{G}2}(U, aad)$ ($H{\mathbb{G}_2}$ is hash fn. mapping into $\mathbb{G}_2$)
- validity checking
Decryption Shares
- Decryption share for $V_i$ for $(U, W)$ is $D_i = [dk_i^{-1}]U$
- Verification for $V_j$, can be done as follows $e(D_i, ek_i) = e([dk_i^{-1}]U, dk_iH) = e(U, H)$
- If validator owns multiple shares, only single DS is necessary
Tx Decryption
- $V_p$ selected as block-proposer
- $V_p$ fills block w/ encrypted txs $(U_i, W_i)$ (PrepareProposal)
- For each validator $V_i \in val_set$ (ExtendVote)
  - For each $(U_j, W_j) \in Block$
    - $V_i$ check validity of $(U_j, W_j)$
    - $V_i$ computes $D_{i,j} = [dk_i^{-1}]U_j$
  - $V_i$ includes $D_{i,j}$ in block (notice, this is linear in $len(block)$)
- For each validator $V_i$ (VerifyExtension)
  - For each $D_{k, j}$ from $V_k$ for each $(U_j, W_j)$ in block
    - $V_i$ checks validity of $D_{k, j}$
  - If all of $V_k$'s shares are valid, add vote from $V_k$
- commit
  - For each $(U_i, W_i)$ in block
    - $V_p$ aggregates $D_{j,i}$ from $V_j \in signers(block)$ into $S_i$, and decrypts $tx_i$
    - Executes, and publishes $S_i$ in block (instead of shares)

Lit

Network of nodes participating in DKG
enables nodes to accept $A$ (condition) for message $ID$, and only produce $D_i$ (decryption share) if $A$ is satisfied

Encryption (not dependent on liveness of lit?)

User requests $D$ from lit for access conditions $A$ (block header of next block (or within $n$ blocks)), for $ID = hash(message)$
- Important, the generation of $D$ (symmetric key) does not depend on Lit val-set (I assume that this process will change as val-set of lit changes, so depends on liveness of lit network)
User encrypts tx, ID according to $D$, and posts to chain

Decryption

block-builder presents IDs for encrypted txs to lit
- Waits for response from lit
Proposer waits for txs for become finalized
Proposer combines shares to decrypt txs

Fairblock

Only broadcast shares $O(len(val_set))$ use identity-based encryption
identity based Encryption
- Pk is determined uniquely from identifying info, i.e TTP generates pbk from pvk + $ID_A$
phases
- Enrollment - validators bond tokens to participate in DKG
- DKG
  - Vals generate shared pk $spk$, and $msk_i$ (sharded master key) (run every-time keeper set changes)
- Encryption + commitment
  - Use BF IBE, where $h = ID$ (block-id), and pk is $spk$
  - broadcasts encrypted tx + commitment to tx plain-text (maintain ordering)

Presentation Outline

High Level Overview

Problem: stop front-running
Potential Solutions
- Proto-rev, cowSwap
- SGX
- etc.
Threshold Decryption + DKG
- DKG + TD
- Ferveo
  - Considerations
  - Disadvantages
    - One share per tx in block (have to b.c vals can't reveal priv-key shares for risk of running DKG again)
- Lit

Computation

Computational Tasks + Models
- Computational Tasks
  - search problems
    - Intuitively, mapping between instances $x$ (input), to solutions $y$ (output). Problem is to identify set of solutions for given instances
    - Let $R \subset {0,1}^* \times {0,1}^$ be a relation, where $(x,y) \in R$ denotes that $y$ is a solution to $x$ (instance). Denote $R(x) = {y : (x,y) \in R}$ (set of solutions to $x$). Function $f : {0,1}^ \rightarrow {0,1}^* \cup {\bot}$, $f(x) \in R(x)$ if $R(x) \not= \emptyset$, and $f(x) = \bot$ otherwise
      - $f$ finds an answer when one exists, and fails otherwise (never outputs wrong answer) (sound?)
      - Consider $R$, where $\forall x \in {0,1}^*, |R(x)| = 1$ (relations w/ unique soln.), $R(x)$ is a fn.
  - decision problems
    - Determination of set membership. I.e given $\mathcal{S} \subset {0,1}^*$, determine $x \in {0,1}, x \in \mathcal{S}$
      - Can also make analog to search problems, i.e $\mathcal{S} = {x \in {0,1}, R(x) \not= \emptyset}$
    - Solution - function $f : {0,1}^* \rightarrow {0,1}$, where $f(x) = 1$ if $x \in \mathcal{S}$, and $f(x) = 0$ otherwise
- Uniform Models (Algorithms)
  - What is computation (intuitively)
    - Modification of environment (witness / inputs / state, etc.), via repeated application of a simple rule
      - simple - depends on / effects a subset of the environment (active zone)
    - active set is bounded, environment is possibly unbounded (unlimited disk, limited RAM, etc.)
  - Turing Machines
    - Computation can be solved by any model of computer iff it can be solved by turing-machine
    - Definition
      - A turing machine is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$
        
        $Q$ - finite set of states
        
        $\Sigma$ - finite set of input symbols
        
        $\Gamma$ - finite ($\Gamma \subset \Sigma$) set of tape symbols, where $\Sigma \subset \Gamma$
        
        $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}$ (transition function)
        
        $q_0 \in Q$ (start state)
        
        $q_{accept} \in Q$ (accept state)
        
        $q_{reject} \in Q$ (reject state)
    - intuition
      - environment - Infinite sequence of cells, each containing a symbol from finite alphabet $\Sigma \subset {0,1}^*$
        
        Sequence of cells called, tape
        
        TM has reference to current position in tape
      - TM also has notion of internal state, i.e $q \in Q$
      - Computation Rule
        
        Finite rule, i.e $\delta: \Sigma \times Q \rightarrow \Sigma \times Q \times {-1, 0, 1}$
        
        I.e $\Sigma$ (current symbol), $Q$ (current state), $\Sigma$ (new symbol), $Q$ (new state), ${-1, 0, 1}$ (tape movement)
        
        New symbol written to current cell before moving forward (does this order even matter?)
    - k-tape TM
      - scratch-pad - Consists of k-tapes
        
        each tape Consists of tape-head (read / write symbol from tape)
      - input-tape
        
        First tape contains input for machine (read-only)
      - Rules
        
        Read $k$ symbols (each at head), read current-state
        
        Apply state-transition (new symbols for $k - 1$ write tapes), get new state, move each head
    - definitions
      - time-constructible
        
        $T : \N \to \N$ is time-constructible if $T(n) \geq n$, and $M_T$ computes $T$ in time $T(n)$
      - restriction of $\Gamma$ to ${0,1, \square, \triangle }$
        
        If $f : {0,1}^* \rightarrow {0,1 }^*$ in $T(n)$ time with $\Gamma$ then $f$ is computable in $4log (|\Gamma)T(n)$ with alphabet ${0,1, \square, \triangle}$
        
        each $\alpha \in \Gamma$ can be encoded in $log(\Gamma)$ cells in ${0,1}^*$, transform each work-tape using encoding
        
        What states are needed for scanning?
        
        Read symbols (how to store symbol?)
        
        Must have some delimiter between symbols in encoded tape? nope, j represent in $log_2(|\Gamma|)$ cells
        
        Start
        
        read $log_2(|\Gamma|)$ cells (from input-tape)
        
        How to store historical symbols? Must encode into state (registers)
        
        I.e for each state in $q \in Q$
        
        Must store whether $\tilde{M}$ is done reading
        
        Must store progress in reading (counter)?
        
        Store $log_2(\Gamma)$ states for each $q \in Q$
        
        Must do this for each tape, i.e $|\tilde{Q}| = |\Gamma|^kQ$
        
        Apply transition (have to store symbols read in state)
        
        Write back new symbol to each tape
        
        intuititon
        
        Can map multiple diff. state spaces i.e $\delta(q_1, \cdots, q_n)$ into one via $Q_1 \times \cdots \times Q_n$
        
        After reading apply transition to new state
        
        For each work-tape, have to write symbol (consists of $log_2(\Gamma)$ steps?)
  - k-tapes to 1-tape
    - Reference OG-transformation
    - Also store each $\alpha_i$ on tape $i$, in $i-th$ spot, i.e $j-th$ symbol on tape $i$, is in $jk + i$-th spot in single tape
      - intermediate states for storing inputs
      - Also have to store each head + move them independently
    - i.e first read + store in state (for each $q \in Q$) the symbols of $M$ in $\tilde{M}$
    - Apply state-transitions (store head movements in state + intermediary state (on path to new state))
      - Update symbols at each head $kT(n)$ steps
      - Sweep back for each tape $k$, and reposition head ($k T(n)$ steps)
      - transition to new state
    - start again
  - bi-directional to uni-directional
    - Transform to 2-tape uni-directional TM
      - Bottom work-tape represents right
      - Top represents left
    - Transition head as necessary
    - Transform from multi-tape to single tape (either OG or AB-transform)
- Universal Machines
  - TMs $M$ are finite, i.e can be represented as $\lfloor M \rfloor \in {0,1}^*$
    - All strings are TMs, i.e $\alpha \in {0,1 }^*$ is $\forall x, M_{\bot}(x) = 0$ if $\alpha$ is not a valid TM
  - Universal Turing Machine
    - Given as input $(\alpha, x) \in {0,1}^* \times {0,1}^*$ returns $M_{\alpha}(x)$, denote this as $\mathcal{U}$, where $\mathcal{U}(x, \alpha)$ halts in $Tlog(T)$ steps, iff $M_{\alpha}(x)$ halts in $T$ steps.
      - Suppose $M$ is TM, w/ work, input, output tapes
      - Then $\mathcal{U}$ has same input tape (storing $x$), and tape holding description of $M$ ($\alpha$) (including transition fn.)
      - $\mathcal{U}$ has tape holding current state of $M$, work tape holding same contents as $M$
      - and output tape
    - intuition
      - Start
        
        Read symbol of input tape, read current state (start-tape), find entry corresponding to current values in transition-tape + output, perform transition on input (move head), $M$-simulation-work tape (write symbol + move head), write output, write new state
      - Next-step
        
        Read state, read input, read work-tape, find entry corresponding to current state
        
        Notice, transform TM tapes into infinite (to right), (search is finite + well-defined) (each search will take approx. $len(\lfloor \delta\rfloor))$ steps to compute (hence, $CT$ steps?)
        
        Transition function determines when machine halts
        
        I.e if in accept-state, $\delta$ always stays
    - Transform to single tape via OG-transform
    - What states for $\mathcal{U}$
      - Notice
        
        States -> registers
        
        tape -> disk (RAM) lookup, etc.
      - states purely used for reading transition fn. / determining output?
        
        $q_{compare_i}$ - compare entry at $i$-th input / work tape from $M$ to current entry in transition-tape
        
        $q_{exec}$ - accept-state, first stage of transition comparison
- Church-Turing Thesis
  - A function can be computed by some TM iff it can be computed by some machine of any other (reasonable (Turing complete)) model of computation
  - sanity-check
    - TM can emulate RAM
      - RAM
        
        infinite memory cells
        
        finite number of registers
        
        Program counter (index into sequence defined below)
        
        Program - Sequence of instructions selected from finite set
        
        Instructions
        
        $reset(r)$ - set $r$ to $0$, where $r$ is the index of register
        
        $inc(r)$ - increment $r$ (index of register)
        
        $load(r_1, r_2)$ - $r_1, r_2$ indices of registers, $r_2$ holds index of memory $m$, value of $m$ is loaded into $r_1$
        
        $store(r_1, r_2)$ - Store contents of $r_1$ into $m$ where $m$ is indexed by contents of $r_2$
        
        $cond-goto(r, l)$ - $r$ index of register, $l$ index of instruction, if $r > 0$ then jump to instruction $l -1$
      - Conversion from RAM -> TM
        
        What is stored on tape?
        
        Contents of memory cells (including inputs), notice, only need to store accessed memory
        
        All instructions
        
        Contents of registers
        
        How to represent instructions?
        
        Instructions are finite? Append them to language?
        
        No represent via state-transition fn. (i.e $\delta$)
        
        How to represent state?
        
        Program counter
        
        Current instruction
        
        Stored on tape, access via index into tape
        
        Current state
modelling efficiency
- Model efficiency based on number of steps necessary for computation
- Given $f : {0,1}^* \rightarrow {0,1}$, and $M_f$ computing $f$ ($\forall x, f(x) = M_f(x)$) in $T(n)$ time, then $M_f(x)$ takes at most $T(|x|)$ steps to complete
Uncomputable funtions
- halting problem
  - Given machine $M$, determine if $M$ halts on input $x$ (i.e runs in finite steps, and outputs some $y$), define $h : {0,1}^* \times {0,1}^* \rightarrow {0,1}$, where $h(M, x) = 1$ if $M$ halts on $x$, and $h(M, x) = 0$ otherwise
- THEOREM
  - The decision problem $(M, x) \in h^{-1}(1) = {(M, x) \in {0,1}, h(M,x) = 1}$
    - Notice here we are conflating $M$ (machine) and $\langle M \rangle$ (machine's description), where $\langle M \rangle \in {0,1}^*$ is a finite-string
    - idea
      - Show that diagonal(diagonalization) of $h$ is not computable, i.e $d : {0,1}^* \rightarrow {0,1}$, where $d(M) = h(\langle M \rangle, \langle M \rangle)$
        
        i.e running $M$ w/ $\langle M \rangle$
        
        Use this to imply that $h$ is not computable
      - To show diagonal is non-computable, define $d' : {0,1}^* \rightarrow {0,1}$, where $d'(M) = \begin{cases} 1 & h(\langle M \rangle, \langle M \rangle) = 1, \land M(\langle M \rangle) = 0 \ 0 \end{cases}$
      - Suppose $d'$ is computable by $M_{d'}$, then, $M_{d'}(M_{d'}) = d'(M_{d'})$, suppose $d'(M_{d'}) = 1$, then $M_{d'}(M_{d'}) = 0$ (contradiction). Conversely, suppose $d'(M_{d'}) = 0$, then $M_{d'}(M_{d'}) = 1$ (contradiction), thus $M_{d'}(\langle M_{d'} \rangle)$, and $d'$ is not computable
      - If $d$ is computable, then $d'$ is computable
        
        Let $M_d$ be machine computing $d$, then for $d'(M)$, transform $M \rightarrow M'$, where $\phi : M'(x) = M(x)$ iff $M(x) = 0$ , otherwise, $M'$ loops infinitely. Notice, $d(M')$ is computable, and $d(M') = d'(M)$, thus $M_d(\phi)$ computes $d'$
      - Thus $d$ is uncomputable, and $h$ is as well
- Turing Reductions
  - $f \rightarrow^T f'$, if when given $A_f$ (algorithm computing f), one can obtain an algorithm $A_{f'}$ computing $f'$
- Rice's Theorem
  - Let $\mathcal{F}$ denote a set of computable partial functions $f : {0,1}^* \rightarrow {0,1}$, let $\mathcal{S}_{\mathcal{F}}$ denote strings that define machines computing functions in $\mathcal{F}$.
    - decision problem for $\mathcal{S}_{\mathcal{F}}$ is un-computable. Prove via Turing reduction from $d$
- Universal Machine
  - TM $M$, s.t given $\langle M' \rangle || x$, outputs $M'(x)$ if $M'$ halts, otherwise undefined
    - TM exists, computes partial function, can make more granular to bound computation, then becomes computable
- Oracle Machines
  - TM augmented s.t it can pose questions externally
    - TM-reductions using oracle as another TM, write $M^f(x)$, when $M$ is given access to $f$
  - formal def
    - Takes additional tape, oracle tape , and 2 additional states, oracle invocation, oracle spoke
    - Execution
      - $d'$, where $d'(q, m) = d(q, m)$, if $q = invoke$, then $d(q, m) = q', m'$, where q' is spoke, and the oracle tape holds the answer to the query

Non-Uniform Models

Collection of finite machines (TMs), one for each input length
- Useful for developing lower bounds on time / space complexity of algo?
- Possibly infinite description, infinite sequence of finitely described TMs
two models
- Boolean circuits
- Machines that take advice
*boolean circuits
- description
  - DAG w/ labels on leaves (inputs)
  - gates internal nodes (have in, out-degree > 1) (gates)
  - Sinks (output), have in-degree = 1
- Operation of BC is computable by TM poly. in input size
- fan-in: max number of inputs to gates
- Let $f : {0,1}^* \rightarrow {0,1}^m$, can define ${C_i }n$, where $C{|x|}(x) = f(x)$ (non-uniform family of circuits)
  - Uniform family: if each circuit $C_n$ can be computed in time poly. in $n$, and size is poly. in $n$ then $f$ is computable by TM
Machines That Take Advice
- Rather than making circuit size non-uniform (non predictable function of input length), have algorithm take advice, length of which is determined by input size
- definition
  - Algorithm $A$ computes $f$, w/ length $l : \mathbb{N} \rightarrow \mathbb{N}$, if $\exists (a_n)_{n \in \mathbb{N}}$ s.t
    - For each $x \in {0, 1}^*$, $A(a_{|x|}, x) = f(x)$ (taking element $|x|$ of advice sequence)
    - $\forall n \in \mathbb{N}$, $|a_n| = l(n)$
Complexity Classes
- Set of functions $f$, such that $M_f$ computes $f$ and the resource consumptions (tape size, number of steps, etc.) satisfy constrains $T : \N \to \N$, on $T(|x|) \leq \alpha$
Problems
- Prove that any fn. that can be computed by a TM, can be computed by TM that never moves left of tape
  - Suppose original TM moves $n$ units from left of tape, and $m$ units to right, add 2 additional symbols, $L, R$, where the left-most boundary, takes $L$, and rightmost boundary $n + m$ to right, takes $R$. Have sub-query (oracle), that moves to right-limit (notice, will also have to reverse directions after moving to rightmost boundary), and vice-versa for left-most
  - Can also construct via 2-tape?
- Prove that fn. that can be computed by a single tape TM iff it can be computed by a 2-tape (multi-tape) TM
  - Multi-tape TM
    - $k$ tapes + $k$ independent heads, $\delta(q, x_1, \cdots, x_k) = (q', \sigma_1, d_1, \cdots, \sigma_k, d_k)$
    - Reads and transitions based upon current head positions,
  - Reverse - triv.
  - Forward
    - Simplest case is two, compress multi-tape into single tape as follows, the $i$-th cell of the single tape contains $i$-th cells of multi-tapes (extend alhabet to $\Sigma^m$)
    - Also have to store-head positions + read from head
      - Could also store every possible combination of tapes? How to create computable mapping between states / head positions?
    - Tape also stores indication of which head is on which tape (modifies tape symbols accordingly)
      - One step of single tape, involves finding other heads, marking tapes accordingly, etc.
- Multi-tape addition
  - 3 heads + 2 states (carry, not carry), write to third state 1, 0 depending on binary addition of inputs ...
- RAM w/ TM?
  - Multi-tape
    - One for memory
      - Memory holds input?
    - One for registers
    - Instructions are encoded in state-transition fn. ?
      - Also can have tape for instructions + symbol marking current PC?
    - What states are held?
      - Can have sub-states for each of the instructions, i.e identify machine what to do / where in instruction execution it is
- Let $\mathcal{F}$, $\mathcal{S}{\mathcal{F}}$ be in definition of Rice's Theorem, present Turing reduction of $d$ from HP, to $\mathcal{S}{\mathcal{F}}$
  - I.e $d(M) = h(M, \langle M \rangle) = \begin{cases} 1 & \text{h halts} \ 0 \end{cases}$
  - If $A_S$ exists solving $\mathcal{S}_{\mathcal{F}}$, then $A_d$ exists determining $d$.
    - Let $A_S$ be a alg. computing $\mathcal{S}{\mathcal{F}}$, define $f \in \mathcal{F}$, and $f{\bot} \not \in \mathcal{F}$ (i.e not defined on any inputs)
    - Given $M$, transform $M \rightarrow M'$, where $M'$ executes $M(\langle M \rangle)$
      - if $M'$ halts, on $\langle M \rangle$, then output $f(x)$, thus if $M(\langle M \rangle)$ halts, then $M' \sim f$, and $A_S(M') = 1$, and $d(M(\langle M \rangle)) = 1$
- Post Correspondence Problem
  - Given two sequences of strings in $\Sigma$, $(\alpha_1, \cdots, \alpha_N), (\beta_1, \cdots, \beta_N)$, determine if there is any sequence $(i_j)j$, where $i_j \in {1, \cdots, N}$, where $\alpha{i_1} \cdots \alpha_{i_j} = \beta_{i_1} \cdots \beta{i_j}$
  - Present Turing reduction to $h$ from HP, i.e $h(M, x) = 1$ iff $M(x)$ halts
    - Given $M$, construct sequences of words s.t the only solution to PCP is full sequence of configurations of $M$ on $x$, where $M$ halts, thus $h$ is solved
- Define TM $M$ to be oblivious if head-movement does not depend on input but input length (i.e for each step, must index all of memory (similar to 1.9))
  - Show that for each $T$ (TC), if $L \in DTIME(T(n))$ ($\exists M_L , steps(M_L(x)) \leq T(n)$), there is oblivious $TM$ that decides $L$ in $T(n)^2$
    - Let $M_L$ be TM for $L$, that halts in $T(|x|)$ steps. Transform to single tape TM via $AB$ transform
      - i.e mark head positions, read head symbols into state (registers), apply state-transitions (move heads independently)
        
        Key consequence - Additional complexity moved into state-blowup, for each state (have to store new state for each symbol per-tape, have to store each progress of finding each symbol in state + steps)
    - Can tweak $\mathcal{U}$ to be oblivious
- Two dimensional TM, each tape is infinite grid, suppose that machine takes $T(n)$ steps (can represent as $T(n)$-tape machine?, and apply AB / OG-transform to single-tape?

NP / NP-Completeness

NP - Class of problems whose solutions can be efficiently verified
- definition
  - $L \subset {0,1}^*$ is in NP, if $\exists p : \N \to \N$, and $M_L, x \in L \iff \exists u \in {0,1 }^{p(|x|)}, M_L(x, u) = 1$ (i.e poly. sized advice string)
relationships
- $P \subset NP \subset \bigcup_{c \geq 1} DTIME(2^{n^c})$
- proof
  - $P \subset NP$ - triv. take advice to be $\empty$
  - $NP \subset DTIME(2^{n^c})$, suppose $x \in L \iff M(x, u) = 1$, where $|u| \leq p(|x|)$, then for $x$, enumerate $u$ (there are $2^{p(|x)|}$) such $u$, and evaluate $M(x, u)$
Non-Deterministic Turing Machines
- Alternative def. for $NP$ (non-deterministic poly. time)
- TM w/ two transition fns. $\delta_1, \delta_2$ (each transition steps randomly chooses one-or-the other)
  - $M(x) = 1$, if on input 1, some sequence of $\delta_1 \cdots, \delta_2$ outputs 1
  - $M(x) = 0$, if every sequence of choices makes $M$ halt (w/o reaching $q_{accept}$)
  - $M$ runs in time $T(n)$ if each input $x$ and all ND choices, $M$ halts in $T(|x|)$ steps
- NTIME
  - For each $T : \N \to \N$, and $L \subset {0,1}^*$, $L \in NTIME(T(n))$ if $\exists M_L$ s.t $\forall x, M_L(x) = f(x)$, and $M$ (NDTM) runs in time $cT(|x|)$
- View witness to $M \in NTIME(T(n))$, as sequence of $\delta_i$ such that $M(x)$ w/ the given sequence outputs $1$
- $NP = \bigcup_{c \in \N}NTIME(n^c)$
  - $NP \subset \bigcup_{c \in \N}NTIME(n^c)$
    - Suppose $L \in NP$, then $x \in L \iff \exists c \in \N, u \in {0,1}^{|x|^c}, M(x, u) = 1$, then transform into $M'$ (NDTM), where on $M'(x)$, at step $i$, $\delta_1$ acts as if $M(x, u')$, where $u'$ is $u$, but $u_i = 0$, and a similar case holds for $\delta_2$. Alternatively, $M'$ takes $n^c$ steps to write down $|u| \leq p(|x|)$, and executes $M(x, u)$ (i.e generate random advice and execute $M$).
  - $\bigcup_{c \in \N}NTIME(n^c) \subset NP$
    - Fix $c \in \N$, Suppose $L \in NTIME(n^c)$, then $\exists M$ (NDTM), s.t $M(x) = 1 \iff x \in L$. If $M(x) = 1$ in less than $T(n) = n^c$ steps, then there exist $|(a_i)n| \leq |x|^c$, where $\delta{a_i}$ is an accepting sequence. Take $M'(x, u)$, where $|u| \leq |x|^c$, where $M'$ emulates $M$ with $\delta_{u_i}$ for step $i$ in computation, and $L \in NP$
Reducibility / NP-completeness
- How to prove that $L_1$ is at least as hard as $L_2$, i.e $M_{L_1} \rightarrow M_{L_2}$
- reduction
  - Language $A \subset {0,1}^$ is polynomial-time Karp reducible to $B \subset {0,1}^$ ($A \leq_p B$), if t.e $f : {0,1}^* \rightarrow {0,1}^*$, s.t $x \in A \iff f(x) \in B$
    - NP-hard - B is NP-hard, if $\forall A \in NP$, $A \leq_p B$
      - $B$ is at least as hard as any other language in $NP$
    - NP-complete - If $B$ is NP-hard, and $B \in NP$
- theorem
  - If $A \leq_p B \land B \leq_p C \to A \leq_p C$
    - Suppose $A \leq_p B$ and $B \leq C$, then $\exists f_B, f_C : {0,1}^* \leq {0,1}^*$, s.t $x \in A \rightarrow f(x) \in B$, and $x \in B \rightarrow f_C(x) \in C$, thus $x \in A \rightarrow f_C(f_B(x)) \in C$, and $A \leq_p C$
  - If $A$ is NP-hard, and $A \in P$, then $NP = P$
    - Suppose $A$ is NP-hard, and $A \in P$, then fix $L \in NP$, then $L \leq_p A$, as such, $f : {0,1}^* \rightarrow {0,1}^*$ exists, where $x \in L \iff f(x) \in A$. Consider $M_L$, where $M_L(x)$ computes $f(x)$, and applies $M_A(x)$, and outputs $M_A(f(x))$, and $M_L \in P$, thus $NP \subset P$
  - If $A$ is NP-complete, then $A \in P \iff NP = P$
    - Converse - Triv, $A \in NP = P$
    - Forward
      - Suppose $A$ is NP-complete + $A \in P$ (apply thm. above)
- theorem
  - TMSAT is NP-complete
  - $TMSAT = {(\alpha, x, 1^n, 1^t) : \exists u \in {0,1}^n \ni M_{\alpha}(x, u) = 1 \text{ within t steps}}$
    - NP-hard
      - I.e show $f$, such that $x \in L \iff f(x) \in TMSAT$, and $f$ is poly. time constructible
      - Fix $L \in NP$, then $\exists M$ (TM), where $x \in L \iff \exists u \in {0,1}^{p(|x|)}, M(x, u) = 1$, then $f(x) = (\lfloor M \rfloor, x, 1^{p(|x|)}, T(|x|)) \in TMSAT$. How to show that $f$ is poly. time constructible?
    - $TMSAT \in NP$
      - Take $M$ as universal TM, and witness as $u$ for $M_{\alpha}$
      - $n$, $t$ may not be poly. in $|x|$? No actually, always will be $c = 1$ linear fn. of length of input
- Cook-Levin THeorem
  - Boolean Formulae + CNF
    - let $\phi : {0,1}^* \rightarrow {0,1}$, then $\phi(u_1, \cdots, u_n) = \bigwedge_i \pi_i$, where $\pi_j = (\bigvee_i u_i)$ (i.e and of ors of variables), each sub-formula may consist of variable or negation (CNF)
      - If $\exists z \in {0,1}^*, \phi(z) = 1$, then $\phi$ is satisfiable
    - expressiveness of boolean formulae
      - For every $f : {0,1}^l \rightarrow {0,1}$, there is an $l$-variate CNF $\phi$ of size $l 2^l$
        
        Let $C_v(u) = v == u$ (notice can be constructed in literal via) $C_v = \bigvee_i \bar{u}i$, let $\mathcal{S} = {u \in {0,1}^l : f(u) = 0}$, $\mathcal{C} = \bigwedge{s \in \mathcal{S}} C_s$
    - Cook-Levin Theorem
      - SAT (set of satisfiable CNF) / 3SAT (set of satisfiable CNF w/ only 2 conjunctions) are NP-complete
        
        NP-hard
        
        Have to display Karp Reduction for arbitrary $L \in NP$
        
        SAT is NP-hard
        
        Fix $L \in NP$, then must construct $f(x) = \phi_x$, s.t $x \in L \iff \phi_x \text{is satisfiable}$
        
        Can use $M_L$ and construct $\phi_x$ s.t certificate for $M_L$ satisfies $\phi_x$?
        
        Notice, $\exists, M_L$, such that $x \in L \iff \exists u \in {0,1}^{p(|x|)}$, thus take $\phi_x = M_L(x, \cdot) : {0,1}^{p(|x|)} \rightarrow {0,1}$
        
        This is incorrect, as transformation is of size $O(2^{|p(x)|})$ (not poly. time constructible)
        
        How to make smaller CNF from $M_L$?
        
        Consider snapshots (i.e state + input / output read), and function mapping snapshot to next snapshot
        
        Transform $M_L$ to be oblivious
        
        advantage, head movement only determined by input-size / step in computation, still $T(M_L) \leq n^c$ (for some $c$)
        
        Let $inputpos(i) \in \Sigma$ denote the input symbol at step $i$
        
        $prev(i)$ denote the last step that the head was at the same pos. as step $i$
        
        Then $z_i = F(z_{i - 1}, z_{prev(i)}, inputpos(i))$
        
        i.e next config. depends on current-state, current symbol on work-tape (determined by prev. configuration ) + input\
        
        Must verify relation $z_1, \cdots, z_T$ satisfy above,
      - SAT is reducible to 3-SAT
    - NP
      - Naturally, $u \in {0,1}^*$ is a witness to $\phi$ (evaluation of CNF in poly. time?), length of witness clearly sub linear in size of CNF formulation. Evaluation linear in size of each literal (maximally size of input)
Decision vs. Search
- If $NP = P$, then for $L \in NP$, t.e pTM, $M_L'$ s.t $M_L(x, M_L'(x)) = 1$ (i.e poly. time to output certificate)
  - Show for SAT
    - Suppose $A$ decides SAT, i.e $A(\phi) = 1 \iff \phi \in SAT$, then construct $B$ s.t on $\phi$ (assume as $n$ input), outputs $u$ (satisfying assignment) in $2n + 1$ calls to $A$
      - For each input $i$, call $\phi_i(0) = \phi(0, x_{i + 1}, \cdots, x_n)$ if decidable use $A$ on $\phi_i$ continue
- Use $f$ (Cook-Levin reduction for $L$), i.e $f(x) = \phi_x$ is poly. time computable, use $A$ + above algorithm to get $(2n + 1)T(SAT)$ time algo. $M$ for generating certificates
- SAT is downward self reducible
  - Given algo. for solving inputs on length $\leq n$, can solve on inputs of length $n + 1$

Alternative Complexity Classes

coNP
- Let $L \subset {0,1}^$, then $\bar{L} = {0,1}^ \backslash L$
  - $coNP = {L : \bar{L} \in NP}$
  - Alternative
    - $L \in coNP$ if $\exists p : \N \to \N$ and PT $M$ (TM), s.t $x \in L \iff \forall u \in {0,1}^{p(|x|)}, M(x, u) = 1$
  - Reductions
    - $L = {\phi : \text{satisfied by all inputs}}$
    - coNP completeness?
      - $L \in coNP$
        
        $\bar{L} = {\phi : \exists u \in {0,1}^*, \bar{\phi} = 1}$
      - $\forall L' \in coNP, L' \leq_p TAUTOLOGY$
        
        Fix $L' \in coNP$, consider $\phi_x \in SAT \iff x \in \bar{L'}$ (LEVIN transform to SAT CNF), then consider $\bar{\phi_x} \in L$
EXP
- $EXP = \bigcup_{c \geq 0}DTIME(2^{n^c})$
NEXP
- $NEXP = \bigcup_{c \geq 0} NTIME(2^{n^c})$

problems

NDTM analog of $\mathcal{U}$?
- Add additional tape $\delta_1$, $\delta_2$, and have transition fn. randomly choose which to apply
  - I.e adapt $\mathcal{U}$ w/ extra tape for $\delta_2$, random transition fn. for $\mathcal{NU}$ determines which transition fns. to reference
- More efficient?
Halting problem NP?
- Let $Halt = {(\alpha, x) : M_{\alpha}(x) \text{halts}}$
  - Show $NP-hard$
    - Fix $L \in NP$, then define $f : {0,1}^* \rightarrow {0,1}^*$, such that $x \in L \iff f(x) = (\alpha, x) \in HALT$
      - Notice, $\exists M_L$, s.t $x \in L \iff \exists u \ni M_L(x, u) = 1$, then $\alpha = \langle M'_L \rangle$, where $M'_L$ generates all possible $u$, and executes $M_L$, and halts if $M_L(u, x) = 1$
  - Show $NP-complete$
    - Not NP-complete, otherwise halting problem is in $DTIME(2^{n^c})$ and is computable :(
$L_1, L_2 \in NP$, $L_1 \cup L_2 \in NP$, $L_1 \cap L_2 \in NP$
- $L_1 \cup L_2$
  - Let $M_{L_1}$ be the machine s.t $x \in L_1 \iff \exists u \in {0,1}^{p(|x|)}, M_{L_1}(x, u) = 1$, similarly for $M_{L_2}$, thus define $M_{L_1 \cup L_2 }$, which runs $M_{L_1}(x, u)$, and $M_{L_2}(x, u)$ if the first execution fails (poly. time algo. + poly. sized witness)
- $L_1 \cap L_2$
  - Define analogously
Reflexivity of $\leq_p$
- Notice $\forall L \in NP$, $L \leq_p HALT$, suppose that $\leq_p$ is reflexive, then $HALT \leq L$, thus $\exists f \ni x \in HALT \iff f(x) \in L$, thus taking $M_{HALT}$ to compute $f$ then $M_L$ (taking as DTM in $EXP$), and HALT is computable (contradiction)
$NP = coNP \iff 3SAT \leq_p TAUTOLOGY$
- Forward
  - Suppose $NP = coNP$. Triv...., $Taut \in NP \rightarrow Taut \leq_p 3SAT$ (3SAT is NP-hard), $3SAT \in coNP \rightarrow 3SAT \leq_p TAUT$
- Reverse
  - Suppose $Taut \leq_p 3SAT$, and $3SAT \leq_p Taut$. Triv, fix $L \in coNP$, then $x \in L \iff f(x) \in 3SAT$, then $M_{Taut}$ which computes $f(x)$, and applies $M_{3SAT}(f(x), u)$ is the TM for NP, vice-versa
$P \subseteq NP \cap coNP$
- $L \in P$, then $\overline{P} \in P$ (i.e use $\overline{M_L}$), thus $\overline{P} \in NP$, and $P \in coNP$
Suppose $L_1, L_2 \in NP \cap coNP$, then $L_1 \otimes L_2 \in NP \cap coNP$
- Where $L_1 \otimes L_2 = {x : (x \in L_1 \land x \not \in L_2) \lor (x \in L_2 \land x \not \in L_1)}$
- $L_1 \otimes L_2 \in NP$
  - consider $L_1 \cup \overline{L_2}$
    - First execute $M_{L_1}$ w/ witness for $M_{L_1}$ if it exists, or for $M_{L_2}$ w/ witness if it exists, and if $x \in L_2$, then output no
  - Similar case as above

Diagonalization

Mechanism for separating Complexity Classes
- i.e construct $M$ in some class $\mathcal{C}$ s.t $M$ gives diff. answer than every machine $M'$ in class $\mathcal{C}'$, thus if $\mathcal{C} = \mathcal{C'}$, then $M_L \in \mathcal{C}'$, however, if $M_L', L' \in \mathcal{C}', M_L' = M_L$ (contradiction)
time-hierarchy theorem
- Allowing TMs more computation time strictly increases set of decidable languages
- If $f, g : \N \to \N$, and $f(n)log(f(n)) = o(g(n))$, then $DTIME(f(n)) \subset DTIME(g(n))$
  - Let $D$ be the machine where on input $x \in {0,1}^*$, runs $1 - \mathcal{U}(M_x, x)$ for $f(|x|)log(|x|)$ steps (if $M_x$ does not halt in time, then output 0), notice, $L = {x: D(x) = 1} \in DTIME(g(n))$. Suppose $L \in DTIME(f(n))$ then $M$ decides $L$, which on input $x$, runs for $c|x|$ timesteps, Thus $D$ which executes $\mathcal{U}$ coincides with $M$, i.e $\forall x \in L, D(x) = M(x)$, choose $|\langle M \rangle| = n$, then $D(\langle M \rangle) = 1 - M(\langle M \rangle)$ which does not coincide with $M(\langle M \rangle)$
space-hierarchy theorem
- space-constructible fn
  - I.e $f: \N \to \N$, s.t $\exists M_f$, where $M(x) = f(x)$, and uses maximally $f(x)$ memory cells
- $f, g$ are space constructible, and $f(n) = o(g(n))$, then $SPACE(f(n)) \subset SPACE(g(n))$
  - $\mathcal{U}$ uses constant time space for simulating $M$
Non-deterministic Time Hierarchy Theorem
- $f, g$ are TC, where $f(n + 1) = o(g(n))$
  - $NTIME(f(n)) \subset NTIME(g(n))$
    - Alternatively, show that $DTIME(2^{f(n)}) \subset DTIME(2^{g(n)})$, not necessarily clear that $log(2^{cf(n)})2^{cf(n)} = cf(n)2^{c(f(n))} = o(2^{g(n)})$ (apply deterministic time-hierarchy)
- Applying results from deterministic Time hierarchy won't work
  - i.e - simulation requires $2^{O(f(n))}$ sims (one for each possible witness), certainly not in $NTIME(g(n))$
- lazy diagonalization
  - Only have to flip on one output (don't have to determine $\overline{L}, \forall L \in NP$)
  - Goal: Define $D \in NTIME(f(n))$, s.t forall $L \in NTIME(f(n))$, $\exists x \in {0,1}^*, D(x)\not= M_L(x)$ (i.e $D$ differs from all $M_L$ on some input)
  - Define some fn. $h : \N \to \N$, where $h(1) = 2$, and $h(i + 1) = 2^{f(h(i) + 1)}$
    - Assuming $f$ is monotonically increasing, goal is to map intervals $(h(i - 1), h(i)] \to M_i$ (NDTMs running in time $f(n)$)
    - Thus for each possible input,
  - Define $D$ (decision process used for diag.), where on input $x, x \in 1^*$ (otherwise, reject)
    - If $h(i - 1) < |x| < h(i)$ (that one can find such a $i$ is triv.) find corresponding $M_i \in NTIME(f(n))$, and return $M_i(1^{|x| + 1})$, execute non-deterministically, otherwise, reject (notice, shld halt in time allocated)
      - Notice, $\mathcal{NU}$ simulates NDTM $m$ in $Ct$ steps
    - If $|x| = h(i)$, deterministically execute $1 - M_i(h(i -1) + 1)$
      - Notice, execution here takes $2^{O(f(h(i - 1) + 1))}$, thus on input, $|x| = h(i)$ (have to define bounds on g, f, s.t $g(h(i)) \geq 2^{f(h(i -1) + 1)}$)
  - Contradiction follows if $M \in NTIME(f)$, where $M = D$ (notice, take $D(\langle M \rangle)$)
    - Then find $i$, where $M_i = M$ (from above), and execute w/ inputs $|x| \geq h(i)$, then $M(1^n) = M(1^{n + 1})$, thus $M(1^{h(i) + 1}) = M(1^{h(i + 1)}) \not= D(1^{h(i + 1)})$ (contradiction)
  - Have to assume that $f$ is super-linear?
Ladner's Theorem
- Suppose $P \not= NP$, then $\exists$ $L \in NP \backslash P$ that is not-NP complete
  - i.e $L$ is not NP-hard, i.e $\exists L' \in NP$, where $L' \not\leq_p L$
- $SAT_H = {\phi 0 1^{n^{H(n)}}: \phi \in SAT \land n = |\phi| }$
- Define $H : \N \to \N$
  - $H(n) = i$, where
    - minimize $i < log (log (n))$, where $\forall x \in {0,1}^*, |x| \leq log(n)$, $M_i$ outputs $SAT_H(x)$ within $i|x|^i$ steps
    - If no such $i$ exists, set $H(n) = log(log(n))$
      - I.e if $SAT_H \in P$, there is some $i$ for which $M_i = SAT_H$, thus, $H(n) = i, \forall n \geq 2^{2^i}$, i.e $H(n) = O(1)$
      - If $SAT_H \in NP$, then $H(n)$ increases w/o bound
- Proof
  - $SAT_H \in P$
    - Then $SAT \leq_p SAT_H$ (i.e each $\phi \in SAT \iff \phi0 1^{n^c} \in SAT_H$), and $P = NP$ (contradiction)
  - $SAT_H$ is NP-complete
    - Then $SAT \leq_p SAT_H$, i.e there is $f, \phi \in SAT \iff f(\phi) \in SAT_H$. If $SAT_H \in P$, then $|\phi| \rightarrow \infty$ (otherwise, there exists $c$, where $M_i = SAT_H$, and runs in time $c x^c$).
- Alternative construction
  - Define $L = {x| x \in SAT \land 2 | f(|x|)}$
    - Define $f$. $\exists y, \forall_{x \geq y} f(x) = c$
      - If $c$ is even, then there are infinitely many $x$, i.e $x, |x| \geq y$ where $x \in L$, thus, $L \in SAT$, $L$ is $SAT\backslash$ finitely many $\phi$
      - If $c$ is odd, then $L \in P$, i.e there are only finitely many $x \in SAT, x \in L$, each $x$ can be evaluated in $P$ time
    - Thus must define $f$, where
      - $L \in P \rightarrow 2 | c$, thus $L \in NP$, notice, $SAT \leq_p L$, thus $NP = P$
      - $L$ is NP-complete, then $f$ gets stuck on odd $c$, thus $NP = P$
    - Let $M_i$ be enumeration of TMs where $M_i$, runs in $x^i$ steps, and $g_i$ be poly. reductions to SAT
      - $f(n -1) = 2i$
        
        if $\exists x, |x| < log(n)$ where $M_i(x) \not= L(x)$, then $f(n) = f(n - 1) + 1$, otherwise $f(n) = f(n - 1)$
        
        Notice if $L \in P$ then some $M_i = L$, thus, this case is reached for some $n$, and $L \in NP$ (contradiction)
      - $f(n - 1) = 2i + 1$
        
        If $\exists x, |x| < log(n)$ where $SAT(x) \not = L(g_i(x))$, then $f(n) = f(n - 1) + 1$, otherwise $f(n) = f(n - 1)$
        
        If $L \in NP$, then $SAT \leq_p L$, thus there exists some $g_i$ reduction, and $f(n) = c$ (which is odd), thus $L \in P$
    - Use bound of $log(n)$ to ensure that $f$ is poly. time computable?
      - Doesn't really matter anyway, in either case, there is infinite repetition and theorem holds
Oracle Machines
- oracle Turing Machines -****
problems
- Show that the following language $L = {\langle M \rangle : M \text{ runs in time } 100n^2 + 200n }$
  - Let $M$ be a machine deciding $L$, then fix $M'$ where $M'(x)$ takes $100n^2 + 200$ time, if $M(\langle M' \rangle) = 0$, and vice. versa. if not, thus $M(\langle M \rangle) = 1 \rightarrow$ $M'$ does not halt in $100n^2 + 200$ time (contradiction)
  - Construction of $M'$
    - Execute $M$ on $M'$, for each input (only for large enough input)? i.e input of size $T(M(\langle M' \rangle))$ (does not affect over-all runtime)
      - Only need to find single input
- $SPACE(n) \not= NP$
  - $NP \subset \bigcup_{c \in \N} SPACE(n^c)$
  - Diagonalization?
  - Suppose $SPACE(n) = NP$
    - Choose $L \in SPACE(n) \cap NP$, then fix $M_L'$, which on $x$, for each write to work-tape, pads write w/ $|x|, 1s$ (runtime only increased by factor of $n$), but space used is $n^2$

Space Complexity

Let $S : \N \to \N$, and $L \subset {0,1}^*$, then $L \in SPACE(S(n))$ (resp. $L \in NSPACE(S(n))$) if $\exists M$ a $TM$ (resp. NDTM) s.t execution on $x$ takes at most $c |x|$ tape cells
- All branches of NDTM halt
- $S$ must be space constructible, i.e $\exists M$ (TM) computing $S$ requiring $S(n)$ tape cells (at most)
  - Analog to TC bounds, i.e TM can understand bounds it is operating under
$DTIME(S(n)) \subset SPACE(S(n))$
- TM can re-use tape-cells, any TM / NDTM can only access one tape cell per time-step
$DTIME(S(n)) \subset SPACE(S(n)) \subset NSPACE(S(n)) \subset DTIME(2^{S(n)})$
- Configuration Graphs
  - Sequence of objects, where each object contains
    - Contents of all non-blank tape entries
    - state + head pos.
- Configuration Graphs
  - Each node is configuration, edges between configurations reachable via single step of $\delta$
    - DTM has out-degree 1
    - NDTM has out-degree 2
Let $G_{M, x}$ be the CG of a space-$S(n)$ machine $M$ on input $x, |x| = n$
- Does it matter if $M$ is TM or M?
$G$'s nodes can be described in $cS(n)$ bits
- i.e given alphabet $\Sigma$, then $c = log_2(|\Sigma|)$ (convert alphabet into bits)
- State + head map to constant size bit string?
  - Max number of states?
$G_{M, x}$ has at most $2^{cS(n)}$ nodes
- Triv. $2^{cS(n)}$ combinations of configurations (possible cycles in configuration graph?)
$$NSPACE(S(n)) \subset DTIME(2^{S(n)})$$
- Construct configuration graph in $2^{(O(S(n)))}$ time (size of CG bound above), and search for path from start to accept

$$NP \subset PSPACE$$

Notice, $3SAT \in PSPACE$, where $n$ is size of $\phi \in 3SAT$ execute $\phi$ on all $x \in {0,1}^k$ ($\phi$ is over $k$ variables).
- Notice $3SAT$ is NP-complete, thus if $L \in NP$, then there exists $f$, s.t $x \in NP \iff f(x) \in 3SAT$
Use same idea for $L \in NP$, take $M_L$ and execute $M_L(x, \omega)$ for each possible witness, erasing $\omega$ after checking

Space Hierarchy Theorem

If $f,g$ are spac -constructible where $f(n) = o(g(n))$, then $SPACE(f(n)) \not \subset SPACE(g(n))$

Randomized Computation

Probablistic Turing Machines

Analogous to TMs for NDTMs / DTMs
Probablistic Turing Machine
- TM w/ $\delta_0, \delta_1$ transition fns. take each w/ prob. 1/2, thus on $x$, PTM $M$ has $2^{T(|x|)}$ outputs each w/ equal prob.
  - Define acceptance via. prob of ending in accepting state.
  - NDTM simply needs single possible accepting state
BPTIME / BPP
- Let $L$ be a language and $T: \N \rightarrow \N$, then PTM $M$ decides $L$ in $T(n)$ time if, it takes $T(n)$ steps (regardless of any sequence of choices of $\delta_i$), and $P[M(x) = L(x)]geq 2/3$
  - $BPTIME(T(n))$, $BPP = \bigcup_{c > 0} BPTIME(n^c)$
$P \subset BPP \subset \bigcup_c DTIME(2^{n^c})$, $BPP \not \subset NP$ (possible $x\not \in L$ w/ certificate)
- Create DTM which generates $\delta_i$ choices at $T(n)$ steps, and executes PTM $M(x, \delta_i ...)$
examples
- Finding median (sort + index) $O(nlog(n))$ time (Merge-sort)
  - Can use BPP algorithm for $O(n)$ time
  - Given $(a_1, \cdots, a_n)$ find $k$-th largest element, median is $\lfloor n/2 \rfloor$ largest
    - Randomly choose $a_j$ in list, Let $A_{<} = {a \in (a_i), a < a_j }$
    - If $|A_{<}| < k$
      - Find $k - |A_{<}|$-largest element of $A \backslash A_{<}$
    - Otherwise
      - Perform same algo. on $A_{<}$
  - complexity
    - Take $T(n) = max(T(k, a_1, \cdots, a_n))$ (i.e time complexity for lists on len $n$)
    - Then $cn$ is complexity of search step (linear time)
      - Recursive steps on lists len $< n$ assume $10cn$ time (recursive assumption), thus
  - $T(n) \leq cn + \frac{1}{n}(\Sigma_{j > k} j + \Sigma_{j < k} T(n - j))$ (apply recursive assumption and simplify)
- Primality Testing
  - Given $N \in \mathbb{Z}$ want to determine if $N$ is prime

One Sided / Zero-Sided Error

two sided error
- $M \in \mathcal{BPP}$, where $x \in L, M(x) = 0 \land x' \not \in L, M(x') = 1$
  - i.e possible false negatives + positives
one sided error
- Most BPTIME $M$, will output $M(x) = 0 \iff x \not \in L$ (never false positive), but prob of $M(x) = 0 \land x \in L$ (i.e prob of false negatives)
- Known as $RPP$
  - $x \in L \rightarrow Pr[M(x) = 1] \geq \frac{2}{3}$
  - $x \not \in L \rightarrow Pr[M(x) = 0] = 1$
- Thus $RP \subset NP$ (i.e no certificates for $x \in L$)
- $RP \subset BPP$
- $coRP = {L : \overline{L} \in RP }$
PTMs that never err
- Always output correctly, but $T_{M, x}$ is random variable describing time taken over random choices of $M$ on $x$, then $T(M) = E[T_{M,x}]$
$ZPP = RP \cap coRP$
- Forward
  - $L \in ZPP$, then $L \in RP \cap coRP$, i.e take $M_L$
    - And $x \in L \iff Pr[M_L(x) = 1] = 1 \geq \frac{2}{3}$ $ZPP \subset RP$
    - Then for $\overline{L}$ take $\overline{M_L}$, i.e $x \not \in \overline{L} \rightarrow x \in L \rightarrow M_L(x) = 1 \rightarrow \overline{M}_L(x) = 0$
- Reverse
  - $L \in RP \cap coRP$
    - Then $M_{RP}, M_{coRP}$ exist, have $M = \overline{M_{RP}} \lor \overline{M_{coRP}}$
      - i.e $x \in L \rightarrow M_{coRP} = 0 \rightarrow M(x) = 1$
      - $x \not \in L \rightarrow M_{RP} = 0 \rightarrow M(x) = 0$

Randomized Reductions

reductions
- Language $B$ reduces to $C$, i.e $B \leq_r C$ if $\exists$ TM $M$, where $\forall x \in {0,1 }^*, Pr[B(M(x)) = C(x)] \geq 2/3$
  - I.e $f$ analog in deterministic reductions is now probablistic

Interactive Proofs

CRS (Blum, Feldman, Micali)

Zero-knowledge proof -> replaced by common random string
components of proof
- Interaction
- Hidden Randomization
- Computational Difficulty
Verifier utilizes Interaction + Hidden randomization -> Force non-adaptivity of prover
- Prove global properties (rather than local (can be forged))
Prover utilizes Computational Difficulty
- Prevent Verifier from learning anything
Indistinguishability

GGPR

Use PCPs to construct Interactive-proofs for NP, verification in time poly-log in input size
Use ECRHs (extractable CRHs) instead of random-oracles to enable knowledge-extraction. i.e given $h(w)$ there exists an algorithm to determine $w$
- SNARGs of knowledge (SNARKs)
- possible knowledge extraction of PCP (witness) to NP TM $M$
QSPs
- Characterization of NP that allows construction of efficient SNARKs w/o PCPs
- Span Programs
  - SP over field $F$ consists of $t \in F^m$ (target vector), ${v_1, \cdots, v_n} \in F^m$, and partition of indices $\mathcal{I}{free}, \mathcal{I}{labelled}$
    - Further partition of $\mathcal{I}{labelled} = \bigcup{i \in {0,1}^n} \mathcal{I}_i$
  - Computes $f : {0,1}^n \rightarrow {0,1}$, if $\forall u \in {0,1}^n$, $t \in \mathcal{I}{free} \bigcup{i} \mathcal{I}_{i, u_i}$
- QSPs
  - $Q$ over $F$, contains two sets of polynomials $\mathcal{V} = {v_k(x) : k \in {0, \cdots, m}}, \mathcal{W} = {w_k(x) : k \in {0, \cdots, m}}$, and $t \in F[X]$, and partition of indices $\mathcal{I} = {0,\cdots, m}$, into $\mathcal{I}{free}, \mathcal{I}{labeled} = \bigcup_{i \in \mathbb{Z}n , j \in {0,1}} \mathcal{I}{i, j}$
  - for $u \in {0,1}^n$, let $\mathcal{I}u = \mathcal{I}{free} \cup \bigcup_{i \in \mathbb{Z}n} \mathcal{I}{i, u_i}$
    - $Q$ computes $f : {0,1}^n \rightarrow {0,1}$, iff $\forall u, f(u) = 1$, $\exists (a_1, \cdots, a_m), (b_1, \cdots, b_m)$, where $a_k = b_k = 0, k \not \in \mathcal{I}u$, s.t $$ t(x) | (v_0 + \Sigma{k = 1}^m a_k v_k(x))(w_0 + \Sigma_{k = 1}^m b_k w_k(x))$$
    - I.e target vector is in ideal generated by $v_k, w_k$

Quadratic Span Programs

Construction of QSP $Q$ for function $f$
- Given $C$ circuit supposedly computing $f$, can construct SP that verifies an assignment of $C$'s wires (a la NP-deterministic verifier)
  - Notice, SP has non-free vectors for internal wires of $C$, i.e it does not compute $C$ rather it checks its computation
- I.e given assignment of internal wires that are non-conflicting, $S$ checks that the assignment is valid for given input
construction of SP (circuit-checker)
- Let $f : {0,1}^n \rightarrow {0,1}$, where $C_f$ has $s$ gates, let $\phi : {0,1}^{n + s} \rightarrow {0,1}$ that given an assignment of $C$'s wires (i.e value at each gate) is valid (i.e results from the input $u$)
- Suppose that gates in $C$ come from finite set $\Gamma$ (eg ${AND, OR, NAND, XOR, \cdots}$), suppose that for each $g \in \Gamma$ there is SP $m'$ that determines given input / output assignments, if they are consistent, i.e $m(x_1, x_2, x_3) = 1 \iff x_1 \land x_2 = x_3$
- Given $C$, and $m_i$ ($|\Gamma|$ possible SPs), there is SP $S$ computing $\phi$ of size $s * m$ (for each gate need sub-SP)
- construction ($N = n + s$)
  - assumptions
    - Each gate $g \in gates(C)$ has two inputs $g_l, g_r \in {0,1}$, and output $g_0 \in {0,1}$ (also used as indices of assignments in input to $\phi$), notice is $g$ is a feeder into $g'$, then $g_o = g'_l$ (i.e there is a wire between them)
      - let $m^{(g)}, d^{(g)}$ denote the rows / columns of $S_g$, i.e $|\mathcal{I}{free} \cup \mathcal{I}{labeled}| = m$, ($m$ possible vectors) $S_g$, and $\mathcal{V}_g \subset F^{d^{(g)}}$ (each vector has dimension $d^{(g)}$)
  - $S = (t, \mathcal{V}, \mathcal{I}{free}, \mathcal{I}{labelled})$
    - $|\mathcal{V}| = \Sigma_{g}m^{(g)}$, and $\mathcal{V} \subset F^d, d = \Sigma_g d^{(g)}$
    - Can view $\mathcal{I}{free} \cup \mathcal{I}{labelled}$ as a $m \times d$ matrix
      - Each $S_g$'s vectors will be composed of first $m^{(g)}$ rows, and $d^{(g)}$ columns (i.e $S$'s matrix is sparse)
    - Consider the sub-matrix of $S$, for $S_g$, consider $\mathcal{I}{free} \cup \mathcal{I}{labelled} = \bigcup_{i \in {g_r, g_l, g_o}, j \in {0,1}} \mathcal{I}_{ij}^{(g)}$
  - For $S$, $t = t^{g_1} | \cdots | t^{g_s}$
    - If $v_k \in \mathcal{I}^{(g)}$, then $\hat{v}_k \in \mathcal{I}_S$, is $v_k$ but holding $0$s in all columns of $S$ not owned by $g$
  - Proof
    - Take $x, \phi(x) = 1$, then for each $g \in C$, with input $x_{g_l}, x_{g_r}, x_{g_o}$, there is a lin comb. of vectors in $\mathcal{I}{free}^{(g)} \cup \mathcal{I}{g_l, x_{g_l}}^{(g)} \cup \mathcal{I}{g_r, x{g_r}}^{(g)} \cup \mathcal{I}{g_o, x{g_o}}^{(g)}$ that equals $t^(g)$, taking the combination over all of these combinations yields $t$
    - Similarly if $\phi(x) = 0$ there is no such combination...
- Translation of SP to polynomials
construction of QSP (Consistency Checker)
- Since the QSP is computing $f$, it must be the case that the interior wires can be used as free vectors (how to ensure that choice of free vectors is internally consistent w/ circuit)?
  - QSP checks consistency of free vectors (i.e internal wires)
- Let $S = (t, \mathcal{V} = (v_1, \cdots, v_m), \mathcal{I}{free}, \mathcal{I}{labeled})$
  - suppose $S$ has dimension $d$, fix $r_1, \cdots, r_d \in F$, set each $\hat{v_k} \in F[X], deg(\hat{v_k}) = d -1$, where $v_k(r_i) = v_{k_i}$ (i.e LGP on $r_i$), let $t(x) = \Pi_i (x - r_i)$, and $v_0(r_i) = -t_i$, then $S_{poly} = (t(x), \mathcal{V} = (v_0, \cdots, v_m), \mathcal{I}{free}, \mathcal{I}{labeled})$
    - Where $S$ is sat iff $\exists (a_1,\cdots,a_m)$ where $t(x) | v_0(x) + \Sigma_k a_k v_k(x)$
      - i.e $v(x) = v_0(x) + \Sigma_k a_k v_k(x) = p(x) * \Pi_i (x - r_i)$, suppose $S$ is satisfied by $(a_i)$, then $-t + \Sigma_k a_k v_k = 0$, thus $\forall r_i, v(r_i) = v_0(r_i) + \Sigma_k a_k v_k(r_i) = 0$, and $t(x) | v(x)$
- consistency checker
  - Why do we need this?
    - Double assignment, let $\mathcal{I}{i0}, \mathcal{I}{i1} \in \mathcal{I}{labelled}$, then for $\exists k_1 \in \mathcal{I}{i1} a_{k_1} \not =0, \forall k_0 \in \mathcal{I}{i0}, a{k_0} = 0$
  - weak version, single assigment from either set
  - Fix $L$, let $\mathcal{I}_0 = {1, \cdots, L}, \mathcal{I}_1 = {L + 1, \cdots, 2L }$, let $\mathcal{I} = \mathcal{I}_0 \cup \mathcal{I}_1$
    - Consistent, fix bit $B$, ${a_k}, {b_k}$ are consistent if, $a_k = b_k = 0, \forall k \in \mathcal{I}_{\overline{B}}$ (i.e a_k, b_k are assigned non-zero values in same partition of $\mathcal{I}$)
    - Non-consistent
      - $\exists k_0 \in \mathcal{I}0, k_1 \in \mathcal{I}1, a{k_0} \not= 0, a{k_1} \not= 0$, and $\exists k, b_k \not = 0$
      - $\exists k_0 \in \mathcal{I}0, k_1 \in \mathcal{I}1, b{k_0} \not= 0, b{k_1} \not= 0$, and $\exists k, a_k \not = 0$
- construction (for single wire)
  - Fix $L' = 3L - 2$, select $\mathcal{R}^{0} = {r_1, \cdots, r_{L'}}, \mathcal{R}^{1} = {r'1,\cdots, r'{L'}}$, and $\mathcal{R} = \mathcal{R}^0 \cup \mathcal{R}^1$, let $t(x) = \Pi_{r \in \mathcal{R}} (x - r)$
  - Consider ${a_i}, {b_i}$, checker is
    - $t(x)$, $\mathcal{V} = {v_k(x) : k \in \mathcal{I}}$, and $\mathcal{W} = {w_k(x) : k \in \mathcal{I}}$, where $$ t(x) | (\Sigma_{k \in \mathcal{I}} a_k v_k(x)) (\Sigma_{k \in \mathcal{I}} b_k w_k(x))$$
    - Forall $v \in \mathcal{V}, \mathcal{W}, deg(v_k) = deg(w_k) = L' + L -1$
      - For $k \in \mathcal{I}_0$, $v_k(r) = 0, \forall r \in \mathcal{R}^0 \cup {r_1^{(1)}, \cdots, r_L^{(1)}}$, except $v_k(r^{(1)}_k) = 1$
        
        $w_k(r) = 0, \forall r \in \mathcal{R}^{1} \cup {r_1^{(0)}, \cdots, r_L^{(0)}}$, and $w_k(r_k^{(0)}) = 1$
    - For $k \in \mathcal{I}_1$, $v_k(r) = 0 \forall r \in \mathcal{R}^{(1)} \cup {r^{(0)}1, \cdots, r^{(0)}L}$, and $v{k - L}(r{k -L}^{(0)}) = 1$
      - $w_k(r) = 0, \forall r \in \mathcal{R}^{(0)} \cup {r_1^{(1)}, \cdots, r_L^{(1)}}$ and $w_{k - L}(r^{(1)}_{k -L}) = 1$
  - Checks to consider?
    - Two assignments of same series in conflicting wires
    - Two assignments of diff series in conflicting wires
    - Non-conflicting assigment

PLONK

definitions
- Assume $F$ is field of prime order, i.e $\mathbb{Z}$ mod prime-ideal
- $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t$ grps of size $r$, and $e$ is efficiently computable + non-degenerate pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_t$, $g_1 \in \mathbb{G}_1, g_2 \in \mathbb{G}_2, e(g_1, g_2) = g_t \in \mathbb{G}_t$
- Algebraic Group Model

Files

crypto.md

Latest commit

History

crypto.md

File metadata and controls

Public Key Crypto

RSA

Algorithms

Powering Algorithms

Euclidean Algorithms

Euclid Extended Algorithm

Basic Defn.

Shannon Cipher + Perfect Security

Definition

Computational Ciphers + Sematic Security

Semantic Security Attack Game

Computational Security

New Directions in Crypto.

One Way Functions

PRGs

Computational Security

Proofs, Arguments, and Knowledge

Definitions + Technical Prelims

Let $f : {0,1}^v \rightarrow \mathbb{F}$ has a unique multi-linear extension over $\mathbb{F}$

problems

Interactive Proofs

Sum-check Protocol

Application of sum-check: $#SAT \in IP$

GKR

Algorithm

How to transform IP to PVPQ

Computer Programs -> Circuits

Circuit Satisfiability Problem

Transformation (Circuit -> CSAT)

Representing Transition Function

Representing Memory Consistency

Sorting?

Succint Arguments

Arguments of Knowledge + SNARKs

First Argument

What does $\mathcal{V}$ need to know about $\tilde{w}$

Knowledge Soundness

Low Degree Tests

MIPs / Succint Arguments

Second Prover?

Why non-adaptivity

MIP for C-SAT

Succint Argument For Deep Circuits

Circuit-SAT -> R1CS-SAT

MIP for R1CS-SAT

PCPs and Succint Arguments

MIP -> PCP

PCP -> succint argument?

Witness Extraction of PCP / Knowledge Soundness

MIP -> PCP

Interactive Oracle Proofs

Polynomial IOPs

Polynomial IOP for R1CS-SAT

Univariate Sum-Check

FRI poly commit

ZK via Commit And Prove

Zero-Knowledge Proofs and Arguments

Graph Non-Isomorphism Proof

Additional Intuition

Quadratic Residue proof

Schnorr's $\Sigma$-Protocol for knowledge of DLog

Schnorr Identification Protocol

Fiat-Shamir in $\Sigma$-protocols

Creating argument of knowledge from $\Sigma$-Protocol via FS

Commitment Schemes

Commitment Scheme From Sigma Protocol

Correctness

Masking Polynomials

Adaptations (ZK via Masking Poly.)

ZK sum-check

Poly Commitments from KZG

Knowledge Extraction

Generic / Algebraic Group Model

Linear PCPs And Succint Arguments