Mentored by Marshall Ball
Proud member of Charles University group consisting of Jan Soukup (Our coordinator), Jan Bronec, Guillermo Gaboa, Svetlana Ivanova, Gaurav Kucheriya, Jáchym Mierva, David Miksanik, David Sychrovsky, Tung Anh Vu, Ilia Zavidnyi.
Description: A GKR protocol, introduced in 2008 has polynomial prover complexity and quasi-linear verifier complexity. We aim to make it non-interactive, zero-knowledge (NIZK for short) protocol, which can potentialy can yield and proof of work with thight prover complexity.
Week 1: Our flight was delayed, but we arrived to US after all. I have met with my advisor and we established a goal for the project. Cryptography is quite a new topic for me, so this week I have learned a lot of the basics like sum-check protocol, interactive/non-interactive and zero-knowledge proofs. I have also prepared an introductory presentation, but I think I've talked too fast and noone understood me 🥲
Week 2: Svetlana Ivanova have joined my research project, so now I have a partner I have spend all week understanding every detail about $\mathsf{GKR}$ protocol and preparing a presentation with explonation of it which we will present on 13.06.2022 to Mr.Ball
Week 3 : Me and Svetlana have presented $\mathsf{GKR}$ protocol to Mr.Ball at NYU Counrant. I think have done a good job of presenting a protocol, though in retrospect I think we mostly did it to understand $\mathsf{GKR}$ ourselves. After that together with Mr.Ball we have decided to proceed with understanding how to make it non-interactive with correlation-intractable functions and we agreed on that. However, I have outsourced that job to Svetlana and spend time on researching existing techniques on turning protocol zero-knowledge. Once I've done that, I understood how to constuct CI hash function family we need, which I realised that it's going to be very hard if we make it zero-knowledge using existing techniques and we'll have to construct hash family we need completely from scratch. Feeling sorta stuck 😥
Week 4 : I have told everything I found out to Mr.Ball on Monday. We spent some time discussing where to go from here until I came up with idea that maybe we could use existing paper which makes protocol zero-knowledge, use their construction, and then instead of sending a transcript to a verifier in clear, prover will send a commitment to a transcript, which will not reveal any information (that verifier cant compute himself in $O(n\log\cdot n)$). Mr.Ball told us that this indeed should work and it will accomplish a goal of our project. I felt very excitied that we have stumbled on the solution as a result of me asking stupid questions. I have not managed to write down the proof due to the lack of focus. Have celebrated my 20th birthday on the weekend, feel excited and scared of what awaits me in the future...
Week 5 : I realised that was not quite sure HOW to write down what we have talked about, so I've went to meet with my advisor to work out a details of what we are trying to achieve. I have written down a sketch of the proof on Overleaf and realised that I have a gap in my knowledge of circuit construction. So I've read this paper (mainly proof of lemma 2.12)
Week 6 : I've spent most of a week in Utah, where I mostly thought of the applications of my research, Specifically, practicality of the application and potential extension to multi-prover systems. On Thursday I've met with my advisor where we discusssed my thoughts and what potential topics we would be interested to research after the REU. On friday got completely side-tracked into reading papers about circuits complexity, SAT NIZK, etc. So I have not done anything research related 😅
Week 7 : This week was a trip to Bell Labs, had to do some paper work, and other social events. I started working on a final presentation which I will present on Thrusday next week. I feel kinda scared and sad for the REU to end, but I'm really gratefull for this opportunity to explore cryptography, meet my amazing colleagues. Special thanks to my advisor with whom I'll be working on my Bachelor thesis.
This work was carried out while the author Ilia Zavidnyi was a participant in the 2022 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.