Can I prove in zero knowledge that the public key corresponding to a secret that I committed is in the Accumulator?

Question

I have a set of users in my system, each having a private/public keypair of a digital signature scheme. I also have an accumulator in my system, where all the public keys of the users are accumulated.

A user needs to anonymously prove to a verifier that she knows the private key corresponding to some public key that is incorporated in the accumulator. Here, both private and private keys of the user are the secret knowledge user wants to prove.

One potential way is that user commits to her private key, and give the commitment to the verifier. Camenisch and Lysyanskaya 1 proposed a protocol to prove in zero knowledge that a committed value is included in the accumulator. However in our case, user commits on her secret, and wants to prove that corresponding public key is included in the accumulator.

I am guessing the solution will depend on the particular signature scheme and commitment scheme that I am going to use. Can you refer to me some article/resource that would help?

1.Camenisch J, Lysyanskaya A. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In: Yung M, editor. Advances in Cryptology — CRYPTO 2002 [Internet]. Berlin, Heidelberg: Springer Berlin Heidelberg; 2002 [cited 2019 Oct 23]. p. 61–76.

Update (9 April, 2020):

I have a format of the Zero knowledge proof of knowledge - but yet to work out the construction. Please let me know why this is/isn't going to work - and any suggestion on the construction of the protocol.

The proof has three parts: i) user knows the value that has been committed, ii) the committed value corresponds to a public key, and iii) the public key is a member of the accumulator. The main challenge is (ii), which depends on the key generation algorithm of the digital signature scheme.

A signature scheme that is suitable for our purpose should i) have a discrete logarithmic relation between public and private key, that can be proved in zero knowledge, and ii) the public key should be a prime, because this is going to be accumulated, and the accumulator used in our work 1 requires the accumulated value to be a prime. Digital signature algorithm (DSA) and Schnorr's signature scheme seem fit for our purpose (both satisfy the first requirement) - here I use Schnorr's scheme.

Schnorr's signature scheme has following algorithms: i) Choosing parameters: A group $G$ is chosen of prime order $q$ in $Z_p^*$, where $p$ is a large prime number. The group has a generator $g$, and the discrete logarithm problem is assumed to be hard. Also, a hash function $H : \lbrace 0,1 \rbrace^* \rightarrow Z_q$ is chosen. ii) Key generation: select a random integer $a$ s.t. $1 \leq a \leq q - 1$, then compute $y = g^a \;\; mod \; p$. Output public key $y$ and private key $a$. iii) Signature generation: slect a random secret integer $k, 1 \leq k \leq q-1$. Then compute $r = g^k \;\; mod \; p, e = H(m||r)$, and $s = ae + k \;\; mod \; q$. The signature is the pair $(s, e)$. iv) Verification: To verify signature $(s, e)$ on $m$, obtain the signers public key $y$. Compute $v = g^sy^{-e} \;\; mod \;p$ and $e' = H(m||v)$. Accept the signature if and only if $e' = e$.

The only restriction we need to put is, the public key $y = g^a \;\; mod \; p$, must be a prime. (This may however be a security concern - we are reducing keyspace)

Let us form the aforementioned zero-knowledge proof of knowledge now.

The common inputs are:

1. Public key of the commitment scheme, $(n, g, h)$ where $n$ is a special RSA modulus, $h \gets QR_n, g \gets \langle h \rangle$, where $\langle h \rangle$ is the group generated by $h$, $QR_n$ denoting quadratic residue modulo $n$. Also, the commitment $nym$, where $nym = g^a \times h^r \;\; \mathtt{mod} \; n$.
2. Public parameters of the Schnorr's signature scheme $\tilde{g}, p$ (we call it $\tilde{g}$ instead of $g$ to remove redundancy) as well as public key of user $PK_U = y$.
3. Public parameters of the accumulator $(N, s)$, also the public value of the accumulator, $A$.

User's private inputs are:

1. Secret random $r$ from the commitment.
2. Private key $SK_U = a$ of Schnorr's signature scheme.
3. Witness of the accumulator, $w$

Now, the zero-knowledge proof of knowledge $\pi$ can be written as:

$\pi = ZKPoK \lbrace a, y, r, w : nym = g^{a}h^{r} \wedge y = \tilde{g}^{a} \;\; mod \; p \wedge w^y = A \;\; mod \; N\rbrace$

Answer 1

I think you actually need a proof with two step.

1. Prove that the prover knows a value in the accumulator. This is straightforward after you choose an accumulator type. Probably, it will be proved by committing the value in the accumulator. Now, treat this value as a public key, and
2. Prove that the prover knows a valid secret key for this committed value. This step will change according to key generation mechanism. However, this method seems to me easier than committing the secret key directly. My answer does not provide specific choice for accumulator and signature schemes but I think you should choose these schemes according to your systems concerns and you highly likely be able to create necessary proofs using the steps above.