3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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)

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Maeher
    May 30 at 6:17
  • $\begingroup$ 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. $\endgroup$
    – Geoffroy Couteau
    May 30 at 16:44
  • $\begingroup$ 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. $\endgroup$
    – user4242
    Jun 1 at 17:46
  • $\begingroup$ To be clear, you want no ROM but are happy with knowledge-of-exponent assumptions? $\endgroup$
    – Geoffroy Couteau
    Jun 2 at 16:55
  • $\begingroup$ knowledge of exponent here would mean dlog hardness style assumption right? $\endgroup$
    – user4242
    Jun 11 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.