Proving multiple products "in the exponent"

Question

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?

Answer 1

Unfortunately, improving over the $O(n)$ solution seems to require the use of non-standard assumption. More precisely:

1. No, Groth-Sahai NIZKs cannot be used for proving this statement with communication less than $O(n)$, because the witness held by the prover is already of size $O(n)$. In fact, even if the prover knew all the discrete logarithms of the group elements (i.e., all the $a_i$'s), Groth-Sahai proofs would still produce proofs of size $O(n)$. The main reason for this is that Groth-Sahai proofs are... Well, proofs (more precisely, they can be either proofs or arguments, depending of the mode of the crs, but they have the same size in both cases since the modes must be indistinguishable). An interactive proof (meaning, with statistical soundness - as opposed to interactive arguments which have computational soundness), zero-knowledge or not, non-interactive or not, cannot have communication sublinear in the witness size unless NP can be decided in subexponential time.
2. It does not seem to be straightforward to obtain a shorter proof for your problem without using "heavy hammer" tools, or the random oracle model. If you are ok with using the random oracle model, then there are sublinear interactive proofs which can prove this statement with logarithmic communication complexity, and can be made non-interactive using Fiat-Shamir (1, 2). In fact, very recently, it was shown here how to build such succinct interactive public-coin arguments directly for bilinear equations a la Groth-Sahai. If you do not want to use random oracles, then you will have to rely on the non-standard and non-falsifiable assumptions underlying the constructions of all SNARGs - there are many available. However, none of them will provide a very good concrete efficiency for your specific problem, and I'd strongly suggest to rely on a solution in the random oracle model instead.