What is the current state of the art zero knowledge proof compiler ? I need one that can minimally handle double exponentiation by a known value E.g.

$$Pok\{(\alpha):h=g^{\alpha^b}\} $$ where b, g and h are public but $\alpha$ is secret.

Preferably it should be able to handle double discrete log proofs E.g.

$$Pok\{(\beta):h=g^{a^\beta}\} $$ where a, g and h are public and $\beta$ s secret.

ZKPDL does not handle at least the later case.

  • $\begingroup$ Fixed that, \alpha should be a and is known. $\endgroup$ – imichaelmiers Mar 22 '13 at 6:03
  • $\begingroup$ Is the order of $g$ known and public? $\:$ $\endgroup$ – user991 Mar 22 '13 at 7:31
  • $\begingroup$ The order of g is known and public. $\endgroup$ – imichaelmiers Mar 23 '13 at 0:31
  • $\begingroup$ Have you checked Charm or results from the CACE (Computer Aided Cryptography Engineering) project? $\endgroup$ – DrLecter Oct 29 '13 at 23:23

A protocol for double discrete log proofs is given in M. Stadler, "Publicly verifiable secret sharing", Eurocrypt '96, Section 3.3.

In Stadler's notation, given $g$, $y$, and $V = g^{y^\alpha}$, and $A = h^\alpha$ for some generator $h$, Stadler's protocol shows how to prove that $\log_h A = \log_y(\log_g V)$. Now, to solve your problem, let $V$, $g$, and $y$ be known. To prove knowledge of $\alpha$, have the verifier choose a generator $h$. The prover provides $A = h^\alpha$ and uses Stadler's protocol to prove that $\log_h A = \log_y(\log_g V)$.

  • $\begingroup$ That is correct, but the OP asked for ZKP compilers, i.e., tools that take an abstract specification of a zero knowledge proof and produce the corresponding code in some programming language. $\endgroup$ – DrLecter Feb 2 '14 at 17:56
  • $\begingroup$ There are two steps involved in "compiling" a ZKPK. Step 1 is to translate the given input parameters into a step-by-step protocol specification. Step 2 is to produce actual code in a standard programming language. Stadler's result takes care of Step 1, i.e. he provides the specification of the protocol steps. Most programmers can easily handle going from the specification to the actual code. It is not clear from the OP's question which step(s) are being asked about. In practice, compiler-generated ZKPK specifications are very inefficient, and hand-designed ones are preferred when available. $\endgroup$ – djao Feb 3 '14 at 2:33
  • $\begingroup$ I fully agree. Since the OP explicitly mentioned ZKPDL, I interpreted this as seeking a tool for rapid prototyping of some protocol (however, then this question may be off-topic as it would be only a reference request). So I think your answer is a valid one :) $\endgroup$ – DrLecter Feb 3 '14 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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