Here is one possible way, that assumes:
C doesn't mind modifying how it signs data
C knows up front what part of the data is the hidden part
We don't mind if it isn't precisely zero knowledge, as long as we're at least as strong as the signature algorithm.
Then, here is how it works:
We'll assume ECDSA (or EdDSA); this assumption is mostly so we can reuse the same hard problem in our padding as in the signature, to make sure we're at least as strong as the signature.
We'll assume a hash function $F(m)$ which takes a message $m$, and converts it into an elliptic curve point; this function $F$ has the property that, for any two $m \ne m'$, the discrete log problem $nF(m) = F(m')$ is hard.
We'll assume another hash function $g(m)$ which takes a message $m$, and converts it into an integer between $1$ and $q-1$, where $q$ is the order of the Elliptic Curve.
To sign the message $(x, y)$ (where $x$ is the public part, and $y$ is the secret part, $C$ computes the elliptic curve point $(g(y))F( x )$, converts that into a bit string, and signs that.
For $A$ to prove that it knows $(x, y)$ that $sign( (g(y))F( x ) )$ is a signature to, it publishes:
- $sign( (g(y))F( x ) )$
- $(g(y))F( x )$
- A zero knowledge proof that $A$ knows a solution to the discrete log problem $zF(x) = (g(y))F( x )$
$B$ then verifies that the signature is a valid signature to $(g(y))F( x )$; he then computes $F(x)$, and verifies that $A$ knows the value $z = g(y)$; he then concludes (because $F$ makes the discrete log problem hard) that $g(y)$ must be the value that $C$ originally used to sign, and hence $A$ must know $y$.