I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement. I'll start by giving an example.

The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$. The verifier only has $g^a, g^b$ and $g^c$. Nobody (not even the prover) knows the exponents $a,b,c, ab, ac, bc, abc$. The prover gives $g^{abc}$ to the verifier and wants to convince him it has done so.

To convince the verifier, the prover can give him a proof consisting of $g^{ab}$. The verifier can check with a bilinear map that $e(g^a, g^b) = e(g^{ab},g)$ and $e(g^{ab}, g^c) = e(g^{abc}, g)$. (I believe we also need to make all group elements "extractable" for this to be secure, but I'm ignoring this for now.)

Assuming this approach for proving $n=3$ "products in the exponent" is sound, the first challenge is it doesn't scale to large $n$: the proof size is linear in $n$.

To see this, let's extend the above example to arbitrary $n$. Specifically, suppose the prover and verifier have $g^{a_i}$'s for all $i\in [1,n]$. In addition, the prover has $g^{\prod_{i\in S} a_i}$ for all subsets $S$ of $[1,n]$. The prover gives $c$ to the verifier and wants to convince him that $c = g^{\prod_{i=1}^n {a_i}}$. Then, the proof will be a tree whose root is $c$, its leaves are the $g^{a_i}$'s, and its internal nodes with their children are DDH tuples (i.e., parent is $g^{\alpha \beta}$ with children $g^{\alpha}$ and $g^{\beta}$). The proof consists of all the internal nodes in this tree, of which there are $O(n)$. Unfortunately, this is too large.

The second challenge is we want the prover to pick a subset of indices $S \subseteq [1,n]$, compute $c = g^{\prod_{i\in S} a_i}$, give $c$ to the verifier and convince him that there exists some subset $S$ of $[1,n]$ such that $c = g^{\prod_{i\in S} a_i}$, without actually having to reveal $S$ itself, which is too large.


  1. Can Groth-Sahai NIZKs [1] be used to efficiently prove such a statement in bandwidth $o(n)$? (Maybe $O(\sqrt{n})$?)
  2. Can you think of other cryptographic techniques that can be applied here?

Your Answer

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

Browse other questions tagged or ask your own question.