Homework 6: Public key, RSA/Dlog and lattices

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 \({\mathbb{Z}}^*_m\)) if \(ed = 1 \pmod{|{\mathbb{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{\mathbb{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\).
   1. (10 points) Prove that given two inputs \(x \neq x' \in {\mathbb{Z}}^*_m\) such that \(f_0(x)=f_1(x')\), one can find \(y^{1/e} \pmod{m}\).
   2. (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 \({\{0,1\}}^\ell\) to \({\mathbb{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 {\{0,1\}}^\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:{\{0,1\}}^n\rightarrow{\{0,1\}}^{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 \({\{0,1\}}^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{\{0,1\}},i\in[\ell]}\) while the public verification key is the tuple \(( y^b_i )_{b\in{\{0,1\}},i\in[\ell]}\) where \(y^b_i = PRG(x_i^b)\)

   • Signing: To sign a message \(m\in {\{0,1\}}^\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{\{0,1\}},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 \({\mathbb{G}}\) be a cyclic group. Pick generator \(g\) for \({\mathbb{G}}\) and \(a\in \{0,\ldots,|{\mathbb{G}}|-1\}\) and let \(h=g^a\). Pick \(H:{\{0,1\}}^\ell\times \{0,\ldots,|{\mathbb{G}}|-1\} {\mathbb{G}}\rightarrow \{0,\ldots,|{\mathbb{G}}|-1\}\) and \(F:{\mathbb{G}}\rightarrow\{0,\ldots,|{\mathbb{G}}|-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 \(|{\mathbb{G}}|\). 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}\).
   1. (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 \({\mathbb{G}}\). See footnote for hint¹
   2. (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 \({\mathbb{G}}\).

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{\mathbb{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{\{0,1\}}\) given the key \((A,y)\), pick \(w\in{\{0,1\}}^m\) and output \(2w^\top A, 2{\langle w,y \rangle}+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 \(|{\langle a,x \rangle}-\sigma|\) is even. (Instead of asking this to be smaller than \(q/10\).)