Sample Exam COMP6453

Monday 12 August 2024

Maximum Marks: 100

If you have not used the CSE lab machines this term, we strongly recommend that you familiarise yourself with the lab machines before the day of the exam by coming in to the lab.

Exam Rules and Conditions

Please read these rules carefully. Note that deliberate violation of exam conditions will be referred to Student Integrity as serious misconduct.

Duration

• There will be 10 minutes of reading time. You can start reading when your supervisor tells you to do so.

• Your supervisor will tell you when you can start working.

• You have 3 hours* to work on the exam. You must stop working once your supervisor tells you to do so.

• * Students with extra exam time approved by Equitable Learning Services (ELS) will be given extra time to complete the exam.

  Communication

• You are not permitted to communicate with anyone during this exam except the exam supervisors.

• If you have any questions during the exam, you must raise your hand and ask a supervisor.

  Resources

• The Internet will be unavailable during the exam. You will also be unable to access the files in your normal CSE account.

• You have been provided with the lecture slides from this term. You may freely use any of these resources in your own answers.

  Special Consideration

• By starting this exam you have acknowledged that you are fit to sit the exam and cannot apply for Special Consideration for issues that existed prior to the exam.

• If a circumstance arises during the exam that prevents you from completing the exam, please raise your hand and talk to a supervisor. After the exam, email [email protected] immediately and apply for special consideration within 3 days of the exam, preferably as soon as possible.

  Submission

• See the submission instructions under each question.

• You can submit multiple times. Only your last submission will be marked.

• Do not wait until just before the deadline to submit all your answers. Submit each question as soon as you finish working on it or submit incrementally throughout the exam.

  Short-Answer Questions

• Justifications/explanations are only required when asked by the question.

  Marking

• Partial marks will be given for correct approach to problems.

Admin

Marks Contributes to

Total Marks 100

Total number of questions 8 (note: the real exam may have a different number of questions)

Write your answers for this question in q1.txt.

Solve the following questions showing all the steps of computation.

1. (3 Marks)

   Compute 220 mod 13

2. (2 Marks)

   Compute gcd(123, 276)

3. (5 Marks)

   Compute multiplicative Inverse of 357 mod 1234

4. (5 Marks)

Solve the following system of equations for x:

x ≡ 12 (mod 25)

x ≡ 9 (mod 26)

x ≡ 23 (mod 27)

Write your answers for this question in q2.txt.

For shift, mono-alphabetic substitution, and Vigenere ciphers prove the following:

1. (3 Marks)

   Prove that if only a single character is encrypted, then the shift cipher is perfectly secret.

2. (5 marks)

   What is the largest message space M for which the mono-alphabetic substitution cipher provides perfect secrecy?

3. (2 Marks)

Prove that the Vigenere cipher using (fixed) period t is perfectly secret when used to encrypt messages of length t.

Write your answers for this question in q3.txt.

Consider a stateful variant of CBC-mode encryption where the sender simply increments the IV by 1 each time a message is encrypted (rather than choosing IV at random each time). Show that the resulting scheme is not CPA-secure.

Write your answers for this question in q4.txt.

1. (3 Marks) What are the challenges in storing data in untrusted servers, for example clouds?

2. (10 Marks) I have stored a large file F in an untrusted server. I do not have a local copy on my disk. How can I verify the integrity of F without downloading the whole file?

3. (7 Marks) What is the communication and computation complexity of the procedure?

Write your answers for this question in q5.txt. Consider the following key-exchange protocol:

1. Alice chooses uniform k, r ∈ {0, 1}n, and sends s := k ⊕ r to Bob.

2. Bob chooses uniform t ∈ {0, 1}n, and sends u := s ⊕ t to Alice.

3. Alice computes w := u ⊕ r and sends w to Bob.

4. Alice outputs k and Bob outputs w ⊕ t. Answer the following two questions:

   1. (5 Marks)

      Show that Alice and Bob output the same key.

   2. (5 Marks)

Analyze the security of the scheme (i.e., either prove its security or show a concrete attack).

Write your answers for this question in q6.txt.

Consider the Protocol below. The signatures does not contain the intended receiver.

Each user U will have a signature scheme with a signing algorithm sigU and a verification algorithm verU . The TA also has a signature scheme with a public verification algorithm verT A. Each user U has a certificate Cert(U ) = (ID(U ), verU , sigT A(ID(U ), verU )), ID(U ) is User U ’s Identifier.

1. (7 Marks)

   Show how this protocol is insecure, by describing a Man-in-the-middle attack.

2. (3 Marks)

Discuss the consequences of this attack, in terms of key authentication properties and how they are violated.

The public domain parameters consist of a group (G, .) and an element α ∈ G having order n.

Write your answers for this question in q7.txt.

Given two graphs G0 and G1, Prover P wants to convince verifier V that it knows a permutation π such that π(G0) = G1. P could simply send π to V , but that is hardly zero-knowledge; we want to convince V that π is an isomorphism without revealing anything about it. The protocol is as follows:

P → V : P randomly chooses a permutation σ and a bit b ∈ {0, 1}, computes H = σ(Gb), and sends H

to V .

0

V → P : V chooses a bit b ←R− {0, 1} and sends it to P .



P → V : P sends the permutation τ to V , where

σ b = b′

τ = σπ−1 b = 0, b′ = 1

σπ b = 1, b′ = 0

V accepts if and only if H = τ (Gb0 ) and τ is a one-to-one mapping between vertices and edges.

1. (5 Marks)

   Complete

2. (5 Marks)

   Sound and

3. (5 Marks)

Zero-knowledge.

Write your answers for this question in q8.txt.

Data from N communicating nodes S = n1, n2, · · · , , nN communicate with an aggregator node na. The aggregator node has to verify the integrity of data collected from N.

1. (3 Marks)

   How can you do so using BLS signatures?

2. (4 Marks)

   What is the complexity of the verification algorithm?

3. (4 Marks)

   Can you design an efficient algorithm to reduce the verification time?

4. (4 Marks)

What is the new time complexity of the new verification algorithm?