FIT5124 - Assessment 1

DEADLINE: 4 April 2025, 11.55PM (Melbourne time)

TOTAL MARKS: 100

1 Overview

The learning objective of this assessment is for you to gain experience in analysing and implementing zero- knowledge proofs.

This is an individual assessment and you are not allowed to discuss any aspect of it with others (excluding teaching team members). Failing this requirement (e.g. helping other students, discussing solutions towards answering assessment questions in any platform) will result in penalties in accordance with the Uni- versity’s Academic Integrity guidelines:

https://www.monash.edu/students/academic/policies/academic-integrity

2 Submission Policy

You need to submit exactly two files on Moodle: (i) one written report answering the questions in Section 4, and (ii) one SageMath file answering the implementation questions in Section 5. Your report must be in PDF format and implementation code must have  .sage file extension. Name your files in the format: [Your Name]-[Student ID]-FIT5124-A1 (followed by file extension such as pdf, sage, etc).

The report should include your name and student ID at the top of Page 1. Please do not spend time trying to come up with a ‘fancy’ cover page. The report should be prepared in 11pt Arial font.

Important notes and penalties

– It is the student’s responsibility that the submitted PDF file can be opened on a standard Windows computer  (without  requiring  specialised  software),  and that the images and texts included are clearly visible/understandable/readable (in English). If the PDF file cannot be opened, you will receive zero mark. Similarly, it is the student’s responsibility that the submitted SageMath implementation file can be run in SageMath 10.5. If the SageMath file cannot be run in SageMath 10.5, you will receive zero mark for the implementation question. After making a draft submission (before finalising it), we recommend you to download your uploaded assessment files and check that they open and run properly. Once you finalise your submission, you will not be able to revise it.

– Note that draft files are NOT accepted and will not be marked. You must finalise your submission (with status shown as “submitted for grading”) for your assessment to be considered as valid. Otherwise, standard late submission penalty will apply.

– Maximum number of pages allowed for the report is 3. Any content exceeding the 3-page limit will be disregarded and not marked.

– Maximum number of characters allowed for the implementation code is 8,000. Any content exceeding the 8,000-character limit will be disregarded and not marked.

– Late submissions incur a 5-point deduction per day. For example, if you submit 2 days and 1 hour late, that incurs 15-point deduction. Submissions more than 7 days late will receive a zero mark.

– If you require extension or special consideration, refer to https://www.monash.edu/students/admin/ assessments/extensions-special-consideration. No teaching team member is allowed to give you extension or special consideration, so please do not reach out to a teaching team member about this. Follow the guidelines in the aforementioned link.

– Zero tolerance on plagiarism and academic integrity violations: If you are found cheating, penalties will apply, e.g., a zero grade for the unit. The demonstration video is also used to detect/avoid plagiarism. Univer-sity policies can be found at https://www.monash.edu/students/academic/policies/academic-integrity.

– All questions in the assessment are marked against technical correctness, clarity of explanations and quality of presentation. For example, if an answer is not presented well, you may not receive full marks even if the answer has the right technical ideas.

3 Scenario for the Assessment

Suppose that we have a cyclic (multiplicative) group G = ⟨g〉of prime order n. We assume that the discrete logarithm problem in G is computationally hard (which implies that n is very large and particularly n > 2128). Let h be another random generator of G (i.e., the discrete logarithm relation between h and g is unknown).

Compute the following value based on your Monash student ID

id = Student_ID mod 1000.

That means, id is the last three digits of your Monash student ID. The questions in this assessment will be based on the id value.

Let’s assume that we have a prover, Patrick, and a verifier, Victoria. Patrick wants to convince Victoria of the following “Patrick’s relation”

R pat = { ((g, h, v); (m, s)) :    v = gm hs Λ m ∈ {0, id}  } .

To prove the above relation, the interactive protocol between Patrick and Victoria works as follows.

0.  Patrick has ((g, h, v); (m, s)) and Victoria has (g, h, v) as protocol input.

1. Patrick: generate random f, r1 , r2  ∈R Zn

2. Patrick: compute a1 = gf hr1   and a2 = gf·m hr2

3. Patrick→ Victoria: send a1 , a2

4. Victoria: sample random c ∈R Zn

5. Victoria→ Patrick: send c

6. Patrick: compute z = f + cm, k1  = r1 + cs and k2  = r2 + s(id · c — z)     (all computed mod n)

7. Patrick→ Victoria: send z, k1 , k2

8. Victoria: Check all of the following: gz hk1   =? vca1 ;     and hk2   =?  vid·c—za2 . If all checks pass, then Victoria accepts the proof. Otherwise, she rejects the proof.

(here, we assume that Victoria also checks a1 , a2  ∈? G; and z, k1 , k2  ∈? Zn, but don’t write them out explicitly) We call the above protocol “PV protocol”.

4 Zero-Knowledge Proof - Analysis [70 marks]

4.1 Protocol diagram [10 marks]

Draw a diagram for the PV protocol in Section 3 clearly demonstrating the interaction between Patrick and Victoria. Your diagram must follow a similar structure as in the Schnorr’s ID protocol presented in the lecture notes. You can, for example, use any of the following methods for drawing:

– hand drawn diagram (with its clearly visible screenshot attached to the assessment report), – PowerPoint,

– cryptocode library in Latex (https://ctan.org/pkg/cryptocode?lang=en).

You are welcome to use any other method. In the end, your diagram must be clearly visible without any confusing parts. The order of the operations must also be clearly understandable (as in the Schnorr’s ID protocol presented in the lecture notes). You may not get full marks if there is any unclarity. The only hand-written part allowed in the assessment is this question; for all other questions, no hand-written submission is accepted.

The diagram must be added to the PDF report with label ‘Q1’.

4.2 Completeness analysis [10 marks]

Prove the completeness of the PV protocol in Section 3. The proof must be added to the PDF report with label ‘Q2’.

4.3 Soundness analysis [25 marks]

Prove the special soundness of the PV protocol in Section 3. The proof must be added to the PDF report with label ‘Q3’.

4.4 Zero-knowledge analysis [25 marks]

Prove the honest-verifier zero-knowledge property of the PV protocol in Section 3. The proof must be added to the PDF report with label ‘Q4’.

5 Zero-Knowledge Proof - Implementation [30 marks]

The implementation must be done in SageMath tool as used in the unit (https://www.sagemath.org/). If your submitted code does not run in SageMath 10.5, you will receive zero mark for the whole implementation part of the assessment.

Your implementation must also properly and meaningfully build on the A1_code .sage file provided in the assessment Moodle page. Failure to meet this requirement will make your implementation invalid and you will receive zero mark for the whole implementation part of the assessment.

5.1    Interactive protocol implementation [22 marks]

Implement the PV protocol in Section 3 in SageMath. The implementation must satisfy the following:

1. have the following functions: commitment, challenge, response, and verify, and

2. generate a protocol transcript using the above functions and run the verify algorithm to check and print the result of verification.

5.2    Conversion to non-interactive variant  [8 marks]

Extend the implementation code above to support running the PV protocol in Section 3 as a non-interactive protocol via the Fiat-Shamir transformation. As instructed in the A1_code .sage file, your final implementation must use the variable MODE to switch between “Interactive” and “Non-interactive” modes of running the protocol.

Submit your final implementation code as a  .sage file on Moodle.