2
$\begingroup$

Suppose we have the description of a group $\mathbb{G}$, a group of unknown order: the size of the group is unknown. For instance, an RSA group ($\mathbb{Z}^{*}_N,$ where $N=pq$ for unknown primes $p$ and $q$) or a class group. The prover wants to convince the verifier that for $h=g^x$ and that the exponent is non-negative ($x\geq0$) for a random, public $g\in_R\mathbb{G}$.

More formally, this is the language I want an efficient (non-interactive) zero-knowledge proof system for: $$\mathcal{R}=\{((h,g,\mathbb{G}),x)\vert g^x=h \land 0\leq x\}. $$

Maybe, it is easy to devise a sigma-protocol for this language? Or some cut-and-choose-like proof system? Ideally, verifier efficiency would be independent of the size of $x$. Do you know any proof system in the literature that satisfies these requirements?

Note: in this context, it makes sense to talk about the sign of a discrete logarithm of an element because you don't know the order of the group $\mathbb{G}$ and you also don't know the order of any elements $g,h\in\mathbb{G}$. Put differently, this is a non-trivial statement, in the sense that $\mathcal{R}\notin BPP$ (bounded-error probabilistic polynomial time), because if the prover was able to provide two different "signs" of the same group element, i.e., $h=g^x=g^{-y}$, then $g^{x+y}=\mathbb{1}\leftrightarrow \vert\mathbb{G}\vert=k(x+y)$, for some $k\in\mathbb{Z}$, which is presumably hard to do in a group of unknown order. Usually, one also assumes that even an integer multiple of the unknown group order is hard to compute.

Note 2: logarithmic range proofs would be suboptimal to apply here because, in principle, $x$ can be an arbitrarily large integer.

$\endgroup$

2 Answers 2

2
$\begingroup$

You can prove that an integer is nonnegative by proving that it can be written as the sum of four squares.

So for your protocol, you would commit to those four squares using Fujisaki Okamoto integer commitments, use something like Efficient Proofs that a Committed Number Lies in an Interval; Section 2.3 to prove that those are actually squares, then add a statement to this Schnorr-like proof that adds all those squares up to $x$ such that $h = g^x$.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. This is the strategy, I will pursue. I think the state of the art instantiation of this sum of four squares technique can be found in the Dew paper: eprint.iacr.org/2022/419.pdf $\endgroup$ Nov 27, 2022 at 19:17
1
$\begingroup$

Ok, here's one attempt; you asked for a NIZKP, I'll write it as interactive (and it's straight-forward to convert it into a noninteractive one).

It is a cut-and-choose protocol:

  • Step 1: the prover selects positive values $a$ and $c$ (with $c < ax$), and publishes the value $j = g^{ax - c}$.

  • Step 2: the verifier asks for either the discrete log, or the values $a, c$

  • Step 3a: if the verifier asked for the discrete log, the prover publishes the value $ax-c$. The verifier validates that it is positive and that $j = g^{ax-c}$

  • Step 3b: if the verifier asked for the values $a, c$, the prover publishes them, and the verifier validates that $a, c$ are positive, and that $h^a = j \cdot g^c$

If the value $x$ the prover knew was negative, then the proof as a probability 0.5 of failing. If the prover selects positive $a, c$ values, then $ax-c$ will be negative, and so it would fail if the verifier asked for that value. If the prover uses any other strategy, then it would fail if the verifier asked for the $a, c$ values.

$\endgroup$
1
  • $\begingroup$ Thank you for the interesting proof system. The proof size is certainly constant here (only depends on the tolerated soundness error), but a crucial disadvantage in my case is that the verifier in Step 3a potentially needs to compute a huge exponentiation g^{ax-c}. In my application x could be arbitrarily large, and Step 3a. makes the verifier really slow. I'm wondering whether one could turn this proof system into one where the verifier's work remains constant... $\endgroup$ Nov 27, 2022 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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