It is well known how to produce a NIZK that curvepoints $aG$ and $aP$ have the same discrete logarithm $a$ with respect to the curvepoints they are multiplied by. There is also a way to prove that a curve point $aG$ has the same discrete logarithm as one of $b_1P$, ..., $b_nP$. I think this is due to Cramer but I first encountered it in Traceable Ring Signatures.

My question is: is there a threshold version of this? That is, given a set of $M$ discrete logarithms, can I prove that I know $N$ of them?


A straightforward way to prove this when you can prove AND as well as OR statements about discrete logarithms is to take all the $K=\binom{M}{N}$ subsets $A_i=\{A_{i_1},\ldots,A_{i_N}\}$ with $N$ elements of points from the set of your $M$ points and prove the statement $$PK\{(\alpha_1,\ldots,\alpha_N): \bigvee_{j\in K} \big( \bigwedge_{A_{j_i}\in A_j} A_{j_i}=\alpha_i P \big) \}.$$

If this proof verifies, then you convince the verifier that you know all $N$ discrete logarithms in one of the $K$ subsets of $N$ elements of all your $M$ discrete logarithms without revealing which one.

The idea of proving OR statements is due to Cramer et al.. Moreover, their result holds for arbitrary monotone access structures.

Non interactivity can be added as usual by using Fiat-Shamir and living with random oracles. This recent approach shows how you can use a related transform which does no longer requires programmable random oracles.

| improve this answer | |
  • $\begingroup$ Thanks. I am reading through the Cramer paper and will accept your answer when I'm done. The other link is no good since it is CRS, i.e. requires trusted setup. Thanks! $\endgroup$ – Andrew Poelstra Sep 28 '14 at 19:29

Your Answer

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

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