Zero-knowledge signature verification

Can you think of any solution to this problem? suppose we have three parties, A, B and C:

• A has some data signed by C, a small part of which (not the signature) it wants to hide from B.

• A wants to prove to B that the data (including the hidden part) has been signed by C. (B can't just verify the signature normally since some data is hidden).

• B knows most of the data and the signature but not the hidden part. B doesn't want to know the hidden part, for him it's enough to know that the rest of the data is what it expects and that all of it was signed by C.

• C won't cooperate for this in any way (other than originally signing the data including the hidden part); A and B are on their own.

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 )$
• $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$.

• Thanks for your answer, @poncho The problem is we can't choose a particular signing scheme: C doesn't know about A and B and it may use one of several signature schemes. Assumptions 1 and 2 can't be counted on. – Alvaro S. Nov 22 '16 at 1:57

This is exactly the intended use of Idemix and U-Prove. A proves knowledge of "hidden data" (a subset of attributes) to B. Stefan Brands' "Rethinking PKI" book might be helpful, see credentica.com Hash is only used to produce challenges with both schemes above, and message is split into a set of attributes. It might be reasonable to start from Schnorr protocol and signature scheme.

• I thought U-Prove was also for things about the signed data which are not just part of the signed data. ​ ​ – user991 Nov 19 '16 at 14:06
• @Ricky Demer With U-Prove we have "token public key" signed, denoted $h$ in the "U-Prove Cryptographic Specification". Encoded in the public key are user attributes $x_i$. "Subset presentation proof" is the major part of the scheme, with "disclosed" and "undisclosed attributes" as input. This proof is basically a Schnorr-style signature. There are U-Prove extensions to prove, for example, equality of undisclosed attributes, specified at related documents. I would consider equality proof as "about" attributes encoded into public key. Maybe we need to agree on definitions. – Vadym Fedyukovych Nov 19 '16 at 19:01
• Thanks for your answer. The problem is we can't choose a particular signing scheme: C doesn't know about A and B and it may use one of several signature schemes. I'll definitely check U-prove, it looks interesting even if it's not the solution – Alvaro S. Nov 22 '16 at 1:53

Here's my naive solution.

Given C has some public and private data (s)he

• Creates a hash h = H(public) + H(private) concatenated together. h[0] is the first half and h[1] the second.
• Then creates signature s = S(h)
• Sending to A: s, public and private parts

A can verify the signature in the usual way by

• also computing h = H(public) + H(private)
• and verifying the signature V(s, h)
• A then sends to B: s, public, h

User B can now test the following

• Verification of C's original signature s via V(s, h)
• That h[0] = H(public)

This should prove to B that the whole of h had been signed by C and that the public part of the message was also the first half of the hash h[0].

I think it would be very difficult for B to forge a signature with half a hash.

To clarify If B wanted to fake the private data to A, then that would require finding a collision between V(s, H(public) + H(private)) = V(s, H(fake data)] and assuming the asymmetric scheme is strong that's the same as H(public) + H(private) = H(fake data) .. in other words very hard.

If the original message was signed using a tree based hash. It should be possible to hide any part of the message (with some minimal resolution) and still use the same signature. Simply by replacing the hidden part with it's hash.