polcom.tex

% !TeX spellcheck = en_UK
\documentclass[runningheads,11pt]{llncs}
\let\spvec\vec
\let\vec\accentvec

\newcommand\hmmax{0}
\newcommand\bmmax{0}

\DeclareFontFamily{U}{mathx}{\hyphenchar\font45}
\DeclareFontShape{U}{mathx}{m}{n}{<-> mathx10}{}
\DeclareSymbolFont{mathx}{U}{mathx}{m}{n}
\DeclareMathAccent{\widebar}{0}{mathx}{"73}

\let\spvec\vec
\usepackage{amssymb,amsmath}
\let\vec\spvec
\usepackage{newtxtext}
%\usepackage{newtxmath,newtxtext}

  \def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}}
  {\mbox{\boldmath$\textstyle#1$}} {\mbox{\boldmath$\scriptstyle#1$}}
  {\mbox{\boldmath$\scriptscriptstyle#1$}}}

\usepackage{bm}

\usepackage{soulutf8} \soulregister\cite7 \soulregister\ref7
\soulregister\pageref7 \usepackage{hyperref}
\usepackage[color=yellow]{todonotes} \hypersetup{final} \usepackage{mathrsfs}
\usepackage[advantage,asymptotics,adversary,sets,keys,ff,lambda,primitives,events,operators,probability,logic,mm,complexity]{cryptocode}

\usepackage{cite} 
\usepackage{booktabs}
\usepackage{paralist}
\usepackage[innerleftmargin=5pt,innerrightmargin=5pt]{mdframed}
\usepackage{caption}
\captionsetup{belowskip=0pt}
\usepackage{bm}
\usepackage{url}
%\usepackage{dirtytalk}
\newcommand{\say}[1]{\emph{``#1''}}
\usepackage[margin=0.7in,a4paper]{geometry}
\usepackage[normalem]{ulem}
\usepackage{dashbox}
\newcommand{\dboxed[1]}{\dbox{\ensuremath{#1}}}
\usepackage{hyperref}
\usepackage[capitalise]{cleveref}
\usepackage{braket} %for the \braket{} command

%\usepackage{mathptmx}


\include{macros}
\include{macros_antonio}

\title{On PHP-based zkSNARKs}

\author{} 
%\iflncs{
\institute{} 

\allowdisplaybreaks

\begin{document} \sloppy \maketitle

\begin{abstract}
  In this paper we investigate properties of zkSNARKs obtained by
  compiling a PHP proof using a polynomial commitment scheme. The question we
  try to answer is \say{What polynomial commitment's properties propagate to
    the resulting zkSNARK?}. The properties we focus on are:
  \begin{compactenum}
  \item simulation extractability,
  \item SRS updatability,
  \item SRS-updatable simulation extractability,
  \item subversion zero knowledge.
  \end{compactenum}
  The research hypothesis is \say{A NIZK obtained from a simulation extractable /
    SRS-updatable / SRS updatable SE / subversion zero knowledge polynomial
    commitment is simulation extractable /
    SRS-updatable / SRS updatable SE / subversion zero knowledge.} To be able to
  show the hypothesis we need to solve a number of problems
  \begin{compactenum}
  \item Neither simulation extractability, SRS-updatability, SRS-updatable
    simulation extractability, nor subversion zero knowledge have been defined
    for a polynomial commitment scheme. Another contribution of the paper is
    defining these properties. 
  \item Similarly, there is no definition for SRS-updatable simulation
    extractable NIZKs.
  \item The polynomial IOP is defined very generally, cf.~\cref{def:piop}, what
    makes showing generic properties difficult. The paper would propose tighter
    definitions which would emphasize more the structure of PHP,
    but would not narrow a class of possible (from the practical point of view)
    PHP too much, cf.~\cref{def:wepiop,def:sdwepiop}.
    \michals{15.11}{Comment re PHP: it doesn't allow to efficiently check statements
      like ``coefficient of $X^n$ is $0$'' what is used e.g.~in Sonic.}
  \end{compactenum}
  
\end{abstract}

\section{Preliminaries}

\begin{definition}[Whitebox Simulation extractable NIZK]
  \label{def:sepcom}
  Let $NIZK = (\kgen, \prove, \verify)$ be a NIZK proof system
  with a simulator $(\simgen, \simprove)$.
  Let $\oracles(\srs, \td, \inp, \wit)$ be an oracle that when $(\inp, \wit)\in
  \REL$, runs $\pi \gets \simprove(\srs, \td, \inp)$ internally, records $(\pi,\inp)$ in $Q$, and returns $\pi$.
  We say that $NIZK$ is \emph{simulation extractable} if for any $\ppt$
  adversary $\adv$ with oracle access to $\oracles$ and $\ro$ there exists extractor
  $\ext_{\adv}$ such that
\[
  \Pr \left[
    \begin{aligned}
      & \verify(\srs, \inp, \pi) = 1, \\
      & \;(\inp, \wit) \neq \REL\\
      & (\pi,\inp) \notin Q
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & (\srs, \td) \gets \simgen(\secparam, \REL),\\
      & (\inp, \pi) \gets \adv^{\oracles,\ro}(\srs; r), \\
      & \wit \gets \ext_\adv(\srs, Q_{sim}, Q_{\ro}; r)
      % & z \sample \FF,\\
      % & (s, o) \gets \adv^{\oracles}(\srs, z; r)
    \end{aligned}
  \right.\right]
  \leq \negl.
\]
\end{definition}
\antonio{19/10/2021}{The definition mention $\ro$, I guess it is an error.}

\paragraph{Polynomial commitment scheme.}
\label{sec:poly_com}
In a polynomial commitment scheme $\PCOM = (\kgen, \com, \open, \verify)$ a
prover $\prover$ convinces a verifier $\verifier$ that some polynomial $\p{f}$
that $\prover$ committed to earlier evaluates to $y$ at some point $x$ chosen by
$\verifier$. The key generation algorithm $\kgen$ takes security
parameter $\secparam$ and a parameter $\maxdeg$ which determines the maximal
degree of the committed polynomial as input and produces a (structured) reference string $\srs$ as output. We assume that $\maxdeg$ can be read from
the $\srs$.
  
We emphasize the following properties of a secure polynomial commitment
$\PCOM$:
\begin{description}
\item[Evaluation binding:] A $\ppt$ adversary $\adv$ which outputs a commitment
  $\vec{c}$ and evaluation points $\vec{x}$ has at most negligible chances to
  open the commitment to two different evaluations $\vec{y}, \vec{y'}$. That is,
  let $k \in \NN$ be the number of committed polynomials, $l \in \NN$ number of
  evaluation points, $\vec{c} \in \GRP^k$ be the commitments,
  $\vec{x} \in \FF_p^l$ be the arguments the polynomials are evaluated at,
  $\vec{y},\vec{y}' \in \FF_p^{kl}$ the evaluations, and
  $\vec{o},\vec{o}' \in \FF_p^l$ be the commitment openings. Then for every
  $\ppt$ adversary $\adv$
	\[
		\Pr
			\left[
			\begin{aligned}
				& \verify(\srs, \vec{c}, \vec{x}, \vec{y}, \vec{o}) = 1,  \\
				& \verify(\srs, \vec{c}, \vec{x}, \vec{y}', \vec{o}') = 1, \\
				& \vec{y} \neq \vec{y}'
			\end{aligned}
			\,\left|\,\vphantom{\begin{aligned}
                  & \\
                  & \\
                  &
                \end{aligned}}
			\begin{aligned}
				& \srs \gets \kgen(\secparam, \maxdeg),\\
				& (\vec{c}, \vec{x}, \vec{y}, \vec{y}', \vec{o}, \vec{o}') \gets \adv(\srs)
			\end{aligned}
			\right.\right] \leq \negl\,.
	\]

\end{description}
\antonio{19/10/2021}{Why do we need to use vectors to define Evaluation Binding? Does the security notion for $l=1$ imply already the notion for $l>1$?}
	

\begin{description}
\item[Commitment of knowledge] For every $\ppt$ adversary
  $\adv = (\adv_1, \adv_2)$ who produces commitment $c$, gets random evaluation
  point $x$, and outputs evaluation $y$ with an opening $o$ there exists a
  $\ppt$ extractor $\ext$ such that
\[
  \Pr \left[
    \begin{aligned}
      & \verify(\srs, c, x, y, o) = 1, \\
      & \p{f} = \ext_\adv(\srs, c, (r_1, r_2)),\\
      & c \neq \com(\srs, \p{f}) \\
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & \srs \gets \kgen(\secparam, \maxdeg),\\
      & (c, \aux) \gets \adv_1(\srs; r_1), z \sample \FF, \\
      &  (y, o) \gets \adv_2(\srs, \aux, c, x; r_2)
    \end{aligned}
  \right.\right]
  \leq \negl.
\]
In that case we say that $\PCOM$ is a commitment of knowledge.
\end{description}
Intuitively when a commitment scheme is a commitment of knowledge then if an
adversary produces a (valid) commitment $c$, which it can open, then it also
knows the underlying polynomial $\p{f}$ which commits to that value.

\markulf{23/08}{Wondering if the $\verify$ condition is really needed for extraction. In the AGM, if the adversary only sees the $\srs$ it has to output group element that is a linear combination of it.}
\michals{25.08}{You may be right that it is not necessary}
\antonio{19/10/2021}{I don't understand this definition. I think something is missing here: what's the rola of
$\adv_2$? how do we use $y,o$ in the event of the probability above? Is the commitment deterministic?}



\paragraph{KZG commitments}
We recall the Kate, Zaverucha, Goldberg polynomial commitment scheme $\Kzg$ \cite{AC:KatZavGol10}, which we use to instantiate our approach.

$\Kzg.\PC = (\Kzg.\kgen, \Kzg.\com, \Kzg.\open, \Kzg.\verify)$ is defined over bilinear groups $\gk=(p,\GG_1,\allowbreak \GG_2, \allowbreak \GG_T )$ with $\GG_1 =\langle g\rangle, \GG_2 =\langle h \rangle$ as follows:
\begin{description}%[topsep=5pt]
\item[$\Kzg.\kgen(1^\secpar, n) \to \srs$:] Set keys
$\srs = \{g^{\xi^i}\}_{i=0}^{n-1}, h^\xi$.
\item[$\Kzg.\CM(\srs; f(X)) \to c$:] For
  $f(X) = \sum_{i=0}^{n-1} f_i X^i$, computes
  $c=\prod _{i=0}^{n-1} g^{f_i \xi^i} = g^{f(\xi)} $.
\item[$\Kzg.\open(\srs; c, x, y; f(X)) \to o$:] For an evaluation point
  $x$, a value $y$, compute the quotient polynomial
  $q(X) = \displaystyle\frac{f(X) -y }{X-x}$ and output a proof
  $o = \Kzg.\CM(\srs; q(X)) $.
\item[$\Kzg.\verify(\srs, c, x, y, o) \to 1/0$:] Check if
  $e(c \cdot g^{-y}, h)=e(o , h^{\xi}\cdot h^{-x})$.
\end{description}

We also define new property for a polynomial commitment scheme,
\emph{binding}. Intuitively, a polynomial commitment scheme is binding if no
$\ppt$ adversary $\adv$ can produce a commitment $c$ and later show a pair
$(f, x, y, o)$, $(f', x, y', o')$ such that $f \neq f'$, $y = f(x)$ and $y' =
f'(x)$ and $o$, $o'$ are valid openings. That is, for all $\ppt$ adversaries
$\adv$
\[
  \Pr\left[
    \begin{aligned}
      & \deg(f), \deg(f') \leq \maxdeg \\
      &\land f(x) = y \land f'(x) = y' \land f
      \neq f' \\
      & \land \verify(\srs, c, x, y, o) = \verify(\srs, c, x, y', o') = 1
      \end{aligned}
      \,\left|\,
        \begin{aligned}
        &  \srs \sample \kgen(\secparam), \\
        &  ((c, f, x, y, o), (c, f', x, y', o')) \gets \adv^{\oraclec}
          \end{aligned}
        \right.\right] \leq \negl
\]

\section{Simulation extractability of polynomial commitments}

\begin{definition}[Simulation extractable polynomial commitment]
  \label{def:sepcom}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment
  scheme with a simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of polynomials that can be
  committed. Let $\oraclec(c)$ be an oracle that when $Q_{chal}= \bot$, samples $x$, sets $Q_{chal}=(c,x)$ and $q_{{chal}}= |Q_{{op}}|$, and returns $x$. Otherwise it returns $\bot$.
  Let $\oracles$ be an oracle which on input
  \begin{description}
%   \item [$(\msg{commit}, f)$:] returns commitment $c = \com(f)$ and adds $(f,
% c)$ to list $Q$.
\item[$(\msg{commit})$:] Run $c \gets \simsample(\secparam)$, add $c$ to $Q_{com}$, return $c$.
  \item[$(\msg{open}, c, x', y)$:] If $c \in Q_{{com}}$ and $x'\neq x$, run
		$o\gets \simopen(\td,c,x',y)$, \antonio{02.09}{It's not clear
		what $x$ should be}\michals{16.11}{Explained later} add $(c,x',y,o)$ to $Q_{op}$, and return $o$. Otherwise
  return $\bot$.
  \end{description}
  $Q_{sim}= (Q_{com},Q_{op})$.
  We say that $\PCOM$ is \emph{simulation extractable} if for any $\ppt$
  adversary $\adv$ with oracle access to $\oracles$ and $\oraclec$ there exists extractor
  $\ext_{\adv}$ such that
\[
  \Pr \left[
    \begin{aligned}
      & \verify(\srs, c, x, y, o) = 1, \\
      & \;c \neq \com(\srs, \p{f})\\
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
      & (y, o) \gets \adv^{\oracles,\oraclec}(\srs; r), \\
      & \p{f} \gets \ext_\adv(\srs, Q_{sim}, Q_{chal}; r)
      % & z \sample \FF,\\
      % & (s, o) \gets \adv^{\oracles}(\srs, z; r)
    \end{aligned}
  \right.\right]
  \leq \negl.
\]
\markulf{2.09}{in that case the extractor would also have to output the randomness}
\michals{25.08}{minor thing -- we should allow the commitment scheme to be
  randomizable}
\michals{16.11}{On PCOM randomization: should we ask the extractor to extract
  commitment randomness as well or maybe we just require that the commiment $c$ is in
  the image $IM(\com(f))$? I think the former suits better.}
% \[
%   \Pr \left[
%     \begin{aligned}
%       & (\p{f} = \ext_\adv(\srs, Q_{sim}, Q_{chal}; r),\\
%       & \;c = \com(\srs, \p{f}))\\
%       & \lor \verify(\srs, c, x, y, o) = 0
%     \end{aligned}
%     \,\left|\,
%       \vphantom{
%         \begin{aligned}
%           & \\
%           & \\
%           & \\
%           &
%         \end{aligned}
%         }
%     \begin{aligned}
%       & (\srs, td) \gets \mathsf{SimGen}(\secparam, \maxdeg),\\
%       & (y, o) \gets \adv^{\oracles,\oraclec}(\srs; r), \\
%       % & z \sample \FF,\\
%       % & (s, o) \gets \adv^{\oracles}(\srs, z; r)
%     \end{aligned}
%   \right.\right]
%   \geq 1 - \epsk(\secpar).
% \]
\end{definition}
Note that when $\oraclec(c)$ has not been queried, $c$ and $x$ equal $\bot$ and $\verify$ returns $0$.

\paragraph{KZG is simulation extractable}

We consider an algebraic adversary $\adv$ that outputs a matrix $K$ with coefficients $\{C_{{1i}}\},\{C_{{2i}}\}, \{C_{{3ij}}\}$ for the commitment $c$ and $\{O_{{1i}}\},\{O_{{2i}}\}, \{O_{{3ij}}\}$ for the opening proof $o$. The matrix $K$ reconstructs $c,o$ as linear combination of the group elements in $\srs$ and $Q_{sim}$. We consider a representation of the group elements in $(\srs,Q_{{sim}})$ in terms of a function $\mathsf{Tr}_{\{x_{ij},y_{ij}\}}(\tau)$ of its underlying secret discrete logarithms $\tau=(\xi,\alpha_{i})$. Where $\xi$ is the trapdoor of the $\srs$ and the $\alpha_{i}$ are the randomness of simulated proofs.
\antonio{02.09}{Why are the $C_{3ij},O_{3ij}$ labeled with two indexes (both $i$ and $j$?)}

We move toward considering a verification equation $V'$ expressed in terms of $K$ and $\mathsf{Tr}_{\{x_{ij},y_{ij}\}}$ for which we have:
$\verify(\srs,c,x,y,o) =  e(c \cdot  g^{-y}, h) - e(\pi , h^{\alpha}\cdot h^{-x}) = 0$ iff $\verify'_{{\xi,x,y}}(K \cdot \mathsf{Tr}_{\{x_{ij},y_{ij}\}} (\tau)) = 0$.

We say that $\verify'_{{X,x,y}}$ is satisfied symbolically, if $\verify'_{{X,x,y}}(K \cdot \mathsf{Tr}_{\{x_{ij},y_{ij}\}} (T)) = 0$ for symbolic variables $T=(X, \{A_{i}\})$.

The symbolic transcript consists of the SRS $\{[X^{i}]_{1}\}, [X]_{2}$, simulated commitments $\{[A_{i}]_{1}$, and simulated opening proofs $ [\frac{A_{ij}-y_{{ij}}}{X-x_{ij}}]\}$.

The honest verification equation is
$[f(X) - y]_1 \bullet [h]_{2} - [q(X)]_1 \bullet [X-x]_{2}=0$ while an adversary can
provide rational functions
$f(X, \{A_{i}\}) = \sum C_{1i} X^{i} + \sum C_{2i} A_{i} + \sum C_{3ij}
\frac{A_{i}-y_{ij}}{X-x_{ij}}$ and
$q(X, \{A_{i}\}) = \sum O_{1i} X^{i} + \sum O_{2i} A_{i} + \sum O_{3ij}
\frac{A_{i}- y_{ij}}{X-x_{ij}}$ computed as linear combinations of elements in the
transcript.
The security game gives us that $x$ is sampled independently from $x_{ij}$ for $j\leq q^{i}_{chal}$ and $x \neq x_{ij}$ otherwise. Here $q^{i}_{chal}$ are the number of simulated opening queries made for commitment $c_{i}$ before the challenge query.

We inline to get the following equation which we then analyze in detail,
\begin{align*}
  \left[\sum C_{1i} X^{i} + \sum C_{2i} A_{i} + \sum C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - y\right]_{1} \!\!\!\bullet\! [1]_{2} - \left[\sum O_{1i} X^{i} + \sum O_{2i} A_{i} + \sum O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}}\right]_{1} \!\!\!\bullet\! [X-x]_{2} = 0
  \end{align*}

We now look at different (rational) monomials in $T$ of this equation to derive constraints on $C_{1i}, C_{{2i}},C_{{3ij}}$ and $O_{1i},O_{2i},O_{3ij}$ imposed by the verification equation:
\begin{itemize}
  \item[$A_{i}X$:] We have that for all $i$, $O_{2i}=0$ as $O_{2i} A_{i} X = 0$.
  \item[$\frac{A_{i}-y_{ij}}{X-x_{ij}}, j>q^{i}_{chal}$:] $C_{3ij}=0$ as $\adv$ did not yet see them when it computes the commitment.
\end{itemize}

To obtain a simplified verificaton equation, we express the equation in the exponent and write $C_{1}(X)$ for $\sum C_{1i} X^{i}$ and  $O_{1}(X)$ for $\sum O_{1i} X^{i}$.
Furthermore, we let $x_{ij}= x+\delta_{ij}$ and replace $x$ with $x_{ij}-\delta_{ij}$
\antonio{02.09}{Minor: maybe better say "we let $\delta_{ij}:=x_{ij}-x$".}
\begin{align*}
C_{1}(X) - y - O_{i}(X)(X-x) + \sum C_{2i} A_{i} + \sum C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} (X-x_{ij}+\delta_{ij}) = 0\\
C_{1}(X) - y - O_{i}(X)(X-x) + \sum C_{2i} A_{i} + \sum C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} (X-x_{ij}) - O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} \delta_{ij} = 0
       \end{align*}

       \markulf{2.09}{We require that $\delta_{ij} \neq 0$}
\begin{itemize}
  \item[$\frac{A_{i}-y_{ij}}{X-x_{ij}}$:] $C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - O_{{3ij}}\delta_{ij} \frac{A_{i}-y_{ij}}{X-x_{ij}}=0$. As
    $C_{3ij}=0$ for $j>q^{i}_{chal}$, it follows that $O_{{3ij}}=0$ for $j>q^{i}_{chal}$. Otherwise, we have $O_{3ij}= C_{3ij}/\delta_{ij}$.
  \item[$A_{i}$:] $C_{2i} A_{i} - \sum O_{3ij} A_{i}=0$.
\end{itemize}

Informal step. $C_{2i}- \sum \frac{C_{3ij}}{x_{ij}-x} =0$ is a rational equation system in $x$. If $x_{ij}\neq x_{ij'}$, then the probability of randomly picking a solution $x$ is small unless all the $C_{2i}$, $C_{3ij}$ are $0$. Thus we also have $O_{{3ij}}=0$.
If $x_{ij} = x_{ij'}$ then the adversary requested openings on the same value for the same commitment (potentially for different $y_{ij}$) multiple times. This is something we want to exclude.

\begin{itemize}
        \item[$X^{i}, i\geq 0$:] $C_{1}(X) - y - O_{1}(X)(X-x) + \sum \sum O_{3ij} y_{ij} = 0$, as $O_{3ij}=0$ we are back to the honest verification equation.
\end{itemize}



\begin{definition}[Vectored simulation extractable polynomial commitment]
  \label{def:sepcom}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment
  scheme with a simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of polynomials that can be
  committed.
  We consider the same $\oracles$ and $Q_{sim}= (Q_{com},Q_{op})$ but an adversary that provides vectors of commitments and openings $\vec{c}, \vec{y}, \vec{o}$.
   Let $\oraclec(\vec{c})$ be an oracle that when $Q_{chal}= \bot$, samples $x$, sets $Q_{chal}=(\vec{c},x)$ and $q_{{chal}}= |Q_{{op}}|$, and returns $x$. Otherwise it returns $\bot$
  We say that $\PCOM$ is \emph{vector simulation extractable} if for any $\ppt$
  adversary $\adv$ with oracle access to $\oracles$ and $\oraclec$ there exists extractor
  $\ext_{\adv}$ such that
\[
  \Pr \left[
    \begin{aligned}
      & \verify(\srs, \vec{c}, x, \vec{y}, \vec{o}) = 1, \\
      & \;\vec{c} \neq \com(\srs, \vec{\p{f}})\\
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
      & (\vec{y}, \vec{o}) \gets \adv^{\oracles,\oraclec}(\srs; r), \\
      & \vec{\p{f}} \gets \ext_\adv(\srs, Q_{sim}, Q_{chal}; r)
      % & z \sample \FF,\\
      % & (s, o) \gets \adv^{\oracles}(\srs, z; r)
    \end{aligned}
  \right.\right]
  \leq \negl.
\]
\end{definition}

\paragraph{A simulation extractable polynomial commitment is also vectored SE.}
From $(\vec{y}, \vec{o}) \gets \adv^{\oracles,\oraclec}(\srs; r)$ we build $(y_{i}, o_{i}) \gets \adv_{i}^{\oracles,\oraclec'}(\srs; r)$ that output only the $i$th opening evaluation and opening proof.

On the same $r$ and $x$, whenever $\adv$ passes verification, $\adv_{i}$ passes verification.  Thus by Definition 1 there exist extractors $\Ext_{\adv_{i}}$ that succeeds to extract for most $r$, $x$ and $\oracles$ randomness.

We build $\Ext_{\adv}(\srs, Q_{sim}, Q_{chal}; r)$ by parsing $Q_{chal}$ as $((c_{1},\dots, c_{k}), x)$ and running all $\Ext_{\adv_{i}}$ as $\p{f}_{i}\gets \Ext_{\adv_{i}}(\srs,Q_{sim},(c_{i},x); r)$ to return $(\p{f}_{1},\dots,\p{f}_{k})$.

\antonio{02.09}{I failed to understand the definition below :( }
\begin{definition}[Vectored $\ro_{aux}$ simulation extractable polynomial commitment]
  \label{def:sepcom}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment
  scheme with a simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of polynomials that can be
  committed. 
  We consider the same $\oracles$ and $Q_{sim}= (Q_{com},Q_{op})$ but an adversary that provides vectors of commitments and openings $\vec{c}, \vec{y}, \vec{o}$.
   Let $\ro_{aux}(\vec{c},aux)$ be an oracle that when $Q_{\ro}[\vec{c},aux] = \bot$, samples $x$, sets $Q_{\ro}[\vec{c},aux]=x$ and $q_{{chal}}= |Q_{{op}}|$. In all cases, it returns $Q_{\ro}[\vec{c},aux]$.
  We say that $\PCOM$ is \emph{vector $\ro_{aux}$ simulation extractable} if for any $\ppt$
  adversary $\adv$ with oracle access to $\oracles$ and $\ro_{aux}$ there exists extractor
  $\ext_{\adv}$ such that
\[
  \Pr \left[
    \begin{aligned}
      & x \gets \ro_{aux}(\vec{c},aux), \\
      & \verify(\srs, \vec{c}, x, \vec{y}, \vec{o}) = 1, \\
      & \;\vec{c} \neq \com(\srs, \vec{\p{f}})\\
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
      & (aux,\vec{c},\vec{y}, \vec{o}) \gets \adv^{\oracles,\ro_{aux}}(\srs; r), \\
      & \vec{\p{f}} \gets \ext_\adv(\srs, Q_{sim}, Q_{\ro}; r)
      % & z \sample \FF,\\
      % & (s, o) \gets \adv^{\oracles}(\srs, z; r)
    \end{aligned}
  \right.\right]
  \leq \negl.
\]
\end{definition}

\paragraph{A vectored simulation extractable polynomial commitment is also vectored $\ro_{aux}$ SE.}
From $(aux, \vec{c}, \vec{y}, \vec{o}) \gets \adv^{\oracles,\ro_{aux}}(\srs; r)$ we build $(\vec{y},\vec{o}) \gets \adv_{i}^{\oracles,\oraclec}(\srs; r\|(Q_{\ro}\setminus x_{i}))$ that simulates $\ro_{aux}$ on the $i$th query using the value $x_{i}$ returned by $\oraclec$ and using its extended random tape otherwise.

On the same $r$ and $x$, whenever $\adv$ passes verification using $\vec{c},aux$ that were passed in the $i$th query to $\ro_{aux}$, then $\adv_{i}$ passes verification.  Thus by Definition 2 there exist extractors $\Ext_{\adv_{i}}$ that succeeds to extract for most $r$, $x$ and $\oracles$ randomness under that condition.

We build $\Ext_{\adv}(\srs, Q_{sim}, Q_{\ro}; r)$ by running both $\adv$
internally by simulating $\oracles$ and $\ro_{aux}$ using $Q_{sim}$ and
$Q_{\ro}$, and by running all $\Ext_{\adv_{i}}$ as $\p{f}_{i}\gets
\Ext_{\adv_{i}}(\srs,Q_{sim},Q_{chal_{i}}; r\|(Q_{\ro}\setminus x_{i}))$ by
splitting $Q_{\ro}$ into $Q_{chal_{i}}$ and $Q_{\ro}\setminus x_{i}$ to return
$\p{f}_{i}$ whenever $\adv$ passed $\vec{c},aux$ in the $i$th query to
$\ro_{aux}$.

\iffalse
\begin{definition}[Simulation extractable polynomial commitment]
  \label{def:sepcom}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment
  scheme. Let $\maxdeg$ be a maximal degree of polynomials that can be
  committed, $H$ be a set of $\maxdeg + 1$ elements in $\FF$ and
  $\van{H}$ is a vanishing polynomial for $H$.
  
  Let $\oracles$ be an oracle which on input
  \begin{description}
%   \item [$(\msg{commit}, f)$:] returns commitment $c = \com(f)$ and adds $(f,
% c)$ to list $Q$.
\item[$(\msg{commit}, f, d)$:] for $\deg(f) = d'$, $d' \leq d \leq \maxdeg$,
  picks $d - d'$ random elements $r_1, \ldots, r_{d - d'}$, sets 
  polynomial $g(X) = f(X) + \van{H}(r_1 X^{d' + 1} + \ldots + r_{d - d'} X^{d})$, returns
  commitment $c = \com(g)$ and adds $(g, c)$ to list $\Qcom$.
  \item[$(\msg{evaluate}, c, z)$:] returns $f(z)$ where $f$ is a polynomial
    which commitment is $c$ and $(f, c) \in \Qcom$; add $z$ to $\Qev$.
  \item[$(\msg{open}, c, x, y)$:] returns an opening $o$ for commitment $c$
    assuring that for some polynomial $f$, such that $c \in \image(\com(f))$,
    holds $f(x) = y$.
  \end{description}
  We say that $\PCOM$ is \emph{simulation extractable} if for any $\ppt$
  adversary $\adv = (\adv_1, \adv_2)$ with oracle access to $\oracles$ there
  exists extractor $\ext$ such that
\[
  \Pr \left[
    \begin{aligned}
      & \p{f} = \ext_\adv(\srs, Q_{\adv}, (r_1, z, r_2)),\\
      & c = \com(\srs, \p{f}),\\
      & \verify(\srs, c, z, s, o) = 1,
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & \srs \gets \kgen(\secparam, \maxdeg),\\
      & (c, \state) \gets \adv_1^{\oracles}(\srs; r_1), \\
      & z \sample \FF, \\
      & (s, o) \gets \adv_2^{\oracles}(\srs, c, z; \state, r_2)
    \end{aligned}
  \right.\right]
  \geq 1 - \epsk(\secpar).
\]
  \michals{23.04}{Can $\ext$ ask $\adv$ to give evaluations of the committed
    polynomial? That is how $\ext$ in a proof system works -- it evaluates
    polynomials submitted by the adversary on multiple challenges.}
\end{definition}

\markulf{17.08}{We can represent $\adv_{1}$ and $\adv_{2}$ using a single adversary $\adv_{\mathsf{chal}}$ with an additional oracle $\oraclec$ that on input $c$ returns $z$ on its single allowed call. The winning condition takes $c,z$ directly from that oracle call.}

\begin{definition}[$(k, \eps)$-aux-simulation extractable polynomial commitment]
  \label{def:sepcom}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment
  scheme. Let $\maxdeg$ be a maximal degree of polynomials that can be
  committed, $H$ be a set of $\maxdeg + 1$ elements in $\FF$ and
  $\van{H}$ is a vanishing polynomial for $H$.
  
  Let $\oracles$ be an oracle which on input
  \begin{description}
\item[$(\msg{commit}, f, d)$:] for $\deg(f) = d'$, $d' \leq d \leq \maxdeg$,
  picks $d - d'$ random elements $r_1, \ldots, r_{d - d'}$, sets 
  polynomial $g(X) = f(X) + \van{H}(r_1 X^{d' + 1} + \ldots + r_{d - d'} X^{d})$, returns
  commitment $c = \com(g)$ and adds $(g, c)$ to list $\Qcom$.
\item[$(\msg{commit}, rand, d)$:] picks a random polynomial $f$ of degree $d$ and
  outputs commitment $c = \com(f)$ and adds $(f, c)$ to the list $\Qcom$.
  \item[$(\msg{evaluate}, c, z)$:] returns $f(z)$ where $f$ is a polynomial
    which commitment is $c$ and $(f, c) \in \Qcom$; add $z$ to $\Qev$.
  \item[$(\msg{open}, c, z, y)$:] returns an opening $o$ for commitment $c$
    assuring that for some polynomial $f$, such that $c \in \image(\com(f))$,
    holds $f(z) = y$.
  \end{description}
  We say that $\PCOM$ is \emph{$(k, \eps)$-aux-simulation extractable} if for
  any $\ppt$ adversary $\adv$ with oracle access to
  $\oracles$ and random oracle $\ro$ there exists extractor $\ext$ such that
\[
  \Pr \left[
    \begin{aligned}
      & \p{f_1}, \ldots, \p{f_k} = \ext_\adv(\srs, Q_{\adv}, Q_{\ro}, r),\\
      & c_i = \com(\srs, \p{f_i}),\\
      & \verify(\srs, c_i, z_i, s_i o_i) = 1, \text{ for } i \in \range{1}{k}\\
      & z = \ro((c_1,\dots, c_{k}),\aux)
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & \srs \gets \kgen(\secparam, \maxdeg),\\
      & ((c_1, \ldots, c_k), \aux, z, (s_1, \ldots, s_k),\\
      & \qquad \qquad (o_1, \ldots, o_k)) \gets \adv^{\oracles, \ro}(\srs, r), \\
    \end{aligned}
  \right.\right]
  \geq 1 - \eps(\secpar).
\]
\end{definition}

\markulf{17.08}{
  We show how to construct $ \ext_\adv$ from $|Q_{H}|$ extractors $\ext_{\bdv_{i}}$ obtained from adversaries $\bdv_{i}$ that run $\adv$ by simulating the random oracle internally using its random tape. Only for the $i$th $\ro$ query, does $\bdv_{i}$ submit the challenge $c$ to $\oraclec$ to learn $z$. As $\bdv_{i}$ is a valid $\adv_{\mathsf{chal}}$ adversary, by $k$ simulation extractability of the polynomial commitment scheme $\ext_{\bdv_{i}}$ exists. $\ext_{\adv}$ runs all $\ext_{\bdv_{i}}$ and thus does not occure an extraction loss for guessing $i$.
}
\fi

\iffalse
 \begin{definition}[One-to-many openable\hl{Good name needed}]
   We call a commitment scheme $\PCOM$ one-to-many openable \hl{good name
     needed} if for any $\adv$ who outputs commitments $c_1, \ldots, c_k$,
   evaluation point $z$, evaluations $s_1, \ldots, s_k$ and batch opening $o$,
   which certifies that polynomials $f_i$ evaluates at $z$ to $s_i$ and
   $c_i \in \image(\com(f_i))$, there exists $\ppt$ algorithm $\bdv$ that
   produces valid openings $o_i$ for each triple $(c_i, z, s_i)$.
 \end{definition}
 Intuitively, we say that a polynomial commitment is one-to-many openable if we
 can deduce that adversary who successfully batch opens a number of polynomial
 commitments could also successfully open each of the commitments separately.

 \michals{23.06}{That's easy for KZG batched as in Plonk (with minor difference)
   -- just get a number of batch openings and do Gaussian elimination.}
\fi
 
 \begin{definition}
\hl{The proof system and the polynomial commitment scheme use virtually the same
SRS. (Both SRS could differ in some efficiency related elements, but computation
of these don't require any secret knowledge)}
\michals{12.07}{Check how it is done in Lunar}
\antonio{29.07}{I think you might want to look at Pag 71 of Lunar's manuscript, Definition 20.}
   \end{definition}

\subsection{Polynomial IOP}
\begin{definition}[Polynomial Holomorphic Proof System (PHP)]
  \label{def:php}
  Let $\REL$ be an indexed relation with a corresponding language $\LANG$, $\FF$
  some finite field, $\maxdeg$ a degree bound, $\vereq_{\cdot}(X) \in \FF[X]$ a
  verification equation, and $\eps, \noofp$ parameters.
  \michals{12.07}{Continue}
\end{definition}

\begin{definition}[Witness encoding PHP (WEPHP)]
  \label{def:wephp}
  Let $\PS$ be a PHP.  We say that $\PS$ is \emph{witness encoding} if there is
  a function $\decode$ and set $\encset \in [\noofp]$ such that for any
  $(\inp, \wit) \in \REL$ and polynomials $\smallset{f_i}_{i \in [\noofp]}$ sent by an
  honest prover, $\decode(\smallset{f_i}_{i \in \encset}) = \wit$. We call $\encset$ the
  \emph{encoding set}.
\end{definition}
In other words, PHP is witness encoding if for any valid proof for a statement
$\inp$ in the language, the corresponding witness can be read from the
polynomial coefficients. We note that this is the case for virtually all
PHPs. \michals{28.04}{Check!}

\antonio{27.07}{This definition reminded me that in Lunar we define straight-line extractability for PHP.
	The straight-line extractability def is stronger than def above but I think that every "natural" PHP should
	also be straight-line extractable. I copy-paste the definition below:}
	%
\begin{definition}[PHPs with straight-line extractor]
\label{def:knownsound_wc_poly}
A $\PS$ is $\eps$-knowledge-sound with straight-line extractor if there exists an
extractor $\ext$ such that for any prover $\prover^*$, every field $\FF \in \Fam$,
relation $\REL$, and instance $\inp$: 
\[ \Prob{ (\REL, \inp, \ext(\tuple\pora{\nprv})) \in \RELGEN}
	\geq \Prob{ \brak{ \prover^*,\verifier^{\indexer(\FF, \REL)}(\FF, \inp) } = 1} - \eps
\]
where $\tuple\pora{\nprv}$ are the polynomials output by $\prover^*$ in an execution of
$\brak{\prover^*, \verifier^{\indexer(\FF, \REL)}(\FF, \inp)}$.
\end{definition}



\subsection{Simulation extractable NIZKs from simulation extractable polynomial
  commitments}
\michals{25.08}{this section is old. Probably need to rewrite it after we are
  sure that a similar result for Plonk holds.}

\begin{theorem}
  Let $\PHP = (\PHP.\prover, \PHP.\verifier, \PHP.\simulator)$ be a ZK PHP
  for $\REL$ with knowledge soundness error $\epsks$ where the prover sends up
  to $\noofp$ polynomials. Let $\PCOM$ be $\eps(\secpar)$-sufficiently
  simulatable polynomial commitment scheme for $\PS$ with extraction error
  $\epsext$. Let $\PS = (\PS.\prover, \PS.\verifier, \PS.\simulator)$ be a proof system such
  that
  \begin{enumerate}
  \item $\PS.\prover$ acts as $\PHP.\prover$, except
    \begin{itemize}
    \item when $\PHP.\prover$ sets up a polynomial oracle $\oracleo_f$,
      $\PS.\prover$ sends commitment $c = \com(f)$;
    \item when $\PS.\verifier$ asks $\PS.\prover$ to open a commitment
      $c = \com(f)$ at $z$ it returns $f(z)$ and a proof $o$ of correctness of
      the opening.
  \end{itemize}
  \item $\PS.\verifier$ acts as $\PHP.\verifier$, except when $\PHP.\verifier$
    asks oracle $\oracleo_f$ for an evaluation of $f$ at $z$, $\PS.\verifier$
    sends $z$ to $\PS.\prover$ and expects $f(z)$ in return.
  \item $\PS.\simulator$ acts as $\PHP.\simulator$, except
     \begin{itemize}
    \item when $\PHP.\simulator$ sets up a polynomial oracle $\oracleo_f$,
      $\PS.\simulator$ sends commitment $c = \com(f)$;
    \item when $\PS.\verifier$ asks $\PS.\simulator$ to open a commitment
      $c = \com(f)$ at $z$ it returns $f(z)$ and a proof $o$ of correctness of
      the opening.
  \end{itemize}
  \end{enumerate}
  Then $\PS$ is simulation extractable with extraction error at most \hl{...}.
\end{theorem}
\begin{proof}
  From the simulation extractability of $\PCOM$ we will derive simulation
  extractability of $\PS$ by constructing a $\PS$ extractor $\ext^{\PS}$ using
  $\PCOM$ extractor $\ext^{\PCOM}$.

  Let $\adv(\srs)$ be a $\PS$ adversary with oracle access to a $\PS$ simulator
  $\simulator$. We show construction of an extractor $\ext^{\PS}$ which from
  acceptable proof $\zkproof$ for instance $\inp$ output by $\adv$ produces
  witness $\wit$ such that $\REL(\inp, \wit) = 1$. We proceed by game hoping.
  
  \ngame{1} Let $\ext^{\PS}_\adv$ be an extractor for adversary $\adv$. In this
  game the adversary is given oracle $\oraclesps$ and produces an instance
  $\inp$ and proof $\zkproof$. $\adv$ wins if $\ext_\adv$ does not output the
  corresponding witness $\wit$.

  \ngame{2} In this game $\adv$'s access to $\oraclesps$ is substituted by
  access to $\bdv^\oraclespcom$ which simulates $\oraclesps$.
  Since $\PCOM$ is sufficiently simulatable for $\PS$, probability that $\adv$
  wins in Game $\game{1}$ but not in $\game{2}$ (or vice-versa) is at most
  $\eps(\secpar)$.

  \medskip\noindent We now analyze the probability that $\adv$ wins in Game
  $\game{2}$. Since $\PCOM$ is simulation extractable, there exists an extractor
  $\ext_\bdv$ which extracts, for $i \in \range{1}{\noofp}$, polynomials $f_i$
  if $\bdv$ output
  \begin{inparaenum}[(1)]
  \item commitment $c_i$ and $c_i \in \image(\com(f_i))$;
  \item evaluations $s_i$ for evaluation points $z_i$ provided by the $\PS.\verifier$;
  \item openings $o_i$;
  \end{inparaenum}
  \michals{28.06}{Stopped here -- we need more details of PHP to argue about
    $\bdv$ returning a valid opening of commitment. Further we want to state
    that if the proof was accepted then the commitments have been opened
    successfully. If the proof system allow for batch opening, then still we can
  open every single commitment.}
  
\end{proof}

\section{Simulation extractable NIZK from a simulation extractable polynomial
  commitment and polynomial protocol}
Here we show that given a simulation extractable polynomial commitment scheme
and polynomial protocol one can use the polynomial protocol-to-NIZK compiler
from \cite{EPRINT:GabWilCio19} to get a simulation extractable NIZK. The idea of
the construction is following. First we observe that since the polynomial
commitment is simulation extractable then for every adversary $\bdv$ who, given
access to a polynomial commitment simulator oracle $\oraclespcom$, outputs a
vector of commitments $\vec{c} = (c_1, \ldots, c_\ell)$ and its valid opening $\vec{o}$ at random points
$\vec{z}$, there exists an
extractor $\ext_\bdv$ which, given
\begin{itemize}
\item $\bdv$'s code,
\item its randomness $r_\bdv$, and
\item auxiliary input $\aux_\bdv$, where $\aux_\bdv$ consists of all
  $\oraclespcom$'s responses for $\bdv$ queries
\end{itemize}
outputs $\vec{f}$ such that $c_i \in \image(\com(f_i))$, for
$i \in \range{1}{\ell}$.  Then we take a simulation-extractability adversary for
the compiled NIZK $\adv$ and build its corresponding extractor $\ext_\adv$ using
$\bdv$ and $\ext_\bdv$.

More precisely, we show that $\adv$'s access to $\oraclesps$ can be substituted
with some \emph{deterministic} algorithm $\bdv$ and $\oraclespcom$. We then
build $\ext_\adv$ using $\bdv$ and $\ext_\bdv$. To do that we need
to ``translate'' $\ext_\adv$'s inputs as $\ext_\bdv$'s inputs. From a high level
perspective this is achieved as follows:
\begin{description}
\item[$\bdv$'s code:] $\bdv$ code compounds of two elements: a subroutine that
  runs $\adv$ and an overlay $\cdv$ that is responsible for providing $\adv$ with
  simulated proofs using its access to $\oraclespcom$. More precisely on
  $\adv$'s query to $\oraclesps$ $\cdv$ parses it as a set of $\oraclespcom$
  queries, then it parses oracle's responeses to make a $\PS$ proof out of
  them. Such proof is send back to $\adv$. Hence, $\bdv$'s code composes of code
  of $\adv$ and some (publicly known and universal, i.e.~one for all $\adv$'s)
  code of algorithm $\cdv$. 
\item[$\bdv$'s randomness:] Since $\cdv$ is deterministic, we have
  $r_\adv = r_\bdv$.
\item[Auxiliary input $\aux_\bdv$:] Since the simulated proofs from $\oraclesps$
  collected in $\aux_\adv$ compounds of polynomial commitments, their evaluation
  and openings, they can be naturally translated to a number of $\oraclespcom$
  calls.
\end{description}
After the extractor $\ext_\bdv$ produces an output -- a vector of polynomials --
$\ext_\adv$ needs to parse it to its needs. To that end, it makes $\PS$'s proofs
out of them.

\begin{lemma}[Trapdoor-free simulatability of polynomial protocols.]
  Let $\PS$ be a polynomial protocol with verification equation
  \[
    \vereq := G(X, h_1(v_1(X)), \ldots, h_\ell(v_\ell (X))) = 0.
  \]
  Assume that for all $i, j, k, l \in \range{1}{\ell}$, $a_j, a_{k, l} \in \FF$ holds
  \[
    h_i(v_i(X)) \neq a_j h_j(v_j(X)) + \sum_{k, l} a_{k, l} h_k(v_k (X)) h_l (v_l (X)),
  \]
  additionaly assume uber assumption \cite{}.
  Then there exists simulator $\simulator$ such that for any $\ppt$ adversary
  $\adv$
  \[
    \text{no polynomial adversary can distinguish the proofs -- computational ZK}
  \]
\end{lemma}
\begin{proof}[draft]
  The simulation idea is similar to the one presented in
  \cite{EPRINT:CFFQR20}. When $\prover$ sends a polynomial commitment $c$ to
  some polynomial $f$, the simulator picks a random commitment
  $c_\simulator$. When all commitments have been submitted, the simulator
  computes $ G(X, h_1(v_1(X)), \ldots, h_\ell(v_\ell (X)))$ and finds its root
  $\chz$. Then it programs the random oracle to return $\chz$ as the polynomial
  protocol challenge.

  First, since the uber assumption holds, no $\ppt$ algorithm can tell
  commitment to a randomly picked $f$ from a real one. \michals{28.07}{Here we
    assume that $\PCOM$ is the KZG scheme but it should be generalizable to any
    polynomial commitment.} Also, relaying on the same assumption, no $\ppt$
  algorithm can tell evaluation of $f$ at a random point from an evaluation of a
  random polynomial.
  Furthermore, since the simulator picks $\chz$ such that verification equation
  holds, the verifier accepts such proof. \michals{28.07}{Probably need to argue
    that $\chz$, which the simulator picks also ``looks random''.}
  \qed
\end{proof}

\begin{theorem}[From simulation extractable $\PCOM$ to simulation extractable $\nizk$.]
\end{theorem}
\begin{proof}
  \qed
\end{proof}


\bibliographystyle{alpha}
\bibliography{cryptobib/abbrev1,cryptobib/crypto}

\appendix
\section{Additional assumptions}
\subsection{On uber assumption}
% \begin{definition}[$(F^1, \ldots, F^m)$-independent polynomial]
%   Let $F^i = \smallset{f^i_1, \ldots, f^i_{k_i}}$, $i \in \range{1}{m}$, be
%   families of polynomials. We say that $g$ is \emph{$2$-independent from
%     $(F^1, \ldots, F^m)$} if
%   \[
%     a_g g(X) = \sum_{i = 1}^{m} \sum_{j_i = 1}^{k_i} a_{j_i} f_{j_i} + %
%     \sum_{i = 1}^{m} \sum_{j_i, i_2}^{k_i, k_j} a_{i_1, i_2} f_{i_1} f_{i_2} +
%     \ldots \sum_{i_1, \ldots, i_m}^{k, \ldots, k} a_{i_1, \ldots, i_m} f_{i_1}
%     \ldots f_{i_m},
%   \]
%   only iff all coefficients $a_h$, $a_{i_1}$, $a_{i_1, i_2}$, \ldots, $a_{i_1},
%   \ldots, a_{i_m}$ are zero. 
% \end{definition}

% In this paper we consider only case of $m = 2$. For that case we ``fine tune''
% the definition above and allow two different families of polynomials that $h$ is
% independent from. That is,

\begin{definition}[$(F, G)$-independent polynomial]
  Let $F = \smallset{f_1, \ldots, f_k}$, $G = \smallset{g_1, \ldots, g_l}$ be
  families of polynomials. We say that $h$ is \emph{$(2, F, G)$-independent} if
  \[
    a_h h(X) = \sum_{i = 1}^{k} a_{i} f_{i} + \sum_{i}^l b_{i} g_i + \sum_{i, j}^{k, l} c_{i, j}
    f_{i} g_{j},
  \]
  only iff all coefficients $a_h$, $a_{i}$, $b_i$, $c_{i, j}$ are zero. 
\end{definition}
This definition is equivalen to definition of independent polynomials from
\cite{PAIRING:Boyen08}.

\begin{definition}[$2$-independent proof system]
  Let $\PHP$ be a PHP proof system, and $F = \brak{f_1, \ldots, f_l}$
  polynomials sent by the prover. Denote by
  $F_{\neg i} = \brak{f_1, \ldots, f_{i - 1}, f_{i + 1}, \ldots, f_l}$.  We say
  that $\PHP$ is \emph{2-independent} \michals{25.08}{good name needed} if for all
  $f_i \in F$, $f_i$ is $(F_{\neg i}, F_{\neg i})$-independent.
\end{definition}

For a family of polynomials $F = \smallset{f_1, \ldots, f_k}$ where each $f_i
\in \FF[X]$ we write $F(x)$ to denote $\smallset{f_1(x), \ldots, f_k(x)}$. 

\begin{definition}[$(F, G)$-uber assumption, \cite{PAIRING:Boyen08}]
  Let $h(X)$ be an
  $(F = \smallset{f_1, \ldots, f_k}, G = \smallset{g_1, \ldots,
    g_l})$-independent polynomial of degree $d$, and $r$ be a random polynomial
  from $\FF^d[X]$. Then for any $\ppt$ adversary $\adv$
  \begin{multline}
%    \begin{split}
    \Pr\left[ \adv(F(x), G(x), F \otimes G (x), r(x)) = 1 \,\left|\, x \sample \FF
      \right.\right] \approx 
    \Pr\left[ \adv(F(x), G(x), F \otimes G (x), h(x)) = 1 \,\left|\, x \sample \FF
      \right.\right].
 % \end{split}
  \end{multline}
\end{definition}

\michals{25.08}{Focus on a single ver eq, work later on multi ver eq case.}

\begin{lemma}[Simulatability of $2$-independent proof systems]
  Let $\PHP$ \michals{25.08}{$\PHP$ or $\PS$?} be a $2$-independent proof system
  \hl{...}  Let $\pf_1(X), \ldots, \pf_k(X)$ be the polynomials that the prover
  sends and $\vereq_i(X) = G_i(X, h_1(v_1(X)), \ldots, h_\ell (v_\ell(X)))$, for
  $i \in \range{1}{m}$, be the set of verification equations \hl{...}
\end{lemma}
\begin{proof}
  For a verification equation $\vereq_i(X)$ denote by $\p{F}_i$ all polynomials
  that are required to compute $\vereq_i(X)$ and by $\pf_{j_i}$ the last
  polynomial in $\p{F}_i$ send by the prover. Set
  $L = \smallset{\pf_{j_1}, \ldots, \pf_{j_m}}$. \michals{25.08}{Need to adjust
    in case some polynomial is ``last'' for more than one verification equation}
  Assume $\pf_{j_i} = \pf_{j_{i'}}$, that is, there is some polynomial that is
  the last polynomial for more than one verification equation. Assume
  $\pf_{j_i}$ is sent by the prover no later than $\pf_{j_{i'}}$ then pick the
  last polynomial from $\p{F}_{i} \setminus \smallset{\pf_{j_i}}$ and add it to
  $L$. Continue till there is no The simulator proceeds as follows: If
  $\pf_i \not\in L$ then $\simulator$ picks a random polynomial $\pf'_i(X)$ ans
  sends it as $\pf_i$. Alternatively, if $\pf_{j_i} \in L$, then the simulator
  computes
  \[
    \vereq_i(X) 
  \]
\end{proof}

\section{Additional definitions and results we may need at some point}

\begin{definition}[Somehow deterministic WEPHP]
  \label{def:sdwephp}
  Let $\PS$ be a WEPHP for $\REL$. For each polynomial $f_i$ sent by the prover
  denote by $A_i$ the set of challenges sent by the verifier and by $F_i$ the
  set of polynomials sent by the prover \emph{before} the prover sends
  $f_i$. Let $\encset$ be an encoding set. We say that $\PS$ is \emph{somehow
    deterministic} (SD) if for any $(\inp, \wit) \in \REL$, polynomials
  $\smallset{f_i}_{i \in [\noofp]}$ send by the prover, and encoding set
  $\encset \neq [\noofp]$ each polynomial
  $f_j \in \smallset{f_i}_{i \in [\noofp] \setminus \encset}$ is determined by
  \begin{itemize}
    \item polynomials $F_j$, and
    \item the verifier's challenges $A_i$, and
    \item the witness $\wit$.
  \end{itemize}
\end{definition}
Intuitively, we say that WEPHP is somehow deterministic if the only
non-deterministic messages send by the prover are polynomials encoding the
witness, and all other messages are determined by the previous one, witness, and
verifier's challenges.

\subsection{From PHP to zkPHP}
\michals{24.06}{Need to show how to get a ZK PHP from PHP}

\begin{theorem}[From WEPHP to ZK WEPHP]
  Let $\PHP = (\prover, \verifier)$ be a WEPHP and $E$ its encoding set,
  $\maxdeg$ be a maximal degree of polynomials sent by the prover; and
  let $\PHP = (\prover', \verifier')$ be a WEPHP such that
  \begin{itemize}
  \item Both parties get as input a set of $\FF$ elements $H$, such that
    $\abs{H} = \maxdeg + 1$. Denote the vanishing polynomial for $H$ by $\van{H}$.
  \item $\prover'$ acts as $\prover$ except for $f_i(X) \in E$. Let $k_i$ be a
    number of queries $\verifier$ makes to the oracle $\oracleo_{f_i}$ and
    $d_i = \deg(f_i)$, then $\prover'$ computes
      \[
        g_i(X) = f_i(X) + \van{H}\left(X^{d_i + 1} b_1 + \ldots
        X^{d_i + k_i + 1} b_{k_i + 1}\right)
      \]
      for random $b_1, \ldots, b_{k + 1}$ and sets oracle $\oracleo_{g_i}$.
    \item $\verifier'$ acts as $\verifier$. \michals{28.06}{We don't want to
        change the verifier and its equations -- that's why we have $\van{H}$.}
  \end{itemize}
\end{theorem}
\antonio{29.07}{How can we choose the set $H$? In other words, how do we select an $H$ that
does not mess with the completeness or the soundness of the PHP?
Can we just say that if the original PHP checks $G(X,h_1(v_1(X)),...)=0$ then the new PHP
checks $G(X,h'_1(v_1(X)),\dots)$ where $h'_i(X)=h'_i(X)+V_H(X)r_i(X)$ for some randomly
chosen $r_i$? ($V_H$ is the vanishing poly at $H$) I guess completeness would hold for any
$H$ but not sure about soundness, right?}
\michals{18.08}{$H$ is given. Need to think about the second part of your question.}
\begin{proof}
  \ncase{Completeness} 

  \ncase{Soundness} 

  \ncase{Zero-knowledge} To show the property we construct a simulator
  $\simulator$ and argue that it produces proofs indistinguishable from proofs
  of a real prover. The simulator behaves as real prover, except for
  witness-encoding polynomials in $\smallset{f_i}_{i \in E}$. For
  $f_j \in \smallset{f_i}_{i \in E}$, where it
  \begin{itemize}
  \item Picks randomizers $b_1, \ldots, b_{\noofq_j}$ and computes polynomial
    $g_i(X) =  \van{H}(b_1 X + \ldots b_{\noofq_j} X^{\noofq_j})$. 
  \item \michals{28.06}{The simulator can open the commitment to any value, but
      he need to know *which* value}
  \end{itemize}
  
\end{proof}

\section{Unoptimized $\plonk$ with arbitrary polynomial commitment $\PCOM$}
\michals{25.08}{This part is unfinished.}
 In the following we assume either
 \begin{enumerate}
 \item the polynomial commitments $\PCOM$ is $l$-hiding, or \michals{16.08}{$l$
    -hiding -- impossible to tell commitments to two polynomials given up to $l$
  evaluations}
 \item \hl{...} uber assumption holds \michals{16.08}{the distinguisher cannot
     tell a commitment to a random polynomial (case of simulated proof) from a
     commitment to a specific polynomial (that is not in the span of SRS
     polynomials, case of a real proof)}
 \end{enumerate}
 that the polynomial commitment has one of the
 following prope
 \subsection{$\plonk$ protocol rolled out}
\label{sec:plonk_explained}
\subsubsection{The constrain system}
Assume $\CRKT$ is a fan-in two arithmetic circuit,
which fan-out is unlimited and has $\numberofconstrains$ gates and $\noofw$ wires
($\numberofconstrains \leq \noofw \leq 2\numberofconstrains$). \plonk's constraint
system is defined as follows:
\begin{itemize}
\item Let $\vec{V} = (\va, \vb, \vc)$, where $\va, \vb, \vc
  \in \range{1}{\noofw}^\numberofconstrains$. Entries $\va_i, \vb_i, \vc_i$ represent indices of left,
  right and output wires of circuits $i$-th gate.
\item Vectors $\vec{Q} = (\vql, \vqr, \vqo, \vqm, \vqc) \in
  (\FF^\numberofconstrains)^5$ are called \emph{selector vectors}:
  \begin{itemize}
  \item If the $i$-th gate is a multiplicative gate then $\vql_i = \vqr_i = 0$,
    $\vqm_i = 1$, and $\vqo_i = -1$. 
  \item If the $i$-th gate is an addition gate then $\vql_i = \vqr_i  = 1$, $\vqm_i =
    0$, and $\vqo_i = -1$. 
  \item $\vqc_i = 0$ always. 
  \end{itemize}
\end{itemize}

We say that vector $\vx \in \FF^\noofw$ satisfies constraint system if for all $i
\in \range{1}{\numberofconstrains}$
\[
  \vql_i \cdot \vx_{\va_i} + \vqr_i \cdot \vx_{\vb_i} + \vqo \cdot \vx_{\vc_i} +
  \vqm_i \cdot (\vx_{\va_i} \vx_{\vb_i}) + \vqc_i = 0. 
\]

\subsubsection{Algorithms rolled out}
\label{sec:plonk_explained}
\plonk{} argument system is universal. That is, it allows to verify computation
of any arithmetic circuit which has no more than $\numberofconstrains$
gates using a single SRS. However, to make computation efficient, for each
circuit there is allowed a preprocessing phase which extend the SRS with
circuit-related polynomial evaluations.

For the sake of simplicity of the security reductions presented in this paper, we
include in the SRS only these elements that cannot be computed without knowing
the secret trapdoor $\chi$. The rest of the SRS---the preprocessed input---can
be computed using these SRS elements thus we leave them to be computed by the
prover, verifier, and simulator.

\paragraph{$\plonk$ SRS generating algorithm $\kgen(\REL)$:}
The SRS generating algorithm picks at random $\xi \sample \FF_p$, computes
and outputs
\[
	\srs \gets \PCOM.\kgen(\secparam).
\]

\paragraph{Preprocessing:}
Let $H = \smallset{\omega^i}_{i = 1}^{\numberofconstrains }$ be a
(multiplicative) $\numberofconstrains$-element subgroup of a field $\FF$
compound of $\numberofconstrains$-th roots of unity in $\FF$. Let $\lag_i(X)$ be
the $i$-th element of an $\numberofconstrains$-elements Lagrange basis. During
the preprocessing phase polynomials $\p{S_{id j}}, \p{S_{\sigma j}}$, for
$\p{j} \in \range{1}{3}$, are computed:
\begin{equation*}
  \begin{aligned}
    \p{S_{id 1}}(X) & = X,\vphantom{\sum_{i = 1}^{\noofc} \sigma(i) \lag_i(X),}\\
    \p{S_{id 2}}(X) & = k_1 \cdot X,\vphantom{\sum_{i = 1}^{\noofc} \sigma(i) \lag_i(X),}\\
    \p{S_{id 3}}(X) & = k_2 \cdot X,\vphantom{\sum_{i = 1}^{\noofc} \sigma(i) \lag_i(X),}
  \end{aligned}
  \qquad
\begin{aligned}
  \p{S_{\sigma 1}}(X) & = \sum_{i = 1}^{\noofc} \sigma(i) \lag_i(X),\\
  \p{S_{\sigma 2}}(X) & = \sum_{i = 1}^{\noofc}
  \sigma(\noofc + i) \lag_i(X),\\
  \p{S_{\sigma 3}}(X) & =\sum_{i = 1}^{\noofc} \sigma(2 \noofc + i) \lag_i(X).
\end{aligned}
\end{equation*}
Coefficients $k_1$, $k_2$ are such that $H, k_1 \cdot H, k_2 \cdot H$ are
different cosets of $\FF^*$, thus they define $3 \cdot \noofc$
different elements. \cite{EPRINT:GabWilCio19} notes that it is enough to set
$k_1$ to a quadratic residue and $k_2$ to a quadratic non-residue.

Furthermore, we define polynomials $\p{q_L}, \p{q_R}, \p{q_O}, \p{q_M}, \p{q_C}$
such that
\begin{equation*}
  \begin{aligned}
  \p{q_L}(X) & = \sum_{i = 1}^{\noofc} \vql_i \lag_i(X), \\
  \p{q_R}(X) & = \sum_{i = 1}^{\noofc} \vqr_i \lag_i(X), \\
  \p{q_M}(X) & = \sum_{i = 1}^{\noofc} \vqm_i \lag_i(X),
\end{aligned}
\qquad
\begin{aligned}
  \p{q_O}(X) & = \sum_{i = 1}^{\noofc} \vqo_i \lag_i(X), \\
  \p{q_C}(X) & = \sum_{i = 1}^{\noofc} \vqc_i \lag_i(X). \\
  \vphantom{\p{q_M}(X)  = \sum_{i = 1}^{\noofc} \vqm_i \lag_i(X),}
\end{aligned}
\end{equation*}

\paragraph{$\plonk$ prover
  $\prover(\REL, \srs, \inp, \wit = (\wit_i)_{i \in \range{1}{3 \cdot
      \noofc}})$.}
\begin{description}
\item[Round 1] Sample $b_1, \ldots, b_9 \sample \FF_p$; compute
  $\p{a}(X), \p{b}(X), \p{c}(X)$ as
	\begin{align*}
		\p{a}(X) &= (b_1 X + b_2)\p{Z_H}(X) + \sum_{i = 1}^{\noofc} \wit_i \lag_i(X) \\
		\p{b}(X) &= (b_3 X + b_4)\p{Z_H}(X) + \sum_{i = 1}^{\noofc} \wit_{\noofc + i} \lag_i(X) \\
		\p{c}(X) &= (b_5 X + b_6)\p{Z_H}(X) + \sum_{i = 1}^{\noofc} \wit_{2 \cdot \noofc + i} \lag_i(X) 
	\end{align*}
	Output polynomial commitments $\PCOM.\com(\p{a}(X)), \PCOM.\com(\p{b}(X)), \PCOM.\com(\p{c}(X))$.
	
	\item[Round 2]
	Get challenges $\beta, \gamma \in \FF_p$
	\[
		\beta = \ro(\zkproof[0..1], 0)\,, \qquad \gamma = \ro(\zkproof[0..1], 1)\,.
        \]
        Compute
        \begin{align*}
          \p{f_{a}}(X) & = a(X) + \beta X + \gamma \\
          \p{f_{b}}(X) & = b(X) + \beta \omega^{n} X + \gamma \\
          \p{f_{c}}(X) & = c(X) + \beta \omega^{2n} X + \gamma \\
          \p{g_{a}}(X) & = a(X) + \beta \p{S_{\sigma 1}}(X) + \gamma \\
          \p{g_{b}}(X) & = b(X) + \beta \p{S_{\sigma 2}}(X) + \gamma \\
          \p{g_{c}}(X) & = c(X) + \beta \p{S_{\sigma 3}}(X) + \gamma \\
        \end{align*}
	Compute permutation polynomial $\p{z}(X)$
	\begin{multline*}
		\p{z}(X) = (b_7 X^2 + b_8 X + b_9)\p{Z_H}(X) + \lag_1(X) + \\
			+ \sum_{i = 1}^{\noofc - 1} 
			\left(\lag_{i + 1} (X) \prod_{j = 1}^{i} 
			\frac{
			(\wit_j +\beta \omega^{j - 1} + \gamma)(\wit_{\noofc + j} + \beta
      \omega^{\noofc + j - 1} + \gamma)(\wit_{2 \noofc + j} +\beta \omega^{2
        \noofc + j- 1} + \gamma)}
			{(\wit_j+\sigma(j) \beta + \gamma)(\wit_{\noofc + j} + \sigma(\noofc + j)\beta + \gamma)(\wit_{2 \noofc + j} + \sigma(2 \noofc + j)\beta + \gamma)}\right)
	\end{multline*}
  Note that $\p{z}\in \FF_{p}^{\leq 3n}[X]$ satisfies the property that
  $\p{z}(\omega)=1$ and for $i > 1$,
  $\p{z}(\omega^{i}) = \prod_{j=1}^{i} \p{f}(\omega^{i})/\p{g}(\omega^{i})$
  where $\p{f} = \p{f_{a}}\p{f_{b}}\p{f_{c}}$ and
  $\p{g} = \p{g_{a}}\p{g_{b}}\p{g_{c}}$.

	Output polynomial commitment $\PCOM.\com(\p{z}(X))$
		
	\item[Round 3]
    %	Get the challenge $\alpha = \ro(\zkproof[0..2])$,
    Compute the quotient polynomials 
\begin{align*}
	\p{t_1}(X) & = (\p{a}(X) \p{b}(X) \selmulti(X) + \p{a}(X) \selleft(X) + 
               \p{b}(X)\selright(X) + \p{c}(X)\seloutput(X) + \pubinppoly(X) + \selconst(X)) 
               \frac{1}{\p{Z_H}(X)} \\
  \p{t_2}(X) & = (\p{f}(X) \p{z}(X) - \p{g}(X) \p{z}(X\omega)) \frac{1}{\p{Z_H}(X)} =\\
             &  ((\p{a}(X) + \beta X + \gamma) (\p{b}(X) + \beta \omega^{\noofc} X + \gamma)(\p{c}(X)
               + \beta \omega^{2 \noofc} X + \gamma)\p{z}(X)) \frac{1}{\p{Z_H}(X)} \\
             & - (\p{a}(X) + \beta \p{S_{\sigma 1}}(X) + \gamma)(\p{b}(X) + \beta 
               \p{S_{\sigma 2}}(X) + \gamma)(\p{c}(X) + \beta \p{S_{\sigma 3}}(X) + 
               \gamma)\p{z}(X \omega))  \frac{1}{\p{Z_H}(X)} \\
	\p{t_3}(X) & =  (\p{z}(X) - 1) \lag_1(X) \frac{1}{\p{Z_H}(X)}
\end{align*}
Output $\cp{t_i} = \gone{\p{t_i}(\xi)}$, for $i \in \range{1}{3}$.
	
\item[Round 4] Get the challenge $\chz \in \FF_p$, $\chz = \ro(\zkproof[0..3])$.
  Output evaluations
	\begin{align*}
    & \ev{a} = \p{a}(\chz), \ev{b} = \p{b}(\chz), \ev{c} = \p{c}(\chz),
    \ev{S}_{\sigma, 1}= \p{S_{\sigma 1}}(\chz), \ev{S}_{\sigma 2} = \p{S_{\sigma 2}}(\chz),  \\
    & \ev{z} = \p{z}(\chz), \ev{z}_\omega = \p{z}(\chz \omega),
    \ev{t}_1 = \p{t_1}(\chz), \ev{t}_2 = \p{t_2}(\chz), \ev{t}_3 = \p{t_3}(\chz)
	\end{align*}
	
	\item[Round 5]
	%Compute the opening challenge $v \in \FF_p$, $v = \ro(\zkproof[0..4])$.
	Compute the openings for the polynomial commitment scheme
        \michals{11.08}{Need to add that commitment scheme is additively homomorphic}

  \begin{align*}
    & \p{W_\chz^{t_1}} = \PCOM.\open(\srs, \cp{t_{1}}, \p{t_1}(\chz)) \\
    & \p{W_\chz^{t_2}} = \PCOM.\open(\srs, \cp{t_{2}}, \p{t_2}(\chz)), \\
    & \p{W_\chz^{t_3}} = \PCOM.\open(\srs, \cp{t_{3}}, \p{t_3}(\chz)), \\
 %  & \p{W_\chz^{\p{r}}} = \PCOM.\open(\srs, \cp{r}, \p{r}(\chz)), \\
    & \p{W_\chz^{\p{a}}} = \PCOM.\open(\srs, \cp{a}, \p{a}(\chz)), \\
    & \p{W_\chz^{\p{b}}} = \PCOM.\open(\srs, \cp{b}, \p{b}(\chz)), \\
    & \p{W_\chz^{\p{c}}} = \PCOM.\open(\srs, \cp{c}, \p{c}(\chz)), \\
    & \p{W_\chz^{\p{S_{\sigma 1}}}} = \PCOM.\open(\srs, \cp{S_{\sigma 1}}, \p{S_{\sigma 1}}(\chz)), \\
    & \p{W_\chz^{\p{S_{\sigma 2}}}} = \PCOM.\open(\srs, \cp{S_{\sigma 2}}, 
      \p{S_{\sigma 2}}(\chz)), \\
    & \p{W_{\chz}^{\p{z}}} = \PCOM.\open(\srs, \cp{z}, \p{z}(\chz)) \\
    & \p{W_{\chz \omega}^{\p{z}}} = \PCOM.\open(\srs, \cp{z}, \p{z}(\chz \omega))
 \end{align*}
 Output the computed polynomial commitment openings.
\end{description}

\ncase{$\plonk$ verifier $\verifier(\REL, \srs, \inp, \zkproof)$}\ \newline
The \plonk{} verifier works as follows
\begin{description}
	\item[Step 1] Validate all obtained group elements.
	\item[Step 2] Validate all obtained field elements.
	\item[Step 3] Validate the instance $\inp = \smallset{\wit_i}_{i =
      1}^\ell$.%instsize.
	\item[Step 4] Compute challenges $\beta, \gamma, \alpha, \chz, v,
    u$ from the transcript.
	\item[Step 5] Compute zero polynomial evaluation
      $\p{Z_H} (\chz) =\chz^\noofc - 1$.
	\item[Step 6] Compute Lagrange polynomial evaluation
      $\lag_1 (\chz) = \frac{\chz^\noofc -1}{\noofc (\chz - 1)}$.
    \item[Step 7] Compute public input polynomial evaluation $\pubinppoly (\chz)
      = \sum_{i \in \range{1}{\instsize}} \wit_i \lag_i(\chz)$.
	\item[Step 8] Compute evaluations of constraint polynomial and
    permutation-argument polynomial
\begin{align*}
	\ev{t_1} & = (\ev{a} \ev{b} \selmulti(\chz) + \ev{a}(\chz) \selleft(\chz) + 
             \ev{b}\selright(\chz) + \ev{c}\seloutput(\chz) + \pubinppoly(\chz) + \selconst(\chz)) 
             \frac{1}{\p{Z_H}(\chz)} \\
	\ev{t_2} & = ((\ev{a} + \beta \chz + \gamma) (\ev{b} + \beta \omega^{\noofc} \chz + \gamma)(\ev{c} 
             + \beta \omega^{2 \noofc} \chz + \gamma)\ev{z} \frac{1}{\p{Z_H}(\chz)} \\
           & - (\ev{a} + \beta \ev{S_{\sigma 1}} + \gamma)(\ev{b} + \beta 
             \ev{S_{\sigma 2}} + \gamma)(\ev{c} + \beta \ev{S_{\sigma 3}} + 
             \gamma)\ev{z_{\omega}}  \frac{1}{\p{Z_H}(\chz)} \\
	\ev{t_3} & =  (\ev{z} - 1) \lag_1(\chz) \frac{1}{\p{Z_H}(\chz)}
\end{align*}
\item[Step 9] Verify all polynomial commitment openings.
\end{description}



\ncase{$\plonk$ trapdoor-less simulator $\simulator(\REL, \srs, \inp)$}\ \newline
The \plonk{} simulator proceeds as an honest prover would, except:
\begin{enumerate}
\item In the first round, it sets
  $\wit = (\wit_i)_{i \in \range{1}{3 \noofc}} = \vec{0}$, and at random picks
  $b_1, \ldots, b_9$. Then it proceeds with that all-zero witness.
\item In Round 3, it picks randomly challenge $\chz$, computes polynomial
  evaluations $\ev{t_i} = \p{t_i}(\chz)$, for $i \in \range{1}{3}$, and picks
  random polynomials $\p{t'_i}(X)$ such that $\p{t'_i}(\chz) = \p{t_i}(\chz)$
  and commits to them.
\end{enumerate}
 
We write $\PHP^{\PCOM}$ to denote a interactive proof system compiled from a PHP $\PHP$ using
polynomial commitment $\PCOM$. We denote its non-interactie variant compiled using Fiat-Shamir by $\PHP^{\PCOM}_{\fs}$. E.g., we denote the above rolled out non-interactive version of the
$\plonk$ proof system by $\plonkprotfs^{\kzg}$, where $\kzg$ denotes the KZG
polynomial commitment scheme.

\begin{theorem}
  Let $\PCOM$ be a polynomial commitment scheme that is evaluation-binding, binding, simulation-extractable, and a commitment of knowledge,
  then $\plonkprotfs^{\PCOM}$ is simulation extractable.
%  \michals{16.08}{$(3, \eps)$-aux-simulation-extractable -- $3$ polynomials are
%    extracted, $1 - \eps$ is probability of extractor's success, aux -- see how
%    we compute the challenge}
\end{theorem}
\begin{proof} \ \\

\noindent
  \textbf{Building simulator for SNARK from simulator for PC}
We describe $\oraclesps,\ro$ in terms of calls to $\oraclespcom,\ro_{\aux}$.

\noindent
We simulate $\ro(x_{1}\|x_{2})$ via calls to $\ro_{aux}(x_{1},x_{2})$, where
$x_{1}$ has the length of 3 commitments. \michals{30.08}{sometimes more than
  just 3}\markulf{02.09}{I switched the order to be $\vec{c},aux$, so it should be 3 no? I think that order is more intuitive, though aux also contains instance $\inp$?.}

\noindent
Queries to $(\inp, \wit)$ to $\oraclesps$ are answered as follows:
\begin{itemize}
      \item Ask $\oraclespcom$ for 7 random commitments,
        $\cp{a}, \cp{b}, \cp{c}, \cp{z}, \cp{t'_1}, \cp{t'_2}, \cp{t'_3}$, using the $(\msg{commit})$ query.
      \item Compute random elements $\beta, \gamma, \chz$ as
        random oracle evaluations of $\ro_{aux}$ at partial transcripts.
      \item Pick random evaluations $\ev{a}, \ev{b}, \ev{c}, \ev{z}$ and ask $\oraclespcom$ to simulate openings of the corresponding commitments at $\chz$ to get
        openings $W^{\p{f}}_\chz$, for
        $\p{f} \in \smallset{\p{a}, \p{b}, \p{c}, \p{z}}$.
      \item Pick random evaluation $\ev{z}_{\omega}$ and ask $\oraclespcom$ to simulate opening of commitment $\cp{z}$ at $\omega \chz$ using the query $(\msg{open}, \cp{z}, \chz, \ev{z}_{\omega})$ to get
        openings $W^{\p{z}}_{\omega \chz}$.
      \item Compute evaluations $\p{S_{\sigma 1}}(\chz)$,
        $\p{S_{\sigma 2}}(\chz)$ and simulate openings $W^{\p{S_{\sigma 1}}}_\chz$,
        $W^{\p{S_{\sigma 2}}}_\chz$ for commitments in $\srss$.
\markulf{02.09}{Probably a good idea for fixed polynomials. In fact, we probably have to do it this way.}
        \michals{30.08}{Why not computing them honestly?}
								\antonio{02.09}{Good question. I think that it is better to ask the simulator, the
								reason is that we could imagine a PolyCom (not KZG, I mean a generic one) that
							uses randomness to produce valid proofs.}
      \item For $i \in \range{1}{3}$, compute values of $\ev{t}_i$ as
        defined by the verification equation.
      \item For $i \in \range{1}{3}$, ask $\oraclespcom$ to simulate opening of $\cp{t'_i}$
        to $\ev{t}_i$ at $\chz$.
      \item From the obtained commitments, evaluations, openings, and random
        elements compute a simulated proof $\zkproof$ for $\inp$.
      \end{itemize}

\noindent
\textbf{Building an adversary for PC from adversary for SNARK}
Given an SE adversary $\adv^{\oraclesps}(\srs, \srss, \radv)$ for $\PS_\fs^{\PCOM}$
we build an adversary $\bdv^{\oraclespcom}(\srs_{\PCOM}, \rbdv)$ for the SE-PCOM.

We equip adversary $\bdv$ with $\adv$'s code and randomness
  $\radv$. (Importantly $\bdv$ does not use any randomness on its
  own). $\bdv$ proceeds as follows
  \begin{enumerate}
  \item Given $\PCOM$ reference string $\srs_{\PCOM}$, prepare $\PS$'s master
    SRS $\srs$ and specialized SRS $\srss$ for relation $\REL$.
  \item Start $\adv(\srs, \srss, \radv)$.
    \item On each $\adv$'s query $(\inp, \wit)$ to $\oraclesps$:
    \begin{enumerate}
    \item Check $\REL(\inp, \wit) = 1$ and ignore if that's not the case.
      \item Prepare a simulated proof $\zkproof$ for $\adv$ using $\oraclespcom$ and $\ro_{aux}$ as described above.

            \iffalse
            , that is
      \begin{itemize}
      \item Ask $\oraclespcom$ for 7 commitments to random polynomials, denote
        the commitments by
        $\cp{a}, \cp{b}, \cp{c}, \cp{z}, \cp{t'_1}, \cp{t'_2}, \cp{t'_3}$.
      \item Compute random elements $\alpha, \beta, \gamma, \delta, \chz$ as
        random oracle evaluations at partial transcripts.
      \item Ask $\oraclespcom$ to evaluate all the polynomials at $\chz$ and get
        openings $W^{\p{f}}_\chz$, for
        $\p{f} \in \smallset{\p{a}, \p{b}, \p{c}, \p{z}}$.  \markulf{24.08}{We
          don't actually know the random polynomials, so we cannot compute their
          evaluations, but just simulating opening proofs for random
          $\ev{a},\dots$ should work.}
        \michals{25.08}{Here we ask the simulator oracle for evaluation. Do you
          think it is also not allowed?}
      \item Ask $\oraclespcom$ to evaluate $\p{z}$ at $\omega \chz$ and get
        openings $W^{\p{z}}_{\omega \chz}$.
      \item Compute evaluations $\p{S_{\sigma 1}}(\chz)$,
        $\p{S_{\sigma 2}}(\chz)$ and openings $W^{\p{S_{\sigma 1}}}_\chz$,
        $W^{\p{S_{\sigma 2}}}_\chz$.
      \item For $i \in \range{1}{3}$, compute values of $\p{t_i}(\chz)$ as
        defined by the proof.
      \item For $i \in \range{1}{3}$, ask $\oraclespcom$ to evaluate $\cp{t'_i}$
        to open $\p{t'_i}(\chz)$ to $\p{t_i}(\chz)$.
      \item From the obtained commitments, evaluations, openings, and random
        elements compute a simulated proof $\zkproof$ for $\inp$.
      \end{itemize}
            \fi
    \item Add $(\inp, \zkproof)$ to $\qadv$.
    \end{enumerate}
  \item On $\adv$'s challenge instance $\inp$ and proof $\zkproof$.
    \begin{enumerate}
    \item Parse $\zkproof$ to obtain
      \begin{itemize}
      \item commitments
        $\cp{a}, \cp{b}, \cp{c}, \cp{z}, \cp{t_1}, \cp{t_2}, \cp{t_3}$,
      \item random elements $\beta, \gamma$,
      \item openings $W_\chz^{\p{a}}, W_\chz^{\p{b}}, W_\chz^{\p{c}}$.
      \end{itemize}
    \item Compute
      $\aux = (\beta, \gamma, \cp{z}, \cp{t_1},
      \cp{t_2}, \cp{t_3})$. \michals{30.08}{aux independent on the instance,
        does it matter?}\markulf{02.09}{You are right, we need $\inp$ here.j}
    \item Output
      \begin{itemize}
      \item commitments $\cp{a}$, $\cp{b}$, $\cp{c}$,
      \item auxiliary input $\aux$,
    %  \item challenge $z = \ro(\aux)$,
      \item openings $o = (W_\chz^{\p{a}}, W_\chz^{\p{a}},  W_\chz^{\p{c}})$.
      \end{itemize}
    \end{enumerate}
  \end{enumerate}

  Now, since the polynomial commitment scheme is simulation
  extractable, then there exists an extractor
  $\ext_{\bdv}(\srs_{\PCOM}, \qbdv, \rbdv)$ that outputs $\p{a}, \p{b}, \p{c}$.\smallskip

\noindent\textbf{Building an extractor for SNARK from an extractor for PC}
  We show how to use the extractor
  $\ext_\bdv(\srs_{\PCOM}, \qbdv, \rbdv)$, where $\qbdv$ is a list of all
  queries to $\oraclespcom$ and their responses, to build an extractor
  $\ext_\adv(\srs, \srss, \qadv, \radv)$, where $\qadv$ is a list of all queries
  to $\oraclesps$ and their responses, that outputs witness $\wit$ such that
  $\REL(\inp, \wit) = 1$.


  The extractor $\ext_\adv$ makes a single call to
  $\ext_{\bdv}$: It gets as input $\srs, \srss$ from which it computes
  $\srs_{{\PCOM}}$. As the simulator for the SNARK can be obtained from the simulator for PC, $\qadv$ allows to derive $\qbdv$.  The
  randomness $\radv$ is reused unchanged as $\rbdv$.
  $\ext_{\bdv}(\srs_{\PCOM}, \qbdv, \rbdv)$ outputs $\p{a}, \p{b}, \p{c}$ from
  which we decode the witness.

  % Since for $\plonk$ these are witness-encoding polynomials, one can reveal
  % $\inp$'s witness $\wit$.
  \comment{ To show that the extractor succeeds with overwheming probability, we
    relate the polynomials $\p{a}, \p{b}, \p{c}$ it produces to the coefficients
    $\p{a}', \p{b}', \p{c}'$ of the corresponding polynomial commitment produced
    by a related knowledge soundness algebraic adversary $\adv'$. $\adv'$ runs
    $\adv$ internally and simulates the signing oracle.

    When $\ext_\adv$ fails to extract a valid witness, one of two cases must
    hold: (i) either $(\p{a}, \p{b}, \p{c}) \neq (\p{a}', \p{b}', \p{c}')$ in
    which case we break the soundness of the polynomial commitment scheme or
    (ii), $\adv'$ breaks knowledge soundness.  }



  \ncase{Game 1} Let $\adv^{\oraclesps}(\srs, \srss, \radv)$ be a (true) SE adversary
  for $\PS_\fs^{\PCOM}$
  \michals{20.08}{Continue -- that's a standard SE game here.}
  The game returns $1$ iff extractor $\ext_\adv(\srs, \srss, \qadv,
  \qroadv{\adv})$ fails to output witness $\wit$ such that for $\adv$'s output
  $(\inp, \zkproof)$ holds $\REL(\inp, \wit)$.
  
  We now show that the extracted polynomials indeed encode witness $\wit'$ (this
  witness may differ from the witness $\wit$ provided by the prover) such that
  $\REL(\inp, \wit') = 1$. For that end, we introduce the following games.

 
  \ncase{Game 2} Is the same as Game 1 except that $\oraclesps$ returns now real
  proofs instead of simulated ones.

  \ncase{$\game{1} \mapsto \game{2}$} The difference in the winning
  probabilities between $\game{1}$ and $\game{2}$ is negligible by the
  zero-knowledge property of the prove system.

  This comes since in $\game{1}$ the adversary $\adv$ sees proofs from the same
  distribution as simulated proofs. In $\game{2}$ adversary $\adv$ gets real
  proofs.  \hl{continue}

  \ncase{Game 3} We combine randomness of
  $\adv, \oracles, \ro$.\michals{30.08}{What does it mean?} That is, we consider
  adversary $\bdv$ that has access to a random oracle $\ro$ and internally run
  $\adv$ and provides it with $\oracles$. $\adv$'s queries to $\ro$, are passed
  by $\bdv$ to the oracle.
  \michals{30.08}{I don't let $\bdv$ control $\ro$ to be able to use $\bdv$ to
    break polynomial comittment binding proeprty} Let $h$ be the upper bound on the number of random
  oracle queries. Let $\bdv_i^{\cp{f}}$, for
  $\pf \in \pF = \smallset{\p{a}, \p{b}, \p{c}, \p{z}, \p{t_1}, \p{t_2},
    \p{t_3}}$, be adversaries such that when $\adv$ makes $i$-th random oracle
  query to $\ro$ and the query's argument is
  \begin{itemize}
  \item $(\inp, \cp{a}, \cp{b}, \cp{c})$ \michals{30.08}{Added instance
      $\inp$}, then $\bdv^{\cp{a}}_i, \bdv^{\cp{b}}_i, \bdv^{\cp{c}}_i$ return
    $\cp{a}$, $\cp{b}$, and $\cp{c}$ respectively.
  \item $(\inp, \cp{a}, \cp{b}, \cp{c}, \beta, \gamma, \cp{z}, \cp{t_1},
    \cp{t_2}, \cp{t_3})$, then $\bdv^{\cp{z}}_i, \bdv^{\cp{t_1}}_i,
    \bdv^{\cp{t_2}}_i, \bdv^{\cp{t_3}}_i$ return
    $\cp{z}$, $\cp{t_1}$, $\cp{t_2}$ and $\cp{t_3}$ respectively.
  \end{itemize}

  Since $\PCOM$ is a commitment of knowledge, there exist extractors
  $\ext_{\bdv^{\cp{f}}_i}$, for
  $(i, \p{f}) \in {\range{1}{h}} \times \p{F}$ that given randomness of
  $\bdv^{\cp{f}}_i$ return $\p{f}$.

  The game returns $1$ if some of the extractors fails. Denote by
  $\eps^{\p{f}}_i$ (negligible) probability that $\ext_{\bdv^{\cp{f}}_i}$
  fails. Probability that the game returns $1$ is then upperbounded by $\sum_{i
    = 1}^h \sum_{\pf \in \p{F}} \eps^{\pf}_i$, which remains negligible.

  \ncase{$\game{2} \mapsto \game{3}$}

  \ncase{Game 4}
  This game aborts if $\adv$ never queried $\ro$ on $(\inp, \cp{a}, \cp{b},
  \cp{c})$.

  \ncase{$\game{3} \mapsto \game{4}$}

  \ncase{Game 5}
  This game aborts if polynomials $\p{a'}, \p{b'}, \p{c'}$ extracted by 
  $\ext_{\bdv^{\cp{a}}_i}, \ext_{\bdv^{\cp{b}}_j}, \ext_{\bdv^{\cp{c}}_k}$, for
  some $i, j, k \in \range{1}{h}$ differ from polynomials $\p{a}, \p{b}, \p{c}$
  extracted by $\ext_\adv$. W.l.o.g.~assume that $\p{a'} \neq \p{a}$.

  \ncase{$\game{4} \mapsto \game{5}$} \michals{30.08}{Here comes binding}
  We
  build a polynomial commitment scheme binding adversary $\rdv$ that succeeds
  if game $\game{5}$ aborts.
  \michals{30.08}{Definie polynomial commitmetn binding property -- note we need
    random entry}

  Adversary $\rdv(\srs_{\PCOM})$ proceeds as follows
  \michals{30.08}{In the following we may remove all occurences of $\p{b},
    \p{c}$ and corresponding algorithms as we assumed that $\p{a'} \neq \p{a}$
    -- that's the only polynomials we need}
  \begin{itemize}
  \item Compute $\srs, \srss$ out of $\srs_{\PCOM}$ and give it to adversaries
    $\adv$, $\bdv$, $\bdv^{\cp{f}}_i$,
    $(i, \pf) \in \range{1}{h} \times \smallset{\p{a}, \p{b}, \p{c}}$ and their
    extractors.
  \item Run $\adv$, $\bdv$,
    $\bdv_{\cp{a}}^{i}, \bdv_{\cp{b}}^{j}, \bdv_{\cp{c}}^{k}$ till commitents
    $\cp{a}, \cp{b}, \cp{c}$ are produced. 
  \item Run $\ext_{\bdv^{\cp{a}}_i}, \ext_{\bdv^{\cp{b}}_i},
    \ext_{\bdv^{\cp{c}}_i}$ to get $\p{a'}, \p{b'}, \p{c'}$.
  \item When $\adv$ and $\bdv$ ask for a challenge $\chz$, send to challenger
    $\challenger$ $\cp{a}$ as a commitment. When it returns $z$ as the
    evaluation point, pass it to $\adv$ and $\bdv$ as the random oracle
    challenge $\chz$.
  \item When $\adv$ is done with its proof, run $\ext_{\adv}$ to reveal
    polynomials $\p{a}$, ${\p{b}}$, $\p{c}$. 
  \item Parse $\adv$'s proof for evaluation $\p{a}(\chz)$ and opening
    $W_{\chz}^{\p{a}}$.
  \item Evaluate $\bdv$'s proof for evaluation $\p{a'}(\chz)$ and opening
    $W_{\chz}^{\p{a'}}$.
  \item Output $(\p{a}, \p{a}(\chz), W^{\p{a}}_\chz)$ and $(\p{a'},
    \p{a'}(\chz), W^{\p{a'}}_\chz)$. \michals{30.08}{This breaks binding}
  \end{itemize}
  
  \ncase{Game 6}
  This game aborts also if the extracted polynomials do not encode the correct
  witness.

  \ncase{$\game{5} \mapsto \game{6}$}
  \michals{30.08}{Reduction to a php adversary}

  \end{proof}
  
\section{DRAFT-Notes on transformation to Universal Interactive Arguments}

\antonio{02.08}{Writing this note to convince myself that things aren't so easy as I
thought. Please could you tell me where the argument below should fail?}
In Lunar we define the notion of Universal Interactive Argument Systems in the SRS model
as a middle ground for our transformation from PHP to Universal SNARKs.

Here I want to show that we can reduce sim-ext of Universal Interactive Argument System
(UIA) to the "standard" security properties of UIA.
We assume the following properties from the UIA:
\begin{itemize}
	\item {\bf Straight-line extractability in the AGM.}
		There exists an ``extractor'' $\Ext$ (the name extractor might be slightly misleading, but I
		cannot find a better name for now) s.t. for any algebraic adversary $\adv$:
		\[
			\Prob[\srs,r]{
					b=1 \wedge (\inp,\wit)\not\in\ind:
					\begin{array}{l}
					\ind,\inp, \vec X \gets\adv(\srs),\\
					(\vec P,b) \gets \braket{\adv(\srs),\verifier(\Iphp(\ind),\inp;r)}\\
					\wit \gets \Ext(\inp,\ind,r,\vec X,\vec P)
					\end{array}
					}\in\negl
		\]
		In the probability above $r$ is uniformly random in $\bin^\secpar$, and $\vec P$ and
		$\vec X$	describe all the group elements output by the adversary as linear combination of
		$\srs$. $b=1$ means that the adversary convinces the verifier. Also, if $\inp$ or $\ind$
		do not contain any group elements then $\vec X$ is	empty. Finally, for simplicity we assumes that the adversary outputs only element in
		$\GG_1$ and $\GG_2$, so only linear combinations are allowed.
	\item {\bf honest-verifier zero-knowledge w/o trapdoor.}
		There exists a simulator $\sdv$ such that for any $\srs,\ind,\inp,\wit$ we have
		$\sdv(\srs,\ind,\inp)\equiv
		\braket{\prover(\srs,\ind,\inp,\wit),\verify(\srs,\Iphp(\ind),\inp)}$
		(For simplicity I am assuming perfectly close, to assume comp./statical closeness one should also
		take care of adaptive choice of $\inp,\ind$ w.r.t. $\srs$)

	\item {\bf (technical property) algebraic simulator.}
		The simulator additionally outputs a matrix $\vec T$ such that the output group elements
		are linear combinations of $\srs,\ind,\inp$

%	\item {\bf (technical property) unpredictability of honest prover .}
%		For any $\srs,\ind,\inp,\wit$ and let $\pmsg_1,\vmsg_1,\dots,\pmsg_m$ be a transcript for
%		$\braket{\prover(\srs,\ind,\inp,\wit),\verifier(\srs,\ind,\wit)}$ then	$\minH(\pmsg_1)\geq \secpar$.
%		(Thus also the simulated $\tilde\pmsg_1$ has a lot of min entropy)
\end{itemize}

Let $\adv$ be an adversary for the sim-ext of the UIA.
We wanna prove that:
\[
			\Prob[\srs,r]{
					b=1 \wedge (\inp,\wit)\not\in\ind:
					\begin{array}{l}
						\ind,\inp, \vec X \gets\adv^{SIM}(\srs),\\
					(\vec P,b) \gets \braket{\adv(\srs),\verifier(\Iphp(\ind),\inp;r)}\\
					\wit \gets \Ext(\inp,\ind,r,\vec X,\vec P)
					\end{array}
					}\in\negl
\]
where $SIM( \ind,\inp )$ produces a simulated (honest-verifier) proof for $\ind$ and $\inp$.
\antonio{02.08}{This notion of sim-ext plus a technical property that says that the first
message of the honest prover is unpredictable (it has high min-entropy) should imply
sim-sound for the compiled fiat-shamir protocol.}

Consider the algebraic adversary $\bdv$ described below:
\begin{itemize}
	\item Input is $\srs$ and it runs $\adv$ with input $\srs$, let $[\vec s]$ be (an
		initially empty)	dynamic vector that includes all the group elements seen by $\adv$ through calls to
		$SIM$.
%	\item Lazy simulate the random oracle (we assume $RO$ codomain is $\FF$ so verifier's
%		messages)
	\item On $\adv$ sending $\ind,\inp$ to $SIM$, notice that $\adv$ is algebraic, thus it
		additionally outputs $\vec X$ that describes $\ind,\inp$ as linear combinations of
		$\srs$ and $[\vec s]$:
		\begin{enumerate}
			\item Let $\vec S$ be a description of $[\vec s]$ as lin.comb of $\srs$ (set to empty
				matrix if first call).
				From $\vec X$ and $\vec S$ we can define a new matrix $\vec X'$ that describes
				$\ind,\inp$ as linear combs of $\srs$.
			\item Run $\sdv(\srs,\ind,\inp)$ and get a simulated transcript together with a matrix $\vec T$
				 that describes all the group elements in the simulated transcript as linear combinations of $\srs,\ind,\inp$.
					From $\vec X'$ and $\vec T$ we can compute a matrix $\vec T'$ that describes all
					the group elements in the transcript of the proof as linear combinations of the
					$\srs$. Update $\vec S$ concatenating the matrix $\vec T'$.
			\item Return the simulated transcript to $\adv$.
		\end{enumerate}
	\item On output $\ind,\inp,\vec X$ of $\adv$ define $\vec X'$ from $\vec X$ and $\vec S$
		and output $\ind,\inp,\vec X$ as first output for the sim-ext experiment.
	\item Similarly, follow the protocol proxing messages from/to $\adv$ and the external verifier.
		Eventually $\adv$ outputs $\vec T$, thus given $\vec S$ and $\vec T$ compute $\vec T'$
		that describes all the group elements in the transcript as linear combinations of the
		$\srs$.
\end{itemize}


Here I am being very sloppy with how we obtain, for example, $\vec X'$ from $\vec X$ and
$\vec S$.
More in detail, if 
$\vec y = (\vec M_0, \vec M_1) \pmtrx{\vec x\\\vec x'}$ and $\vec x' = \vec N \vec x$ then
easily $\vec y = \vec M' \vec x$ where $\vec M' = \vec M_0 + \vec M_1\vec N$.

\section{Results from the Edinburgh visit}
\newcommand{\Qop}{Q_{op}}
\newcommand{\Qh}{Q_{ro}}

%\newcommand{oraclechal}{\oracleo_{chal}}

\newcommand{\qop}{q_{op}}
\newcommand{\qchal}{q_{chal}}
\subsection{To be added to preliminaries}
Let proof system $\PS$ compounds of $\mu + 1$ messages sent by the prover and $\mu$
messages sent by the verifier. We say that such proof system has $\mu$ \emph{rounds}
or $(2\mu + 1)$ \emph{messages}. We define a round by a pair of messages: one that
comes from the prover, and another coming from the verifier. When the first message
in the proof system comes from the verifier, we assume that the first round of such
proof system contains empty prover's message.

We denote the proof by $\zkproof$ and its partial transcripts that contains all
prover's and verifier's messages exchanged up to and including Round $i - 1$ by
$\zkproof[i - 1]$.

\subsection{Proof system definitions}

\begin{definition}[Evaluation ready polynomial]
  Let $\p{p} (\vec{X})$ be a polynomial over random variable $\vec{X}$. We call
  $\p{p}$ \emph{evaluation ready} if all $X \in \vec{X}$ have been already realised.
\end{definition}

\subsubsection{The idealised proof system}
  \label{def:ps}
  An idealised zero knowledge proof system $\PS$ consists of four parties: indexer
  $\indexer$, prover $\prover$, verifier $\verifier$, and simulator
  $\simulator$.

  \paragraph{Indexer.} The protocol starts with the indexer $\indexer$ providing
  index $\ind$. This step needs to be performed only once for all circuits up to
  given size. \michals{13.12}{Should we introduce here universal setup vs specialized
    setup?}

  \paragraph{Prover.} Prover $\prover$ gets as input the index $\ind$, instance $\inp$ and the
  corresponding witness $\wit$ and starts the protocol with picking $l$ random values
  $\vec{b} = b_1, \ldots, b_l$. Then in each Round $i$ it sends messages
  $m_{i, 1}, \ldots m_{i k'_i}$ and sets up polynomial oracles
  $\oracleo_{\p{p}_{i, 1}}, \ldots, \oracleo_{\p{p}_{i, k_i}}$ for polynomials
  $\p{p}_{i, 1} (\vec{X}, \vec{b}), \ldots, \p{p}_{i, k_i} (\vec{X}, \vec{b})$, where
  $\vec{X}$ is a vector of length $l'$.
  
  \paragraph{Verifier.} The verifier in Round $i$ sends challenges, which we divide
  into two groups:
  \begin{itemize}
  \item \emph{protocol building challenges} $\beta_{i, j}$ where index $(i, j)$
    should be interpreted as $j$-th challenge in Round $i$. We denote by
    $\vec{\beta_i}$ the vector of all challenges sent by the verifier in Round $i$.
  \item \emph{evaluation challenges} $\vec{x_{i, j, k}}$, where index $(i, j, k)$
    means $k$-th challenge to polynomial $\p{p}_{i, j}$. Denote by $K_{i, j}$ number
    of evaluation challenges that the verifier sends to the oracle
    $\oracleo_{\p{p}_{i, j}}$. When all $K_{i, j}$ evaluation challenges are sent,
    the verifier learns $\p{p}_{i, j} (\vec{x_{i, j, k}}, \vec{b})$, for
    $k = 1, \ldots, K_{i, j}$.
  \end{itemize}

  Eventually, the verifier decides either to accept or reject the proof. 

  We interpret messages $m_{i, j}$ sent by the prover as polynomials that are
  independent of random variables in $(\vec{X}, \vec{B})$ which has not been
  realised yet. Other way around, messages $m_{i, j}$ are polynomials which
  evaluations points are fully specified, i.e.~constants. For the sake of
  convenience, we write $\p{p}_{i, j + k_i} (\vec{X}, \vec{B})$ to denote $m_{i,
    j}$. That is, we append polynomials corresponding to messages $m_{i, j}$ to the
  end of the list of polynomials $\p{p}_{i, j} (\vec{X}, \vec{B})$. From now on, we
  will use only $\p{p}_{i, j} (\vec{X}, \vec{B})$ and not $m_{i, j}$. Importantly,
  since polynomials $\p{p}_{i, k_i + j} (\vec{X}, \vec{B})$ are independent of random
  variables that have not been realised yet, the prover sends their evaluations
  directly to the verifier without setting up oracles for them. For the rest of the
  polynomials the oracles are set up as usual.

  Before we describe how the last party -- the simulator -- works, we introduce some
  new definitions and make some assumptions on our proof system.

  In the following we consider two kinds of polynomials -- randomised and determined.
  \begin{definition}[Randomised and determined polynomials]
  \begin{itemize}
  \item Let $\p{p}_{i', j'} (\vec{X}, \vec{B})$ be a polynomial that is evaluated at
    $K_{i', j'}$ points. We call $\p{p}_{i', j'} (\vec{X}, \vec{B})$
    \emph{randomised} if there are
    $B_{i_1}, \ldots, B_{i_{K_{i' j'}}} \in \smallset{B_1, \ldots, B_l}$ such that
    $\p{p}_{i', j'} (\vec{X}, \vec{B})$ has non-zero coefficient next to $B_{i_k}$
    while for all $\p{p}_{i, j}$ for $(i, j) < (i', j')$, coefficient next to
    $B_{i_k}$ is zero. We denote the set of randomized polynomials by $R$. In that
    case we also say that $\p{p}_{i', j'}$ \emph{introduces} $B_{i_k}$. Hence, a
    randomised polynomial evaluated at $K$ points is a polynomial that introduces at
    least $K$ randomizers $B_{i}$.

    Importantly, we assume that there is no polynomials $\p{p}_{i', j'}$ which are
    evaluated at $K$ points but that introduces only $K'$, for $K' \in \range{1}{K - 1}$,
    randomisers $B_{i'_1}, \ldots, B_{i_K'} \in \smallset{B_1, \ldots, B_l}$.

  \item Polynomials $\p{p}_{i, j} (\vec{X}, \vec{B})$ that are not \emph{randomised
      polynomials} are called \emph{determined}. We denote the set of determined
    polynomials by $D$.
  \end{itemize}
\end{definition}

Let $(\ind, \inp, \wit) \in \REL$, $\vec{b} \sample \FF^{l}$ and
$(\p{p}_{i, j} (\vec{X}, \vec{b}))_{(i, j)}$ be randomised polynomials which an honest
prover $\prover (\ind, \inp, \wit)$ sets an oracle for. Denote by $(\dist{P}_{i, j,
  k})_{(i, j, k)}$ a composed distribution such that
\begin{equation}
  \left\{ (\p{p}_{i, j} (\vec{x_{i, j, k}}, \vec{b}))_{(i, j)}\right\}_{\vec{x_{i, j,
        k}}} \approx (\dist{P}_{i, j, k})_{(i, j, k)}.\label{eq:distribution_P}
\end{equation}

That is, $\dist{P}_{i, j, k}$ is a distribution of evaluation values of the
polynomials sent by the prover w.r.t.~the randomisers the prover picked and
verifier's challenges. We note that in popular proof systems like, e.g.~Plonk,
Marlin, Sonic, etc.~this distribution is a uniform distribution -- regardless of the
challenges picked by the verifier.

The following shows that for a polynomial $\p{p} (\vec{X}, \vec{B})$ that evaluates at
points $(\vec{x_i}, \vec{b})_{i \in I}$ to $(r_i)_{i \in I}$ one, given $(\vec{x'_i})_i$
could compute $\vec{b'}$ and polynomial $\p{p'}$ that evaluates to $(r_i)_{i \in I}$ at
$(\vec{x'_i}, \vec{b'})$. This lemma will be particularly useful later, when we show how
the simulator can compute polynomials which evaluations match evaluations of polynomials
provided by some honest prover.

    \begin{lemma}
      \label{lem:matching_R_polys}
      Let $\p{p}_{i, j} (\vec{X}, \vec{B})$ be a polynomial, $\vec{x_{i, j, k}}$ be
      an evaluation point and let $\vec{b}$ be a vector.  Then there is a a PPT
      algorithm $\adv$ that for any $\vec{x'_{i, j, k}}$ outputs a rational function
      $\p{p}'_{i, j} (\vec{X}, \vec{B})$ and vector $\vec{b'}$ such that
      $\p{p}_{i, j}(\vec{x_{i, j, k}}, \vec{b}) = \p{p}'(\vec{x'_{i, j, k}},
      \vec{b'})$.
    \end{lemma}
    \begin{proof}
      Algorithm $\adv$ begins by picking coefficients of $\p{p}''_{i, j} (\vec{X}, \vec{B})$
      randomly and defines
      \[
        \p{p}'_{i, j} (\vec{X}, \vec{B}) = \p{r} (\vec{X}, \vec{B})  +
      \sum_{k = 1}^{K_i, j} b_{i, j, k} (\vec{X}),
    \]
    where $\p{r} (\vec{X}, \vec{B})$ and $b_{i, j, k} (\vec{X})$ are defined as
    follows:
    \begin{align*}
      \p{r} (\vec{X}, \vec{B}) & = \p{p}''_{i, j} (\vec{X}, \vec{B}) \cdot \prod_{k = 1}^{K_{i, j}} (X_1 \cdot \ldots \cdot X_{l'} - x'_{i, j, k, 1} \cdot \ldots \cdot x'_{i, j, k, l'}) \\
      b_{i, j, k} (\vec{X}) & =  r_{i, j, k} \prod_{k' = 1, k' \neq k}^{K_{i, j}} \frac{(X_1 \cdot \ldots \cdot
                              X_{l'} - x'_{i, j, k', 1} \cdot \ldots \cdot x'_{i, j, k', l'})}{(x'_{i, j, k' 1} \cdot \ldots \cdot
                              x'_{i, j, k', l'} - x'_{i, j, k', 1} \cdot \ldots \cdot x'_{i, j, k', l'})},
    \end{align*}
    where $r_{i, j, k} = \p{p}_{i, j} (\vec{x_{i, j, k}}, \vec{b})$.
      
    That is, for all $\vec{x'_{i, j, k}}$ polynomial $\p{r} (\vec{X}, \vec{B})$
zeroes; and $b_{i, j, k} (\vec{x'_{i, j, k}}) = r_{i, j, k}$ and
    $b_{i, j, k} (\vec{x'_{i, j, k'}}) = 0$, for $k' \neq k$. Eventually
    $\p{p}'_{i, j, k} (\vec{x'_{i, j, k}}, \vec{b'}) = r_{i, j, k}$. \qed
  \end{proof}

  The following lemma shows that evaluations of randomized polynomials determines
  evaluations of the determined polynomials. More precisely, we show that if a polynomial
  $\p{p}_{i, j}$ is not randomized then its evaluation is determined by
  \begin{inparaenum}[(1)]
  \item evaluation point,
\item protocol building challenges,
\item evaluations of previous polynomials.
\end{inparaenum}
Hence, we conclude, to make sure that all polynomials in a simulated proof evaluates to
the same values as polynomials in some real proof it is enough to assure that randomized
polynomials in these two cases match.
  
  \begin{lemma}
    \label{lem:rand_imp_det}
    Let $r_{i, j, k} = \p{p}_{i', j'} (\vec{x_{i, j, k}}, \vec{b})$ and let
    $\p{p}'_{i', j'} (\vec{X}, \vec{B})$ be such that
    $\p{p}'_{i', j'} (\vec{x'_{i, j, k}}, \vec{b'}) = r_{i, j, k}$ for some
    $ (\vec{x'_{i, j, k}}, \vec{b'})$ and all $(i', j') \in R$. Then for all
    $(i', j') \in D$ holds
    \[
      \p{p}_{i', j'} (\vec{x_{i, j, k}}, \vec{b}) =\p{p}'_{i', j'} (\vec{x'_{i, j,
          k}}, \vec{b'}).
    \]
    That is, if $\adv$ produces polynomials $\p{p}'_{i, j}$, for $(i, j) \in R$, as
    in \cref{lem:matching_R_polys} then
    $\p{p}_{i, j} (\vec{x_{i, j, k}}, \vec{b}) = \p{p}'_{i, j} (\vec{x'_{i, j, k}}, \vec{b'})$ for all $(i, j)$.
  \end{lemma}
  \begin{proof}
    Note that each polynomial $\p{p}_{i', j'} (\vec{X}, \vec{B})$ sent by the prover
    can be written as
  \[
    \p{p}_{i', j'} (\vec{X}, \vec{B}) = \p{h}_{i', j'}\left(\vec{X},
      (\vec{\beta_i})_{i \leq i' - 1}, (\p{p}_{i, j} (\vec{X}, \vec{B}))_{(i, j) \leq
        (i', j')} \right).
  \]
  Denote by $E$ a set of indices $(i, j)$ such that
  $\p{p}'_{i, j} (\vec{x'_{i, j, k}}, \vec{b'}) = \p{p}_{i, j} (\vec{x_{i, j,
      k}}, \vec{b})$. Obviously, $R \subset E$. Note that there is a minimal index
  $(i^*, j^*) \in D \setminus E$ such that for all $(i, j) \leq (i^*, j^*)$ polynomials
  $\p{p}_{i, j}$ are in $E$. For $\p{p}_{i^*, j^*}$ holds
  \begin{equation}
    \begin{split}
      \p{p}_{i^*, j^*} (\vec{x_{i^*, j^*, k^*}}, \vec{b}) =
      \p{h}_{i^*, j^*}\left((\vec{x_{i^*, j^*, k}})_{k \leq k^*},
        (\vec{\beta_{i}})_{i \leq i^* - 1}, (\p{p}_{i, j} (\vec{x_{i, j, k}},
        \vec{b}))_{(i, j) < (i^*, j^*)} \right) = \\ \p{h}_{i^*, j^*}\left((\vec{x_{i^*, j^*,
            k}})_{k \leq k^*}, (\vec{\beta_i})_{i \leq i^* - 1}, (\p{p}'_{i, j} (\vec{x'_{i, j, k}},
        \vec{b'}))_{(i, j) < (i^*, j^*)} \right) = \p{p}'_{i^*, j^*} (\vec{x'_{i^*, j^*, k^*}},
      \vec{b'}),
    \end{split}
  \end{equation}
 Hence, $(i^*, j^*)$ is in $E$ as well.  
  \qed
\end{proof}
  
\michals{9.12}{Note that in the definition above i removed $\vec{B}$. That is, polynomial
  $h$ depends on $\vec{B}$ only indirectly, i.e.~via polynomials $p$. Formalize that}

Although the lemmata above work for any efficiently sampleable $\dist{P}_{i, j, k}$
(cf.~\cref{eq:distribution_P}) in our applications we are interested in
$(\dist{P}_{i, j, k} \| \p{p}' (\vec{x_{i, j, k}}))_{(i, j, k)} \approx \bigtimes_{(i, j, k)}
\dist{U}_q$, where $\p{p'} (\vec{X})$ (as defined below) is a polynomial which
coefficients are identical to $\p{p} (\vec(X), \vec{B})$ except these which stand
next to monomials containing some $B_i$-s which are zero in case of $\p{p'}$. Also, $\dist{U}_q$
is a uniform distribution over $\FF_q$. That is, we claim that the evaluations of
polynomials $\p{p} (\vec{X}, \vec{b})$ are uniformly random even when some of the
coefficients of $\p{p}$ are known. We note that adding $\p{p'} (\vec{X})$ is important
when zero knowledge is shown. In that case, polynomial $\p{p'} (\vec{X})$ may be provided
by an adversarial algorithm.  

\begin{lemma}
  Let $\p{p} (\vec{X}, \vec{B})$ be a randomized polynomial that is evaluated at $K$
  points $\vec{X_1}, \ldots, \vec{X_K}$ after $\vec{B}$ is set to some
  $\vec{b}$. Write $\p{p} (\vec{X}, \vec{b}) = \p{p'} (\vec{X}) + \p{b} (\vec{X})$
  such that $\p{p'}$ is a polynomial compound of all monomials in $\p{p}$ that are
  independent of $\vec{B}$. Furthermore, let $\deg \p{p'} (\vec{X}, \vec{b}) = l'$
  and
  $\p{b} (\vec{X}) = (\sum_{i = 1}^{k'} b_{l' + i} X^{l' + i}) \cdot \p{q} (\vec{X})$
  for some polynomial $\p{q} (\vec{X})$, such that $\deg \p{b} (\vec{X}) \geq K$.%
  \michals{3.1}{I am not sure how to write well that sometimes we take $\vec{B}$ as a
    variable and sometimes as a coefficient. (Mathematical formalism here would be
    quite ugly)} %
  Then, if $\vec{B}$ has been picked uniformly at random, holds
  $(\dist{P}_{i, j, k} \| \p{p'} (\vec{X}))_{(i, j)} \approx \bigtimes_{(i, j)}
  \dist{U}_q$.  \michals{3.1}{Note the change -- added $\p{p'}$ part of the
    distribution. The distribution should be uniform even when coefficients of $\p{p'}$ are
    known. Really, if we consider composable zk definition, where the adversary picks
    witness, then it knows all-but-$\vec{B}$-related $\p{p'}$'s coefficients }
\end{lemma}

\begin{proof}
  Note that for an adversary who learns only $K$ evaluations
  $(y_i)_{i \in \range{1}{K}} = (\p{p} (\vec{x_i}, \vec{b}))_{i \in \range{1}{K}}$
  any other evaluations of that polynomial remains random as $\deg \p{p} (\vec{X},
  \vec{b}) \geq K$ \qed
\end{proof}
We note that polynomial $\p{q} (\vec{X}) = 1$ for e.g.~Basilisk \cite{C:RafZap21} and
Claymore \cite{EPRINT:Szepieniec20} and $\p{q} (\vec{X})$ is a so-called vanishing
polynomial for Marlin \cite{EC:CHMMVW20} and Plonk \cite{EPRINT:GabWilCio19}.

  \paragraph{Simulator.}
  In the following we denote by $\p{p}_{i, j}$ polynomials
  computed as defined in the protocol and by $\p{p}'_{i, j}$ the corresponding
  simulated rational functions corresponding to $\p{p}_{i, j}$. As previously we
  denote by $R$ (resp.~$D$) the set of all randomized (resp.~determined)
  polynomials in $\PS$.

  The simulator $\simulator$ for instance $\inp$ picks a random witness $\wit'$,
  randomisers $\vec{b'}$, and in Round $i$ proceeds as follows:
  \begin{enumerate}
  \item \michals{13.12}{Since the simulator picks polynomials in $R$ randomly, we probably
      doesn't need to wait till it learns all evaluation points to reveal evaluations}
    For $j = k_i + 1, \ldots, k_i + k'_i$, send to the verifier (constant) polynomials
    $\p{p}_{i, j} (\vec{X}, \vec{b})$ evaluated w.r.t~$\zkproof[i - 1]$.
  \item On verifier's evaluation query $\vec{x_{i, j, K_{i, j}}}$, i.e. for the last
    evaluation query for an oracle corresponding to polynomial $\p{p}_{i, j}$:
    \begin{itemize}
    \item Pick evaluations $r_{i, j, k}$ randomly w.r.t distribution
      $\dist{P}_{i, j, k}$.
    \item Compute rational functions $\smallset{\p{p}'_{i, j}}_{(i, j) \in R}$ as described
      in \cref{lem:matching_R_polys}. 
    \item Compute rational functions $\smallset{\p{p}'_{i, j}}_{(i, j) \in D}$
      according to the protocol.
    \item Send evaluations $r_{i, j, k} = \p{p}' (\vec{x_{i, j, k}}, \vec{b'})$, for
      $k \in \range{1}{K_{i, j}}$.
    \end{itemize}
  \end{enumerate}

  Before it is shown that such simulator indeed outputs proofs indistinguishable from
  proofs output by an honest verifier some definitions and additional assumptions are needed.
    
\begin{definition}[Polynomial independence]
  Let $\smallset{\p{p}_{i, j} (\vec{X}, \vec{b})}_{i = 1, j = 1}^{\mu, k_i}$ be polynomials
  which the prover set oracles for. We call these polynomials \emph{independent} if
  $\smallset{\p{p}_{i, j} (\vec{X}, \vec{B})}$ are linearly independent.
\end{definition}

\michals{25.11}{If we add $m$ as polynomials how that affects independence?}
\michals{29.11}{Polynomials that encode messages $m$ are already constants, i.e. all
  variables are known, hence they don't affect independence. However, the definition
  has to be clear about that.}
\michals{29.11}{Should we introduce $Q$-independence? Where $Q$ would be the set of
  allowed operations, here linear, then we could use an uber assumption
  w.r.t. $Q$. (OTOH if $Q$ contains only linear operations, uber assumption probably
  is not needed.)}
  
\begin{definition}[Some weak version of uber assumption]
  \michals{24.11}{We don't need a full-blown uber assumption here (probably).}
\end{definition}

\michals{29.11}{Comment after call with Markulf: definition of ZK and ZK equivalence
  theorem should be light, the heavy lifting specific for our framework should be
  done in the reduction, where $\bdv$ uses PCOM to simulate PS.}

\begin{definition}[$\vec{Z}$-Zero knowledge]
  \michals{13.12}{Here will be a definition for zero knowledge}
\end{definition}

\begin{theorem}[$\vec{Z}$-Zero knowledge]
  \label{def:ips_zk}
  Let $\vec{Z} = \smallset{z_{i, j}}_{i = 1, j = 1}^{\mu, k_i}$. Let $\PS$ be a proof
  system as described in \cref{def:ps} such that
  \begin{itemize}
  \item $\smallset{\p{p}_{i, j} (\vec{X}, \vec{b})}$ are pairwise independent;
    \michals{2.12}{All of the polynomials or only these in $R$?}
  \item The verifier makes less than $z_{i, j}$ evaluation queries to an oracle set
    for polynomial $\p{p}_{i, j}$.
  \end{itemize}
  Then $\PS$ is zero-knowledge with the simulator as above.
\end{theorem}
\begin{proof}
  We note that since \cref{lem:matching_R_polys} holds, for every instance $\inp$,
  random witness $\wit'$ and evaluations $r_{i, j, k}$ computed by the simulator,
  there exists a real prover that for instance $\inp$, witness $\wit$ and randomness
  $\vec{b}$ sets oracles for polynomials $\p{p}_{i, j}$ such that
  $\p{p}_{i, j} (\vec{x_{i, j, k}}, \vec{b}) = r_{i, j, k}$. Since the simulated
  evaluations were picked according to distributions of the real evaluations
  (i.e.~evaluations of polynomials computed by an honest prover), a simulated proof
  is indistinguishable from a real one.
\end{proof}

\iffalse
% Old proof
  The proof is twofold. First we show that the proof provided by the simulator is
  acceptable, then we show that it is indistinguishable from a real proof.

  \ncase{Completeness} For the first part, we note that the simulator provides
  evaluations such that the verification equation holds. That is, it gives random
  numbers as evaluations of randomised polynomials, and computes evaluations of the
  determined polynomials as an honest prover would compute.

  Importantly, since the polynomials in $R$ are randomised, for each $\p{p}_{i, j}$,
  s.t.~$(i, j) \in R$, for witness $\wit$ there is a randomness $\tilde{\vec{b}}$
  that gives the same evaluation at $\smallset{\chz_{i, j, k}}_{k = 1}^{K_{i, j}}$.
  \michals{1.12}{Do we need to justify that?} We denote by $\tilde{\zkproof}$ the
  proof that uses the real witness $\wit$ and randomness $\vec{\tilde{b}}$.

  Furthermore, since evaluations $p_{i, j, k}$ for $(i, j) \in D$ are already
  determined by $p_{i, j, k}$ for $(i, j) \in R$ and $\zkproof [i - 1]$, these values
  are the same in the simulated proof and in $\tilde{\zkproof}$. Similarly for the
  polynomials $\p{p}_{i, j}$, $j \in \range{k_i, k_i + k'_{i}}$. Hence, if
  $\tilde{\zkproof}$ is acceptable, so is the simulated proof.
  
  \ncase{Zero knowledge} We argue about zero knowledge using the same argument as in
  the case of completeness. Since there is a randomness $\vec{\tilde{b}}$ that for a
  real witness $\wit$ gives the same proof as the simulated one, distribution of real
  ans simulated proofs are indistinguishable. 
   
  \fi

\michals{29.11}{To our reduction to work we need to have witness encoded as
  coefficients of some of the polynomials sent by the prover. This assumption need to
be done in the reduction part, not here.}

\iffalse
\begin{theorem}
  Zero knowledge, as defined in \cref{def:ips_zk}, implies zero-knowledge as defined
  in \hl{AHP zero knowledge reference}.
\end{theorem}
\begin{proof}
\end{proof}
\fi

\iffalse
\subsection{Polynomial commitment SE definitions equivalence}

\begin{definition}[Simple simulation extractability]
  \label{def:se_bdv0}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed. Let $\oraclec (c)$ be an oracle that when
  $\Qchal = \bot$, samples $x$, sets $\Qchal = (c, x)$ \mxout{and $\qchal = \abs{\qop}$} and
    returns $x$. Otherwise it returns $\bot$. Let $\oracles$ be an oracle which on
    input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x'$ not returned by $\oraclec_0$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_0$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_0}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \verify(\srs, c, x, y, o) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & (c, x, y, o) \gets \bdv_0^{\oracles,\oraclec}(\srs; r), \\
             & (c, x) = \Qchal, \\
             & \p{f} \gets \ext_{\bdv_0}(\srs, Q_{sim}, Q_{chal}; r)
           \end{aligned}
         \right.\right] \leq \negl.
     \]
\end{definition}

\begin{definition}[Flexible simulation extractability]
  \label{def:se_bdv1}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed. $\oraclec$ takes as input $c$ and samples
  challenge $x$, then it adds the challenge to, initially empty, list
  $\Qchal[c]$.  Eventually, $\oraclec$ returns $x$. Let $\oracles$ be an oracle which on input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x' \not\in \Qchal[c]$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     Let $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_1$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_1}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \verify(\srs, c, x, y, o) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & (c, x, y, o) \gets \bdv_1^{\oracles,\oraclec}(\srs; r), \\
             & x \in \Qchal[c], \\
             & \p{f} \gets \ext_{\bdv_1}(\srs, Q_{sim}, Q_{chal}; r)
           \end{aligned}
         \right.\right] \leq \negl.
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv0}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv1}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_1}$ from $\ext_{\bdv_0}$. We denote by
  $\bdv_0^{j}$, $j \in \range{1}{\abs{\Qchal_2}}$ an adversary who internally runs
  $\bdv_1$ and provides it with access to oracles $\oracles$ and $\oraclec_1$ by
  passing its queries to $\oracles$ and $\oraclec_0$. Since $\oraclec_0$ takes a
  single input a commitment $c$, while $\oraclec_1$ allows the adversary to query the
  oracle multiple time, $\bdv_0^{j}$ processes $\bdv_1$ calls to $\oraclec_1$ as
  follows. For a $j$-th query $c_j$ and the corresponding challenge $x$, $\bdv_1^{j}$
  takes commitment $c_j$, submits it to $\oraclec_0$ and get a challenge $x$. For all
  other queries, $\bdv_0$ returns a random $x$, see below. Eventually, when $\bdv_1$ returns
  $(c_j, x, y, o)$, $\bdv_0^{j}$ returns $(c_j, x, y, o)$ and $\bot$ if $\bdv_1$
  returns opening for another commitments or challenge.

  Extractor $\ext_{\bdv_1} (\srs, \Qsim, \Qchal_1, r_{\bdv_1})$ runs internally
  $\ext_{\bdv_0^j} (\srs, \Qsim, \Qchal_0, r_{\bdv_0^j})$ where
  \begin{itemize}
  \item $\Qchal_0$ consists of a pair $(c, x)$ where $c$ is the $j$-th commitment in
    $\Qchal_1$ and $x$ the corresponding challenge (also stored in $\Qchal_1$).
  \item $r_{bdv_0}$ consists of $r_{\bdv_1}$ which is then passed to $\bdv_1$ run
    internally by $\bdv_0^j$, and $r$ which compounds of commitment--challenge pairs
    $(c', x') \in \Qchal$, such that $(c', x') \neq (c, x)$. More precisely,
    randomness $r$ is used by $\bdv_0$ to answer $\bdv_1$'s $\oraclec_1$ queries that
    are not the picked query $(c, x)$ that is going to be output eventually by $\bdv_0$. 
  \end{itemize}
\end{proof}


\begin{definition}[Flexible simulation extractability for vector of commitments]
  \label{def:se_bdv2}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed.  $\oraclec$ takes as input $\vec{c}$ and samples
  challenge $x$, then it adds the challenge to, initially empty, list
  $\Qchal[\vec{c}]$. Eventually, $\oraclec$ returns $x$. Let $\oracles$ be an oracle
  which on input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x' \not\in \Qchal[c]$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     Let $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_2$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_2}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \verify(\srs, \vec{c}, x, \vec{y}, \vec{o}) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & (\vec{c}, x, \vec{y}, \vec{o}) \gets \bdv_2^{\oracles,\oraclec}(\srs; r), \\
             & x \in \Qchal [\vec{c}], \\
             & \p{f} \gets \ext_{\bdv_2}(\srs, \Qsim, \Qchal; r)
           \end{aligned}
         \right.\right] \leq \negl.
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv1}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv2}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_2}$ from $\ext_{\bdv_1}$. We denote by
  $\bdv_1^{j,k}$, $j \in \range{1}{\abs{\Qchal_2}}$, $k \in \range{1}{l}$
  \michals{23.11}{Introduce $l$ as the length of the vector} an adversary who
  internally runs $\bdv_2$ and provides it with access to oracles $\oracles$ and
  $\oraclec_2$ by passing its queries to $\oracles$ and $\oraclec_1$. Since
  $\oraclec_1$ takes as input a single commitment $c$, while $\oraclec_2$ takes
  vectors, $\bdv_1^{j, k}$ processes $\bdv_2$ calls to $\oraclec_2$ as follows. For a
  $j$-th query $\vec{c} = (c_1, \ldots, c_l)$ and the corresponding challenge $x$,
  $\bdv_1^{j, k}$ takes commitment $c_j$, submits it to $\oraclec_1$ and get a
  challenge $x$. Then it writes $(\vec{c}, x)$ in a locally stored
  $\Qchal_2$. Eventually, when $\bdv_2$ returns $(\vec{c}, x, \vec{y}, \vec{o})$,
  $\bdv_1^{j, k}$ returns $(c_k, x)$ where $c_k$ is $k$-th coordinate of the $j$-th
  vector $\bdv_2$ passed to $\Qchal_2$.
\end{proof}


\begin{definition}[Flexible simulation extractability for vector of commitments and
  multiple challenges]
  \label{def:se_bdv3}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed.  $\oraclec$ takes as input $\vec{c}$ and samples
  challenge $x$, then it adds the challenge to, initially empty, list
  $\Qchal[\vec{c}]$. Eventually, $\oraclec$ returns $x$.  Let $\oracles$ be an oracle
  which on input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x' \not\in \Qchal[c]$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     Let $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_3$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_3}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \forall i \in I, \verify(\srs, \vec{c_i}, x_i, \vec{y_i}, \vec{o_i}) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & \smallset{(\vec{c_i}, x_i, \vec{y_i}, \vec{o_i})}_{i \in I} \gets \bdv_3^{\oracles,\oraclec}(\srs; r), \\
             & \smallset{x_i \in \Qchal[\vec{c_i}]}_{i \in I}, \\
             & \p{f} \gets \ext_{\bdv_3}(\srs, \Qsim, \Qchal; r)
           \end{aligned}
         \right.\right] \leq \negl.
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv2}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv3}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_3}$ from $\ext_{\bdv_2}$. We denote by
  $\bdv_2^j$ an adversary who internally runs $\bdv_3$ and provides it with access to
  oracles $\oracles$ and $\oraclec_3$ by passing its queries to $\oracles$ and
  $\oraclec_2$. Eventually, when $\bdv_3$ returns
  $\smallset{\vec{c_i}, x_i, \vec{y_i}, \vec{o_i}}_{i \in I}$, $\bdv_2^j$ returns
  $(\vec{c_j}, x_j, \vec{y_j}, \vec{o_j})$.

  Extractor $\ext_{\bdv_3} (\srs, \Qsim, \Qchal_3, r_{\bdv_3})$ internally runs $\abs{\Qchal}$
  copies of $\ext_{\bdv_2^j}(\srs, \Qsim, \Qchal_2, r_{\bdv_2^j})$ for each $j \in
  \range{1}{\abs{\Qchal}}$, where $r_{\bdv_2^j} = r_{\bdv_3}$ and $\Qchal_2 =
  \Qchal_3$.

  Probability of $\ext_{\bdv_3}$ succeeds is lower-bounded by probability that all fo
  $\ext_{\bdv_2^j}$ succeeds. Assuming $\abs{\Qchal} = \poly$ and $\ext_{\bdv_2^j}$
  succeeds with overwhelming probability, $\ext_{\bdv_3}$ succeeds with overwhelming
  probability as well. 
\end{proof}

\begin{definition}[Flexible simulation extractability with random oracle]
  \label{def:sepcom}
  \label{def:se_bdv4}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment scheme with
  a simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed.  We consider the same $\oracles$ and
  $Q_{sim}= (Q_{com},Q_{op})$ but an adversary that provides vectors of commitments
  and openings $\vec{c}, \vec{y}, \vec{o}$.  Let $\ro_{aux}(\vec{c},aux)$ be an
  oracle that when $Q_{\ro}[\vec{c},aux] = \bot$, samples $x$, sets
  $Q_{\ro}[\vec{c},aux]=x$ and $q_{{chal}}= |Q_{{op}}|$. In all cases, it returns
  $Q_{\ro}[\vec{c},aux]$.  We say that $\PCOM$ is \emph{vector $\ro_{aux}$ simulation
    extractable} if for any $\ppt$ adversary $\bdv_4$ with oracle access to
  $\oracles$ and $\ro_{aux}$ there exists extractor $\ext_{\adv}$ such that
\[
  \Pr \left[
    \begin{aligned}
      & x \gets \ro_{aux}(\vec{c},aux), \\
      & \verify(\srs, \vec{c}, x, \vec{y}, \vec{o}) = 1, \\
      & \;\vec{c} \neq \com(\srs, \vec{\p{f}})\\
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
      & \smallset{(\aux_i, \vec{c_i}, \vec{x_i}, \vec{y_i}, \vec{o_i})}_{i \in I} \gets
      \bdv_4^{\oracles,\ro_{aux}}(\srs; r), \\
      & \Qchal[\aux, \vec{c_i}] = x_i\\
      & \vec{\p{f}} \gets \ext_{\bdv_4}(\srs, Q_{sim}, Q_{\ro}; r)
    \end{aligned}
  \right.\right]
  \leq \negl,
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv3}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv4}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_4}$ from $\ext_{\bdv_3}$. To that end, we show
  how $\bdv_3$ can use its oracles $\oracles, \oraclec_3$ to simulate
  $\oracles, \oraclec_4$ for $\bdv_4$. $\bdv_3$ runs internally $\bdv_4$ and answers
  its queries. First, note that the simulator oracle $\oracles$ works the same in
  both definitions, so $\bdv_3$ only needs to simulate $\oraclec_4$ with
  $\oraclec_3$. This is done as follows. For every query $(\vec{c}, \aux)$ to
  $\oraclec_4$, $\bdv_3$:
  \begin{itemize}
  \item checks whether $(\vec{c}, \aux)$ is stored and if it is the case, returns
    $\bot$,
  \item if $(\vec{c}, \aux)$ is not stored, then $\bdv_3$ stores the query in
    $\Qchal_3$ and parses it to get $\vec{c}$ which it then submits to $\oraclec_3$
    and gets challenge $x$. Then $\bdv_3$ returns $x$ to $\bdv_4$.
  \end{itemize}

  Extractor $\ext_{\bdv_4}$ on input $(\srs, \Qsim, \Qh; r_{\bdv_4})$ runs internally
  $\ext_{\bdv_3} (\srs, \Qsim, \Qchal_3; r_{\bdv_3})$ (which internally runs
  $\bdv_3$) such that $\Qchal_3$ is created as above from the queries in $\Qh$ and
  $r_{\bdv_3} \gets r_{\bdv_4}$. The latter point corresponds to the fact that
  $\bdv_3$ uses all its randomness to internally run $\bdv_4$.
\end{proof}
\fi

In our reduction we also need a weak version of a unique response property. In
general unique response property assures that no adversary can produce two valid
proofs that matches at some $i$ first prover's messages. Ganesh et al.~\cite{}
recently proposed a weaker version of this property which states that no adversary,
who can see simulated proofs for chosen instances, can produce a proof that matches a
\emph{simulated} proof at the first $i$ entries. Here we modify the definition
proposed by Ganesh et al.~a bit and adjust it to idealised proof systems (the
original definition was w.r.t.~an interactive proof system). 

\michals{3.1}{Cite Ganesh et al (Bulletproof non-malleability)}
\begin{definition}{Weak unique response property}
  Let $\PS = (\indexer, \prover, \verifier, \simulator)$ be a proof system. We say
  that $\PS$ has \emph{weak unique response property from $i$ on} if there is no PPT
  \michals{3.1}{has it be ppt? or maybe we just need to limit the number of the
    simulator queries to be polynomial?} adversary probability
  \[
    \Pr \left[ %
      \begin{aligned}
        & (\inp, \zkproof) \gets \adv^{\simulator} (\ind), \zkproof[:i] =
        \zkproof'[:i], \\
        & \verifier (\ind, \inp, \zkproof) = \verifier (\ind, \inp', \zkproof') = 1 %
      \end{aligned}
      \,\left| \, %
        \ind \gets \indexer (\secparam) \right. %
    \right] \leq \negl,
  \]
  where $\zkproof'$ is a proof produced by the simulator $\simulator$
\end{definition}

\subsection{From idealized proof system to SNARK}
Below we show how to compile an idealized proof system $\PS$ into a NIZK $\PSc$ using
a polynomial commitment. Proof system
$\PSc = (\kgen, \prover, \verifier, \simulator)$ is defined as follows:
\begin{description}
\item[$\kgenc (\secparam)$:] Run indexer $\indexer (\secparam)$ \michals{27.12}{What
    exactly the indexer does?}
\item[$\proverc (\srs, \inp, \wit)$:] Run $\prover (\ind, \inp, \wit)$ internally, when it
  \begin{itemize}
  \item  sets an oracle for polynomial $\p{p}$, output a commitment $c$ to
    that polynomial;
  \item  outputs a constant polynomial $\p{p}$, output the same polynomial;
  \item  is asked to provide an evaluation of $\p{p}$ at $x$, provide the
    evaluation and open the commitment.
  \end{itemize}
\item[$\verifierc (\srs, \inp, \zkproof)$:] Run verifier
  $\verifier (\ind, \inp, \zkproof)$ and when it 
  \begin{itemize}
  \item sends a challenge, send the same challenge to $\proverc$,
  \item accepts or rejects the proof, accept or reject $\proverc$'s proof.
  \end{itemize}
  When $\proverc$ outputs a constant polynomial $\p{p}$, send it to $\verifier$, also
  when $\proverc$ sends a commitment $c$, let $\verifier$ know that an oracle for a
  polynomial has been set.
\item[$\simulatorc (\srs, \inp)$:] Run internally simulator $\simulator (\ind, \inp)$
  and whenever it
  \begin{itemize}
  \item outputs constant polynomials $\p{p}$, output $\p{p}$ as well;
  \item computes rational functions $\p{p}$ pick a random commitment $c$ and output
    it;
  \item reveals evaluation $r$ of some polynomial $\p{p}$, open the corresponding
    commitment $c$ to $r$.
  \end{itemize}
\end{description}

\begin{theorem}
  Let $\PS$ be a proof system and $\PSc$ a zkSNARK obtained from $\PS$ using the
  technique from \cref{sec:compiler}. $\PSc$ is knowledge sound and
  zero-knowledge if $\PS$ is knowledge sound and zero-knowledge.
\end{theorem}

\begin{lemma}
  If $\PS$ has weak unique response property after $i$, then $\PSc$ has unique response
  property after $i$.
\end{lemma}

\subsection{From SE polynomial commitment to SE NIZK}
\michals{20.12}{The main reduction goes here}
\begin{theorem}
  Let $\PS$ be a proof system and $\PSc$ a zkSNARK obtained from $\PS$ using the
  technique from \cref{sec:compiler}. Assume that 
  \begin{itemize}
  \item $\PCOM$ is simulation-extractable,
  \item $\PS$ has $\tilde{i'}$ weak unique response property,
  \item there is no evaluation challenges before Round $\tilde{i}$,
  \item $\tilde{i'} \leq \tilde{i}$.
  \end{itemize}
  Then $\PSc$ is simulation extractable.
  \michals{27.12}{Now unique response property is a property of the idealized proof
    system as well. Need to define that.}
\end{theorem}
\begin{proof}
  We show the theorem by building a reduction $\bdv$ that given oracle access to
  $\PCOM$ simulator and challenge oracle, internally runs NIZK SE adversary
  $\adv$. Then we show that existence of an extractor for $\bdv$ implies existence of
  an extractor for $\adv$.
  
  Reduction $\bdv^{\oracles^{\PCOM}}$ proceeds as follows:
\begin{enumerate}
\item On input $\inp$ from the adversary $\adv$ compute the simulated proof as
  follows, for each Round $i$:
  \begin{itemize}
  \item Parse the protocol building challenges $\vec{\beta_{i - 1}}$.
  \item Ask the simulator for $k_i$ simulated commitments
    $c_{i, 1}, \ldots, c_{i, k}$ that correspond to commitments to $k_i$ polynomials
    $\p{p}_{i, j}$ sent by the prover in the round.
  \item For randomized polynomial $\p{p}_{i, j}$, pick $r_{i, j, k}$ according to
    $\dist{P}_{i, j}$ and save it as an evaluation of $\p{p}_{i, j}$ at
    $\vec{X_{i, j, k}}$ (note, the evaluation point may not be known yet).
  \item If the verifier asks to reveal evaluation of a randomized polynomial
    $\p{p_{i', j}} (\vec{x_{i', j, k}}, \cdot)$ use stored $r_{i', j, k}$.
  \item If the verifier asks to reveal evaluation of a determined polynomial
    $\p{p_{i', j}} (\vec{x_{i', j, k}}, \cdot)$ compute $r_{i', j, k}$ according to
    the previously computed values (cf.~\cref{lem:rand_imp_det}) and the partial
    transcript; then output it.
  \item If the verifier asks for a proof of evaluation correctness, ask the simulator
    to trapdoor open $c_{i', j}$ to $r_{i', j, k}$.
  \item Compute the protocol building and evaluation challenges $\vec{\beta_{i}}$,
    $\vec{x_{i', j, k}}$ for the next round by querying the random oracle on
    $((\p{p}_{i, j})_{j \in \range{1}{k_{i}}} \| \aux)$ where $\aux$ is the partial
    transcript at this point. 
  \end{itemize}
\item On random oracle query $x$ from the adversary, pass the query to the oracle and
  return the answer.
\item On proof $\zkproof$ from $\adv$, abort if it is unacceptable.  Else, for all
  openings $\vec{o} = (o_{i, j, k})$ the proof contains and which has not been
  provided by the simulator, find corresponding commitments $\vec{c} = (c_{i, j})$
  and random oracle queries which answer contain evaluation challenges
  $\vec{x} = (\vec{x_{i, j, k}})$ for that commitment. $\bdv$ outputs
  $(\vec{c}, \vec{x}, \vec{y}, \vec{o})$, where $\vec{y}$ is a vector of evaluations
  corresponding to challenges $\vec{x}$.
\end{enumerate}

We note that since in $\PSc$ the verifier sends evaluation challenges no sooner than
in Round $\tilde{i}$, the proof system has $\tilde{i'}$ unique response property,
and $\tilde{i'} \leq \tilde{i}$, then with overwhelming probability evaluation challenges
in $\zkproof$ are not included in any simulated proof $\bdv$ produced. More
precisely, if some evaluation challenge in the final proof $\zkproof$ equals an
evaluation challenge from a simulated proof, then either the adversary broke the
unique response property or a collision in a random oracle has been found, each of
which happens with negligible probability only.

Since the $\PCOM$ verifier accepts $(\vec{c}, \vec{x}, \vec{y}, \vec{o})$ there exists an
extractor $\extb (\srs_{\PCOM}, \Qsimpc, \Qchal, \Qop, \rb)$ that outputs
$\vec{\p{f}}$ such that $\vec{c} = \com (\vec{\p{f}})$.
%
Given $\extb (\srs_{\PCOM}, \Qsimpc, \Qchal, \Qop, \rb)$ we show that there is an
extractor $\exta (\srs, \Qsim, \Qro, \ra)$ for $\adv$. We construct
$\exta (\srs, \Qsim, \Qro, \ra)$ explicitly. The extractor internally runs $\extb$,
hence it is important to show how $\exta$ inputs are mapped to $\extb$ inputs:
\begin{itemize}
\item $\srs$ is computed using $\srs_{\PCOM}$.
\item $\Qsim$ contains instances and their proofs, that is
  $\Qsim = (\inp_w, \zkproof_w = (c_{i, j}, \vec{\beta_i}, \vec{x_{i, j, k}},
  \vec{r_{i, j, k}}, \vec{o_{i, j, k}})_{i \in \range{1}{\mu}, j \in \range{1}{k_i +
      k'_i}, k \in \range{1}{K_{ij}}})_{w \in \range{1}{W}}$, where $W$ is the number
  of proofs $\adv$ asked $\simulator$ to generate. Instance $\inp_w$ comes from
  $\adv$, the proof is computed as follows:
  \begin{itemize}
  \item commitments $c_{i, j}$ come from the simulator, i.e they are part of list $\Qsimpc$;
  \item challenges $\vec{\beta_i}$ and $\vec{x_{i, j, k}}$ come from the random
    oracle, i.e.~they are part of $\Qchal$;
  \item evaluations $r_{i, j, k}$ are part of $\bdv$ randomness $\rb$;
  \item openings $\vec{o_{i, j, k}}$ come from the simulator, i.e.~they are part of $\Qop$; 
  \end{itemize}
\item $\Qro$ contains list of random oracle queries, this is part of $\Qchal$;
\item $\ra$ contains remaining, i.e.~not used to compute $r_{i, j, k}$, random bits
  from $\rb$.
\end{itemize}
\qed 
\end{proof}

\subsection{Polynomial commitment SE definitions equivalence w.r.t.~polynomials}
\michals{23.11}{This section is to show that SE defs are equivalent even when the
  challenge the adversary responds to is polynomially related to the challenge output
by the oracle}

\paragraph{KZG is simulation extractable}

We consider an algebraic adversary $\adv$ that outputs a matrix $K$ with coefficients
$\{C_{{1i}}\},\{C_{{2i}}\}, \{C_{{3ij}}\}$ for the commitment $c$ and
$\{O_{{1i}}\},\{O_{{2i}}\}, \{O_{{3ij}}\}$ for the opening proof $o$. The matrix $K$
reconstructs $c,o$ as linear combination of the group elements in $\srs$ and
$Q_{sim}$. We consider a representation of the group elements in $(\srs, Q_{{sim}})$
in terms of a function $\mathsf{Tr}_{\{x_{ij},y_{ij}\}}(\tau)$ of its underlying
secret discrete logarithms $\tau= (\xi, \alpha_{i})$, where $\xi$ is the trapdoor of
the $\srs$ and the $\alpha_{i}$ are the randomness of simulated proofs.

We move toward considering a verification equation $V'$ expressed in terms of $K$ and
$\mathsf{Tr}_{\{x_{ij},y_{ij}\}}$ for which we have:
$\verify (\srs, c, \p{h} (x_0), y, o) = \gone{c - y} \bullet \gtwo{1} - \gone{o} \bullet
\gtwo{\alpha - \p{h} (x_0)} = 0$ iff
$\verify'_{{\xi, x_0, y}}(K \cdot \mathsf{Tr}_{\{x_{ij},y_{ij}\}} (\tau)) = 0$. 
%
We say that $\verify'_{{X,x_0,y}}$ is satisfied symbolically, if
$\verify'_{{X,x_0,y}}(K \cdot \mathsf{Tr}_{\{x_{ij},y_{ij}\}} (T)) = 0$ for symbolic
variables $T=(X, \{A_{i}\})$. \changedm{Here $\p{h} (X)$ is a fixed, public,
  non-constant polynomial that is applied to the challenge $x_0$. More precisely,
  adversary $\adv$ given $x$ is supposed to give an evaluation of the polynomial in
  $c$ at $\p{h} (x_0)$. We note that since $x_0$ is random and $\p{h} (X)$
  not-constant, then $\p{h} (x_0)$ is random as well. In the following we set
  $x = \p{h} (x_0)$.}

The symbolic transcript consists of the SRS $\gone{X^{i}}, \gtwo{X}$, simulated
commitments $\gone{A_{i}}$, and simulated opening proofs
$ \gone{\frac{A_{ij}-y_{{ij}}}{X-x_{ij}}}$.
%
The honest verification equation is
$\gone{f(X) - y} \bullet \gtwo{h} - \gone{q(X)} \bullet \gtwo{X - x} = 0$ while an
adversary can provide rational functions
$f(X, \{A_{i}\}) = \sum C_{1i} X^{i} + \sum C_{2i} A_{i} + \sum C_{3ij}
\frac{A_{i}-y_{ij}}{X-x_{ij}}$ and
$q(X, \{A_{i}\}) = \sum O_{1i} X^{i} + \sum O_{2i} A_{i} + \sum O_{3ij} \frac{A_{i}-
  y_{ij}}{X-x_{ij}}$ computed as linear combinations of elements in the transcript.
The security game gives us that $x$ is sampled independently from $x_{ij}$ for
$j\leq q^{i}_{chal}$ and $x \neq x_{ij}$ otherwise. Here $q^{i}_{chal}$ are the
number of simulated opening queries made for commitment $c_{i}$ before the challenge
query.

We inline to get the following equation which we then analyze in detail,
\begin{align*}
  \gone{\sum C_{1i} X^{i} + \sum C_{2i} A_{i} + \sum C_{3ij}
  \frac{A_{i}-y_{ij}}{X-x_{ij}} - y} \bullet \gtwo{1} - \gone{\sum O_{1i} X^{i}
  + \sum O_{2i} A_{i} + \sum O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}}} \bullet \gtwo{X -
  x} = 0
\end{align*}

We now look at different (rational) monomials in $T$ of this equation to derive
constraints on $C_{1i}, C_{{2i}},C_{{3ij}}$ and $O_{1i},O_{2i},O_{3ij}$ imposed by
the verification equation:
\begin{itemize}
  \item[$A_{i}X$:] We have that for all $i$, $O_{2i}=0$ as $O_{2i} A_{i} X = 0$.
  \item[$\frac{A_{i}-y_{ij}}{X-x_{ij}}, j>q^{i}_{chal}$:] $C_{3ij}=0$ as $\adv$ did
    not yet see them when it computed the commitment.
\end{itemize}

To obtain a simplified verificaton equation, we express the equation in the exponent
and write $C_{1}(X)$ for $\sum C_{1i} X^{i}$ and $O_{1}(X)$ for $\sum O_{1i} X^{i}$.
Furthermore, we let $\delta_{ij} = x_{i j} - x$ and replace $x$ with
$x_{ij} - \delta_{ij}$. Importantly, since $x$ is random and unknown to adversary
before it picks $x_{i j}$ then $\delta_{i j} \neq 0$ with probability at least
$\infrac{\abs{I}}{\abs{\FF}}$. \michals{24.11}{$I$ is the set of all $i$}

\begin{align*}
  C_{1}(X) - y - O_{i}(X)(X-x) + \sum C_{2i} A_{i} + \sum C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} (X-x_{ij}+\delta_{ij}) = 0\\
  C_{1}(X) - y - O_{i}(X)(X-x) + \sum C_{2i} A_{i} + \sum C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} (X-x_{ij}) - O_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} \delta_{ij} = 0
\end{align*}

\begin{itemize}
\item[$\frac{A_{i}-y_{ij}}{X-x_{ij}}$:]
  $C_{3ij} \frac{A_{i}-y_{ij}}{X-x_{ij}} - O_{{3ij}}\delta_{ij}
  \frac{A_{i}-y_{ij}}{X-x_{ij}}=0$. As $C_{3ij}=0$ for $j>q^{i}_{chal}$, it follows
  that $O_{{3ij}}=0$ for $j>q^{i}_{chal}$. Otherwise, we have
  $O_{3ij}= C_{3ij}/\delta_{ij}$.
\item[$A_{i}$:] $C_{2i} A_{i} - \sum O_{3ij} A_{i}=0$.
\end{itemize}

Informal step. $C_{2i}- \sum \frac{C_{3ij}}{x_{ij}-x} =0$ is a rational equation
system in $x$. If $x_{ij}\neq x_{ij'}$, then the probability of randomly picking a
solution $x$ is small unless all the $C_{2i}$, $C_{3ij}$ are $0$. Thus we also have
$O_{{3ij}}=0$.  If $x_{ij} = x_{ij'}$ then the adversary requested openings on the
same value for the same commitment (potentially for different $y_{ij}$) multiple
times. This is something we want to exclude.

\michals{29.11}{The following magenta text is to replace the informal step}

\changedm{ Write $C_{2i} - \sum_{j = 1}^{k_i} \frac{C_{3ij}}{x_{ij} - x} = 0$ as a
  polynomial $\p{D} (X)$, that is
  $\p{D} (X) = C_{2 i} \cdot (x_{i 1} - X) \cdot \ldots \cdot (x_{i k_i} - X) -
  \sum_{j = 1}^{k_i} C_{3 i j} \cdot (x_{i 1} - X) \cdot \ldots \cdot (x_{i j - 1} -
  X) \cdot (x_{i j + 1} - X) \cdot \ldots \cdot (x_{i k_i} - X)$. Let $d_j$ be a
  coefficient that stands next to $X^j$ in $\p{D} (X)$. We want to show that
  $\p{D} (X)$ is a zero polynomial and coefficients $C_{2 i}, C_{3 i j}$ are all zero
  with overwhelming probability. First, we note that $D_{k_i} = C_{2 i}$. Hence, if
  $\p{D} (X)$ evaluates to $0$ at random $x$ with probability at most
  $\infrac{k_i}{\abs{\FF}}$ if $\p{D} (X)$ is a non-zero polynomial. Hence, from now
  on we assume that $\p{D} (X) \equiv 0$. Second, we show that $\p{D} (X)$ being zero
  polynomial implies $C_{3 i j}$ are, with overwhelming probability, zero as well. We
  define polynomials
  $\p{C}_{3 i j} (X) := C_{3 i j} \cdot (x_{i 1} - X) \cdot \ldots \cdot (x_{i j - 1}
  - X) \cdot (x_{i j + 1} - X) \cdot \ldots \cdot (x_{i k_i} - X)$.

  Note that $C_{3 i k_i} = - \sum_{j = 1}^{k_i - 1} C_{3 i j}$ and
  $\p{C}_{3 i k_i} (X) = -\sum_{j = 1}^{k_i - 1} \p{C}_{3 i j} (X)$. This comes since
  $D_{k_i - 1} = \sum_{j = 1}^{k_i} C_{3 i j}$.  }

\iffalse
  \changedm{Assuming 
  $x_{ij} \neq x_{i'j'}$ for $(i, j) \neq (i', j')$ we have that
  $C_{3 i j} \cdot (x_{i 1} - x) \cdot \ldots \cdot (x_{i j - 1} - x) \cdot (x_{i j +
    1} - x) \cdot \ldots \cdot (x_{i k_i} - x) = C_{3 i j'} \cdot (x_{i 1} - x) \cdot
  \ldots \cdot (x_{i j' - 1} - x) \cdot (x_{i j' + 1} - x) \cdot \ldots \cdot (x_{i
    k_i} - x)$ with negligible probability only over a choice of $x$. This follows
  from the Schwartz-Zippel lemma. More precisely, define
  \begin{equation}
    \begin{aligned}
      \p{D}_{i j j'} (X) = & C_{3 i j} \cdot (x_{i 1} - X) \cdot \ldots \cdot (x_{i j - 1}
      - X) \cdot (x_{i j + 1} - X) \cdot \ldots \cdot (x_{i k_i} - X) - \\
      & C_{3 i j'} \cdot (x_{i 1} - X) \cdot \ldots \cdot (x_{i j' - 1} - X) \cdot
      (x_{i j' + 1} - X) \cdot \ldots \cdot (x_{i k_i} - X).
    \end{aligned}
  \end{equation}
  If $C_{3 i j} \neq C_{3 i j'}$ then $\p{D}_{i j j'}$ has degree $k_i - 1$. On the
  other hand, if $C_{3 i j} = C_{3 i j'} \neq 0$ and, as assumed $x_{ij}$, are
  pairwise different, then $\p{D}_{i j j'}$ is a non-zero polynomial. Hence,
  probability that $\p{D}_{i j j'} (X)$ equals $0$ for some randomly picked $x$ is
  upper-bounded by $\infrac{(k_i - 1)}{\abs{\FF}}$ unless
  $C_{3 i j} = C_{3 i j'} = 0$. Hence, with overwhelming probability
  $\smallset{C_{3 i j} \cdot (x_{i 1} - x) \cdot \ldots \cdot (x_{i j - 1} - x) \cdot
    (x_{i j + 1} - x) \cdot \ldots \cdot (x_{i k_i} - x)}_{j = 1}^{k_i}$ are pairwise
  different.}
  \fi

\begin{itemize}
\item[$X^{i}, i\geq 0$:]
  $C_{1}(X) - y - O_{1} (X) (X - x) + \sum \sum O_{3ij} y_{ij} = 0$, as $O_{3ij}=0$ we
  are back to the honest verification equation.
\end{itemize}

\newcommand{\ph}[1]{\p{h} (#1)}

\begin{definition}[$\ph{X}$-simple simulation extractability]
  \label{def:se_bdv0}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed. Let $\oraclec (c)$ be an oracle that when
  $\Qchal = \bot$, samples $x$, sets $\Qchal = (c, x)$ and $\qchal = \abs{\qop}$ and
    returns $x$. Otherwise it returns $\bot$. Let $\oracles$ be an oracle which on
    input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x'$ not returned by $\oraclec_0$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$. \michals{24.11}{We could have here $\ph{x'}$
         instead of $x'$ but I think it changes nothing.}
     \end{description}
     $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_0$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_0}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \verify(\srs, c, \ph{x}, y, o) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & (c, x, y, o) \gets \bdv_0^{\oracles,\oraclec}(\srs; r), \\
             & (c, x) = \Qchal, \\
             & \p{f} \gets \ext_{\bdv_0}(\srs, Q_{sim}, Q_{chal}; r)
           \end{aligned}
         \right.\right] \leq \negl.
     \]
\end{definition}

\begin{definition}[$\ph{X}$-flexible simulation extractability]
  \label{def:se_bdv1}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed. $\oraclec$ takes as input $c$ and samples
  challenge $x$, then it adds the challenge to, initially empty, list
  $\Qchal[c]$.  Eventually, $\oraclec$ returns $x$. Let $\oracles$ be an oracle which on input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x' \not\in \Qchal[c]$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     Let $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_1$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_1}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \verify(\srs, c, \ph{x}, y, o) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & (c, x, y, o) \gets \bdv_1^{\oracles,\oraclec}(\srs; r), \\
             & x \in \Qchal[c], \\
             & \p{f} \gets \ext_{\bdv_1}(\srs, Q_{sim}, Q_{chal}; r)
           \end{aligned}
         \right.\right] \leq \negl.
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv0}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv1}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_1}$ from $\ext_{\bdv_0}$. We denote by
  $\bdv_0^{j}$, $j \in \range{1}{\abs{{\Qchal}_2}}$ an adversary who internally runs
  $\bdv_1$ and provides it with access to oracles $\oracles$ and $\oraclec_1$ by
  passing its queries to $\oracles$ and $\oraclec_0$. Since $\oraclec_0$ takes a
  single input a commitment $c$, while $\oraclec_1$ allows the adversary to query the
  oracle multiple time, $\bdv_0^{j}$ processes $\bdv_1$ calls to $\oraclec_1$ as
  follows. For a $j$-th query $c_j$ and the corresponding challenge $x$, $\bdv_1^{j}$
  takes commitment $c_j$, submits it to $\oraclec_0$ and get a challenge $x$. For all
  other queries, $\bdv_0$ returns a random $x$, see below. Eventually, when $\bdv_1$ returns
  $(c_j, x, y, o)$, $\bdv_0^{j}$ returns $(c_j, x, y, o)$ and $\bot$ if $\bdv_1$
  returns opening for another commitments or challenge.

  Extractor $\ext_{\bdv_1} (\srs, \Qsim, {\Qchal}_1, r_{\bdv_1})$ runs internally
  $\ext_{\bdv_0^j} (\srs, \Qsim, \Qchal_0, r_{\bdv_0^j})$ where
  \begin{itemize}
  \item $\Qchal_0$ consists of a pair $(c, x)$ where $c$ is the $j$-th commitment in
    $\Qchal_1$ and $x$ the corresponding challenge (also stored in $\Qchal_1$).
  \item $r_{bdv_0}$ consists of $r_{\bdv_1}$ which is then passed to $\bdv_1$ run
    internally by $\bdv_0^j$, and $r$ which compounds of commitment--challenge pairs
    $(c', x') \in \Qchal$, such that $(c', x') \neq (c, x)$. More precisely,
    randomness $r$ is used by $\bdv_0$ to answer $\bdv_1$'s $\oraclec_1$ queries that
    are not the picked query $(c, x)$ that is going to be output eventually by $\bdv_0$. 
  \end{itemize}
\end{proof}


\begin{definition}[$\vec{\p{h}}(X)$-Flexible simulation extractability for vector of commitments]
  \label{def:se_bdv2}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed.  $\oraclec$ takes as input $\vec{c}$ and samples
  challenge $x$, then it adds the challenge to, initially empty, list
  $\Qchal[\vec{c}]$. Eventually, $\oraclec$ returns $x$. Let $\oracles$ be an oracle
  which on input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x' \not\in \Qchal[c]$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     Let $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_2$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_2}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \verify(\srs, \vec{c}, x, \vec{y}, \vec{o}) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & (\vec{c}, x, \vec{y}, \vec{o}) \gets \bdv_2^{\oracles,\oraclec}(\srs; r), \\
             & x \in \Qchal [\vec{c}], \\
             & \p{f} \gets \ext_{\bdv_2}(\srs, \Qsim, \Qchal; r)
           \end{aligned}
         \right.\right] \leq \negl.
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv1}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv2}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_2}$ from $\ext_{\bdv_1}$. We denote by
  $\bdv_1^{j,k}$, $j \in \range{1}{\abs{\Qchal_2}}$, $k \in \range{1}{l}$
  \michals{23.11}{Introduce $l$ as the length of the vector} an adversary who
  internally runs $\bdv_2$ and provides it with access to oracles $\oracles$ and
  $\oraclec_2$ by passing its queries to $\oracles$ and $\oraclec_1$. Since
  $\oraclec_1$ takes as input a single commitment $c$, while $\oraclec_2$ takes
  vectors, $\bdv_1^{j, k}$ processes $\bdv_2$ calls to $\oraclec_2$ as follows. For a
  $j$-th query $\vec{c} = (c_1, \ldots, c_l)$ and the corresponding challenge $x$,
  $\bdv_1^{j, k}$ takes commitment $c_j$, submits it to $\oraclec_1$ and get a
  challenge $x$. Then it writes $(\vec{c}, x)$ in a locally stored
  $\Qchal_2$. Eventually, when $\bdv_2$ returns $(\vec{c}, x, \vec{y}, \vec{o})$,
  $\bdv_1^{j, k}$ returns $(c_k, x)$ where $c_k$ is $k$-th coordinate of the $j$-th
  vector $\bdv_2$ passed to $\Qchal_2$.
\end{proof}


\begin{definition}[Flexible simulation extractability for vector of commitments and
  multiple challenges]
  \label{def:se_bdv3}
  Let $\PCOM = (\kgen, \com, \op, \verify)$ be a polynomial commitment scheme with a
  simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed.  $\oraclec$ takes as input $\vec{c}$ and samples
  challenge $x$, then it adds the challenge to, initially empty, list
  $\Qchal[\vec{c}]$. Eventually, $\oraclec$ returns $x$.  Let $\oracles$ be an oracle
  which on input
     \begin{description}
     \item[$(\msg{commit})$:] Run $c \gets \simsample (\secparam)$, add $c$ to
       $\Qcom$, return $c$.
     \item[$(\msg{open}, c, x', y)$:] If $c \in \Qcom$ and $x' \not\in \Qchal[c]$, run
       $o \gets \simopen(\td, c, x', y)$, add $(c, x', y, o)$ to $\Qop$, and return
       $o$. Otherwise return $\bot$.
     \end{description}
     Let $\Qsim = (\Qcom, \Qop)$.  We say that $\PCOM$ is \emph{simulation
       extractable} if for any $\ppt$ adversary $\bdv_3$ with oracle access to
     $\oracles$ and $\oraclec$ there exists extractor $\ext_{\bdv_3}$ such that
     \[
       \Pr \left[
         \begin{aligned}
           & \forall i \in I, \verify(\srs, \vec{c_i}, x_i, \vec{y_i}, \vec{o_i}) = 1, \\
           & c \neq \com(\srs, \p{f})\\
         \end{aligned}
         \,\left|\, \vphantom{
             \begin{aligned}
               & \\
               & \\
               & \\
               &
             \end{aligned}
           }
           \begin{aligned}
             & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
             & \smallset{(\vec{c_i}, x_i, \vec{y_i}, \vec{o_i})}_{i \in I} \gets \bdv_3^{\oracles,\oraclec}(\srs; r), \\
             & \smallset{x_i \in \Qchal[\vec{c_i}]}_{i \in I}, \\
             & \p{f} \gets \ext_{\bdv_3}(\srs, \Qsim, \Qchal; r)
           \end{aligned}
         \right.\right] \leq \negl.
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv2}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv3}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_3}$ from $\ext_{\bdv_2}$. We denote by
  $\bdv_2^j$ an adversary who internally runs $\bdv_3$ and provides it with access to
  oracles $\oracles$ and $\oraclec_3$ by passing its queries to $\oracles$ and
  $\oraclec_2$. Eventually, when $\bdv_3$ returns
  $\smallset{\vec{c_i}, x_i, \vec{y_i}, \vec{o_i}}_{i \in I}$, $\bdv_2^j$ returns
  $(\vec{c_j}, x_j, \vec{y_j}, \vec{o_j})$.

  Extractor $\ext_{\bdv_3} (\srs, \Qsim, \Qchal_3, r_{\bdv_3})$ internally runs $\abs{\Qchal}$
  copies of $\ext_{\bdv_2^j}(\srs, \Qsim, \Qchal_2, r_{\bdv_2^j})$ for each $j \in
  \range{1}{\abs{\Qchal}}$, where $r_{\bdv_2^j} = r_{\bdv_3}$ and $\Qchal_2 =
  \Qchal_3$.

  Probability of $\ext_{\bdv_3}$ succeeds is lower-bounded by probability that all fo
  $\ext_{\bdv_2^j}$ succeeds. Assuming $\abs{\Qchal} = \poly$ and $\ext_{\bdv_2^j}$
  succeeds with overwhelming probability, $\ext_{\bdv_3}$ succeeds with overwhelming
  probability as well. 
\end{proof}

\begin{definition}[Flexible simulation extractability with random oracle]
  \label{def:sepcom}
  \label{def:se_bdv4}
  Let $\PCOM = (\kgen, \com, \open, \verify)$ be a polynomial commitment scheme with
  a simulator $(\simgen, \simsample, \simopen)$. Let $\maxdeg$ be a maximal degree of
  polynomials that can be committed.  We consider the same $\oracles$ and
  $Q_{sim}= (Q_{com},Q_{op})$ but an adversary that provides vectors of commitments
  and openings $\vec{c}, \vec{y}, \vec{o}$.  Let $\ro_{aux}(\vec{c},aux)$ be an
  oracle that when $Q_{\ro}[\vec{c},aux] = \bot$, samples $x$, sets
  $Q_{\ro}[\vec{c},aux]=x$ and $q_{{chal}}= |Q_{{op}}|$. In all cases, it returns
  $Q_{\ro}[\vec{c},aux]$.  We say that $\PCOM$ is \emph{vector $\ro_{aux}$ simulation
    extractable} if for any $\ppt$ adversary $\bdv_4$ with oracle access to
  $\oracles$ and $\ro_{aux}$ there exists extractor $\ext_{\adv}$ such that
\[
  \Pr \left[
    \begin{aligned}
      & x \gets \ro_{aux}(\vec{c},aux), \\
      & \verify(\srs, \vec{c}, x, \vec{y}, \vec{o}) = 1, \\
      & \;\vec{c} \neq \com(\srs, \vec{\p{f}})\\
    \end{aligned}
    \,\left|\,
      \vphantom{
        \begin{aligned}
          & \\
          & \\
          & \\
          &
        \end{aligned}
        }
    \begin{aligned}
      & (\srs, \td) \gets \simgen(\secparam, \maxdeg),\\
      & \smallset{(\aux_i, \vec{c_i}, \vec{x_i}, \vec{y_i}, \vec{o_i})}_{i \in I} \gets
      \bdv_4^{\oracles,\ro_{aux}}(\srs; r), \\
      & \Qchal[\aux, \vec{c_i}] = x_i\\
      & \vec{\p{f}} \gets \ext_{\bdv_4}(\srs, Q_{sim}, Q_{\ro}; r)
    \end{aligned}
  \right.\right]
  \leq \negl,
\]
\end{definition}

\begin{lemma}[]
  If polynomial commitment is simulation extractable w.r.t.~\cref{def:se_bdv3}, then
  it is simulation extractable w.r.t~\cref{def:se_bdv4}.
\end{lemma}
\begin{proof}
  Here we build extractor $\ext_{\bdv_4}$ from $\ext_{\bdv_3}$. To that end, we show
  how $\bdv_3$ can use its oracles $\oracles, \oraclec_3$ to simulate
  $\oracles, \oraclec_4$ for $\bdv_4$. $\bdv_3$ runs internally $\bdv_4$ and answers
  its queries. First, note that the simulator oracle $\oracles$ works the same in
  both definitions, so $\bdv_3$ only needs to simulate $\oraclec_4$ with
  $\oraclec_3$. This is done as follows. For every query $(\vec{c}, \aux)$ to
  $\oraclec_4$, $\bdv_3$:
  \begin{itemize}
  \item checks whether $(\vec{c}, \aux)$ is stored and if it is the case, returns
    $\bot$,
  \item if $(\vec{c}, \aux)$ is not stored, then $\bdv_3$ stores the query in
    $\Qchal_3$ and parses it to get $\vec{c}$ which it then submits to $\oraclec_3$
    and gets challenge $x$. Then $\bdv_3$ returns $x$ to $\bdv_4$.
  \end{itemize}

  Extractor $\ext_{\bdv_4}$ on input $(\srs, \Qsim, \Qh; r_{\bdv_4})$ runs internally
  $\ext_{\bdv_3} (\srs, \Qsim, \Qchal_3; r_{\bdv_3})$ (which internally runs
  $\bdv_3$) such that $\Qchal_3$ is created as above from the queries in $\Qh$ and
  $r_{\bdv_3} \gets r_{\bdv_4}$. The latter point corresponds to the fact that
  $\bdv_3$ uses all its randomness to internally run $\bdv_4$.
\end{proof}



\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: