polyprottechnionseminar2020.tex

\documentclass[shadesubsections,compress,14pt,mathserif]{beamer}
\usepackage[danish]{babel}	
\usepackage{tikz}
\usetikzlibrary{shapes, positioning}
\usenavigationsymbolstemplate{}
\usepackage{pgfplots}
\usepackage[absolute,overlay]{textpos}

%\usepackage[T1]{fontenc}
%\usepackage{fourier}
% Dokumentets sprog
%\usepackage{mathtools}
%\usepackage{pxfonts}
\usepackage{amssymb, 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{\prot}{\mathbf{P}}
\newcommand{\aggdeg}[1]{\mathfrak{d}(#1)}
\renewcommand{\deg}{\mathrm{deg}}
\newcommand{\adv}{\ensuremath{\mathcal A}}
\newcommand{\xor}{\ensuremath{\oplus}}
\newcommand{\plonk}{\ensuremath{\mathcal{P} \mathfrak{lon}\mathcal{K}}}
\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}

%\setbeamersize{text margin left=3mm,text margin right=3mm} 
\title{\large{Ranged Polynomial Protocols}}    % Enter your title between curly braces
\author{\small{Ariel Gabizon }\\                 % Enter your name between curly braces
                                       }      % 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
  \includegraphics{azteclogo.png}
\end{frame}
\begin{frame}
 \frametitle{Outline}   % Insert frame title between curly braces
 \begin{itemize}
  \item A few slides of motivation and context
  \item Polynomial Protocols -  dfns,results + open question.
 \end{itemize}

\end{frame}
\begin{frame}
 \frametitle{Succinct arguments in a nutshell}   % Insert frame title between curly braces
 Public program $T$, public output $z$.\\ \pause
 \vspace{0.4in}
 Want to prove ``I know input $x$ for program $T$ that generates output $z$.\\ \pause
 \vspace{0.4in}
Want proof size and verification time to be much smaller than run time of $T$. \\ 
{\small (SNARK:=Succinct Non-Interactive Argument of Knowledge)}\\ \pause
 \vspace{0.4in}
 Arithmeitization {\small [LFKN,......]}: Reduce claim to claim of form ''I know polynomials that satisfy some identity`` \pause
\end{frame}
\begin{frame}
 \frametitle{Succinct arguments in a nutshell}   % Insert frame title between curly braces
 Advantage of claims about polynomials is that suffice to check at one random point \\ \pause
 \vspace{0.4in}
 But need to solve ''chicken and egg problem``: Prover must commit to polynomials before knowing the challenge point. 
 \vspace{0.4in}
 
\end{frame}
\begin{frame}
 \frametitle{Polynomial commitment schemes {\small [KZG, 10]}}   % Insert frame title between curly braces
\begin{itemize}
 \item Prover send short commitment $\cm(f)$ to polynomial.\pause
 \item Later Verifier can choose value $i\in \F$.\pause
 \item Prover sends back $z=f(i)$ ; together with proof $\open{f,i}$ that $z$ is correct.\pause
\end{itemize}
KZG give us PCS with commitments and openings are practically 32 bytes.\\ 
Notation: $\enc{x}=g^x$ where $g$ generator of elliptic curve group.
\end{frame}


\begin{frame}

 Setup: $\enc{1},\enc{x},\ldots,\enc{x^d}$, for random $x\in \F$.\\ \pause
 \vspace{0.4in}
 $\cm(f)\defeq   \enc{f(x)}$\\ \pause
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
 $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\ \pause
 \vspace{0.4in}
 $\verify{\cm,\pi,z,i}:$
\[e(\cm-\enc{z},\enc{1}) \stackrel{?}{=} e(\pi, \enc{x-i})\]
\end{frame}


 


\begin{frame}
\frametitle{Idealized Polynomials Protocols}   % Insert frame title between curly braces
 
 \textbf{Preprocessing/inputs:} : $\prv$ and $\ver$ agree in advance on $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 (constant number) of 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}


$$\aggdeg{\prot}\defeq\left(\sum_{i\in [\ell]} \deg(f_i)+1\right)$$.\pause \\
 \vspace{0.2in}
\textbf{Thm:\footnote{similar statements in Marlin/Fractal/Supersonic}}
Can compile to ``real'' protocol in Algebraic Group Model, where prover complexity  $\sim \aggdeg{\prot}$ .\\ \pause
 \vspace{0.2in}
\textbf{proof sketch:}
 Use [KZG] polynomial commitment scheme. $\prv$ commits to all polys. $\ver$ checks identity at random challenge point. 
\end{frame}
\begin{frame}
\frametitle{Ranged polynomials protocols}   % insert frame title between curly braces

\textbf{Preprocessing/inputs:} Predefined polynomials $g_1,\ldots,g_t\in \polysofdeg{d}$\\
\textbf{Range:} $H\subset\F$.\\ \pause
\vspace{0.4in}
\textbf{Protocol:}
 
 \begin{enumerate}
\item $\prv$'s  msgs are to ideal party $\ideal$. Must be $f_i\in \polysofdeg{d}$.
\item At end, $\ver$ asks $\ideal$ if some identity holds 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
 
 
 $\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$.\\ \pause
\item $\prv$ sends  $T\in \polysofdeg{d}$.\\ \pause
\item $\ver$ checks identity
$a_1\cdot P_1 + a_2\cdot P_2 \equiv T\cdot Z_H$.
\end{itemize}
 \vspace{0.2in}
$Z_H(X)\defeq \prod_{a\in H}(X-a)$. \\
($Z_H$ will be a preprocessed polynomial).\\
 \vspace{0.2in}
 

\end{frame}
\begin{frame}
\frametitle{$H$-ranged protocol using polynomial protocol:}   % Insert frame title between curly braces
Motivates - for $H$-ranged protocol $\prot$ define
 \[\aggdeg{\prot}\defeq \left(\sum_{i\in [\ell]} \deg(f_i)+1\right) + D- |H|.\]

$D\defeq$ max degree of identity $C$ checked in exec with honest $\prv$.\\
 \vspace{0.2in}
 

\end{frame}

\begin{frame}
\frametitle{Multiset equality check}
Given $a,b\in \F^3$, want to check $\{b_1,b_2,b_3\} \stackrel{?}{=} \{a_1,a_2,a_3\}$ \\ \pause
 \vspace{0.2in}

  
 Choose random $\gamma\in \F$. Check
  \[(a_1 + \gamma)(a_2+ \gamma)(a_3 + \gamma) \stackrel{?}{=} (b_1+\gamma)(b_2+\gamma)(b_3+\gamma)\]\pause
%   \[a'_1 = a_1 + \gamma, a'_2 = a_2 + \gamma, a'_3 = a_3 + \gamma\]
%  \[b'_1 = b_1 + \gamma, b'_2 = b_2 + \gamma, b'_3 = b_3 + \gamma\]\pause

 \vspace{0.2in}
 If $a,b$ different as sets then w.h.p products different.\pause
 
\end{frame}



\begin{frame}
\frametitle{Multiset equality check - polynomial version}
Given $f,g\in \polysofdeg{d}$, want to check $\sett{f(x)}{x\in H} \stackrel{?}{=} \sett{g(x)}{x\in H}$ as multisets \\ 
 
\end{frame}
\begin{frame}
\frametitle{Reduces to:}   % Insert frame title between curly braces
 $H=\set{\gen,\gen^2,\ldots,\gen^n}$.\\
 \vspace{0.2in}
 
 $\prv$ has sent $f',g'\in \polysofdeg{n}$.\\
 \vspace{0.2in}
 Wants to prove:
 \[\prod_{i\in [n]}  f(\gen^i) = \prod_{i\in [n]} g(\gen^i)\]

 $f\defeq f' +\gamma,g\defeq g'+\gamma$

\end{frame}

\begin{frame}
\frametitle{Multiplicative subgroups:}   % Insert frame title between curly braces
 $H=\set{\gen,\gen^2,\ldots,\gen^n=1}$.\\
 \vspace{0.2in}
 $L_i$ is i'th lagrange poly of $H$:
 \[L_i(\alpha^i)=1,L_i(\alpha^j) =0, j\neq i\]
\end{frame}


\begin{frame}
\frametitle{Checking products with $H$-ranged protocols \small{[GWC19]}}   % Insert frame title between curly braces
 \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$.   \pause
  \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)$\pause
 \end{enumerate}

 \end{enumerate}
 \vspace{0.2in}
We get $\aggdeg{\prot}=n+2n -|H| = 2n$.


\end{frame}
\begin{frame}
\frametitle{Example 2: Range checks}
Integer $M<n$. Given $f\in \polysofdeg{n}$, want to check $f(x)\in [1..M]$ for each $x\in H$.\\ \pause
(most?) common SNARK operation: SNARK recursion requires simulating one field using another \\ 

\end{frame}
\begin{frame}
\frametitle{Example 2: Range checks}

\textbf{Simplifying assumption:} $[1..M]\subset \sett{f(x)}{x\in H}$\\ \pause
\textbf{Protocol:}
 \begin{enumerate}
 \item $\prv$ computes ''sorted version of $f$``: $s\in \polysofdeg{n}$ with
 $\sett{s(x)}{x\in H}=\sett{f(x)}{x\in H}$, $s(\alpha^i)\leq s(\alpha^{i+1})$.\pause
 \item $\prv$ sends $s$ to $\ideal$.\pause
 \item $\ver$ checks that
 \begin{enumerate}
  \item Mutli-set equality between $s$ and $f$.\pause
  \item $s(\alpha)=1$
  \item $s(\alpha^n) = M$\pause
  \item For each $x\in H\setminus \set{1}$,\pause
  \[ (s(x\cdot \alpha) - s(x))^2 = s(x\cdot \alpha) - s(x)\]
 \end{enumerate}

\end{enumerate}


We get $\aggdeg{\prot}=3n$ \\
\end{frame}
\begin{frame}
To remove assumption use preprocessed ''table poly`` $t$ with $\sett{t(x)}{x\in H}=[1..M]$\\
(details on next slide)
 \vspace{0.2in}



\end{frame}

\begin{frame}
% \frametitle{Example 2: Range checks}

\textbf{Preprocessed poly:} $t\in \polysofdeg{M}$ with $\sett{t(x)}{x\in H}=[1..M]$ \\ \pause
\textbf{Protocol:}
 \begin{enumerate}
 \item $\prv$ computes ''sorted version of $f\cup t$``: $s\in \polysofdeg{n+M}$ with
 $\sett{s(x)}{x\in H}=\sett{f(x),t(x)}{x\in H}$, $s(\alpha^i)\leq s(\alpha^{i+1})$.\pause
 \item $\prv$ sends $s$ to $\ideal$.\pause
 \item $\ver$ checks that
 \begin{enumerate}
  \item Mutli-set equality between $s$ and $f\cup t$.\pause
  \item $s(\alpha)=1$
  \item $s(\alpha^n) = M$
  \item For each $x\in H\setminus \set{1}$,\pause
  \[ (s(x\cdot \alpha) - s(x))^2 = s(x\cdot \alpha) - s(x)\]
 \end{enumerate}

\end{enumerate}


We get $\aggdeg{\prot}= \deg(s)+\deg(Z)+D-|H| = 3n+4M$.
\end{frame}
\begin{frame}
Given integer $d$ decomposing each element to $d$ elements in range $[1..M^{1/d}]$ can 
give us $$\aggdeg{\prot} = 4dn+4M^{1/d}$$(by sending an auxiliary polynomial of degree $<dn$ with the decomposition of each element and then running the $M^{1/d}$ size range proof on this polynomial).\\

 \vspace{0.2in}
\textbf{Question: can we do better?}


\end{frame}


\end{document}