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

Question

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.

Answer 1

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.

Answer 2

I believe that you original proposal suffers from the same "double pairs" problem. Defining $r_{k} = H_{q}(1||s_{k})$ and knowing that $s_{k} = c^{-1}_{i}(p_{i} - m_{i})$ and $m_{i} = r_{k} - x_{i}$. Having two sets of disclosed $(p_{1}, c_{1}, x_{1})$ and $(p_{2}, c_{2}, x_{2})$, one can derive $r_{k}$ and then any $m_{i}$, and finally $s_{k}$. Where $r_{k} = (p_{1}.c_{2} + x_{1}.c_{2} - p_{2}.c_{1} - x_{2}.c_{1}).(c_{2} - c_{1})^{-1}$ if I'm not mistaken. Then, why not releasing the point $Q_{i} = pG$ in the signature output instead of just $p$? Normally points are protected by the trapdoor generator. I suppose this may solve the problem.