This is a test applicant challenge for the position of Cryptographer Researcher at =nil; Foundation. If you think it might be you, here’s a detailed job description - follow the link to apply with your resume and attach the link to this challenge solved.

You can also only submit your resume and solve the challenge during the second tour of the interviews.

See **nil.foundation** to know more about who we are and what we do. If you’re interested in this position, don’t miss the Research section.

Cryptography Researcher test

FRI-based polynomial commitment schemes are commonly used for building transparent zkSNARKs. Some variants of such schemes have a wide range of parameters for finding a trade-off between the performance and security of the overall system. For example, a larger proximity parameter of the FRI protocol allows for a more efficient commitment scheme but requires careful consideration when analyzing the system's security level. We propose to consider two specific proof systems, Redshift [1] and Plonky2 [2] (both use the FRI-based commitment scheme), and answer the following research questions.

  1. Redshift describes ways to guarantee the uniqueness of setup polynomials (see section 4.3 [1]). Namely, they propose to use extra evaluation points. How many extra points will ensure a 128-bit security level for a 256-bit finite field and code rate = 1/8?
  2. Describe (briefly) how an attacker can exploit the absence of such extra points.
  3. Does the Soundness notion capture such types of attacks?
  4. Does Plonky2 use extra evaluation points? If yes, how many are used? Why exactly so many? If not, is the system still safe to use? Why?
  5. Can the attack described in the first answer be applied to Plonky2?

To prepare your answers, you may need to refer to the source code of these proof systems. We expect you to prepare your answer using LaTeX.

[1] Kattis, A., Panarin, K., & Vlasov, A. (2019). RedShift: Transparent SNARKs from List Polynomial Commitment IOPs. IACR Cryptol. ePrint Arch., 2019, 1400.

[2] Polygon Zero Team (2022). Plonky2: Fast Recursive Arguments with PLONK and FRI. url: https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/plonky2.pdf