**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.

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**

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**

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**

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**

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**

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**

Before I'd written up that proof, on the 9th, Eric told me that SZK_L was actually already known to be closed under complementation, and so I got to work trying to prove it: however, it wasn't as trivial as I thought it was, even given that. Today, I got rid of most of that proof method, and then tried working on another simple approach, although I suspect this method isn't zero-knowledge. Eric sent me a few papers which might help with proving these properties, and I'm knocking myself on the head for not thinking of checking these earlier, but hopefully they have enough to allow me to finish proving at least one of these two problems, since I feel like the closure property is true and I felt close to proving it.

Proving anything about SREN's properties still seems pretty intimidating, although I could be overthinking.

Not much else of import done. Work on the final presentation will likely begin tomorrow or Sunday.

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**

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**

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.