2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The fact that anyone took the time to try reaching such an answer is formidable. I did not yet fully understood the answer, but for that you already have my points. $\endgroup$ – shumy Feb 1 at 14:34
  • $\begingroup$ 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. $\endgroup$ – VincBreaker Feb 1 at 15:07
  • $\begingroup$ 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. $\endgroup$ – shumy Feb 1 at 16:42
  • $\begingroup$ 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. $\endgroup$ – VincBreaker Feb 1 at 16:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ While I could not so how you came up with the $r_k=...$ equation, I came up with a more direct one: $s_k=(p_1+x_1-p_2-x_2)(c_1-c_2)^{-1}$. One must not use $Q_i=pG$ as it would make signature forgery trivial since $Q_i=M_i+c_i P_k$. One could have $X_i=x_iG$ which would prevent both attacks but allow a party knowing $D_k$ and a $\sigma$ to compute $X=D_k-M$ without knowledge of $S_k$. $\endgroup$ – VincBreaker Feb 2 at 18:44
  • $\begingroup$ I fail to understand how releasing $Q_{i}$ is different from just releasing $p$? $p$ is already needed to validate the signature. Any one can derivate $Q_{i}$ from there. The same with $X_{i}$. $\endgroup$ – shumy Feb 4 at 9:41
  • $\begingroup$ So you want the signature to look like $(M, p, Q_i)$? I do not see how this would fix the issues since the attacker still has access to $p$. If you ment that $\sigma=(M, Q_i)$, the signature is not safe as one could easily forge one as stated in my previous comment. $\endgroup$ – VincBreaker Feb 4 at 12:55
  • 1
    $\begingroup$ Sorry, I misinterpreted your statement, mainly because, one doesn't need $\sigma$ to compute a valid $X_{i}$. It can generate a $M_{i}$ with a different $s_{k}$ and then the respective $X_{i}$, breaking my requirement. Without a proper solution, this is no different than the proposed Pedersen scheme. $\endgroup$ – shumy Feb 4 at 16:40
  • $\begingroup$ Now I've got it. Yeah, that would work. $\endgroup$ – VincBreaker Feb 4 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.