Let $E$ be the supersingular elliptic curve from Section 22.1.

1. Let $P\ne \infty$ and $Q\ne \infty$ be multiples of $P_0\text{.}$ Show that $\tilde{e}(P\text{,}Q)\ne 1\text{.}$ (Hint: Use the fact that $\tilde{e}(P_0\text{,}{P}_0)=\omega$ is a $q$th root of unity and that ${\omega }^x=1$ if and only if $x\equiv 0(\text{mod}q)\text{.}$)

2. Let $Q\ne \infty$ be a multiple of $P_0$ and let $P_1\text{,}{P}_2$ be multiples of $P_0\text{.}$ Show that if $\tilde{e}(P_1\text{,}Q)=\tilde{e}(P_2\text{,}Q)\text{,}$ then $P_1=P_2\text{.}$

Let $E$ be the supersingular elliptic curve from Section 22.1.

1. Show that

   $$\tilde{e}(aP\text{,}bQ)=\tilde{e}(P\text{,}Q{)}^{ab}$$

   for all points $P\text{,}Q$ that are multiples of $P_0\text{.}$

2. Show that

   $$\tilde{e}(P+Q\text{,}R)=\tilde{e}(P\text{,}R)\tilde{e}(Q\text{,}R)$$

   for all $P\text{,}Q\text{,}R$ that are multiples of $P_0\text{.}$

Let $E$ be the supersingular elliptic curve from Section 22.1. Suppose you have points $A\text{,}B$ on $E$ that are multiples of $P_0$ and are not equal to $\infty \text{.}$ Let $a$ and $b$ be two secret integers. Suppose you are given the points $aA$ and $bB\text{.}$ Find a way to use $\tilde{e}$ to decide whether or not $a\equiv b(\text{mod}q)\text{.}$

Let $p\equiv -1(\text{mod}3)$ be prime.

1. Show that there exists $d$ with $3d\equiv 1(\text{mod}p-1)\text{.}$

2. Show that if $a^3\equiv b(\text{mod}p)$ if and only if $a\equiv b^d(\text{mod}p)\text{.}$ This shows that every integer $\text{mod}p$ has a unique cube root.

3. Show that $y^2\equiv x^3+1(\text{mod}p)$ has exactly $p+1$ points (including the point $\infty$). (Hint: Apply part (b) to $y^2-1\text{.}$) (Remark: A curve mod $p$ whose number of points is congruent to 1 mod $p$ is called supersingular.)

(for those who know some group theory)

1. In the situation of Exercise 4, suppose that $p=6q-1$ with $q$ also prime. Show that there exists a point $P_0\ne \infty$ such that $q{P}_0=\infty \text{.}$

2. Let $Q=(2\text{,}3)\text{,}$ as in Exercise 9 in Chapter 21. Show that if $P\cancel{\in }\left\{\infty \text{,}Q\text{,}2Q\text{,}3Q\text{,}4Q\text{,}5Q\right\}\text{,}$ then $6P\ne \infty$ and $6P$ is a multiple of $P_0\text{.}$ (For simplicity, assume that $q>3\text{.}$)

Let $H_0$ be a hash function that takes a binary string of arbitrary length as input and then outputs an integer mod $p\text{.}$ Let $p=6q-1$ be prime with $q$ also prime. Show how to use $H_0$ to construct a hash function $H_1$ that takes a binary string of arbitrary length as input and outputs a point on the elliptic curve $y^2\equiv x^3+1(\text{mod}p)$ that is a multiple of the point $P_0$ of Section 22.1. (Hint: Use the technique of Exercise 4 to find $y\text{,}$ then $x\text{.}$ Then use Exercise 5(b).)

1. In the identity-based encryption system of Section 22.4, suppose Eve can compute $k$ such that $H_1$ ([email protected]) =k P0.$=k{P}_0\text{.}$$=k{P}_0\text{.}$. Show that Eve can compute $g^r$ and therefore read Bob’s messages.

2. In the BLS signature scheme of Section 22.5.1, suppose Eve can compute $k$ such that $H(m)=k{P}_0\text{.}$ Show that Eve can compute $S$ such that $(m\text{,}S)$ is a valid signed document.

3. In the identity-based signature scheme of Section 22.5.1, suppose Eve can compute $k$ such that $H_1(I{D}_{\text{Alice}})=k{P}_0\text{.}$ Show that Eve can compute $D_{\text{Alice}}$ and therefore forge Alice’s signature on documents.

4. In the keyword search scheme of Section 22.6, suppose Eve can compute $k$ such that $H_1(w)=k{P}_0\text{.}$ Show that Eve can compute $T_w$ and therefore find the occurrences of encrypted $w$ on documents.

Let $E$ and $P_0$ be as in Section 22.1. Show that an analogue of the Decision Diffie-Hellman problem can be solved for $E\text{.}$ Namely, if we are given $a{P}_0\text{,}b{P}_0\text{,}c{P}_0\text{,}$ show how we can decide whether $ab{P}_0=c{P}_0\text{.}$

Suppose you try to set up an identity-based cryptosystem as follows. Arthur chooses large primes $p$ and $q$ and forms $n=pq\text{,}$ which is made public. For each User, he converts the User’s identification $ID$ to a number $e_{\text{ User}}$ by some public method and then computes $d$ with $d{e}_{\text{ User}}\equiv 1(\text{mod}\varphi (n))\text{.}$ Arthur gives $d$ to the User. The integer $n$ is the same for all users. When Alice wants to send an email to Bob, she uses the public method to convert his email address to $e_{\text{ Bob}}$ and then uses this to encrypt messages with RSA. Bob knows $d\text{,}$ so he can decrypt. Explain why this system is not secure.

You are given a point $P\ne \infty$ on the curve $E$ of Section 22.1 and you are given a $q$th root of unity $\omega \text{.}$ Suppose you can solve discrete log problems for the $q$th roots of unity. That is, if $\alpha \ne 1$ and $\beta$ are $q$th roots of unity, you can find $k$ so that ${\alpha }^k=\beta \text{.}$ Show how to find a point $Q$ on $E$ with $\tilde{e}(Q\text{,}P)=\omega \text{.}$