Let be the supersingular elliptic curve from Section 22.1.
Let and be multiples of Show that (Hint: Use the fact that is a th root of unity and that if and only if )
Let be a multiple of and let be multiples of Show that if then
Let be the supersingular elliptic curve from Section 22.1.
Show that
for all points that are multiples of
Show that
for all that are multiples of
Let be the supersingular elliptic curve from Section 22.1. Suppose you have points on that are multiples of and are not equal to Let and be two secret integers. Suppose you are given the points and Find a way to use to decide whether or not
Let be prime.
Show that there exists with
Show that if if and only if This shows that every integer has a unique cube root.
Show that has exactly points (including the point ). (Hint: Apply part (b) to ) (Remark: A curve mod whose number of points is congruent to 1 mod is called supersingular.)
(for those who know some group theory)
In the situation of Exercise 4, suppose that with also prime. Show that there exists a point such that
Let as in Exercise 9 in Chapter 21. Show that if then and is a multiple of (For simplicity, assume that )
Let be a hash function that takes a binary string of arbitrary length as input and then outputs an integer mod Let be prime with also prime. Show how to use to construct a hash function that takes a binary string of arbitrary length as input and outputs a point on the elliptic curve that is a multiple of the point of Section 22.1. (Hint: Use the technique of Exercise 4 to find then Then use Exercise 5(b).)
In the identity-based encryption system of Section 22.4, suppose Eve can compute such that ([email protected])
. Show that Eve can compute and therefore read Bob’s messages.
In the BLS signature scheme of Section 22.5.1, suppose Eve can compute such that Show that Eve can compute such that is a valid signed document.
In the identity-based signature scheme of Section 22.5.1, suppose Eve can compute such that Show that Eve can compute and therefore forge Alice’s signature on documents.
In the keyword search scheme of Section 22.6, suppose Eve can compute such that Show that Eve can compute and therefore find the occurrences of encrypted on documents.
Let and be as in Section 22.1. Show that an analogue of the Decision Diffie-Hellman problem can be solved for Namely, if we are given show how we can decide whether
Suppose you try to set up an identity-based cryptosystem as follows. Arthur chooses large primes and and forms which is made public. For each User, he converts the User’s identification to a number by some public method and then computes with Arthur gives to the User. The integer 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 and then uses this to encrypt messages with RSA. Bob knows so he can decrypt. Explain why this system is not secure.
You are given a point on the curve of Section 22.1 and you are given a th root of unity Suppose you can solve discrete log problems for the th roots of unity. That is, if and are th roots of unity, you can find so that Show how to find a point on with