%me=0 student solutions, me=1 - my solutions, me=2 - assignment
\def\me{0}
\def\num{2}  %homework number
\def\due{February 19, 2026}  %due date
\def\course{COMS BC3262} %course name
\def\name{**** INSERT YOUR NAME HERE ****}
%
\iffalse
INSTRUCTIONS: replace # by the homework number.
(if this is not ps#.tex, use the right file name)

Clip out the ********* INSERT HERE ********* bits below and insert
appropriate TeX code.  Once you are done with your file, run

``latex ps#.tex''

from a UNIX prompt.  If your LaTeX code is clean, the latex will exit
back to a prompt.  To see intermediate results, type

``xdvi ps#.dvi'' (from UNIX prompt)
``yap ps#.dvi'' (if using MikTex in Windows)

after compilation. Once you are done, run

``dvips ps#.dvi''

which should print your file to the nearest printer.  There will be
residual files called ps#.log, ps#.aux, and ps#.dvi.  All these can be
deleted, but do not delete ps1.tex. To generate postscript file ps#.ps,
run

``dvips -o ps#.ps ps#.dvi''

I assume you know how to print .ps files (``lpr -Pprinter ps#.ps'')
\fi
%
\documentclass[11pt]{article}
\usepackage{tikz}
\usepackage{amsfonts}
\usepackage{latexsym}

\usetikzlibrary{automata,positioning}
\setlength{\oddsidemargin}{.0in}
\setlength{\evensidemargin}{.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\handout}[5]{
	\renewcommand{\thepage}{#1, Page \arabic{page}}
	\noindent
	\begin{center}
		\framebox{
			\vbox{
				\hbox to 5.78in { {\bf \course} \hfill #2 }
				\vspace{4mm}
				\hbox to 5.78in { {\Large \hfill #5  \hfill} }
				\vspace{2mm}
				\hbox to 5.78in { {\it #3 \hfill #4} }
			}
		}
	\end{center}
	\vspace*{4mm}
}

\newcounter{pppp}
\newcommand{\prob}{\arabic{pppp}}  %problem number
\newcommand{\increase}{\addtocounter{pppp}{1}}  %problem number

\newcommand{\newproblem}[2]{\increase
	\section*{Problem \prob~(#1) \hfill {#2}}}


\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\def\qed{\hspace*{\fill}
	\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newenvironment{solution}{\color{purple}\begin{trivlist}\item[]{\bf Solution:}}
	{\qed \end{trivlist}}
\newenvironment{solsketch}{\color{purple}\begin{trivlist}\item[]{\bf Solution Sketch:}}
	{\qed \end{trivlist}}
\newenvironment{code}{\begin{tabbing}
		12345\=12345\=12345\=12345\=12345\=12345\=12345\=12345\= \kill }
	{\end{tabbing}}

\newcommand{\eqref}[1]{Equation~(\ref{eq:#1})}

\newcommand{\hint}[1]{({\bf Hint}: {#1})}
%Put more macros here, as needed.
\newcommand{\room}{\medskip\ni}
\newcommand{\brak}[1]{\langle #1 \rangle}
\newcommand{\bit}{\{0,1\}}
\newcommand{\zo}{\{0,1\}}

\newcommand {\eps} {\varepsilon}

\newcommand{\nin}{\not\in}
\newcommand{\set}[1]{\{#1\}}
\renewcommand{\ni}{\noindent}
\renewcommand{\gets}{\leftarrow}
\renewcommand{\to}{\rightarrow}
\newcommand{\assign}{:=}

\newcommand{\AND}{\wedge}
\newcommand{\OR}{\vee}

\newcommand{\For}{\mbox{\bf For }}
\newcommand{\To}{\mbox{\bf to }}
\newcommand{\Do}{\mbox{\bf Do }}
\newcommand{\If}{\mbox{\bf If }}
\newcommand{\Then}{\mbox{\bf Then }}
\newcommand{\Else}{\mbox{\bf Else }}
\newcommand{\While}{\mbox{\bf While }}
\newcommand{\Repeat}{\mbox{\bf Repeat }}
\newcommand{\Until}{\mbox{\bf Until }}
\newcommand{\Return}{\mbox{\bf Return }}

\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Enc}{\mathsf{Enc}}
\newcommand{\Dec}{\mathsf{Dec}}
\newcommand{\MAC}{\mathsf{MAC}}

\newcommand {\A} {\mathcal{A}}
\newcommand {\K} {\mathcal{K}}
\newcommand {\C} {\mathcal{C}}
\newcommand {\D} {\mathcal{D}}
\newcommand {\M} {\mathcal{M}}
\newcommand {\T} {\mathcal{T}}
\newcommand {\Y} {\mathcal{Y}}

\newcommand {\ZZ} {\mathbb{Z}}
\newcommand {\NN} {\mathbb{N}}
\newcommand {\RR} {\mathbb{R}}

\newcommand{\Adv}{\mathcal{A}}


\usepackage{enumitem}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\newtheorem{lemma}{Lemma}

\begin{document}
	
	\ifnum\me=0
	\handout{PS\num}{\today}{Name: **** INSERT YOUR NAME HERE ****}{Due:
		\due}{Solutions to Problem Set \num}
	
	I collaborated with *********** INSERT COLLABORATORS HERE (INDICATING
	SPECIFIC PROBLEMS) *************.
	\fi
	\ifnum\me=1
	\handout{PS\num}{\today}{Instructor: Eysa Lee}{Due: \due}{Solutions
		for Problem Set \num}
	\fi
	\ifnum\me=2
	\handout{PS\num}{\today}{Instructor: Eysa Lee}{Due: \due}{Problem
		Set \num}
	\fi

\ifnum\me=2
\paragraph{Guidelines.} Solutions will be graded for correctness and clarity.
If you do not know how to solve a problem, you may write \textbf{``I don't know how to do this''} to receive $20\%$ credit for any problem not marked as extra credit.
In your proofs, justify every step and, if needed, write down definitions/theorems that were presented in class and that you rely on. When refuting a claim, provide a counterexample and show that it does not satisfy the required definition.


\paragraph{Collaboration.} You are allowed to discuss problems with other students in the class. However, you should write up your solutions on your own and may not read or copy the solutions of others. You should try solving each problem on your own before discussing with others. \textbf{If you work with others on a problem, you must note with whom you discussed the problem at the beginning of your solution write-up.} For example, ``I discussed Problem 1 with Alice and Bob and Problem 2 with Carol.''
You may not use external resources apart from the textbooks.

\paragraph{Generative AI Policy.} The use of generative AI for anything related to assignments is prohibited in this class. \textbf{It is always prohibited to input any substantial portion of any assignment into any AI resource.} It is also always forbidden to incorporate any substantive portion of an AI resource's output into your answers, even if you paraphrase it or rewrite it in your own words.

\fi

\newproblem{PRG or Not?}{15 points + 5 Extra Credit}
Let $G:\bit^n\to\bit^{2n}$ be a PRG. 
Each sub-problem is worth 5 points, and for each of these sub-problems you must determine whether the proposed constructions of $G'$ are \emph{necessarily} PRGs or not. 
If yes, give a proof that $G'$ \emph{must} be a PRG. Otherwise, give a counterexample. For a counterexample, you should show that if PRGs exist there is some function $G$ which is a PRG but $G'$ is not\footnote{In some counterexamples it may be possible to write a distinguisher that works for \emph{any} PRG $G$, but in others, you may need to write a distinguisher that works only for some \emph{specific} $G$. In the latter example, provide a description of the specific $G$ and a proof that it is a PRG. If necessary, you can also assume there exists some other PRG $G''$ and use $G''$ to construct the specific $G$ you require to disprove $G'$.}.

\begin{enumerate}
\item $G'(s) = G(s||0)$
\item $G'(s) = G(s \oplus {1^{n}})$
\item $G'(s) = G(s)||G(s \oplus (0^{n-1}||1))$

(i.e., $G$ is run twice, with the second one flipping the last bit of $s$. These two outputs are appended to each other.)
\item $G'(s) = G(s)\oplus(0^n||s)$
\end{enumerate}

\newproblem{EAV-Secure but not CPA-Secure}{10 pts}

Let $F:\bit^n\times\bit^n\to\bit^n$ be a pseudorandom function. Consider the following private-key encryption scheme $\Pi = (\Gen,\Enc,\Dec)$:
\begin{itemize}
    \item $\Gen(1^n)$: Output $k \gets \bit^n$
    \item $\Enc(k,m)$: On input $m\in\bit^n$, output $c = m \oplus F_k(0)$
    \item $\Dec(k,c)$: On input $c \in \bit^n$, output $m = c \oplus F_k(0)$
\end{itemize}
Prove the following two statements about $\Pi$:
\begin{enumerate}
\item $\Pi$ has indistinguishable encryptions in the presence of an eavesdropper.
\item  $\Pi$ is not CPA-secure.
\end{enumerate}

\newproblem{EAV-Security?}{ 5 pts}
Consider the following encryption scheme $\Pi = (\Gen, \Enc,\Dec)$ with key space $\K = \bit^n$ and message/ciphertext space $\M=\C = \bit^{2n}$:
\begin{itemize}
    \item $\Gen(1^n)$: Output $k \gets \bit^n$.
	\item $\Enc(k,m)$: Split the message $m \in \bit^{2n}$ into a ``left half'' $m_0 \in \bit^n$ and a ``right half'' $m_1 \in \bit^n$ so that $m=m_0||m_1$ where $||$ denotes string concatenation. Compute $c_0 = k \oplus m_0$, $c_1 = k\oplus m_1$, 
    and output $c = c_0||c_1$. 
	 \item $\Dec(k,c)$: Parse the ciphertext as $c=c_0||c_1$, and output $m = (c_0 \oplus k)||(c_1 \oplus k)$. 
\end{itemize}
Show that $\Pi$ is \emph{not} EAV-secure. 

\newproblem{PRF or Not?}{10 pts}
Let $F$ be a PRF family with $n$-bit key, $n$-bit input and $n$-bit output.
\begin{enumerate}
	\item Show that $F'_{k}(x) = F_{k}(x)||F_{k}(x \oplus 1^n)$ can never be a secure PRF.
	\item Show that $F'_k(x) =  F_k(x) \oplus x$ is always a secure a PRF.  
\end{enumerate}

\end{document}


