Cryptography
signature zero-knowledge-proofs commitments
Updated Wed, 08 Jun 2022 01:31:33 GMT

How do I create a cryptographic signature and commitment scheme with accountable evidence?

This is a weird one... I am looking for a method which I don't even know how to call, nor whether it actually exists!

Given a pair of asymmetric keys $$s_{k}/P_{k}$$ and defining $$Sig_{k} \dagger B_{i}$$ as the signature of block $$B_{i}$$ using $$s_{k}$$. Is there a a function $$\otimes$$ with the following characteristics?

1. $$Sig_{k} \dagger B_{1} \otimes X_{1} => D_{k}$$

2. $$Sig_{k} \dagger B_{2} \otimes X_{2} => D_{k}$$

3. $$Sig_{w} \dagger B_{i} \otimes X_{i} \neq> D_{k}$$

, where $$\dagger$$ has precedence over $$\otimes$$.

1. If I sign a block with $$s_{k}$$ there should be a bitset $$X_{1}$$ related with the block $$B_{1}$$ and, when applying $$\otimes$$ gives a $$D_{k}$$ that has a relation with $$P_{k}$$.

2. If any other $$B_{2}$$ is used there should be a $$X_{2}$$ that gives the same result.

3. If a different key pair is used $$s_{w}/P_{w}$$, we should not be able to find any pair ($$B_{i}$$, $$X_{i}$$) capable of resulting in $$D_{k}$$.

Finding $$X_{i}$$ from $$B_{i}$$ or $$Sig_{k} \dagger B_{i}$$ (to verify the condition) should be easy only if one has $$s_{k}$$.

We should not be able to infer $$P_{k}$$ from $$D_{k}$$ without having the inputs.

Application:

$$D_{k}$$ serves as a commitment scheme and has the requirement of being immutable for a $$s_{k}$$.

One can publish a proof of ownership of $$D_{k}$$ knowing $$s_{k}$$. This proof has a specific ($$B_{i}$$, $$X_{i}$$) pair that is delivered to a specific entity $$I_{i}$$ (also with the signature). In case that entity publishes the proof without authorization, it can be identified and accountable for the security breach.

The alternative I'm using now is to apply a deterministic signature function $$H(Sig_{k} \dagger B) => D_{k}$$. Where $$H$$ is a SHA-256 function and $$B$$ is static, always resulting in the same $$D_{k}$$. One cannot infer $$P_{k}$$ because the signature is hidden using the hash (assuming all $$P_{k}$$ are public). If I disclose $$Sig_{k} \dagger B$$ I can prove $$D_{k}$$ is mine. However, if I share this proof with multiple parties, I cannot use it to "point fingers" in an eventual security breach.

Solution

I, personally, did not know of any scheme with such properties yet so I took the challenge of creating one and succeeded. After that, I was really unsure on whether to post it or not since it SHOULD NOT BE USED. I decided to do so for the mere point of showing that such schemes are probably possible.

Given an elliptic curve with a generator $$G$$ of order $$q$$ and a hash function $$H_q(x)$$ which maps $$x$$ to $$[1, q]$$:

$$\operatorname{GenKey}():$$

1. $$s_k \leftarrow Z_q$$
2. $$P_k := s_kG$$
3. $$D_k := H_q(1||s_k)G$$

$$\operatorname{Sign}(s_k, B):$$

1. $$m = H_q(2||s_k||B)$$, $$M = mG$$
2. $$c = H_q(P_k||M||B)$$
3. $$p = m+c*s_k$$
4. $$\sigma = (M, p)$$

$$\operatorname{Verify}(P_k, B, \sigma):$$

1. $$c = H_q(P_k || M || B)$$
2. Check if $$M+cP_k = pG$$

So far, this is a variation of the Schnorr signature scheme which uses the hash-function to generate the private masking key, like it's done in EdDSA instead of randomly picking one. Please note that I highly discourage anyone from using this scheme already since it hasn't gone through formal research.

Based one the rationale that this masking key private, we can use it to create a derivation key to $$D_k$$.

$$\operatorname{GenX}(s_k, B):$$

1. $$x = H_q(1||s_k)-H_q(2||s_k||B)$$

$$\operatorname{DeriveD_k}(\sigma, x):$$

1. $$D_k = M + xG$$

Let's discuss the properties of this scheme:

1. Obviously, there is an $$X_i$$ for each $$B_i$$ which can be computed easily if you know $$s_k$$.
2. Also, each $$(\sigma, x)$$ tuple should lead to the same $$D_k$$.
3. Computing any $$\sigma$$ should require $$s_k$$. Calculating $$x$$ from any $$\sigma$$ requires knowledge of $$s_k$$ as well.
4. Even if you know $$D_k$$ and a $$\sigma$$, finding $$x$$ is as hard as solving the discrete logarithm of $$D_k-M$$.
5. Even if you know $$D_k$$, and choose a $$x \leftarrow Z_q$$, you would need to forge a signature.
6. Let's discuss the privacy of the signer by assuming one would compute the challenge by $$H_q(M || B)$$ and someone knows $$\sigma$$. He could then compute $$P = c^{-1}(pG - M)$$. This is circumvented by incorporating the public key into the challenge.
7. Given a dishonest signer, he could chose a random $$y \leftarrow Z_q$$ and use it as private key for $$D_k$$ instead of $$H_q(1||s_k)$$ or could create commitments which do not lead to $$D_k$$.

Again, I do not recommend using this scheme since it has not undergone any research at all instead of my two hours.

• +0 – Another idea I had was having a Pedersen-commit style scheme where $s_k$ and $d$ are the private key, $P$ is the public key, and a commit is $C=aG+bP$ which turns out to be $D=dG$ when $b=s_k^{-1}(d-a)$. This scheme allows easy recovery of $P$ with $a,b,C$ and you would loose the signature aspect at $a$ but calculating $b$ requires the secret key and I could imagine that security proofs are easier with scheme. — Feb 01, 2019 at 15:07
• +0 – I was also looking into Pedersen scheme, and that is much simpler. $P_{k}$ is public, no need to worry about recovering it. What if $a = H_{q}(Sig_{k} \dagger B)$? I disclose ($a$,$b$) confirming $D_{k}$. I believe this would work. But I do have to save $Sig_{k} \dagger B$ and $B$ to prove accountability. — Feb 01, 2019 at 16:42
• +0 – While this would work in principle, there is a attack where the attacker has access to two pairs $(a_1,b_1)$ and $(a_2,b_2)$ since $b_1-b_2=s_k^{-1}(a_2-a_1)$ which transforms to $s_k=(a_2-a_1)(b_1-b_2)^{-1}$ so you would need to replace the keys once an identity discloses it commit since the other identities can recover the private key in that case. Also, Identities must not hack each other in your threat model. — Feb 01, 2019 at 16:57