NIZK Proof of knowledge N of M discrete logarithms (threshold)

Question

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?

Answer 1

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.