\usepackage{amsthm}
\usepackage{xcolor}

\usepackage{fullpage}
\usepackage{microtype,pdfsync}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{tabu}
\usepackage{url}
\usepackage{graphicx}

\usepackage{xspace}
\usepackage{multirow}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{mathtools}

\usepackage{framed}
\usepackage{booktabs}
\usepackage{caption}

\usepackage{nopageno}

\usepackage[T1]{fontenc}
\usepackage{fourier}
\DeclareSymbolFont{calletters}{OMS}{cmsy}{m}{n}
\DeclareSymbolFontAlphabet{\mathcal}{calletters}

% xspace with not in math mode
\newcommand{\xspacemm}{\ifmmode\else\xspace\fi}
% contents in math mode, xspace after if outside it
\newcommand{\mathnoun}[1]{\ensuremath{#1}\xspacemm}
% new macro with contents as mathnoun
\newcommand{\newmathnoun}[2]{\newcommand{#1}{\mathnoun{#2}}}
% renew macro with contents as mathnoun
\newcommand{\renewmathnoun}[2]{\renewcommand{#1}{\mathnoun{#2}}}
% new argument-taking macro with contents as mathnoun
\newcommand{\newmathfn}[3]{\newcommand{#1}[#2]{\mathnoun{#3}}}
% renew argument-taking macro with contents as mathnoun
\newcommand{\renewmathfn}[3]{\renewcommand{#1}[#2]{\mathnoun{#3}}}

\usepackage[hang,flushmargin]{footmisc}

\usepackage{hyperref}
\hypersetup{
	colorlinks=true,
	linkcolor={blue!60!black},
	citecolor={blue!60!black},
	urlcolor={blue!60!black},
	bookmarksopen=true
}
\usepackage{bookmark}

\bookmarksetup{  numbered,
depth=5}
\usepackage{scalerel}
\setcounter{secnumdepth}{2}

\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{arrows.meta}

\newcommand{\ignore}[1]{}
%\numberwithin{equation}{section}


\newmathnoun{\concat}{\mathbin{||}}

%fields and groups
\newmathnoun{\F}{\mathbb{F}}
\newmathnoun{\Fp}{\F_p}
\newmathnoun{\Fq}{\F_q}
\newmathnoun{\Ftwo}{\F_2}
\newmathnoun{\Q}{\mathbb{Q}}
\newmathnoun{\N}{\mathbb{N}}
\newmathnoun{\Z}{\mathbb{Z}}
\newmathnoun{\R}{\mathbb{R}}
\newmathnoun{\C}{\mathbb{C}}
\newmathnoun{\T}{\mathbb{T}}
\newmathnoun{\Qbar}{\overline{\Q}}
\newmathnoun{\G}{\mathbb{G}}
\newmathnoun{\Vs}{\mathbb{V}}
\newmathnoun{\Fbar}{\overline{\mathbb{F}}}

\DeclareMathOperator*{\Exp}{\mathbb{E}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator*{\Var}{\mathrel{Var}}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

%vectors, etc.
\newmathnoun{\av}{\mathbf{a}} \newmathnoun{\cv}{\mathbf{c}}
\newmathnoun{\dv}{\mathbf{d}} \newmathnoun{\ev}{\mathbf{e}}
\newmathnoun{\rv}{\mathbf{r}} \newmathnoun{\sv}{\mathbf{s}}
\newmathnoun{\tv}{\mathbf{t}} \newmathnoun{\uv}{\mathbf{u}}
\newmathnoun{\vv}{\mathbf{v}} \newmathnoun{\wv}{\mathbf{w}}
\newmathnoun{\xv}{\mathbf{x}} \newmathnoun{\yv}{\mathbf{y}}
\newmathnoun{\zv}{\mathbf{z}} \newmathnoun{\zerov}{\mathbf{0}}
\newmathnoun{\A}{\mathcal{A}} \newmathnoun{\B}{\mathcal{B}}
\newmathnoun{\dash}{\mbox{---}}
\renewmathnoun{\O}{\mathcal{O}}
\newmathnoun{\qq}{\mathfrak{q}}
\newmathnoun{\QQ}{\mathfrak{Q}}
\newmathnoun{\ZQ}{\Z_{q}}
\newmathnoun{\Zp}{\Z_p}

\newmathnoun{\vk}{\mathbf{k}}
\newmathnoun{\vu}{\mathbf{u}}

\newcommand{\todo}[1]{\noindent {\color{blue} {\footnotesize {\bf TODO}:~{#1}}}}

\newmathfn{\mr}{1}{\mathrm{{#1}}}
\newmathnoun{\la}{\leftarrow}
\newmathnoun{\ra}{\rightarrow}
\newmathnoun{\ala}{\ \la\ }
\newmathnoun{\ara}{\ \ra\ }
\newmathnoun{\rf}{\overset{\$}{\la}}

\newmathnoun{\calA}{\mathcal{A}}
\newmathnoun{\calB}{\mathcal{B}}
\newmathnoun{\calC}{\mathcal{C}}
\newmathnoun{\calD}{\mathcal{D}}
\newmathnoun{\calE}{\mathcal{E}}
\newmathnoun{\calF}{\mathcal{F}}
\newmathnoun{\calG}{\mathcal{G}}
\newmathnoun{\calH}{\mathcal{H}}
\newmathnoun{\calI}{\mathcal{I}}
\newmathnoun{\calJ}{\mathcal{J}}
\newmathnoun{\calK}{\mathcal{K}}
\newmathnoun{\calL}{\mathcal{L}}
\newmathnoun{\calM}{\mathcal{M}}
\newmathnoun{\calN}{\mathcal{N}}
\newmathnoun{\calO}{\mathcal{O}}
\newmathnoun{\calP}{\mathcal{P}}
\newmathnoun{\calQ}{\mathcal{Q}}
\newmathnoun{\calR}{\mathcal{R}}
\newmathnoun{\calS}{\mathcal{S}}
\newmathnoun{\calT}{\mathcal{T}}
\newmathnoun{\calU}{\mathcal{U}}
\newmathnoun{\calV}{\mathcal{V}}
\newmathnoun{\calW}{\mathcal{W}}
\newmathnoun{\calX}{\mathcal{X}}
\newmathnoun{\calY}{\mathcal{Y}}
\newmathnoun{\calZ}{\mathcal{Z}}

% -- bold math symbols, for some reason --
\newmathnoun{\boldalpha}{\boldsymbol{\alpha}}
\newmathnoun{\boldchi}{\boldsymbol{\chi}}
\newmathnoun{\boldtau}{{\boldsymbol{\tau}}}
\newmathnoun{\boldstar}{\mathbf{*}}
\newmathnoun{\bolda}{\mathbf{a}}
\newmathnoun{\boldb}{\mathbf{b}}
\newmathnoun{\boldc}{\mathbf{c}}
\newmathnoun{\boldd}{\mathbf{d}}
\newmathnoun{\bolde}{\mathbf{e}}
\newmathnoun{\boldf}{\mathbf{f}}
\newmathnoun{\boldg}{\mathbf{g}}
\newmathnoun{\boldh}{\mathbf{h}}
\newmathnoun{\boldi}{\mathbf{i}}
\newmathnoun{\boldj}{\mathbf{j}}
\newmathnoun{\boldk}{\mathbf{k}}
\newmathnoun{\boldl}{\mathbf{l}}
\newmathnoun{\boldm}{\mathbf{m}}
\newmathnoun{\boldn}{\mathbf{n}}
\newmathnoun{\boldo}{\mathbf{o}}
\newmathnoun{\boldp}{\mathbf{p}}
\newmathnoun{\boldq}{\mathbf{q}}
\newmathnoun{\boldr}{\mathbf{r}}
\newmathnoun{\bolds}{\mathbf{s}}
\newmathnoun{\boldt}{\mathbf{t}}
\newmathnoun{\boldu}{\mathbf{u}}
\newmathnoun{\boldv}{\mathbf{v}}
\newmathnoun{\boldw}{\mathbf{w}}
\newmathnoun{\boldx}{\mathbf{x}}
\newmathnoun{\boldy}{\mathbf{y}}
\newmathnoun{\boldz}{\mathbf{z}}
\newmathnoun{\boldzero}{\boldsymbol{0}}
\newmathnoun{\boldone}{\boldsymbol{1}}
\newmathnoun{\boldpi}{\boldsymbol{\pi}}
\newmathnoun{\boldPi}{\boldsymbol{\Pi}}

% -- bold italic math symbols, for some reason --
\newmathnoun{\boldia}{\boldsymbol{a}}
\newmathnoun{\boldib}{\boldsymbol{b}}
\newmathnoun{\boldic}{\boldsymbol{c}}
\newmathnoun{\boldid}{\boldsymbol{d}}
\newmathnoun{\boldie}{\boldsymbol{e}}
\newmathnoun{\boldif}{\boldsymbol{f}}
\newmathnoun{\boldig}{\boldsymbol{g}}
\newmathnoun{\boldih}{\boldsymbol{h}}
\newmathnoun{\boldii}{\boldsymbol{i}}
\newmathnoun{\boldij}{\boldsymbol{j}}
\newmathnoun{\boldik}{\boldsymbol{k}}
\newmathnoun{\boldil}{\boldsymbol{l}}
\newmathnoun{\boldim}{\boldsymbol{m}}
\newmathnoun{\boldin}{\boldsymbol{n}}
\newmathnoun{\boldio}{\boldsymbol{o}}
\newmathnoun{\boldip}{\boldsymbol{p}}
\newmathnoun{\boldiq}{\boldsymbol{q}}
\newmathnoun{\boldir}{\boldsymbol{r}}
\newmathnoun{\boldis}{\boldsymbol{s}}
\newmathnoun{\boldit}{\boldsymbol{t}}
\newmathnoun{\boldiu}{\boldsymbol{u}}
\newmathnoun{\boldiv}{\boldsymbol{v}}
\newmathnoun{\boldiw}{\boldsymbol{w}}
\newmathnoun{\boldix}{\boldsymbol{x}}
\newmathnoun{\boldiy}{\boldsymbol{y}}
\newmathnoun{\boldiz}{\boldsymbol{z}}

\newmathfn{\transpose}{1}{{#1}^{\intercal}}

\newmathnoun{\boldA}{\mathbf{A}}
\newmathnoun{\boldB}{\mathbf{B}}
\newmathnoun{\boldC}{\mathbf{C}}
\newmathnoun{\boldD}{\mathbf{D}}
\newmathnoun{\boldE}{\mathbf{E}}
\newmathnoun{\boldF}{\mathbf{F}}
\newmathnoun{\boldG}{\mathbf{G}}
\newmathnoun{\boldH}{\mathbf{H}}
\newmathnoun{\boldI}{\mathbf{I}}
\newmathnoun{\boldJ}{\mathbf{J}}
\newmathnoun{\boldK}{\mathbf{K}}
\newmathnoun{\boldL}{\mathbf{L}}
\newmathnoun{\boldM}{\mathbf{M}}
\newmathnoun{\boldN}{\mathbf{N}}
\newmathnoun{\boldO}{\mathbf{O}}
\newmathnoun{\boldP}{\mathbf{P}}
\newmathnoun{\boldQ}{\mathbf{Q}}
\newmathnoun{\boldR}{\mathbf{R}}
\newmathnoun{\boldS}{\mathbf{S}}
\newmathnoun{\boldT}{\mathbf{T}}
\newmathnoun{\boldU}{\mathbf{U}}
\newmathnoun{\boldV}{\mathbf{V}}
\newmathnoun{\boldW}{\mathbf{W}}
\newmathnoun{\boldX}{\mathbf{X}}
\newmathnoun{\boldY}{\mathbf{Y}}
\newmathnoun{\boldZ}{\mathbf{Z}}

\newmathnoun{\deq}{\mathrel{\mathop:}=}
\newmathnoun{\zo}{\{0,1\}} % bits
\newmathnoun{\zon}{\{0,1\}^n} % bits

% Theorem definitions

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem*{claims}{Claim}
\newtheorem*{theorems}{Theorem}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{construction}[theorem]{Construction}

\newcounter{problemcnt}
\newcommand{\problem}[1]{\refstepcounter{problemcnt}\paragraph{Problem~\arabic{problemcnt}: #1.}}
\newcommand{\solution}{\paragraph{Solution:}}

%% custom macros

\newcommand{\esm}[1]{\ensuremath{#1}}
\newcommand{\ms}[1]{\esm{\mathsf{#1}}}

\newmathnoun{\poly}{\esm{\mr{poly}}}
\newmathnoun{\polylog}{\operatorname{polylog}}
\newmathnoun{\negl}{\esm{\mr{negl}}}

\newmathfn{\ord}{1}{\esm{{#1}^{\mr{th}}}}

\newmathnoun{\getsr}{\mathrel{\mathpalette\rgetscmd\relax}}
\newcommand{\rgetscmd}{\ooalign{$\leftarrow$\cr
    \hidewidth\raisebox{1.2\height}{\scalebox{0.5}{\ \rm \$}}\hidewidth\cr}}

\newmathnoun{\app}{\approx}
\newmathnoun{\appc}{\stackrel{c}{\approx}}
\newmathnoun{\apps}{\stackrel{s}{\approx}}
\newmathfn{\abs}{1}{\left| #1 \right|}

\newmathnoun{\classP}{\ms{P}}
\newmathnoun{\classBPP}{\ms{BPP}}
\newmathnoun{\classNP}{\ms{NP}}

\newmathfn{\round}{1}{\left\lfloor #1 \right\rceil}
\newmathfn{\floor}{1}{\left\lfloor #1 \right\rfloor}
\newmathfn{\ceil}{1}{\left\lceil #1 \right\rceil}
\newmathfn{\iprod}{1}{\left\langle #1 \right\rangle}
\newmathfn{\norm}{1}{\left\| #1 \right\|}
\newmathfn{\set}{1}{\left\{ #1 \right\}}

\newmathnoun{\Zq}{\Z_q}

\newmathnoun{\eqq}{\stackrel{?}{=}}

\newmathnoun{\Otilde}{\widetilde{O}}

\newmathnoun{\xstar}{x^*}
\newmathnoun{\ystar}{y^*}

\newmathnoun{\DDHAdv}{\ms{DDHAdv}}
\newmathnoun{\PRFAdv}{\ms{PRFAdv}}
\newmathnoun{\SCPRFAdv}{\ms{SC\hbox{-}PRFAdv}}

\newmathnoun{\ct}{\ms{ct}}

\newmathnoun{\view}{\ms{view}_{P,V^*}}
\newmathnoun{\viewHonest}{\ms{view}_{P,V}}
\newmathnoun{\Sim}{\calS}

\newmathnoun{\SIS}{\ms{SIS}}
\newmathnoun{\ISIS}{\ms{ISIS}}
\newmathnoun{\LWE}{\ms{LWE}}
\newmathnoun{\mLWE}{\ms{MatrixLWE}}

\newmathnoun{\LWEadv}{\ms{LWEAdv}}
\newmathnoun{\HNFLWEadv}{\textsf{HNF-LWEAdv}}
\newmathnoun{\mLWEadv}{\ms{MatrixLWEAdv}}
\newmathnoun{\SISadv}{\ms{SISAdv}}
\newmathnoun{\ISISadv}{\ms{ISISAdv}}

\newmathfn{\pro}{1}{\langle #1 \rangle}
\newmathnoun{\cSAT}{\ms{circuit}\text{-}\ms{SAT}}

\newmathnoun{\sk}{\ms{sk}}
\newmathnoun{\pk}{\ms{pk}}

\newmathnoun{\td}{\ms{td}}
\newmathnoun{\TrapGen}{\ms{TrapGen}}

\newmathfn{\Mod}{1}{\ (\mathrm{mod}\ #1)}

\newmathnoun{\Commit}{\ms{Commit}}
\newmathnoun{\Open}{\ms{Open}}
\newmathnoun{\Verify}{\ms{Verify}}
\newmathnoun{\IdxOpen}{\ms{IdxOpen}}
\newmathnoun{\IdxVerify}{\ms{IdxVerify}}
