\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{color,amsfonts,amsmath}

\newcommand{\todo}[1]{\noindent{\textcolor{red}{{\textbf{[TODO]}: #1}}}}


\title{CS848 Winter 2021 Assignment 3}
\author{\todo{[Student Name]}}
\date{Due by March 29, 11pm}

\begin{document}

\maketitle

Please submit a pdf solution on Learn: "Submit" $\rightarrow$  "Dropbox folder" $\rightarrow$  "Assignment 3". 

\section*{Q1. Design Choice I}

Consider a database schema consists of 3 attributes Grade(StudentID, ClassID, Score). Below is a listed of intended queries on this database:

\begin{itemize}
    \item Select * from Grade where StudentID = ``xh23";  
    \item Select ClassID, Count(*) from Grade Group By ClassID; 
    \item Select Count(*) from Grade where Score $\in [60,100]$;
    \item Select Max(Score) from Grade where classID =``cs848";
\end{itemize}

\subsection*{(a) Ciphertext Schema} [8 points] 
Consider the possible encryption schemes (e.g. slide 23, or the onion of encryption on slide 33). What ciphertext schema do you recommend for an encrypted database stored using CryptDB?

\todo{State the ciphertext schema, e.g. slide 31 or slide 34, and justify your choice in terms of (i) security guarantee; (ii) storage cost; (iii) performance.}

\vspace{1cm}


\subsection*{(b) Non-sensitive/sensitive Attributes} [2 points]
If ClassID is not a sensitive attribute that requires no encryption, will you make any changes to your ciphertext schema?

\todo{State Yes/No and justify your choice.}
\vspace{1cm}



\newpage
\section*{Q2. Design Choice II}

Recall the edge table from Assignment 1: 
a table of edges (e.g. Table~\ref{tab:edge}) for an undirected graph of $n$ nodes. Each row in the table represents an edge $(v_i,v_j)$ in the graph, the node with smaller index stores in the first column (source) and the node with bigger index stores in  the second column (dest). 
Suppose this table is encrypted and stored on the cloud. The client is interested in querying the triangle count in the graph. 

\begin{table}[h]
    \centering
    \begin{tabular}{c|c}
    \hline
        source & dest  \\\hline 
         $v_1$ &  $v_2$ \\
         $v_1$ &  $v_3$ \\
         $v_2$  & $v_3$ \\
         $\vdots$ & $\vdots$\\
         $v_{n-1}$ & $v_n$ \\
         \hline 
    \end{tabular}
    \caption{Edge Table}
    \label{tab:edge}
\end{table}



\subsection*{(a) Strong Encryption} 
[5 points] If all the node ids in the Edge Table are encrypted with RND encryption, please discuss how to answer a triangle counting query  on this encrypted table stored on a untrusted cloud? 

\todo{Please state the assumptions (trusted client/hardware), the encryption protocols for the columns, and how the query could be answered, the performance overhead for the client and the server.}
\vspace{1cm}



\subsection*{(b) Weaker Encryption} 
[5 points] Please describe how to apply a weaker encryption such that the query can be processed more efficiently. Also, describe what is the security trade-off for the performance gain. 

\todo{Please state the assumptions (trusted client/hardware), the encryption protocols for the columns, and how the query could be answered, the performance overhead for the client and the server, and state the possible information leakage/problems}
\vspace{1cm}




\end{document}
