old-collection.tex

\documentclass[11pt]{book}
\usepackage{url,amsmath,setspace,amssymb,fullpage,color,tikz}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage[margin=1in]{geometry}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{graphicx}
\usepackage{frame,comment}
\usepackage{mathrsfs}
\usepackage{xspace, extarrows}

\floatstyle{boxed}
\restylefloat{figure}
\usepackage[most]{tcolorbox}
\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox[\textwidth]{
     \begin{minipage}{0.9\textwidth} \onehalfspacing
       {\bf CS 276 -- Cryptography} \hfill #2

       {\centering \Large #5

       }\medskip

       {\it #3 \hfill #4}
     \end{minipage}
   }
   \end{center}
}

\newcommand{\scribe}[4]{\heading{#1}{#2}{Instructor:
Sanjam Garg}{GSI: #4}{Lecture #1: #3}}

%\setlength{\parindent}{0in}

\newcommand{\proof}{\noindent{\bf Proof. }} %% To begin a proof write \proof
\newcommand{\qed}{\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\rule{0.6em}{0.6em}$}} %%to end your proof write $\qed$.
\newcommand{\ma}{{\mathcal A}}
\newtheorem{lemma}{Lemma}[chapter]
\newtheorem{remark}{Remark}[chapter]
\newtheorem{claim}{Claim}[chapter]
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{corollary}{Corollary}[chapter]
\newtheorem{construction}{Construction}[chapter]
\newtheorem{definition}{Definition}[chapter]
\newtheorem{proposition}{Proposition}[chapter]
\newtheorem{exercise}{Exercise}[chapter]
\bibliographystyle{plain}



%\newtcolorbox[auto counter,list inside=defs,number within=section]{definition}[2][]{title={Definition~\thetcbcounter},colback={white!30!yellow},colbacktitle={gray},coltitle=black,#1}

\newcommand{\binset}[1]{\{ 0, 1 \}^{#1}}
\newcommand{\binfunc}[2]{\binset{#1} \rightarrow \binset{#2}}

\newcommand{\concat}[0]{\; || \;}

\newcommand{\tnotes}[1]{{\color{red} Teaching Notes: #1}}

\newcommand{\sanjam}[1]{{\color{red} Sanjam: #1}}

\newcommand{\peihan}[1]{{\color{blue} Peihan: #1}}
\renewcommand{\sanjam}[1]{}

%\DeclarePairedDelimiter{\Prfences}{[}{]}

\title{CS276: Graduate Cryptography\thanks{Based on scribe notes by students from taking CS276 in fall 2014. Also, thanks to Peihan Miao and Akshayaram Srinivasan for helping improve these notes.}\\ \textbf{This draft is continually being updated.}}
\author{Sanjam Garg\\ University of California, Berkeley}

\begin{document}
\maketitle

\tableofcontents

\input{Old Scribe Notes/lec02.tex}



\newcommand{\gen}{\mathsf{Gen}}
\newcommand{\enc}{\mathsf{Enc}}
\newcommand{\dec}{\mathsf{Dec}}
\newcommand{\pk}{\mathsf{pk}}
\newcommand{\sk}{\mathsf{sk}}
\newcommand{\fake}{\mathsf{FAKE}}
\newcommand{\mright}[3]{
    $#1$ & \quad$\xrightarrow{\parbox{3cm}{\centering$#2$}}$\quad & $#3$ \\
}
\newcommand{\mleft}[3]{
    $#1$ & \quad$\xleftarrow{\parbox{3cm}{\centering$#2$}}$\quad & $#3$ \\
}

\input{Old Scribe Notes/lec05.tex}
\input{Old Scribe Notes/lec06.tex}


\input{Old Scribe Notes/assumptions}  

%Signatures
\input{Old Scribe Notes/lec13}

%PKE
\input{Old Scribe Notes/lec09}
\input{Old Scribe Notes/lec12}

%IBE
%


\input{Old Scribe Notes/lec07}
\input{Old Scribe Notes/lec08}
%NIZK
%\input{Old Scribe Notes/lec10.tex}
%\input{Old Scribe Notes/lec11.tex}


\input{Old Scribe Notes/lec14}

%Secure Computation
\input{Old Scribe Notes/lec15}

\input{Old Scribe Notes/sec_com}
\input{Old Scribe Notes/lec16}
%\input{Old Scribe Notes/oram.tex}

\input{Old Scribe Notes/lec18}
\input{Old Scribe Notes/lec19}
\input{Old Scribe Notes/lec20}
\input{Old Scribe Notes/lec22}


\iffalse

\input{Old Scribe Notes/ram}
% IO


%\chapter{Fully-Homomorphic Encryption}
%\begin{itemize}
%	\item $(KeyGen, Enc, Dec, Eval)$
%
%	\item $Eval (C)$ output a circuit $C'$ such that $C'(e)$ is an encryption of $C(x)$ if $e$ was an encryption of $x$ and we have that $|e|\leq poly(|m|,k)$.
%	\item How can I improve communication complexity of secure computation and NIZK?	
%	\item Some more definitions
%\begin{itemize}
%	\item $d$-HE is an HE scheme that allows for $Eval$ on circuits of depth $d$ with the property that $|e|\leq poly(|m|,k)$.
%	\item Encryption scheme has decryption circuit of some depth say $\alpha\cdot d$.
%	\item circularly secure encryption	
%\end{itemize}
%	\item Construct 0 depth homomorphic encryption? DDH-Elgamal
%	\item Given a circularly secure $d$-HE with decryption circuit of size $\alpha\cdot d$ construct an FHE.
%	\item Open: Does FHE imply IBE? Can we do without circular security?	
%\end{itemize}
\fi
\bibliography{cryptobib/abbrev0,cryptobib/crypto}
\bibliographystyle{plainnat}
\printbibliography
\end{document}