# Proving multiple products “in the exponent”

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.

Questions:

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?