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

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.