StanfordJan2020UniversalUpdatable.tex

\documentclass[shadesubsections,trans,14pt,mathserif]{beamer}
\usepackage[danish]{babel}	
%\usepackage[T1]{fontenc}
%\usepackage{fourier}
% Dokumentets sprog
%\usepackage{mathtools}
%\usepackage{pxfonts}
\usepackage{eulervm}
% Class options include: notes, notesonly, handout, trans,
%                        hidesubsections, shadesubsections,
%                        inrow, blue, red, grey, brown

% Theme for beamer presentation.
%\usepackage{beamertheme} 
% Other themes include: beamerthemebars, beamerthemelined, 
%                       beamerthemetree, beamerthemetreebars  
\newcommand{\adv}{\ensuremath{\mathcal A}}
\newcommand{\F}{\ensuremath{\mathbb F}}
\newcommand{\set}[1]{\ensuremath{\left\{#1\right\}}}
\newcommand{\sett}[2]{\ensuremath{\left\{#1\right\}_{#2}}}
\newcommand{\enc}[1]{\ensuremath{\left[#1\right ]}}
\newcommand{\cm}{\ensuremath{\mathsf{cm}}}
\newcommand{\open}[1]{\ensuremath{\mathsf{open}(#1)}}
\newcommand{\verify}[1]{\ensuremath{\mathsf{verify}(#1)}}
\newcommand{\defeq}{\ensuremath{:=}}
\newcommand{\helper}{\ensuremath{\mathcal{H}}}
\newcommand{\ver}{\ensuremath{\mathcal{V}}}
\newcommand{\prv}{\ensuremath{\mathcal{P}}}
 \newcommand{\polysofdeg}[1]{\F_{< #1}[X]}
 \newcommand{\polys}{\F[X]}
\newcommand{\acc}{{\mathbf{acc}}}
\newcommand{\ideal}{\mathbf{I}}
\newcommand{\gen}{\alpha}
\newcommand{\spac}{\\  \vspace{0.2in} \noindent}
\newcommand{\polylog}{\ensuremath{\mathsf{polylog}}\xspace}
%\setbeamersize{text margin left=3mm,text margin right=3mm}  
\title{\large{A  introduction to Hasse's theorem with some cool facts on Ellipitic curves along the way}}    % Enter your title between curly braces
\author{{Ariel Gabizon}\\                 % Enter your name between curly braces
\tt{\small{Aztec} } }      % Enter your institute name between curly braces
\date{}                    % Enter the date or \today between curly braces
%\usefonttheme{professionalfonts}
%\usefonttheme[onlymath]{serif}
\begin{document}
\boldmath
% Creates title page of slide show using above information
\begin{frame}
  \titlepage
\end{frame}
                           % typeset with the notes or notesonly class options

%\section[Outline]{}

% Creates table of contents slide incorporating
% all \section and \subsection commands
%\begin{frame}
  %\tableofcontents
%\end{frame}

\begin{frame}
Should this talk be at zksummit

If so because of works like this:
ecfft

\end{frame}
\begin{frame}
How to get ec with n bits?


Hasse's thm

Just pick prime p with n bits
any a,b with 4a^3+27b^2/neq 0

and take curve y^2=x^3+ax+b
will have p+1 -+ 2sqrt p points
\end{frame}

\begin{frame}
set a=p+1-N

L(X)
=X^2-aX+p




so L(X)= (x-a1)(x-a2)

Claim: enough to show L's roots are not real


==>
\Delta=
a^2-4c<0

(for prime p cannot hit the = case cause 2sqrt(p) is not an integer)


\end{frame}
Sidenote: exists curves over extension field where (x^p,y^p) = b(x,y) for some b
i.e. frob is integer
==================




===========
Frob:
phi:(x,y)->(x^p,y^p)


L is char polynomial of phi/phi is a zero of L:
For any curve point in E(\bar{F}_p)
(x^p^2,y^p^2)-a(x^p,y^p)+p(x,y)=0

maybe interesting in future for snark optimizers (trivial for points in F_p)

p*(x,y) = a(x^p,y^p) - (x^p^2,y^p^2)


Interesting proof element:
E_n={P\in E,n*P=0}. When gcd(n,p)=1 E_n= Z_n\times Z_n
so phi action on E_n can be described by 2\times 2 matrix phi_n
Can show L is char poly
det(phi_n) = p mod n,   trace(phi_n) = a mod n
Can show matrix is zero of L for all n r.p. to p


===========

We want to show phi "corresponds" to imaginary number that is also root of L

detour: complex multiplication && endomorhpisms
Endomorphisms: 
"Hommorhpisms that "know" the group is an EC"
phi(P+Q) = phi(P)+phi(Q)
phi(0) = 0
If P=(x,y)
phi(x,y) = (r(x,y),s(x,y))
for rational func r,s

Examples
P-> c*P   for fixed c
P->phi(P) 

in fact, except for super-singular curves, all endomorphisms over F_p are combinations 
of these two.

===========

Thm:
Usually, 
The ring of endomorphisms of E is isomorphic to a ring
Z+Z*a

for some complex number a (p. 314, a = c*sqrt(-d) for pos integer c)

So phi corresponds either to element t of Z, which would mean t|p - not possible when t is prime.
So t is complex.

==========
A little history, where did this thm come from?
Tori/curve equivalnce over complex numbers.


===========














\begin{frame}
\frametitle{(preproccessing) zk-SNARKs}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
Arithmetic circuit $C$. ``Public input'' $x$.
  \begin{itemize}
  \item $\prv$ can prove she knows $w$ s.t. $C(x,w)=0$.
  \end{itemize}
\end{frame}

\begin{frame}
\frametitle{(preproccessing) zk-SNARKs}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
Arithmetic circuit $C$. ``Public input'' $x$.
  \begin{itemize}
  \item $\prv$ can prove she knows $w$ s.t. $C(x,w)=0$.
   \item Proof size - $\mathsf{polylog}|w|$.
  \end{itemize}
\end{frame}
\begin{frame}
\frametitle{(preproccessing) zk-SNARKs}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
Arithmetic circuit $C$. ``Public input'' $x$.
  \begin{itemize}
  \item $\prv$ can prove she knows $w$ s.t. $C(x,w)=0$.
   \item Proof size - $\mathsf{polylog}|w|$.
\item Proof doesn't leak info on $w$.
  \end{itemize}
\end{frame}
\begin{frame}
\frametitle{(preproccessing) zk-SNARKs}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
Arithmetic circuit $C$. ``Public input'' $x$.
  \begin{itemize}
  \item $\prv$ can prove she knows $w$ s.t. $C(x,w)=0$.
   \item Proof size - $\mathsf{polylog}|w|$.
\item Proof doesn't leak info on $w$.
  \item One time setup procedure to generate common reference string (depends on $C$, not on $x$).
  \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Talk outline}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
  \begin{enumerate}
\item The problem with prev constructions.
 \item The solution with recent ones.
\end{enumerate}

\end{frame}

\begin{frame}
\frametitle{Talk outline}   % Insert frame title between curly braces
 
  \begin{enumerate}
\item The problem with prev constructions.
 \item The solution with recent ones.
\end{enumerate}
 \vspace{0.2in}
\emph{We probably won't get too far with 2, unless you want to skip 1.}

\end{frame}


% 
% \begin{frame}
%    % Insert frame title between curly braces
% %Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
% 
% 
% Left values: 
% $l_1,l_2$\\
% Right values: $r_1,r_2$\\
% Output values:
% $o_1,o_2$
% 
% 
%  \vspace{0.2in}
% 
% Gate checks:
%  $l_1 + r_1 = o_1 , l_2\cdot r_2 = o_2$\;\;\textbf{\small{(easy)}}
% 
% 
% Wire/copy checks:
% $o_1 = l_2$\;\;\textbf{\small{(hard)}}-ignore for now
% 
% Public input checks: $o_2=7$ \textbf{\small{(easy)}}
% \end{frame}




\begin{frame}
\frametitle{The QAP approach \normalsize{[GGPR,..]}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Reduces to $\prv$ 
knowing deg $<n$ polynomials $L,R,O$ with
\begin{enumerate}
 \item $Z\mid L\cdot R - O$, 
 \item $(L,R,O)\in V_C$.
\end{enumerate}
 \vspace{0.2in}
 $Z(X):= X^n-1$. $n=$ num. of mult gates  \\
\vspace{0.2in}
\noindent
$V_C:=$ affine subspace depending on $C$ 
% \small{(slightly oversimplified)}
 \end{frame}

 \begin{frame}
\frametitle{\normalsize{Verifying first cond. with pairings+KEA \normalsize{[Groth10,...]}} }  % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Setup: uniform secret $s\in \F$, $g\in G$-group with pairing.\\
 \noindent
 CRS: $g,g^s,\ldots,g^{s^n}$.\\
 \vspace{0.2in}
\noindent 

\end{frame}
 \begin{frame}
\frametitle{\normalsize{Verifying first cond. with pairings+KEA \normalsize{[Groth10,...]}} }  % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Setup: uniform secret $s\in \F$, $g\in G$-group with pairing.\\
 \noindent
 CRS: $g,g^s,\ldots,g^{s^n}$.\\
 \vspace{0.2in}
\noindent 
 $\prv$ computes $T=(L\cdot R - O)/Z$.\\
 \vspace{0.2in}
 \noindent
 $\prv$ computes and sends $g^{L(s)},g^{R(s)},g^{O(s)},g^{T(s)}$.\\
 \vspace{0.2in}
  \noindent

\end{frame}
 \begin{frame}
\frametitle{\normalsize{Verifying first cond. with pairings+KEA \normalsize{[Groth10,...]}} }  % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Setup: uniform secret $s\in \F$, $g\in G$-group with pairing.\\
 \noindent
 CRS: $g,g^s,\ldots,g^{s^n}$.\\
 \vspace{0.2in}
\noindent 
 $\prv$ computes $T=(L\cdot R - O)/Z$.\\
 \vspace{0.2in}
 \noindent
 $\prv$ computes and sends $g^{L(s)},g^{R(s)},g^{O(s)},g^{T(s)}$.\\
 \vspace{0.2in}
  \noindent
$\ver$ checks using pairings if 
\[L(s)\cdot R(s) - O(s) = T(s)\cdot Z(s)\]

\end{frame}
 \begin{frame}

 \noindent
 CRS:=$g,g^s,\ldots,g^{s^n}$.\\
  \vspace{0.2in}
\noindent 
 CRS is universal and updatable:
 \begin{itemize}
  \item Universal - depends only on circuit size
 \end{itemize}

\end{frame}

 \begin{frame}

 \noindent
 CRS:=$g,g^s,\ldots,g^{s^n}$.\\
  \vspace{0.2in}
\noindent 
 CRS is universal and updatable:
 \begin{itemize}
  \item Universal - depends only on circuit size
  \item Updatable:  At any point new party $P$ can update CRS with new secret $s'$
  \[\mathrm{CRS_{new}}\defeq g,(g^s)^{s'},\ldots,(g^{s^n})^{s'^n}\]
 \end{itemize}

\end{frame}
 \begin{frame}

 \noindent
 CRS:=$g,g^s,\ldots,g^{s^n}$.\\
  \vspace{0.2in}
\noindent 
 CRS is universal and updatable:
 \begin{itemize}
  \item Universal - depends only on circuit size
  \item Updatable:  At any point new party $P$ can update CRS with new secret $s'$
  \[\mathrm{CRS_{new}}\defeq g,(g^s)^{s'},\ldots,(g^{s^n})^{s'^n}\]
 \end{itemize}
Set of all updaters from all time is required to reconstruct secret of current CRS.

\end{frame}

 \begin{frame}
\frametitle{Verifying second condition}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Now to check $(L,R,O) \in V_C$. \spac
 Include in CRS 
 $g^{\alpha\cdot f(s)}$
 for secret $\alpha\in \F$ (only) for $f\in V_C$. \spac
 
 Ruins universality and updatability of CRS.
 
 
 
\end{frame}


 \begin{frame}
\frametitle{Polynomial commitment schemes}   % Insert frame title between curly braces

{\small{[Groth10,GGPR,..]}} approach: check equation at secret point in the exponent, \emph{limited to degree two checks because of pairings}\\
 \vspace{0.2in}
\noindent

 
\end{frame}
 \begin{frame}
\frametitle{Polynomial commitment schemes}   % Insert frame title between curly braces

{\small{[Groth10,GGPR,..]}} approach: check equation at secret point in the exponent, \emph{limited to degree two checks because of pairings}\\
 \vspace{0.2in}
\noindent

``PCS approach:'' {\small{[MBKM,..,..]}}  $\prv$ will commit to its polynomials
and open them later at random verifier point. 
 
 
\end{frame}
 \begin{frame}
\frametitle{Polynomial commitment schemes}   % Insert frame title between curly braces

{\small{[Groth10,GGPR,..]}} approach: check equation at secret point in the exponent, \emph{limited to degree two checks because of pairings}\\
 \vspace{0.2in}
\noindent

``PCS approach:'' {\small{[MBKM,..,..]}}  $\prv$ will commit to its polynomials
and open them later at random verifier point. \spac
Can be done with single group element commit/opens using {\small [KZG]} scheme.
 
 
\end{frame}

\begin{frame}
  \frametitle{The KZG polynomial commitment scheme}   % Insert frame title between curly braces
 SRS: \enc{1},\enc{s},\ldots,\enc{s^d}, for random $s\in \F$.\\
 \vspace{0.4in}
 $f(X) = \sum_{i=0}^d a_i X^i$\\
 \vspace{0.4in}
 $\cm(f)\defeq  \sum_{i=0}^d a_i \enc{s^i}=  \enc{f(s)}$\\
 \vspace{0.4in}
 
\end{frame}
\begin{frame}
 SRS: \enc{1},\enc{s},\ldots,\enc{s^d},\\
 for random $s\in \F$.
 \vspace{0.4in}
 
 $\cm(f)\defeq   \enc{f(s)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(s)}$, where
$h(X)\defeq \frac{f(X)-f(i)}{X-i}$
 \vspace{0.4in}
 
\end{frame}



\begin{frame}
\frametitle{Idealized Polynomials Protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 \textbf{Preprocessing:} $\ver$ chooses polynomials $g_1,\ldots,g_t\in \polysofdeg{d}$.\\
 \vspace{0.4in}
\textbf{Protocol:}
  \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item 
$\prv$'s  msgs are to ideal party $\ideal$. Must be $f_i\in \polysofdeg{d}$.
 \item At protocol end $\ver$ asks $\ideal$ if some identities hold between $\set{f_1,\ldots,f_\ell,g_1,\ldots,g_t}$.  Outputs $\acc$ iff they do.
\end{enumerate}
\end{frame}











\begin{frame}
\frametitle{Plonk \normalsize{[GWC19]}:}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
  \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item All you need is a permutation check.
 \item Permutations are easier to check on mutliplicative subgroups
\end{enumerate}


\end{frame}
\begin{frame}
\textbf{example:} Prove knowledge of $a,b,c$ with

 
\[(a+b)\cdot c =7\]




\end{frame}


\begin{frame}
Left values: 
$l_1,l_2$\\
Right values: $r_1,r_2$\\
Output values:
$o_1,o_2$


 \vspace{0.2in}

\end{frame}

\begin{frame}
Left values: 
$l_1,l_2$\\
Right values: $r_1,r_2$\\
Output values:
$o_1,o_2$


 \vspace{0.2in}

Gate checks:
 $l_1 + r_1 = o_1 , l_2\cdot r_2 = o_2$


Wire/copy checks:
$o_1 = l_2$

Public input checks: $o_2=7$.
\end{frame}





\begin{frame}

\frametitle{Copy checks with permutations\\ \normalsize{similar to [Groth09,BCGGHJ17]}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 
 \[V= (l_1,l_2,r_1,r_2,o_1,o_2)\]
 
 

\end{frame}


\begin{frame}
\frametitle{Copy checks with permutations\\ \normalsize{similar to [Groth09,BCGGHJ17]}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 
 \[V= (l_1,l_2,r_1,r_2,o_1,o_2)\]
 
 $o_1=l_2$ iff $V=\sigma(V)$ \\
 For permutation $\sigma = (25)$
 
 

\end{frame}





\begin{frame}
\large{Part 2: Permutations are easier to check on mutliplicative subgroups
}

\end{frame}

% \begin{frame}
% \textbf{Feel life is too short to constantly cite the Schwartz-Zippel Lemma?}
% \end{frame}
% 



% \begin{frame}
% \textbf{Feel life is too short to constantly cite the fundamental thm of Algebra?}
% \end{frame}

\begin{frame}
\frametitle{$H$-ranged Polynomials Protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 \textbf{Preprocessing:} $\ver$ chooses polynomials $g_1,\ldots,g_t\in \polysofdeg{d}$, $H\subset\F$.\\
 \vspace{0.4in}
\textbf{Protocol:}
 
 \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item $\prv$'s  msgs are to ideal party $\ideal$. Must be $f_i\in \polysofdeg{d}$.
\item At end, $\ver$ asks $\ideal$ if some identities hold between $\set{f_1,\ldots,f_\ell,g_1,\ldots,g_t}$   \textbf{\textit{on $H$}}. 

\end{enumerate}
\end{frame}


% \begin{frame}
% \frametitle{$H$-ranged protocol using polynomial protocol:}   % Insert frame title between curly braces
% %Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
%  
%  
%  $\ver$ wants to check identities $P_1,P_2$ on $H$.\\
%  \vspace{0.2in}
% \begin{itemize}
% \item  After $\prv$ finished sending \set{f_i}, $\ver$ sends random $a_1,a_2\in \F$.\\
% \item $\prv$ sends  $T\in \polysofdeg{d}$.\\
% \item $\ver$ checks identity
% $a_1\cdot P_1 + a_2\cdot P_2 \equiv T\cdot Z_H$.
% \end{itemize}
% 
% 
% \end{frame}



\begin{frame}
\frametitle{Checking permutations with $H$-ranged protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Permutation $\sigma: [n]\to [n]$.
 $H=\set{\gen,\gen^2,\ldots,\gen^n}$.\\
 \vspace{0.2in}
 
 $\prv$ has sent $f\in \polysofdeg{d}$.\\
 \vspace{0.2in}
 Wants to prove $f=\sigma(f)$:
 \[\forall i\in [n], f(\gen^i) = f(\gen^{\sigma(i)})\]

 

\end{frame}
\begin{frame}
\frametitle{Using [BG12] reduces to:}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 $H=\set{\gen,\gen^2,\ldots,\gen^n}$.\\
 \vspace{0.2in}
 
 $\prv$ has sent $f,g\in \polysofdeg{d}$.\\
 \vspace{0.2in}
 Wants to prove:
 \[\prod_{i\in [n]}  f(\gen^i) = \prod_{i\in [n]} g(\gen^i)\]

 

\end{frame}




\begin{frame}
\frametitle{Checking products with $H$-ranged protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 \begin{enumerate}
  \item $\prv$ computes $Z$ with 
  $ Z(\gen)=1, Z(\gen^i) = \prod_{j<i}  f(\gen^j)/g(\gen^j)$, {\small{$i=2..n+1$}}.
  \item Sends $Z$ to $\ideal$.

 \end{enumerate}


\end{frame}

\begin{frame}
\frametitle{Checking products with $H$-ranged protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 \begin{enumerate}
  \item $\prv$ computes $Z$ with 
  $ Z(\gen)=1, Z(\gen^i) = \prod_{j<i}  f(\gen^j)/g(\gen^j)$.
  \item Sends $Z$ to $\ideal$.
  \item $\ver$ checks following identities on $H$.
  \begin{enumerate}
   \item $L_1(X) (Z(X)-1) =0$
   \item $Z(X) f(X) = Z(\gen\cdot X)g(X)$
 \item $L_n(X) (Z(\gen\cdot X) -1)=0$ 
 \end{enumerate}

 \end{enumerate}


\end{frame}




\begin{frame}
\frametitle{The bottom line {\normalsize{(on BLS-381 curve)}}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 600 byte proofs with one trusted setup for all fan-in two circuits of $n$ gates.\\
  \vspace{0.2in}
Prover does $11n$ $G_1$ exp {\small{(or $9n$ $G_1$ exp with 700 byte proof)}}.\\
  \vspace{0.2in}
For batch of proofs on same circuit only $3n$ $G_1$ exp and $240$ bytes for each additional proof.
 

\end{frame}


\begin{frame}
\large{Bonus material: The KZG polynomial commitment scheme
}

\end{frame}

\begin{frame}
 SRS: \enc{1},\enc{x},\ldots,\enc{x^d}, for random $x\in \F$.\\
 \vspace{0.4in}
 $f(X) = \sum_{i=0}^d a_i X^i$\\
 \vspace{0.4in}
 $\cm(f)\defeq  \sum_{i=0}^d a_i \enc{x^i}=  \enc{f(x)}$\\
 \vspace{0.4in}
 
\end{frame}
\begin{frame}
 SRS: \enc{1},\enc{x},\ldots,\enc{x^d},\\
 for random $x\in \F$.
 \vspace{0.4in}
 
 $\cm(f)\defeq   \enc{f(x)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
$h(X)\defeq \frac{f(X)-f(i)}{X-i}$
 \vspace{0.4in}
 
\end{frame}

% 
% \begin{frame}
%  $\cm(f)\defeq   \enc{f(x)}$\\
%  \vspace{0.4in}
% $\open{f,i}\defeq \enc{h(x)}$, where
%  $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\
%  \vspace{0.4in}
% \textbf{exercise} - using pairing, define:\\
%  \vspace{0.2in}
%  $\verify{\cm,\pi,z,i}$,
%  where $z$ is allegedly $f(i)$
%  \end{frame}




\begin{frame}

 $\cm(f)\defeq   \enc{f(x)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
 $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\
 \vspace{0.4in}
 $\verify{\cm,\pi,z,i}:$
\[e(\cm-\enc{z},\enc{1}) \stackrel{?}{=} e(\pi, \enc{x-i})\]
\end{frame}


 


\begin{frame}

 $\cm(f)\defeq   \enc{f(x)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
 $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\
 \vspace{0.4in}
 $\verify{\cm,\pi,z,i}:$
\[e(\cm-\enc{z},\enc{1}) \stackrel{?}{=} e(\pi, \enc{x-i})\]
 \vspace{0.4in}
\textbf{Thm}{\footnotesize{[KZG,MBKM]}}: \emph{This works in the Algebraic Group Model.}
 \end{frame}


\end{document}