
\documentclass[11pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{color}


%%%%%%%%%%%%%%% MACROS specific to this PSET %%%%%%%%%%%%%%%%%%%%%%


\newcommand{\lat}{\mathcal{L}}
\newcommand{\basis}{\mathbf{B}}

\newcommand{\vol}{\mathsf{vol}}
\newcommand{\sh}{\lambda_1}
%\newcommand{\det}{\mathsf{det}}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}

%%%%%%%%% Vectors and Matrices

\newcommand{\vecv}{\mathbf{v}}
\newcommand{\vecb}{\mathbf{b}}
\newcommand{\vecbt}{\widetilde{\vecb}}
\newcommand{\vecs}{\mathbf{s}}
\newcommand{\vect}{\mathbf{t}}
\newcommand{\vecy}{\mathbf{y}}

\newcommand{\matB}{\mathbf{B}}

\newcommand{\poly}{\mathsf{poly}}
\newcommand{\Span}{\mathsf{Span}}
\newcommand{\dist}{\mathsf{dist}}


\def\rot{\mathsf{Rot}}
\def\bydef{\stackrel{\Delta}{=}}


\def\matA{\mathbf{A}}
\def\vecy{\mathbf{y}}
\def\vece{\mathbf{e}}
\def\vecz{\mathbf{z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\title{MAT 301 Problem Set 5\\{\large [Posted: March 25, 2013. Due: noon on April 3 (\textbf{Wednesday}), 2013. Worth: 100 points]}}
\author{}
\date{}

\begin{document}
\maketitle
%\input{pset-preamble.tex}

%\lecture{1}{Vinod Vaikuntanathan}{September 13, 2011}{October 3, 2011}


\def\sslwe{\mathsf{ssLWE}}
\def\lwe{\mathsf{LWE}}

% Macros for vectors
\def\veca{\mathbf{a}}
\def\vecs{\mathbf{s}}
\def\vecc{\mathbf{c}}

\vspace*{-0.7in}

\medskip\noindent

\begin{enumerate}


\item \textbf{Elliptic Curves (50 points)}

\begin{enumerate}

\item Let $E$ be the elliptic curve over the rationals $\mathbb{Q}$ defined by the equation $Y^2 = X^3 - 2X + 4$ and let $P = (0,2)$ and 
$Q = (3,-5)$. (Check that $P$ and $Q$ are actually on the curve). 

Compute $P \oplus Q$, $2P$ and $2Q$.

\item Let $p$ be a prime satisfying $p = 2 \pmod{3}$. Let $E$ be the elliptic curve over $\mathbb{F}_p$ defined by $y^2 = x^3 + 1 \pmod{p}$.
How many points does $E$ have, and why?


\end{enumerate}


\item \textbf{Secret Sharing (50 points)}
Suppose that the teaching staff of a course consists of three professors and two TAs.
The solutions to problem sets in the course are encrypted with a key $K$ that is shared
between the five staff members. Your goal is to come up with a method of secret-sharing the
key so that

\begin{enumerate}
\item \underline{all the three professors together}, or

\item \underline{both the TAs together}, or

\item \underline{any TA together with any professor}
\end{enumerate}

should be able to access the solutions. No other combination of staff members should be able to lay their hands on
it (for example, if two professors come together, they should have no idea what the key $K$ is, and therefore, they
will not be able to decrypt and figure out the solutions).


Assume that the key is a number in $\mathbb{Z}_q$ for some prime number $q$.
\end{enumerate}

\end{document}
