Krüptograafilised protokollid 2021/22 sügis

Homework 6: Zero-knowledge proofs

First, do parts 1 and 3 of previous year's homework.

Second, describe the message exchange between Prover and Verifier, where the former is trying to prove to the latter that it has committed to a polynomial of degree less than 8 (i.e. at most 7). The relevant details of the protocol are the following:

• The work is being done over the field Z_257.
  • FYI: one of the generators of the multiplicative group Z*_257 is 3.
• Prover's polynomial is f(X) = 18 X^7 + 146 X^6 + 39 X^5 + 13 X^4 + 212 X^3 + 92 X^2 + 118 X + 10
• Interactive oracle proofs are in use. Initially, the values of the polynomial on the 128-element subgroup of the multiplicative group Z*_257 have been included in the proof string.
• The verifier's challenges r are 63, 49, 161 for d=3, d=2, d=1.
• The verifier does the linearity checks for the points 23, 60, 104, 133, 249 for the case d=3. For d=2, the linearity checking points are the squares of the points for d=3. For d=1, square them again.

Explain, what polynomials will be committed to over which fields, what are the points in the proof strings that the Verifier wants to open, and what are the values that he gets from the opening, what are the checks that the Verifier makes.

Additional terms:

1. The homework is individual. You are expected to do your own thinking.
2. The solution can be presented in any text format. Pdf file is preferred.
3. If you will be late, please alert the lecturer in advance.

Deadline: January 10th, 2022, 23:59 EEST.

Delivery: upload through the course website (see below)