% Homework 6: Public key, RSA/Dlog and lattices

<!--- ~ MathDefs   --->

\newcommand{\zo}{\{0,1\}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\getsr}{\leftarrow_R\;}
\newcommand{\Gp}{\mathbb{G}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
<!--- ~  --->

### Total of 120 points

1. (KL Ex 8.10, 15 points) Prove that for every $x\in \{0,\ldots, m-1\}$ (even if $x$ is not in $\Z^*_m$) if $ed = 1 \pmod{|\Z^*_m|}$ then $(x^e)^d = x \pmod{m}$.

2. (KL Ex 8.20, 25 points) Let $m,e$ be as in the RSA problem, let $y\in\Z^*_m$, and let $f_0$ be the RSA function $f_0(x)=x^e$ and $f_1$ be its "shifted by $y$" variant $f_1(x)=y\cdot x^e$.
     a. (10 points) Prove that given two inputs $x \neq x' \in \Z^*_m$ such that $f_0(x)=f_1(x')$, one can find $y^{1/e} \pmod{m}$.
     b. (15 points) Conclude that $\ell = 10\log m$, if we pick $m,e,y$ as above and let $H_{m,e,y}(z_1,\ldots,z_\ell)$ be defined as $f_{z_1}(f_{z_2}(\cdots (f_{z_{\ell}}(1))\cdots))$ then this collection is a  _collision resistant hash family_ mapping $\zo^\ell$ to $\Z^*_m$ if the RSA function is hard to invert. That is, if there is an algorithm that given a random hash function $H$ from this collection finds $z\neq z' \in \zo^\ell$ such that $H(z)=H(z')$ then there is an algorithm to invert the RSA function.

3. (One time signatures, 25 points) As I mentioned it is in fact possible to get digital signatures based on only private key cryptography. In this exercise we will show a baby version of this. We say that a signature scheme $(G,S,V)$ is a _one time signature scheme_ if it satisfies the security definition of digital signatures (with a public verification key) with the restriction that the adversary is only allowed to make a _single query_ $m$ to the signing oracle, and needs to output a signature on a messahe $m' \neq m$. Let $PRG:\zo^n\rightarrow\zo^{2n}$ be a pseudorandom generator. Prove that the following scheme is a secure one-time signature scheme for messages of length $\ell$:

    * _Key generation_: Pick $2\ell$ independent random strings in $\zo^n$ which we'll denote by $x^0_1,\ldots,x^0_\ell,x^1_1,\ldots,x^1_\ell$. The secret signing key is the tuple $( x^b_i )_{b\in\zo,i\in[\ell]}$  while the public verification key is the tuple $( y^b_i )_{b\in\zo,i\in[\ell]}$   where $y^b_i = PRG(x_i^b)$

    * _Signing_: To sign a message $m\in \zo^\ell$, output the $\ell$-tuple $(x^{m_1}_1,\ldots,x^{m_\ell}_\ell)$.

    * _Verification_: To verify a message $m$ w.r.t. signature $(x'_1,\ldots,x'_\ell)$ and public key $( y^b_i )_{b\in\zo,i\in[\ell]}$, check that $PRG(x'_i)=y^{m_i}_i$ for all $i\in[\ell]$.

4. (30 points) Consider the following variant of the DSA signature scheme:
    * _Key generation:_ Let $\Gp$ be a cyclic group. Pick generator $g$ for $\Gp$ and $a\in \{0,\ldots,|\Gp|-1\}$ and let $h=g^a$. Pick $H:\zo^\ell\times \{0,\ldots,|\Gp|-1\} \Gp\rightarrow \{0,\ldots,|\Gp|-1\}$ and $F:\Gp\rightarrow\{0,\ldots,|\Gp|-1\}$ to be some  functions that we consider as random oracles. The public key is $(g,h)$  (as well as the functions $H,F$) and secret key is $a$.
    * _Signature:_ To sign a message $m$, pick $b$ at random,  let $f=g^b$, let $c=F(f)$ and $d=H(m,c)$  and then let $s= b^{-1}[d+a\cdot c]$ where all computation is done modulo $|\Gp|$. The signature is $(f,s)$.
    * _Verification:_ To verify a signature $(f,s)$ on a message $m$, compute $c=F(f)$ and $d=H(m,c)$  and then check that $s\neq 0$ and $f^s=g^{d}h^{c}$.

    a. (20 points) Prove that this is a secure one-time signature scheme in the random oracle model, assuming the difficulty of the discrete logarithm problem in $\Gp$. See footnote for hint[^hintDSA]
    b. (10 points) Prove that this is a secure (many times) signature scheme in the random oracle model, assuming the difficulty of the discrete logarithm problem in $\Gp$.

[^hintDSA]: You need to design a reduction that takes $h=g^a$ and returns $a$ using "in its belly" an adversary for the signature scheme. You can use $h$ as the public key. The scheme ensures that to produce a valid signature the adversary will first need to ask $F$ on the query $f$, and then ask $H$ on the query $m,F(f)$. The idea is that once an adversary makes a query $f$ to the oracle $F$, then they have "committed" to the value $b$ such that $g^b=f$ even if they didn't disclose it. Now, if they are able to successfully sign the message $m$ with decent probability over the output of $H(m,c)$ then we'll be able to find two different responses $d \neq d'$ for which they can sign successfully. This will yield two linearly independent equations on the two unknowns $b$ and $a$.

5.  (25 points) Prove that under the LWE assumption, the following variant of our lattice based encryption scheme is secure: (you can use the assumption of security of the scheme presented in class if it helps.)

     * _Parameters:_ Let $\delta(n)=1/n^4$ and let $q=poly(n)$ be a prime such that LWE holds w.r.t. $q,\delta$. We let $m = n^2\log q$. _(Same as before)_

     * _Key generation:_ Pick $x\in\Z_q^n$. The private key is $x$ and the public key is $(A,y)$ with $y=Ax+e$ with $e$ a $\delta$-noise vector and $A$ a random $m\times n$ matrix. _(Same as before)_

     * _Encrypt:_ To encrypt $b\in\zo$ given the key $(A,y)$, pick $w\in\zo^m$ and output $2w^\top A, 2\iprod{w,y}+b$ (all modulo $q$ of course). The difference is that instead of adding either $0$ or $q/2$, we add either $0$ or $1$, but multiply this by $2$ so the result would be _even_ or _odd_ as needed.

     * _Decrypt:_ To decrypt $(a,\sigma)$, output $0$ iff $|\iprod{a,x}-\sigma|$ is even. (Instead of asking this to be smaller than $q/10$.)