Score:3

Assumptions on zero-knowledge proofs without trusted setup

bj flag

Let's start with what got me wondering about this issue: It's a curious construction, that while most digital signature schemes come from public-key encryption (Impagliazzo's cryptomania), there are constructions like SPHINCS that construct secure signature out of a hash function (Impagliazzo's minicrypt).

Now there exists a SNARK construction without trusted setup ala Hyrax. Has there been any work on reducing a succint zero-knowledge proof system without trusted setup to another cryptographic construction, like the ones from Cryptomania or Minicrypt, instead of basing it on assumptions like dlog-hardness directly?

Score:4
cn flag

Strongly unforgeable digital signatures exist from one-way function, so they are indeed a Minicrypt assumption, even though most efficient construction use public key cryptography.

For succinct zero-knowledge, Kilian's protocol is a succinct zero-knowledge argument for all of NP assuming only collision-resistant hash functions, which is also typically seen as a Minicrypt assumption. Whether OWF could suffice for this is a long-standing open problem.

Using the Fiat-Shamir heuristic, you can turn it into a transparent SNARK. If you want something more concretely efficient, try Ligero, for example.

If you don't want to use the Fiat-Shamir heuristic or to assume random oracles, then indeed we have an unsatisfying situation:

  • SNARKs can be constructed unconditionally from a random oracle, so they are very much a Minicrypt-style assumption, yet
  • We don't have any provably secure constructions of them from any standard Minicrypt assumption like OWF, CRHF or others.

Note, however, that there's nothing specific to succinct arguments or tu trusted setups for that: the same applies to non-interactive zero-knowledge proofs in general (without succinctness, and even with trusted setup). Getting NIZKs from Minicrypt assumptions is a long-standing, probably very hard open problem. Indeed, until recently we did not even have NIZKs from most public-key-style assumptions, such as LWE or DDH! (For the former, we now have a construction due to Peikert and Shiehan, and for the latter, Jain and Jin recently built one from subexponential DDH)

cn flag
I would argue that in the context of constructions without trusted setup resorting to the ROM is cheating. The ROM gives you a common random string (and much more) for free.
Geoffroy Couteau avatar
cn flag
I assumed that in the context of this question, "no trusted setup" referred to a transparent setup -- i.e., with a distinction between a common random string, and a common reference string. In the real world, it is relatively reasonable (though debatable) to view the first one as "no trusted setup" due to the plethora of nothing-up-my-sleeve techniques to generate the string.
user4242 avatar
bj flag
Yes I meant no ROM, but accepted this answer given my attempts to find constructions in this direction also failed. If anyone actually knows a proper "no trusted setup" without ROM or a work in that direction. Suggestions are welcome.
Geoffroy Couteau avatar
cn flag
To be clear, you want no ROM but are happy with knowledge-of-exponent assumptions?
user4242 avatar
bj flag
knowledge of exponent here would mean dlog hardness style assumption right?
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.