Name:
UID:
Collaborators:
CS/ECE 498 AC 3/4 Fall 2020 – Problem Set 3
Due Monday, November 9, 6pm (Submit via Gradescope)
• Please write your name, UID, and the names
of anyone you collaborated with in the spaces
provided and attach this sheet to the front of
your solutions.
• Please write your answers in a neat and
readable hand-writing. Each answer should be
on a separate page. There are plenty of extra
spaces, you do not need to fill them all. You
should expect answers to be fairly short.
• Always explain your answers. When a proof is
requested, you should provide a rigorous
proof. This usually involves a reduction.
• 10% of the points will be given if your answer
is “I don’t know”. However, if instead of
writing “I don’t know” you write things that
do not make any sense, no points will be given.
• The homework is expected to take several (≥ 8)
hours. Start early.
Honor Code (READ CAREFULLY). When submitting my solution set, I agree to follow the
following rules concerning homework and problem sets:
• When formulating a high-level approach to the problems I am given, I am allowed to ask the
TA for help, and to collaborate with my fellow UIUC students, and I will acknowledge in
writing the names of every student that I collaborated with on my work. I understand that
collaboration and study groups are encouraged. My grade will not suffer if I acknowledge
help from other students, but may suffer if I collaborate without explicit acknowledgement.
• When writing solutions or code, I will do so entirely on my own, without the help of any
other person or any other students notes or solutions or code. I will not discuss
implementation details with other students.
• I will not seek out or make use of any outside source of information, except sources explicitly
linked to in the exam. Outside sources include but are not limited to: any information found
online (except on the course website or linked in the homework), other textbooks or articles. If
necessary, I may ask for permission in advance from the TA to deviate from this rule. The
textbook for the course (Boneh-Shoup) and my own notes are excepted from this rule.
• I understand that I may be suspended from UIUC for violating this honor code.
• If I have difficulty with understanding lectures or the book due to difficulty with the English
language, or if someone asks for my help because of difficulties with language, I will discuss
the situation with the professor or TA as soon as possible, to ensure that the honor code is
upheld. I will follow these rules in good faith, and not try to find loopholes that violate the
spirit of the rules. If I am unsure about what the spirit of the rule is or what a rule means, then
I will ask for clarification from the professor or TA, and I will adhere to rules as clarified.
1
1. Verifiable Random Functions (25 points). Let G be a cyclic group of prime order q generated
by g ∈ G. Let F be a PRF such that F (k,m) := H(m)k for k ∈ Zq,m ∈M, where H : M → G is
a hash function modeled as a random oracle.
(a) (5 points). Prove that F is a PRF under the DDH assumption (when H is modeled as a
random oracle).
(b) A verifiable random function (VRF) is a PRF, with the additional property that anyone
can verify that the PRF value at a given point is computed correctly. Specifically, a VRF
defined over (X, Y ) is a triple of efficient algorithms (G′, F ′, V ′), where algorithm G′
outputs a public key pk and a secret key sk. Algorithm F ′ is invoked as (y, pi)← F ′(sk, x)
where x ∈ X, y ∈ Y , and where pi is a validity proof. Algorithm V ′ is invoked as
V ′(pk, x, y, pi), and outputs accept or reject. We say that y is the value of the VRF at the
point x, and pi is the validity proof for y. The VRF must satisfy the following properties:
• Correctness. For all (pk, sk) output by G′, and all x ∈ X , if (y, pi)← F ′(sk, x) then
V ′(pk, x, y, pi) = accept.
• Uniqueness. For all pk and every x ∈ X , only a single y ∈ Y can have a valid proof
pi. More precisely, if V ′(pk, x, y, pi) = V ′(pk, x, y0, pi0) = accept then y = y0. This
ensures that even with the secret key, an adversary cannot lie about the value of the
VRF at the point x.
• Security. VRF security is defined using two experiments, analogous to the
characterization of a PRF. In both experiments, the challenger generates (pk, sk)
using G′, and gives pk to the adversary. The adversary then makes a number of
function queries and a single test query (with any number of function queries before
and after the test query). In a function query, the adversary submits x ∈ X and
obtains (y, pi)← F ′(sk, x). In the test query, the adversary submits x˜ ∈ X : in one
experiment, he obtains y˜, where (y˜, p˜i)← F ′(sk, x˜); in the other experiment, he
obtains a random y˜ ∈ Y . The test point x˜ is not allowed among the function queries.
The VRF is secure if the adversary cannot distinguish the two experiments.
We will try to build a VRF using the PRF F discussed in the previous item. Let Π be the
Chaum-Pedersen protocol, and let Φ denote the non-interactive version of this protocol
(with negligible soundness error) in the random oracle model, as discussed in class.
Our VRF is (G′, F ′, V ′), which is defined over (M,G). G′ chooses k ∈ Zq at random, k is
the secret key, and gk is the public key; F ′(k,m) := (y, pi), where y = F (k,m) = H(m)k
and pi is a proof, generated using Φ, that (H(m), gk, H(m)k) is a DH-triple; V ′(gk,m, y, pi)
checks that (H(m), gk, y) is a DH-triple by verifying the proof pi using Φ.
i. (5 points). Describe the functions F ′ and V ′ in detail.
ii. (10 points). Using the ZK property for Φ, show that if we model both H and H ′ as
random oracles, then under the DDH assumption for G, the VRF (G′, F ′, V ′) satisfies
the VRF security property defined above.
iii. (5 points). This VRF does not satisfy the uniqueness property defined above.
Nevertheless, it does satisfy a weaker, but still useful property. Using the soundness
property for Φ, show that it is infeasible for an adversary to come up with a triple
(m, y, pi) such that such that V ′(gk,m, y, pi) = accept, yet y 6= F (k,m).
Note: In parts (a), (b) (ii) and (b) (iii), provide explicit reductions.
2
(Extra Page for Solution)
3
(Extra Page for Solution)
4
(Extra Page for Solution)
5
2. Schnorr Signatures with Related Keys (15 points.) Let vk = gx ∈ G be a random verification key for
the non-interactive Schnorr signature/identification scheme, as discussed in the lecture. Define n
related verification keys vk1, . . . , vkn by setting vki = (vk) · gi ∈ G for i = {1, 2, . . . , n}.
(a) (5 points). Show that the scheme we saw in class is insecure w.r.t. related verification keys as
described above. In particular, show that an adversary that is given vk1, . . . , vkn generated as
above, and a signature on message m with respect to vkj for some j ∈ [n] will be able to construct
a signature on m w.r.t. a different vki for some i 6= j.
(b) (10 points). Now suppose we modify the identification scheme so that for any verification key
vki, instead of computing challenge h = H(m,R), h is computed as H(m,R, vki). Show that this
scheme is multi-key secure with respect to the n verification keys vk1, . . . , vkn.
That is, consider an adversary that is given vk and can issue signing queries to all n verification
keys. Each query is a pair (vk(j),mj), for j = 1, . . . , Q, and the response is a signature on mj with
respect to vk(j) ∈ {vk1, . . . , vkn}. Show that the adversary cannot produce, with non-negligible
probability, an existential forgery (vk,m, σ) where vk ∈ {vk1, . . . , vkn} and (vk,m) is not one of
the signing queries. Your security argument should be based on the hardness of computing
discrete-log in G, where the hash function used in the scheme is modeled as a random oracle.
6
(Extra Page for Solution)
7
(Extra Page for Solution)
8
3. Revisiting conference key setup/multi-party key exchange (20 points). Parties A1, A2 and A3 wish to
generate a secret conference key. All parties should know the conference key, but an eavesdropper
should not be able to output the key. They decide to use bilinear maps: there is a public generator g of a
group G1 and q = |G1|. Suppose there exists a bilinear map e : G1 ×G1 → GT such that
e(ga, gb) = e(g, g)ab, where a, b ∈ {0, 1, . . . , q − 1} and e(g, g) is a generator of GT .
(a) (8 points). Consider the following two computational assumptions:
• Assumption 1: The distributions D0 and D1 are indistinguishable where
– D0 = (g, ga, gb, gc, gabc) where a, b, c← {0, 1, . . . , q − 1}.
– D1 = (g, ga, gb, gc, gd) where a, b, c, d← {0, 1, . . . , q − 1}.
• Assumption 2: The distributions E0 and E1 are indistinguishable where
– E0 = (g, ga, gb, gc, e(g, g)abc) where a, b, c← {0, 1, . . . , q − 1}.
– E1 = (g, ga, gb, gc, e(g, g)d) where a, b, c, d← {0, 1, . . . , q − 1}.
Show that Assumption 1 implies Assumption 2.
(b) (12 points). Devise a non-interactive key exchange scheme, where parties (A1, A2, A3) need only
simultaneously broadcast a single message to each other. After this point, (A1, A2, A3) can derive
a shared secret key that is known only to these three parties.
Under Assumption 1, prove that an eavesdropper that observes the messages sent by (A1, A2, A3)
cannot guess the secret key. Namely, show that if there exists an efficient algorithm A that given
the messages sent by (A1, A2, A3) outputs the shared secret key, then there also exists an efficient
algorithm B that breaks Assumption 1.
9
(Extra Page for Solution)
10
(Extra Page for Solution)
Feedback. Did you find this homework assignment too easy/too hard/just right? How is the
pace of the course so far? Please add any feedback about lectures and/or homework that would
help improve the course.
11

欢迎咨询51作业君