10
$\begingroup$

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?
$\endgroup$

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.