Jacob Gray's Project Page for DIMACS REU 2022

Personal Info

Student: Jacob Gray
School: University of Massachusetts Amherst (UMass)
Email: jacobg@umass.edu
Project: Metacomplexity and Non-interactive Zero Knowledge Proofs
Mentor: Eric Allender

Academically, I'm interested broadly in theoretical computer science, mathematics, philosophy, and logic. I currently feel most confident in TCS, particularly in areas like circuit complexity, but I hope to become more knowledgeable in areas like proof complexity, computability, and descriptive complexity. In the area of mathematics, my current biggest interests are in model theory, proof theory, and set theory, although I know next to nothing of the first two besides some basic results and terminology. My philosophical interests lie broadly in epistemology and metaphysics, as well as in philosophy of mathematics. Some results I particularly like are Godel's theorems, the Immerman-Szelepcsényi theorem, and barrier results in complexity theory, because I think the basic ideas are fairly intuitive, quite creative, and philosophically interesting (to me :) - 6/14

"A recent publication (joint with DIMACS REU students) that studied "metacomplexity" (i.e., the computational complexity of showing that problems are hard to compute) resulted in the definition of a new complexity class. This class dealt with a class of problems that have space-bounded non-interactive zero-knowledge proofs. Many basic properties of this complexity class remain unexplored. This project will aim to get a better understanding of this new complexity class."

There are two main initial goals of this project: the first is to try proving equivalences between various subclasses of NISZK, using the class NISZK_L introduced in [1] as a starting place. Intuitively, this could be interpreted as hinting that the power of a zero knowledge proof system is not very dependent on the power of the verifier. In this context, being able to understand more complex proofs wouldn't always change what could be proven.

The second initial goal is to try improving on results in [3] , which showed that there are one-way functions in NC0 (a very weak circuit class) iff there are one-way functions in more powerful classes, like ParityL. It is currently a large open question if one-way functions exist, and a proof of their (non)existence would be a very large result in cryptography. Considering that these more powerful classes (eg. ParityL) are known to contain some likely candidates for one-way functions, NC0 also seems likely to contain one-way functions if they exist. This suggests that even very easy to compute functions can still be one-way, being hard to invert by definition. Given [3], it seems reasonable to believe that there could be one-way functions in NC0 iff they're in P, although the results we hope to prove are much more modest than that.

Intro presentation: may be difficult to follow, considering we didn't write notes of what was said during the presentation. Also note that on slide 3, relations are meant to be inclusion, with lower classes generally being included in higher ones: many of these inclusions are not known to be strict (eg. it is unknown if L = NP.)
Errors: the relation between ParityL, NL, and RL is currently unknown.

Final presentation: currently no known errors, although there is a lack of technical detail on certain aspects (such as log-space and NISZK.)

Final report: this is the somewhat formal final report to the REU program. This report is merely for reference: if interested more deeply in the results, a more reference to our detailed paper will be linked here, if/when it is published.

My 10/18/22 presentation for the UMass Theory Seminar: This presentation primarily focuses on the work I helped with immediately following the end of the REU, in which we proved that SZK_L is closed under a restricted form of truth-table reducibility. This result is not in the final presentation or report, but can be found as the last section of our published paper (section 7, SZK_L closure under L_bf-tt reductions.)

Our paper on ECCC: We've been accepted to RANDOM 2023, but given as we are still finalizing things for RANDOM, I'll leave this ECCC link up in the meantime. This paper is the go-to resource on what we accomplished during the REU, as well as a few extra results.

Week 1, 5/29 - 6/4

So far, I've primarily been reading the Cryptographic Hardness paper [1]. I currently have a decent idea of what it's about, a very rough idea of how part of it is done, and a good idea of the end results, although I need time to process them. I've spent a lot of time getting used to being at Rutgers and being part of the REU, so I hope to become a lot more efficient next week, as I get more and more used to things. - 6/2

I already had a decent idea of what the project was about from the description on the DIMACS page, as well as when Pengxiang and I talked with Eric online before the program started, but I wasn't quite sure what the end goal actually was: in some respects, there very well may not be one clear goal, since we have a new, underdeveloped complexity class. So far, I've primarily been reading the Cryptographic Hardness paper [1], since that paper will be relevant no matter what we do, but I also plan on taking time and reading a lot of background papers on related topics, since I want to get an idea of what results could possibly come from the study of this class. Currently, I'm thinking on the results on areas of complexity I already know about, but I'm also learning a lot of new classes as I'm going along. Computational complexity often seems to me like a colossal, mesmerizing web, so the number of questions that this class could shed light on is probably "a lot." - 6/2

The main things I did this week were refresh myself on background knowledge, get an intuition for the complexity classes we're dealing with, and work with Pengxiang to get our intro presentation to an "almost finished" state for Monday. - 6/4

Week 2, 6/5 - 6/11

I spent a good part of Sunday just reviewing the slides I made on Saturday, as well as doing some additional reading on the Cryptographic Hardness [1] paper.

On Monday, Pengxiang and I presented our project and watched everyone else's presentations. There were actually a good number of people doing projects related to circuit complexity, zero-knowledge, or related topics, which I wasn't really aware of. I feel like a lot of it went over my head (as to be expected,) but I always find these kinds of things interesting anyways, since they give a good idea of what the broader world looks like.

Other than that, I've still mostly been reading: last week, I was stuck for a while on the beginning of the Cryptographic Hardness paper, since it involved some decent math and I had to review a lot of things, but I feel mostly caught up in the sense that the rest of the paper should be more straightforward to read, or at the very least, more immediately intuitive to me. - 6/6

I got a much better idea of the technical details involved in the proof that EA_(NC0) is in NISZK_L, based on my reading of an almost identical proof given in [2], and have begun thinking about how to potentially prove NISZK_L = NISZK_(NC^1). On Tuesday, Pengxiang and I talked with Eric for a bit, and afterwards Pengxiang explained to me a potential way to prove it, but at the time, I really didn't have any clue if what he was suggesting would work. At this point, I think his ideas are promising, but we need to see if all of the steps are actually computable in NC^1. - 6/9

The proof seems like it works to me, although we've moved on to other questions since he talked about it with me. I've finished reading [1], but I'm going to dig deeper into it as time goes on. I've started focusing more on reading other papers, such as [2] and [3], and I'm now thinking about potential ways to prove NISZK_L = NISZK_(PARITYL). Pengxiang provided a very rough proof, but there was a problem and I currently feel like we're at square one, although we have a lot to work off of. - 6/11

Week 3, 6/12 - 6/18

I read the rest of [2], which was really interesting, especially since I've never seen truth table reductions before. I feel like I have a much better idea of what goes on in that paper now, and I've started focusing more particularly on just [3]. I want to get a better idea of how the randomized encodings are constructed in NC^0, and then revisit [1] to review how the completeness proof worked.

Aside from that, Eric, Harsha, Pengxiang, and I met and talked about the project for a few hours today. I left with a much better idea of which direction to take in potentially proving NISZK_L = NISZK_NL, and I'm going to start trying to prove it so I can see where and why things become difficult. - 6/14

I tried starting an approach, but I didn't get very far. I feel like I should be able to start proving things, but I'm just stuck for some reason. I thought over the NISZK_L completeness proof from [1], and I feel like I understand it intuitively, but I may be failing to understand the subtleties or technicalities in some way. I plan to keep thinking over the proof and asking questions.

Over the past week, Pengxiang has been presenting and continually revising proofs that NISZK_L = NISZK_NL, although I've been having trouble understanding them. They seem promising, and Eric has been giving feedback and advice on where things need to be elaborated further or fixed. - 6/18

Week 4, 6/19 - 6/25

I feel pretty happy because I realized that what's been confusing me for the past week or so was an elementary mistake regarding what exactly the input was to the randomized encoding of M_x in the SDU_NC0 hardness proof of [1]. Now I should hopefully be able to make good progress towards checking and working on Pengxiang's proof. - 6/19

We all met on Wednesday and because of something Eric realized, it seems like Pengxiang's approach as-is won't work, since one of the distributions we're working with is a lot less ordered than we originally thought. Eric provided us with a new direction to look into, and I think this approach makes more sense to me, although I still have many questions.

Since Wednesday, I've been reading over some emails and meeting with the others to try to understand what I'm confused on, and I think I understand the encoding we're working with now (although there are still complications I'm not focusing on right now.) Today, we all met again (along with Saachi, who is joining us on the project,) and I think that cleared up the main thing I was confused on. I want to try a naiive computation of the entropy of the central distribution we're working with, ignoring things I'm unsure on for now, and then adjusting the calculations later to account for those hopefully small perturbations. - 6/24

Week 5, 6/26 - 7/2

I didn't end up doing any calculations because Pengxiang ended up finding an issue with the approach we were thinking of taking to approximate the entropy of the YES and NO distributions: because M_x can be arbitrary on its small support in the NO case, it seems like the encoding can also have arbitrary entropy, which means that trying to reduce whether an NL simulator for some x is a YES or NO instance to the problem of determining if the entropy is nearly uniform won't seem to work with the method we were considering, although intuitively there should probably be some way to distinguish them.

Eric, Harsha, Pengxiang, and I met again today and we went over the other results we wanted to try proving. I think for now I'm going to work on getting an intuition for something Harsha asked, which relates to classes where the simulator and verifier have different powers. It would be nice if I could find a simple counterexample somehow and then the question would be answered, but I suspect there could actually be some kind of complicated implication in there, which would be extremely helpful to know about, since then we could potentially "step-ladder" up to show NISZK subclasses equal to one another. I think this could end up being very difficult though, so I may turn to trying something else if I hit a wall. - 6/28

I thought a little bit about the question Harsha asked, but didn't reach any strong conclusions besides realizing a trivial inclusion where NISZK with a C verifier contains C, regardless of the simulator's power. Harsha's question revolves around comparing stronger verifiers as opposed to stronger simulators, so it seems to me like maybe trying to show that a simulator with power C contains C would be interesting and provide some insight, although I'm very unsure whether proving that would even be reasonable or helpful.

On Wednesday, Eric met with Harsha, Pengxiang, and I, and introduced a few new problems we could try to approach. The one I felt was most comprehensible was seeing if SREN was closed under MAJORITY, since we don't know much else outside of [3] about these encodings. I also want to think about potentially proving other properties after, if possible, but I'm concerned first and foremost with the case that SREN actually doesn't have these properties: if that's the case, I think it would be much harder to prove, but I may be wrong. Over the past few days, I've been thinking over ways to attack the problems that Eric and Harsha mentioned, but I haven't made a ton of progress. My intuition is getting better, however, and I hope to try throwing some ideas at them and seeing what works. - 7/1

Week 6, 7/3 - 7/9

On Friday (7/1,) Pengxiang mentioned a result he discovered relating to Harsha's problem. I wasn't fully convinced at first, but I ended up reasoning through it myself and coming to the same conclusions he did. The result was two equivalences, and it seemed possible those two equivalences might allow a further equivalence: that if A and B are complexity clases with A contained in B contained in NISZK_A, then NISZK_A = NISZK_B. This would be an extremely interesting but strange result, since it would form equivalence classes, and unless some class like NISZK_NC0 = NISZK_EXP, then it would have to be the case that some class between the two would have to be equal to its NISZK version, which seems unlikely (at least to me.) For this reason, I think it's false.

Pengxiang tried giving a proof of this equivalence which failed and seems unsalvageable, and I devised a proof on my own which I also found major problems with. Disproving the equivalence only needs a counterexample, but we have no real good examples for NISZK subclasses besides NISZK_L, so disproving this will probably wait. However, to reiterate, what Pengxiang did prove is still very interesting, at least to me: although there is still a lot to know, I think it definitely gives us a better intuition for these classes, which was Harsha's motivation for asking his question in the first place.

In the past few days, I've still been thinking on SREN. I feel like it might be promising to compute majority on the encoded outputs somehow, but that seems very troublesome: if it's done in some class like L, then an encoding has to be applied on top of that, which means that decoding the encoding doesn't give the result of the majority, but the encoding of the result of the majority. I plan to go back and read more tomorrow on the randomized encodings, since I think I intuitively understand them well, but proving that majority can be done might involve more work. - 7/3

Eric won't be here due to travel, so before he left, all of us (Eric, Harsha, Saachi, Pengxiang, and I) met to discuss the general state of the project. This involved seeing what we had accomplished so far, but also considering what we want to continue trying to prove. The problems I wanted to work most on most out of those Eric suggested were closure properties for SREN (which seems to be at a standstill,) a potential closure property for SZK_L, and some possible properties for NISZK_L.

I've put thinking about SREN on pause for now, since I'm not sure how to approach it, and it seems nobody else is sure how to either. I've been thinking a lot on the SZK_L property, which is closure under logspace Turing reductions, and although it seemed easy to approach at first, I've come to believe that this closure property is true iff SZK_L is closed under complementation, which is a bit intimidating. I've thought about a potential way to prove complementation as a result, but if I could easily do this, the same method could probably prove NISZK_L is closed under complementation, which Eric seemed very skeptical of being able to prove. I may try switching my focus to the NISZK_L properties, and then after thinking on these 3 big problems, approach the one which seems easiest. A proof idea for one would probably be helpful for the others. - 7/8

Week 7, 7/10 - 7/16

Week 8, 7/17 - 7/23

Saachi, Pengxiang, and I worked on the presentation and finished it. We presented today, on Thursday. Saachi asked Eric some questions about the SZK_L closure properties, so our current plan is to read the resources/papers Eric gave to us (which I haven't read much of due to the events of the past weeks,) and then we'll convene and see if we can prove more on them. - 7/21

Week 9, 7/24 - 7/30

All of us met yesterday and discussed various things, mainly the progress we'd been attempting to make on the SZK_L closure problem. Saachi ended up realizing that the approach she was thinking of taking wouldn't work, although the discussion did give me a much better idea of the direction Eric was thinking of taking to prove it, and why that approach seemed like a good idea. I realized while they were talking, and from the paper Saachi mentioned, that using my failed naiive proof method should work for monotone increasing/decreasing functions (for the "truth-table" aspect of the truth table reduction,) although I think this is an extremely strong assumption, so I'm not sure how helpful it'd be. Despite thinking that should work, I haven't had time to approach it yet because we need to write the final report for the REU: I probably won't have a chance to try proving things until we get that submitted and the program is over, although I plan on continuing to work on things after the program ends. - 7/27

We finished work on the final report and I've arrived back home from the program. Overall, I think the program was great for providing me insight not only into what grad school is like, but what areas I have to improve in and what kinds of traits I need to cultivate in order to survive there. I really liked worked with Eric: if the chance ever arises, I advise talking to him, he's great at explaining and knows the field inside and out. All of us are lucky to be able to be able to continue working with him on this project, since we probably have enough to submit to a conference. This site will be updated then or as particularly notable developments occur. - 7/31

Post-program

Conference submission in progress. - 7/31/22

We submitted a collection of different results to a conference and will also be submitting to a journal very soon as well. Many of the results obtained during the REU were better formalized, checked, and repaired at certain points, and a few small results were added after the REU.

Back at the end of the program, I mentioned a proof idea for showing closure for NISZK_L under monotone truth-table reductions, but that method didn't end up working out since it was fairly naiive. However, Eric suggested that we use the approach from [4], which dealth with SZK, to show closure for both NISZK_L and SZK_L under a stronger type of truth-table reduction. Adapting that method using logspace and branching programs worked for SZK_L, but we were unable to adapt it for NISZK_L, since NISZK_L's complete problems can't use the same approach without some new methods. NISZK also seems generally harder to prove things for, as opposed to SZK, which has a good number of nice properties known for it.

As a personal update, I will be giving a talk on 10/18 as part of the UMass Theory seminar on parts of this project; in particular, I plan to cover the adaptation of the SZK closure properties, which I'm most familiar with. My talk will probably be around half an hour, and I plan to put the slides here after the presentation. - 9/30/22

I've finally updated the website with the presentation: it can be found at the top of the page, underneath the final report. The presentation went well, but may be hard to follow. I also have good news: we were finally accepted at a conference (RANDOM 2023!) The link to our paper can be found at the top of the page. Apologies for the super long delay on the update. -8/20/23

I would like to thank my advisor, Eric Allender, and his graduate student, Harsha Tirumala for helping and guiding me, both with the project and with other related questions and issues. Thanks are also in order for my partners, Pengxiang and Saachi, who especially impressed me with how fast they seemed to pick up the project.

I would also like to thank the DIMACS REU 2022 program at Rutgers University for giving me the opportunity to do this research and meet fellow students, as well as organize funding for me to be there.

A large thanks to the NSF for providing funding for me this summer, as this research was primarily supported by NSF grant CCF-1852215.

Finally, I have deep gratitude to David Mix Barrington and Rik Sengupta from UMass Amherst for writing my recommendation letters for me for this program.

[1] Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle: Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity, Proc. 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pp. 54:1--54:17.

[2] Goldreich, Oded & Sahai, Amit & Vadhan, Salil. (1999). Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of NISZK. Electronic Colloquium on Computational Complexity - ECCC. 6. 791-791. 10.1007/3-540-48405-1_30.

[3] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC0. SIAM Journal964 on Computing, 36(4):845-888, 2006. doi:10.1137/S0097539705446950.